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.util.*;
import java.nio.charset.StandardCharsets;
// import java.math.BigInteger;

public class C {
    static Writer wr;

    static boolean check(int[]a, int[] b) {
        for(int i=0;i<a.length;i++) {
            if(a[i]!=b[i]) return false;
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        // long startTime = System.nanoTime();

        // String testString = "";
        // InputStream stream = new ByteArrayInputStream(testString.getBytes(StandardCharsets.UTF_8));
        // Reader in = new Reader(stream);

        Reader in = new Reader();
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        
        wr = new Writer();

        /* Precomputation */


        // long elapsedTime = System.nanoTime() - startTime;
        // double seconds = (double)elapsedTime / 1000000000.0;
        // wr.writeRedLn(seconds);

        /* Input */
        // int N = in.nextInt();

        char[] s = in.readLine().trim().toCharArray();

        int N = s.length;

        char[] open = {'[', '(', '<', '{'};
        char[] close = {']', ')', '>', '}'};

        HashMap<Character,Integer> open_rev = new HashMap<>();
        HashMap<Character,Integer> close_rev = new HashMap<>();

        for(int i=0;i<4;i++) {
            open_rev.put(open[i],i);
            close_rev.put(close[i],i);
        }

        int[] open_count = new int[4];
        int[] close_count = new int[4];

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++) {
            int type = 0;
            for(int j=0;j<4;j++) {
                if(s[i]==open[j]) {
                    open_count[j]++;
                    type = 0;
                    break;
                }
                if(s[i]==close[j]) {
                    close_count[j]++;
                    type = 1;
                    break;
                }
            }
            sb.append((char)(type+'0'));
        }

        

        Stack<Integer> st = new Stack<>();
        Stack<Character> st2 = new Stack<>();
        boolean flag = true;

        int ans = 0;
        for(int i=0;i<N;i++) {
            if(st.empty()) {
                st.add(sb.charAt(i)-'0');
                st2.add(s[i]);
            }
            else {
                int curr = st.peek();
                int nx = (sb.charAt(i)-'0');
                if((curr == 0) && (nx==1)) {
                    st.pop();
                    char open_ch = st2.pop();
                    char close_ch = s[i];
                    // wr.writeGreenLn(open_ch + ", " + close_ch);
                    if(open_rev.get(open_ch) != close_rev.get(close_ch)) ans++;
                }
                else {
                    st.add(nx);
                    st2.add(s[i]);
                }
            }

        }

        if(st.size()>0) {
            flag = false;
        }
        
        if(flag) {
            
            // wr.writeRedLn(Arrays.toString(open_count));
            // wr.writeRedLn(Arrays.toString(close_count));

            out.write(ans + "\n");
        }
        else {
            out.write("Impossible\n");
        }


        
        out.flush();
    }
}



class Writer {
    public void writeRedLn(Object x) { writeRedLn(x+""); }
    public void writeBlueLn(Object x) { writeBlueLn(x+""); }
    public void writeGreenLn(Object x) { writeGreenLn(x+""); }
    public void writePinkLn(Object x) { writePinkLn(x+""); }
    public void writeRedLn(String x) { System.out.println((char)27 + "[31m" + (char)27 + "[40m" + x + (char)27 + "[0m"); }
    public void writeBlueLn(String x) { System.out.println((char)27 + "[34m" + (char)27 + "[3m" + x + (char)27 + "[0m"); }
    public void writeGreenLn(String x) { System.out.println((char)27 + "[32m" + (char)27 + "[3m" + x + (char)27 + "[0m"); }
    public void writePinkLn(String x) { System.out.println((char)27 + "[30m" + (char)27 + "[45m" + x + (char)27 + "[0m"); }
    public void writeRed(String x) { System.out.print((char)27 + "[31m" + (char)27 + "[40m" + x + (char)27 + "[0m"); }
    public void writeBlue(String x) { System.out.print((char)27 + "[34m" + (char)27 + "[3m" + x + (char)27 + "[0m"); }
    public void writeGreen(String x) { System.out.print((char)27 + "[32m" + (char)27 + "[3m" + x + (char)27 + "[0m"); }
    public void writePink(String x) { System.out.print((char)27 + "[30m" + (char)27 + "[45m" + x + (char)27 + "[0m"); }
}


class Reader {
    final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
    public Reader(){din=new DataInputStream(System.in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;}
    public Reader(InputStream stream){din=new DataInputStream(stream);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;}
    public int[] ni_array(int N) throws IOException { int[] ans = new int[N]; for(int i=0;i<N;i++) { ans[i] = nextInt(); } return ans; }
    public String readLine()throws IOException{byte[] buf=new byte[1000024];int cnt=0,c;
        while((c=read())!=-1){if(c=='\n')break;buf[cnt++]=(byte)c;}return new String(buf,0,cnt);}
    public char nextChar()throws IOException{byte c=read();while(c<=' ')c=read();return (char)c;}
    public int nextInt()throws IOException{int ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');
        if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;} 
    public long nextLong()throws IOException{long ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');
        if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;}
    public double nextDouble()throws IOException{double ret=0,div=1;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c = read();do {ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');
        if(c=='.')while((c=read())>='0'&&c<='9')ret+=(c-'0')/(div*=10);if(neg)return -ret;return ret;}
    private void fillBuffer()throws IOException{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;}
    private byte read()throws IOException{if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];}
    public void close()throws IOException{if(din==null) return;din.close();}
}