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.io.*;
import java.math.BigInteger;
import java.util.*;

/**
 * Created by ribra on 11/15/2015.
 */
public class Main {

    private static InputReader sc = new InputReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);



    public static void main(String [] args) throws Exception {

        String str = sc.next();
        Set<Character> open = new HashSet<>(Arrays.asList('[', '(', '<', '{'));
        Set<Character> close = new HashSet<>(Arrays.asList(']', ')', '>'));

        int n = str.length();
        Stack<Character> stack = new Stack<>();
        int counter = 0;
        boolean isOk = true;
        for (int i = 0; i < n; i++) {
            char c = str.charAt(i);
            if (open.contains(c)) {
                stack.add(c);
            }
            else {
                if (stack.size() == 0) {
                    isOk = false;
                    break;
                }
                char q = stack.pop();
                if (!((q == '[' && c == ']')
                        || (q == '(' && c == ')')
                        || (q == '<' && c == '>')
                        || (q == '{' && c == '}'))) {
                    counter++;
                }
            }
        }

        if (stack.size() != 0) out.print("Impossible");
        else if (!isOk) out.print("Impossible");
        else out.print(counter);





        terminate();
    }

    




    public static void terminate() {
        out.close();
    }


    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());
        }

    }

    static class Graph {
        private int V;
        private int E;
        private Set<Integer>[] adj;

        public Graph(int V) {
            this.V = V;
            this.E = 0;
            adj = new HashSet[V];
            for (int i = 0; i < V; i++)
                adj[i] = new HashSet<>();
        }


        public int V() {
            return V;
        }

        public int E() {
            return E;
        }

        public void addEdge(int v, int w) {
            adj[v].add(w);
            adj[w].add(v);
            E++;
        }

        public Iterable<Integer> adj(int v) {
            return adj[v];
        }


        public static int degree(Graph g, int v) {
            int degree = 0;
            for (int w : g.adj(v)) degree++;
            return degree;
        }


        public static int maxDegree(Graph g) {
            int max = 0;
            for (int i = 0; i < g.V(); i++)
                max = Math.max(degree(g, i), max);
            return max;
        }


        public static int avgDegree(Graph g) {
            int sum = 0;
            for (int i = 0; i < g.V(); i++)
                sum += degree(g, i);
            return sum / g.V();
        }


        public static int avgDegreeEfficient(Graph g) {
            // g.E = sum degree of every graph
            // 2 * g.E - because if v is connected to w, then w is connected to v as well
            // and divide by number of vertices
            return 2 * g.E() / g.V();
        }

        public static int numberOfSelfLoops(Graph g) {
            int count = 0;
            for (int i = 0; i < g.V(); i++)
                for (int w : g.adj(i))
                    if (i == w) count++;
            return count / 2;
        }

        public String toString()
        {
            String s = V() + " vertices, " + E() + " edges\n";
            for (int v = 0; v < V(); v++)
            {
                s += v + ": ";
                for (int w : this.adj(v))
                    s += w + " ";
                s += "\n";
            }
            return s;
        }

    }
}