Problem: You are given string s consists of opening and closing brackets of four kinds <>, {}, [], (). There are two types of brackets: opening and closing. You can replace any bracket by another of the same type. For example, you can replace < by the bracket {, but you can't replace it by ) or >.

The following definition of a regular bracket sequence is well-known, so you can be familiar with it.

Let's define a regular bracket sequence (RBS). Empty string is RBS. Let s1 and s2 be a RBS then the strings <s1>s2, {s1}s2, [s1]s2, (s1)s2 are also RBS.

For example the string "[[(){}]<>]" is RBS, but the strings "[)()" and "][()()" are not.

Determine the least number of replaces to make the string s RBS.

Input

The only line contains a non empty string s, consisting of only opening and closing brackets of four kinds. The length of s does not exceed 106.

Output

If it's impossible to get RBS from s print Impossible.

Otherwise print the least number of replaces needed to get RBS from s.

Examples

Input

[&lt;}){}


Output

2

Input

{()}[]


Output

0

Input

]]


Output

Impossible

Solution (in JAVA):

Solution:
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    //---------------------------------------------------------------------------

    HashMap<Character, Integer> map;

    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        //-----------------------------------------------------------------------
        HashMap<Character, Integer> map = new HashMap();
        map.put('<', 0);
        map.put('>', 1);
        map.put('{', 2);
        map.put('}', 3);
        map.put('[', 4);
        map.put(']', 5);
        map.put('(', 6);
        map.put(')', 7);
        HashMap<Integer, Character> map1 = new HashMap();
        map1.put(0, '<');
        map1.put(1, '>');
        map1.put(2, '{');
        map1.put(3, '}');
        map1.put(4, '[');
        map1.put(5, ']');
        map1.put(6, '(');
        map1.put(7, ')');
        char[] a = in.next().toCharArray();
        int n = a.length;
        LinkedList<Character> q = new LinkedList();
        int c = 0;
        for (int i = 0; i < n; i++) {
            if (map.get(a[i]) % 2 == 1) {
                if (q.isEmpty()) {
                    out.println("Impossible");
                    out.close();
                    return;
                }
                if (q.getLast() != map1.get(map.get(a[i]) - 1)) {
                    c++;
                }
                q.removeLast();
            } else {
                q.add(a[i]);
            }
        }
        if (q.isEmpty()) {
            out.println(c);
        } else {
            out.println("Impossible");
        }
        //-----------------------------------------------------------------------
        out.close();
    }

    //---------------------------------------------------------------------------
    static class Pair implements Comparator {

        int first, second;

        public Pair() {

        }

        public Pair(int f, int s) {
            this.first = f;
            this.second = s;
        }

        @Override
        public int compare(Object o1, Object o2) {
            Pair p1 = (Pair) o1;
            Pair p2 = (Pair) o2;
            int ret = Integer.compare(p1.first, p2.first);
            if (ret == 0) {
                ret = Integer.compare(p1.second, p2.second);
            }
            return ret;
        }
    }

    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public boolean hasNext() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    String s = reader.readLine();
                    if (s == null) {
                        return false;
                    }
                    tokenizer = new StringTokenizer(s);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return true;
        }
    }
}