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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class C612C {

    public static void main(String[] args) throws Exception {
        new C612C().run();
        out.close();
    }

    boolean isSameType(char c, char d) {
        return c == '(' && d == ')'
                || c == '[' && d == ']'
                || c == '{' && d == '}'
                || c == '<' && d == '>';
    }

    void run() throws Exception {
        String s = nextToken();
        LinkedList<Character> list = new LinkedList<>();
        int res = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == ')' || c == ']' || c == '}' || c == '>') {
                if (list.isEmpty()) {
                    out.print("Impossible");
                    return;
                } else if (!isSameType(list.poll(), c)) {
                    ++res;
                }
            } else {
                list.push(c);
            }
        }
        if (!list.isEmpty()) {
            out.print("Impossible");
        } else {
            out.print(res);
        }
    }

//~~~~~~~~~~~~~~~~~~~~~~~~~~~ template ~~~~~~~~~~~~~~~~~~~~~~~~~~~
    int[] nextIntArray(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            res[i] = nextInt();
        }
        return res;
    }

    int[][] nextIntArray(int nx, int ny) throws IOException {
        int[][] res = new int[nx][ny];
        for (int i = 0; i < nx; ++i) {
            for (int j = 0; j < ny; ++j) {
                res[i][j] = nextInt();
            }
        }
        return res;
    }

    long[] nextLongArray(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; ++i) {
            res[i] = nextLong();
        }
        return res;
    }

    long[][] nextLongArray(int nx, int ny) throws IOException {
        long[][] res = new long[nx][ny];
        for (int i = 0; i < nx; ++i) {
            for (int j = 0; j < ny; ++j) {
                res[i][j] = nextLong();
            }
        }
        return res;
    }

    void fill(int[][] arr, int val) {
        for (int i = 0; i < arr.length; ++i) {
            Arrays.fill(arr[i], val);
        }
    }

    void fill(int[][][] arr, int val) {
        for (int i = 0; i < arr.length; ++i) {
            fill(arr[i], val);
        }
    }

    int[][] newIntArray(int nx, int ny, int val) {
        int[][] res = new int[nx][ny];
        fill(res, val);
        return res;
    }

    int[][][] newIntArray(int nx, int ny, int nz, int val) {
        int[][][] res = new int[nx][ny][nz];
        fill(res, val);
        return res;
    }

    long[][] newLongArray(int nx, int ny, long val) {
        long[][] res = new long[nx][ny];
        for (int i = 0; i < nx; ++i) {
            Arrays.fill(res[i], val);
        }
        return res;
    }

    long[][][] newLongArray(int nx, int ny, int nz, long val) {
        long[][][] res = new long[nx][ny][nz];
        for (int i = 0; i < nx; ++i) {
            for (int j = 0; j < ny; ++j) {
                Arrays.fill(res[i][j], val);
            }
        }
        return res;
    }

    <T> ArrayList<T>[] newArrayListArray(int sz) {
        ArrayList<T>[] res = new ArrayList[sz];
        for (int i = 0; i < sz; ++i) {
            res[i] = new ArrayList<>();
        }
        return res;
    }

    String nextToken() throws IOException {
        while (strTok == null || !strTok.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null) {
                return null;
            }
            strTok = new StringTokenizer(line);
        }
        return strTok.nextToken();
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    static StringTokenizer strTok;
    final static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    final static PrintWriter out = new PrintWriter(System.out);
}