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.IOException;
import java.math.BigInteger;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class TestAC {

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

		Scanner input = new Scanner(System.in);

		String a = input.next();
		int res = 0;
		 
		Stack<Character> stack = new Stack<>();
		 if(a.startsWith(">") ||a.startsWith("}")||a.startsWith(")")||a.startsWith("]") || a.endsWith("<") ||a.endsWith("[") || a.endsWith("{") || a.endsWith("(") )
		 {
			 System.out.println("Impossible");
			 return;
		 }
			 
			 for (int i = a.length() - 1; i >= 0; i--) {
             
			if(a.charAt(i)=='{'){
				if(!stack.isEmpty())
			 if(stack.peek()=='}'){
				  
				 stack.pop();
			 }else{
				 res++;
				 stack.pop();
			 }
			 continue;
			}
			
			if(a.charAt(i)=='('){
				if(!stack.isEmpty())
				 if(stack.peek()==')'){
					
					 stack.pop();
				 }else{
					 res++;
					 stack.pop();
				 }
				 continue;
			}
			
			if(a.charAt(i)=='['){
				if(!stack.isEmpty())
				 if(stack.peek()==']'){
					 stack.pop();
				 }else{
					 res++;
					 stack.pop();
				 }
				 continue;
			}
			if(a.charAt(i)=='<'){
				if(!stack.isEmpty())
				 if(stack.peek()=='>'){
					 stack.pop();
				 }else{
					 res++;
					 stack.pop();
				 }
				 continue;
			}
			stack.push(a.charAt(i));
			 
			
			
	 
            
		}
		if(stack.isEmpty())
			System.out.println(res);
		else
		System.out.println("Impossible");

	}

	public static BigInteger fact(int big) {

		BigInteger f = new BigInteger("1");
		for (int i = big; i >= 1; i--) {
			f = f.multiply(new BigInteger(i + ""));
		}
		return f;
	}

	public static boolean checkPalindrom(String S) {
		StringBuilder S1 = new StringBuilder(S);
		if (S1.reverse().toString().equals(S))
			return true;
		else
			return false;
	}

	public static Map sortByValue(Map unsortMap) {
		List list = new LinkedList(unsortMap.entrySet());

		Collections.sort(list, new Comparator() {
			public int compare(Object o1, Object o2) {
				return ((Comparable) ((Map.Entry) (o1)).getValue()).compareTo(((Map.Entry) (o2)).getValue());
			}
		});
		// Collections.sort(list,Collections.reverseOrder());
		Map sortedMap = new LinkedHashMap();
		for (Iterator it = list.iterator(); it.hasNext();) {
			Map.Entry entry = (Map.Entry) it.next();

			sortedMap.put(entry.getKey(), entry.getValue());
		}
		return sortedMap;
	}
}