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 s_1 and s_2 be a RBS then the strings <s_1>s_2, {s_1}s_2, [s_1]s_2, (s_1)s_2 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 10^6.


-----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
[<}){}

Output
2
Input
{()}[]

Output
0
Input
]]

Output
Impossible

Difficulty: interview

Starter code:

Solutions:
seq = input()
a = []
fl = True
z = 0
for i in seq:
    if i == '<' or i == '[' or i == '{' or i == '(':
        a.append(i)
    elif i == '>':
        if len(a) and a[-1] == '<': a.pop()
        elif len(a) and a[-1] != '<':
            a.pop()
            z += 1
        else:
            fl = False
            break
    elif i == ')':
        if len(a) and a[-1] == '(': a.pop()
        elif len(a) and a[-1] != '(':
            a.pop()
            z += 1
        else:
            fl = False
            break
    elif i == ']':
        if len(a) and a[-1] == '[': a.pop()
        elif len(a) and a[-1] != '[':
            a.pop()
            z += 1
        else:
            fl = False
            break
    elif i == '}':
        if len(a) and a[-1] == '{': a.pop()
        elif len(a) and a[-1] != '{':
            a.pop()
            z += 1
        else:
            fl = False
            break
if len(a): fl = False
if fl: print(z)
else: print('Impossible')

s = input()
d = []
ans = 0
for f in s:
    if f in '{[<(':
        d.append(f)
    elif f == ')' and d and d[-1] == '(':
        d.pop()
    elif f == '}' and d and d[-1] == '{':
        d.pop()
    elif f == ']' and d and d[-1] == '[':
        d.pop()
    elif f == '>' and d and d[-1] == '<':
        d.pop()
    elif not d:
        print('Impossible')
        break
    else:
        ans += 1
        d.pop()
else:
    if not d:
        print(ans)
    else:
        print('Impossible')

s = input()

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

clopen = { ']': '[', '}': '{', '>': '<', ')': '(' }
popen = []
c = 0
for i in range(len(s)):
    if s[i] in open:
        popen.append(s[i])
    else:
        if len(popen) == 0:
            print('Impossible')
            return
        p = popen.pop()
        if clopen[s[i]] != p:
            c += 1

print(c if len(popen) == 0 else 'Impossible')


import math

s = input().rstrip()
n = len(s)
stack = []
k = 0
D = {'(' : 0, '{' : 2, '[' : 4, '<' : 6,
     ')' : 1, '}' : 3, ']' : 5, '>' : 7}
for i in range(n):
    c = s[i]
    if D[c]%2 == 0:
        stack.append(c)
    elif len(stack) == 0 or D[stack[-1]]%2:
        print('Impossible')
        break
    else:
        k += (D[c] - D[stack[-1]] != 1)
        stack.pop()
else:
    print(k if len(stack) == 0 else 'Impossible')
        


s = input()
open = '<', '(', '[', '{'
close = '>', ')', ']', '}'
resp = {close[i]: open[i] for i in (0, 1, 2, 3)}
cnt = 0
st = []
flag = True
for c in s:
    if c in open:
        st.append(c)
    elif st and st[-1] == resp[c]:
        st.pop()
    elif st:
        st.pop()
        cnt += 1
    else:
        flag = False
        break
if st: flag = False
print(cnt if flag else 'Impossible')
    



def solve():
    S = input()

    P = {
        '>': '<',
        ']': '[',
        ')': '(',
        '}': '{',
    }

    stack = []
    n = 0
    ans = 0
    for i, c in enumerate(S):
        if c in '<[{(':
            n += 1
            stack.append(c)
        else:
            n -= 1
            if len(stack) == 0:
                print('Impossible')
                return
            x = stack.pop()
            if x != P[c]:
                ans += 1

    if n != 0:
        print('Impossible')
        return

    print(ans)


def __starting_point():
    solve()

__starting_point()

s2=input()
dic={'{':1,'}':-1,'<':2,'>':-2,'[':3,']':-3,'(':4,')':-4}
stack=[]
count=0
n=0
for x in s2:
    if dic[x]<0:
        if n==0:
            print("Impossible")
            quit()
        if dic[stack[n-1]]+dic[x]!=0:
            count+=1
        stack.pop()
        n=n-1
    else:
        stack.append(x)
        n=n+1
if n!=0:
    print("Impossible")
else:
    print(count)


from functools import reduce
from operator import *
from math import *
from sys import *
from string import *
from collections import *
setrecursionlimit(10**7)
dX= [-1, 1, 0, 0,-1, 1,-1, 1]
dY= [ 0, 0,-1, 1, 1,-1,-1, 1]
RI=lambda: list(map(int,input().split()))
RS=lambda: input().rstrip().split()
#################################################
val={'<':1, '>':2, '[':1, ']':2, '(':1, ')':2, '{':1, '}':2}
pairs={'<':'>', '[':']','(':')','{':'}'}
s=input()
st=[]
ans=0
for i in s:
    if len(st) and val[st[-1]]==val[i]-1:
        if pairs[st[-1]]!=i:
            ans+=1
        st.pop()
    else:
        st.append(i)
print([ans,"Impossible"][len(st)>0])


BRACKETS = "{ }, [ ], < >, ( )"
openers = dict()
closers = dict()
for opener, closer in [x.split() for x in BRACKETS.split(",")]:
    openers[opener] = closer
    closers[closer] = opener
stack = list()
impossible = False
res = 0
for char in input():
    if char in openers:
        stack.append(char)
    else:
        if not stack:
            impossible = True
            break
        elif stack[-1] != closers[char]:
            res += 1
        stack.pop()
impossible |= len(stack) > 0
if impossible:
    print("Impossible")
else:
    print(res)


stack = []

def main():
    s = str(input())
    open = list("<{[(")
    close = list(">}])")

    answer = 0

    for e in s:
        if len(stack) == 0:
            if e in open:
                stack.append(e)
            else:
                print("Impossible")
                return
        else:
            top = len(stack) - 1
            if e in open:
                if stack[top] in close:
                    if open.index(e) != close.index(stack[top]):
                        answer += 1

                    stack.pop(top)
                else:
                    stack.append(e)
            else:
                if stack[top] in close:
                    stack.append(e)
                else:
                    if close.index(e) != open.index(stack[top]):
                        answer += 1

                    stack.pop(top)

    if len(stack) != 0:
        print("Impossible")
    else:
        print(answer)

def __starting_point():
    main()
__starting_point()

stack = []

def main():
    s = str(input())
    open = list("<{[(")
    close = list(">}])")

    answer = 0

    for e in s:
        if len(stack) == 0:
            if e in open:
                stack.append(e)
            else:
                print("Impossible")
                return
        else:
            top = len(stack) - 1
            if e in open:
                if stack[top] in close:
                    if open.index(e) != close.index(stack[top]):
                        answer += 1

                    stack.pop(top)
                else:
                    stack.append(e)
            else:
                if stack[top] in close:
                    stack.append(e)
                else:
                    if close.index(e) != open.index(stack[top]):
                        answer += 1

                    stack.pop(top)

    if len(stack) != 0:
        print("Impossible")
    else:
        print(answer)

def __starting_point():
    main()
__starting_point()

s = input()

stack = []
answer = 0
corrects = ('[]', '{}', '<>', '()')
for i in s:
    if i == '[' or i == '{' or i == '<' or i == '(':
        stack.append(i)
    else:
        if len(stack) == 0:
            print('Impossible')
            return
        else:
            top = stack.pop()
            if top + i not in corrects:
                answer += 1

print(answer if len(stack) == 0 else 'Impossible')


stack = []
counter = 0
possible = True
for b in input():
    if b in "{<([":
        stack.append(b)
    else:
        if not stack:
            possible = False
            break
        popped = stack.pop()
        if  (b == "}" and popped != "{") or \
            (b == ">" and popped != "<") or \
            (b == ")" and popped != "(") or \
            (b == "]" and popped != "["):
            counter += 1

if possible and not stack:
    print(counter)
else:
    print("Impossible")

s = input()
open = "({<["
close = ")}>]"
clopen = {']': '[', '}': '{', '>': '<', ')': '('}
ir2 = 0
ir = 0
if len(s) % 2 == 1:
    print("Impossible")
    return
else:
    l = []
    for i in range(len(s)):
        if s[i] in open:
            ir += 1
            l.append(s[i])
        else:
            ir -= 1
            if ir == -1:
                print("Impossible")
                return
            p = l.pop()
            if clopen[s[i]] != p:
                ir2 += 1
if ir != 0:
    print("Impossible")
    return
else:
    print(ir2)


opens = ['(', '{', '<', '[']
closes = [')', '}', '>', ']']

def solve(inp):
    stack = []
    res = 0
    for i, x in enumerate(inp):
        if x in opens:
            stack.append((i,x))
        if x in closes:
            if not stack:
                return 'Impossible'
            ii, xx = stack.pop()
            if closes.index(x) != opens.index(xx):
                res += 1
    if stack:
        return 'Impossible'
    return res

print(solve(input()))


from collections import deque 
import sys

strv = list(input())

if len(strv) % 2 != 0:
    print ("Impossible")
    return

openQ = deque([])

y=0

for brk in strv:
    if brk in ['[','{','(', '<']:
        openQ.append(brk) 
    else: 
        if len(openQ) >= 1:
            lastIn = openQ.pop() 
            if brk=="}":
                if lastIn != "{":
                    y=y+1
            elif brk=="]":
                if lastIn != "[":
                        y=y+1
            elif brk==")":
                if lastIn != "(":
                        y=y+1
            elif brk==">":
                if lastIn != "<":
                        y=y+1
        else:
            y="Impossible"
            break

if len(openQ) == 0 :
    print(y)
else:
    print("Impossible")


word = input()

BRACKETS = [
    ('<', '>'),
    ('{', '}'),
    ('[', ']'),
    ('(', ')'),
]

OPENING = [b[0] for b in BRACKETS]

MATCH = dict(BRACKETS)

IMPOSSIBLE = 'Impossible'

def is_opening(w):
    return w in OPENING

def same_kind(wo, wc):
    return MATCH[wo] == wc

def solve(word):
    temp = []
    result = 0
    for w in word:
        if is_opening(w):
            temp.append(w)
        else:
            if len(temp) == 0:
                return IMPOSSIBLE
            wo = temp.pop()
            if not is_opening(wo):
                return IMPOSSIBLE
            if not same_kind(wo, w):
                result += 1
    if len(temp) != 0:
        return IMPOSSIBLE
    return result
                
print(solve(word))


# -*- coding: utf-8 -*-
import sys

def fun():
    try:
        str = input()
    except ValueError:
        print('Invalid number')
        return
    S = {"}": "{",")": "(",">": "<","]":"["}
    L = []
    ans = 0
    for c in str:
        if c in S.values():
            L.append(c)
            pass
        else:
            if(len(L) >0 ):
                ans += 0 if S[c] == L.pop() else 1
            else:
                ans = -1
                break
            pass
    if( len(L)> 0 or ans <0):
        print('Impossible')
    else:
        print(ans)
    pass

def __starting_point():
    fun()
    '''
    for i,v in enumerate(map(int,input().split())):
        print(i,v)
    '''
__starting_point()

def solution(s):
    st = []
    ans = 0
    for i, j in enumerate(s):
        if j in open:
            st.append((i,j))
        if j in close:
            if not st:
                return ("Impossible")
            q,w = st.pop()
            if close.index(j) != open.index(w):
                ans += 1
    if st:
        return ("Impossible")
    return ans
s=str(input())
open = ['(', '{', '<', '[']
close = [')', '}', '>', ']']
print(solution(s))

#!/usr/bin/env python3

import sys

s = input()
OPENING = ('<', '{', '[', '(')
CLOSING = ('>', '}', ']', ')')
result = 0
stack = []

for c in s:
    if c in OPENING:
        stack.append(c)
    else:
        if stack:
            last_br = stack.pop()
            if c != CLOSING[OPENING.index(last_br)]:
                result += 1
        else:
            print("Impossible")
            return
print("Impossible" if stack else result)


#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2016 missingdays <missingdays@missingdays>
#
# Distributed under terms of the MIT license.

"""

"""

opening = {
        "[": "]",
        "<": ">",
        "{": "}",
        "(": ")",
}

closing = {
        "]": "[",
        ">": "<",
        "}": "{",
        ")": "(",
}

s = input()

stack = []

answ = 0

for c in s:
    if c in opening:
        stack.append(c)
    else:
        if len(stack) == 0:
            print("Impossible")
            return

        op = stack.pop()

        if c != opening[op]:
            answ += 1

if len(stack) != 0:
    print("Impossible")
    return
print(answ)


s = input()
cnt = 0
st = []
for elem in s:
    if elem in '([{<':
        st.append(elem)
    else:
        if len(st) == 0:
            print('Impossible')
            break
        elem2 = st.pop()
        if elem2 + elem not in '()[]{}<>':
            cnt += 1
else:
    if len(st) == 0:
        print(cnt)
    else:
        print('Impossible')

from collections import deque

def f(s1):
    return s1 in "<{[("

s = list(input())

d = deque([])
ans = 0
for i in s:
    if f(i):
        d.append(i)
    else:
        if len(d) == 0:
            print("Impossible")
            return
        elif ord(d[-1]) + 2 == ord(i) or ord(d[-1]) + 1 == ord(i):
            d.pop()
        else:
            d.pop()
            ans += 1
if len(d) > 0:
    print("Impossible")
    return
print(ans)

a=input()
b=0
c='([{<'
d=')]}>'
e=[]
f=False
for i in a:
    if i in c:e+=[i]
    else:
        if not e:
            print('Impossible')
            f=True
            break
        if d.index(i)!=c.index(e[-1]):b+=1
        e.pop()
if e:print('Impossible')
elif not f:print(b)


s = input()
open = {'(', '{', '[', '<'}
res = 0
our = []
for elem in s:
    if elem in open:
        our.append(elem)
    else:
        if our:
            res += (abs(ord(elem) - ord(our[-1])) > 2)
            our.pop()
        else:
            print('Impossible')
            return
if our:
    print('Impossible')
else:
    print(res)