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:
//package cf;

import java.io.*;
import java.util.*;

public final class Cf {

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);        
        FastReader sc = new FastReader();
        char c[]=sc.next().toCharArray();
        int cnt=0,replace=0;
        HashMap<Character,Integer>map=new HashMap<>();
        for(int i=0;i<c.length;i++)
        {
            if(c[i]=='['||c[i]=='<'||c[i]=='{'||c[i]=='(')cnt++;
            else
            {
                if(cnt>0)cnt--;
                else {cnt=1;break;}
            }
            map.put(c[i],map.getOrDefault(c[i], 0)+1);
        }
        if(cnt!=0)out.write("Impossible");
        else
        {
            Stack<Character>opening=new Stack<>();
            for(char ch:c)
            {
                if(ch=='['||ch=='<'||ch=='{'||ch=='(')opening.add(ch);
                else
                {
                    Character temp=opening.pop();
                   if(ch==']'&&temp!='[')replace++;
                   if(ch=='}'&&temp!='{')replace++;
                   if(ch==')'&&temp!='(')replace++;
                   if(ch=='>'&&temp!='<')replace++;
                   
                    //debug("ch is "+ch+" temp is "+temp+" replace is "+replace);
                    
                }
            }
            out.write(replace+"");
        }
        out.flush();
        
    }
    public static int check_for_braces(HashMap<Character,Integer>map)
    {
        if(!map.containsKey('('))return 0;
        if(!map.containsKey(')'))return map.get('(');
        if(map.get(')')>=map.get('('))return 0;
        return map.get('(')-map.get(')');
    }
        public static int check_for_cbraces(HashMap<Character,Integer>map)
    {
        if(!map.containsKey('{'))return 0;
        if(!map.containsKey('}'))return map.get('{');
        if(map.get('}')>=map.get('{'))return 0;
        return map.get('{')-map.get('}');
    }

  public static int check_for_sbraces(HashMap<Character,Integer>map)
    {
        if(!map.containsKey('['))return 0;
        if(!map.containsKey(']'))return map.get('[');
        if(map.get(']')>=map.get('['))return 0;
        return map.get('[')-map.get(']');
    }
     public static int check_for_abraces(HashMap<Character,Integer>map)
    {
        if(!map.containsKey('<'))return 0;
        if(!map.containsKey('>'))return map.get('<');
        if(map.get('>')>=map.get('<'))return 0;
        return map.get('<')-map.get('>');
    }
    ///////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////////////////
    static class FastReader {        
        
        BufferedReader br;        
        StringTokenizer st;        
        
        public FastReader() {            
            br = new BufferedReader(new InputStreamReader(System.in));            
        }        
        
        String next() {            
            while (st == null || !st.hasMoreElements()) {                
                try {                    
                    st = new StringTokenizer(br.readLine());                    
                } catch (IOException e) {                    
                    e.printStackTrace();                    
                }                
            }            
            return st.nextToken();            
        }        
        
        int nextInt() {            
            return Integer.parseInt(next());            
        }        
        
        long nextLong() {            
            return Long.parseLong(next());            
        }        
        
        double nextDouble() {            
            return Double.parseDouble(next());            
        }        
        
        String nextLine() {            
            String str = "";            
            try {                
                str = br.readLine();                
            } catch (IOException e) {                
                e.printStackTrace();                
            }            
            return str;            
        }        
    }
    //////////////////////////////////////////////////////////////////

    static 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(String file_name) throws IOException {            
            din = new DataInputStream(new FileInputStream(file_name));            
            buffer = new byte[BUFFER_SIZE];            
            bufferPointer = bytesRead = 0;            
        }        
        
        public String readLine() throws IOException {            
            byte[] buf = new byte[1002]; // line length 
            int cnt = 0, c;            
            while ((c = read()) != -1) {                
                if (c == '\n') {
                    break;
                }                
                buf[cnt++] = (byte) c;                
            }            
            return new String(buf, 0, cnt);            
        }        
        
        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();            
        }        
    }    

    public static void debug(String s) {
        System.out.println(s);
    }
}