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: MEDIUM
Tags: Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
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 collections import *
from itertools import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from sys import *

def fast():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in fast().split()]
(z, zz) = (input, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer):
	stdout.write(str(answer))
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
cnt = 0
arr = fast()
opn = {'(': ')', '<': '>', '[': ']', '{': '}'}
openBract = 0
que = deque()
for i in arr:
	if i in opn:
		openBract += 1
		que.append(opn[i])
	else:
		try:
			x = que.pop()
			if i != x:
				cnt += 1
				que.appendleft(x)
		except:
			print('Impossible')
			exit()
print(cnt if openBract == len(arr) - openBract else 'Impossible')


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)
			elif 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()


import sys
s = input()
OPENING = ('<', '{', '[', '(')
CLOSING = ('>', '}', ']', ')')
result = 0
stack = []
for c in s:
	if c in OPENING:
		stack.append(c)
	elif stack:
		last_br = stack.pop()
		if c != CLOSING[OPENING.index(last_br)]:
			result += 1
	else:
		print('Impossible')
		return
print('Impossible' if stack else result)


s = input()
otc = {'[': ']', '{': '}', '(': ')', '<': '>'}
cto = {'>': '<', '}': '{', ')': '(', ']': '['}
stack = []
res1 = 0
for c in s:
	if c in otc.keys():
		stack.append(c)
		continue
	if len(stack) == 0:
		res1 = -1
		break
	o = stack[len(stack) - 1]
	stack.pop()
	if c == otc[o]:
		continue
	else:
		res1 += 1
if res1 == -1 or len(stack) != 0:
	print('Impossible')
else:
	print(res1)


S = input()
N = len(S)
lt = {'[', '(', '{', '<'}
rt = {']', ')', '}', '>'}
stack = []
res = 0
for i in range(N):
	if S[i] in lt:
		stack.append(i)
	elif not stack:
		print('Impossible')
		break
	else:
		c = stack.pop()
		if S[c] + S[i] not in {'[]', '()', '{}', '<>'}:
			res += 1
else:
	if not stack:
		print(res)
	else:
		print('Impossible')


opening = set(['(', '<', '[', '{'])
closing = set([')', '>', ']', '}'])

def im_noob(s):
	ans = 0
	l = 0
	stack = []
	for i in s:
		if i in opening:
			if i == '[':
				stack.append(']')
			elif i == '<':
				stack.append('>')
			elif i == '{':
				stack.append('}')
			elif i == '(':
				stack.append(')')
			l += 1
		else:
			try:
				if i != stack[l - 1]:
					ans += 1
					stack.pop()
					l -= 1
				else:
					stack.pop()
					l -= 1
			except:
				return 'Impossible'
	if l > 0:
		return 'Impossible'
	return ans
s = input()
print(im_noob(s))


from sys import stdin

def main():
	s = stdin.readline()
	stack = []
	ok = True
	ans = 0
	close = '>}])'
	open = '<{[('
	for i in range(len(s) - 1):
		if s[i] in close:
			if not stack:
				ok = False
				break
			else:
				i1 = close.index(s[i])
				i2 = open.index(stack[-1])
				if i1 != i2:
					ans += 1
				stack.pop()
		else:
			stack.append(s[i])
	if stack or not ok:
		print('Impossible')
	else:
		print(ans)
main()


from collections import deque
s = deque()
v = input()
ans = 0
for i in range(len(v)):
	if len(s) == 0:
		if v[i] == ')' or v[i] == '}' or v[i] == ']' or (v[i] == '>'):
			print('Impossible')
			exit()
	if v[i] == '(' or v[i] == '<' or v[i] == '[' or (v[i] == '{'):
		s.append(v[i])
	else:
		k = abs(ord(v[i]) - ord(s[len(s) - 1]))
		if abs(ord(v[i]) - ord(s[len(s) - 1])) <= 2:
			s.pop()
		else:
			ans += 1
			s.pop()
if len(s) != 0:
	print('Impossible')
else:
	print(ans)


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)
	elif len(d) == 0:
		print('Impossible')
		exit()
	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')
	exit()
print(ans)


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
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 sys import stdin
from collections import deque
lst = deque(stdin.readline().strip())
opened = '([<{'
closed = ')]>}'
stack = []
change = 0
for i in lst:
	stack.append(i)
	if len(stack) >= 2:
		if i in closed and stack[-2] in opened:
			if closed.index(i) != opened.index(stack[-2]):
				change += 1
			del stack[-2:]
		elif i in closed and stack[-2] in closed:
			change = 'Impossible'
			break
if len(stack) != 0:
	change = 'Impossible'
print(change)


s = input()
(left, ans) = (list(), 0)

def type(ch):
	if ch in '<>':
		return 0
	if ch in '{}':
		return 1
	if ch in '[]':
		return 2
	if ch in '()':
		return 3
for ch in s:
	if ch in '<{[(':
		left.append(ch)
	else:
		if len(left) == 0:
			print('Impossible')
			exit(0)
		ch_left = left.pop()
		if type(ch) != type(ch_left):
			ans += 1
print(ans if len(left) == 0 else '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)


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
fun()


from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import *
input = stdin.readline
prin = stdout.write
from random import sample
from collections import Counter, deque
from math import sqrt, ceil, log2, gcd
mod = 10 ** 9 + 7

class DisjSet:

	def __init__(self, n):
		self.rank = [1] * n
		self.parent = [i for i in range(n)]

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		xset = self.find(x)
		yset = self.find(y)
		if xset == yset:
			return
		if self.rank[xset] < self.rank[yset]:
			self.parent[xset] = yset
		elif self.rank[xset] > self.rank[yset]:
			self.parent[yset] = xset
		else:
			self.parent[yset] = xset
			self.rank[xset] = self.rank[xset] + 1

def f(arr, i, j, d, dist):
	if i == j:
		return
	nn = max(arr[i:j])
	for tl in range(i, j):
		if arr[tl] == nn:
			dist[tl] = d
			f(arr, i, tl, d + 1, dist)
			f(arr, tl + 1, j, d + 1, dist)

def ps(n):
	cp = 0
	lk = 0
	arr = []
	countprev = 0
	while n % 2 == 0:
		n = n // 2
		lk += 1
	for ps in range(3, ceil(sqrt(n)) + 1, 2):
		lk = 0
		while n % ps == 0:
			n = n // ps
			lk += 1
	if n != 1:
		lk += 1
		return [lk, 'NO']
	return [lk, 'YES']

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def factorials(n, r):
	slr = n
	dpr = r
	qlr = 1
	qs = 1
	mod = 10 ** 9 + 7
	for ip in range(n - r + 1, n + 1):
		qlr = qlr * ip % mod
	for ij in range(1, r + 1):
		qs = qs * ij % mod
	ans = qlr * modInverse(qs) % mod
	return ans

def modInverse(b):
	qr = 10 ** 9 + 7
	return pow(b, qr - 2, qr)
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def power(arr):
	listrep = arr
	subsets = []
	for i in range(2 ** len(listrep)):
		subset = []
		for k in range(len(listrep)):
			if i & 1 << k:
				subset.append(listrep[k])
		subsets.append(subset)
	return subsets

def dis(xa, ya, xb, yb):
	return sqrt((xa - xb) ** 2 + (ya - yb) ** 2)

def ii():
	return int(input())

def ilist():
	return [int(x) for x in input().strip().split()]

def outstrlist(array: list) -> str:
	array = [str(x) for x in array]
	return ' '.join(array)

def islist():
	return list(map(str, input().split().rstrip()))

def outfast(arr: list) -> str:
	ss = ''
	for ip in arr:
		ss += str(ip) + ' '
	return prin(ss)
t = 1
for jj in range(t):
	aa = input().strip()
	kk = []
	ss = {'<': 0, '{': 1, '[': 2, '(': 3, '>': 4, '}': 5, ']': 6, ')': 7}
	cc = 0
	bb = 0
	for i in aa:
		if ss[i] < 4:
			kk.append(ss[i])
		elif len(kk) > 0:
			if ss[i] - kk[-1] != 4:
				cc += 1
			kk.pop()
		else:
			bb = 1
			break
	if bb == 1 or len(kk) > 0:
		print('Impossible')
	else:
		print(cc)


k = input()
p = 0
q = []
for i in range(len(k)):
	if k[i] == '(' or k[i] == '{' or k[i] == '[' or (k[i] == '<'):
		q.append(k[i])
	else:
		if len(q) <= 0:
			print('Impossible')
			exit(0)
		m = q.pop()
		if k[i] == ')' and m == '(':
			continue
		elif k[i] == '}' and m == '{':
			continue
		elif k[i] == ']' and m == '[':
			continue
		elif k[i] == '>' and m == '<':
			continue
		else:
			p += 1
if len(q) != 0:
	print('Impossible')
	exit(0)
print(p)


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import *
from collections import defaultdict, deque, Counter
import math, string
from heapq import *
from operator import add
from itertools import accumulate
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inf = float('inf')
en = lambda x: list(enumerate(x))
ceil_ = lambda a, b: (a + b - 1) // b
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
o = '<{[('
c = '>}])'
z = {j: i for (i, j) in zip(o, c)}
arr = []
x = 0
ans = 0
for i in input():
	if i in o:
		x += 1
		arr += (i,)
	else:
		x -= 1
		if x < 0:
			print('Impossible')
			exit()
		if arr.pop() != z[i]:
			ans += 1
if x:
	print('Impossible')
	exit()
print(ans)


(k, s) = (0, [])
for q in input():
	i = '[{<(]}>)'.find(q)
	if i > 3:
		if not s:
			s = 1
			break
		if s.pop() != i - 4:
			k += 1
	else:
		s += [i]
print('Impossible' if s else k)


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)


import sys
import bisect
from bisect import bisect_left as lb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
d = {')': '(', ']': '[', '}': '{', '>': '<'}
op = ['(', '[', '{', '<']

def hnbhai():
	s = sa()
	stck = []
	tot = 0
	for i in s:
		if i in op:
			stck.append(i)
		elif len(stck) == 0:
			print('Impossible')
			return
		else:
			if d[i] != stck[-1]:
				tot += 1
			stck.pop()
	if len(stck) == 0:
		print(tot)
	else:
		print('Impossible')
for _ in range(1):
	hnbhai()


def main(s: str):
	if len(s) == 0 or len(s) % 2 != 0:
		return 'Impossible'
	leftchr = ['(', '{', '<', '[']
	stack = list()
	opdict = {'(': ')', '{': '}', '<': '>', '[': ']'}
	mix = 0
	for oper in s:
		if oper in leftchr:
			stack.append(oper)
		else:
			try:
				top = stack.pop()
			except:
				return 'Impossible'
			if opdict.get(top) != oper:
				mix += 1
	if len(stack) != 0:
		return 'Impossible'
	return mix
s = str(input())
print(main(s))


s = list(input())
d = {'(': ')', '[': ']', '<': '>', '{': '}'}
stack = []
ans = 0
c = 0
for i in s:
	if i in d.keys():
		stack.append(i)
		c += 1
	else:
		c -= 1
		if c < 0:
			print('Impossible')
			exit()
		b = stack.pop()
		if i != d[b]:
			ans += 1
if c == 0:
	print(ans)
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')


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))


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')


R = lambda : list(map(int, input().split()))
s = input()
ok = True
ans = 0
st = []
opn = set('<[({')
inv = {'}': '{', ')': '(', '>': '<', ']': '['}
for i in s:
	if i in opn:
		st.append(i)
	else:
		if not st:
			ok = False
			break
		if inv[i] != st[-1]:
			ans += 1
		st.pop()
if not ok or st:
	print('Impossible')
else:
	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)


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)
	elif 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')


def main(s: str):
	if len(s) == 0:
		return 'Impossible'
	leftchr = ['(', '{', '<', '[']
	rightchr = [')', '}', '>', ']']
	stack = list()
	opdict = {'(': ')', '{': '}', '<': '>', '[': ']'}
	mix = 0
	for oper in s:
		if oper in leftchr:
			stack.append(oper)
		elif oper in rightchr:
			if len(stack) == 0:
				return 'Impossible'
			else:
				top = stack.pop()
			if opdict.get(top) != oper:
				mix += 1
	if len(stack) != 0:
		return 'Impossible'
	return mix
s = str(input())
print(main(s))


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


l = []
cnt = 0
for i in input():
	if i in '[<{(':
		l.append(i)
	elif len(l) > 0:
		if l.pop() != {'}': '{', ')': '(', ']': '[', '>': '<'}[i]:
			cnt += 1
	else:
		print('Impossible')
		break
else:
	if len(l) > 0:
		print('Impossible')
	else:
		print(cnt)


s = input()
s1 = []
for i in s:
	if i == '(':
		s1.append(1)
	elif i == '[':
		s1.append(2)
	elif i == '{':
		s1.append(3)
	elif i == '<':
		s1.append(4)
	elif i == ')':
		s1.append(-1)
	elif i == ']':
		s1.append(-2)
	elif i == '}':
		s1.append(-3)
	else:
		s1.append(-4)
m = []
c = 0
for char in s1:
	if len(m) > 0:
		if m[-1] > 0:
			if m[-1] == -char:
				m.pop()
			elif char < 0:
				m.pop()
				c += 1
			else:
				m.append(char)
		else:
			m.append(char)
	else:
		m.append(char)
if len(m) > 0:
	print('Impossible')
else:
	print(c)


def getresult(mystr):
	stack = []
	dictionary = {'<': '>', '{': '}', '[': ']', '(': ')'}
	result = 0
	for x in mystr:
		if x in dictionary:
			stack.append(x)
		elif len(stack) == 0:
			return 'Impossible'
		elif dictionary[stack.pop()] != x:
			result += 1
		else:
			pass
	if len(stack) == 0:
		return result
	else:
		return 'Impossible'
mystr = input()
print(getresult(mystr))


import sys
import math
import collections
import heapq
import decimal
s = input()
n = len(s)
c = 0
c1 = 1
for i in range(n):
	if s[i] in ['(', '<', '{', '[']:
		c += 1
	else:
		c -= 1
	if c < 0:
		c1 = 0
		break
if c1 == 0 or c != 0:
	print('Impossible')
else:
	l = []
	c1 = 1
	d = {'<': '>', '[': ']', '{': '}', '(': ')'}
	c = 0
	for i in range(n):
		if s[i] in ['(', '<', '{', '[']:
			l.append(s[i])
		elif l == []:
			c1 = 0
			break
		elif d[l[-1]] == s[i]:
			l.pop()
		else:
			l.pop()
			c += 1
	if c1 == 0:
		print('Impossible')
	else:
		print(c)


s = input()
brackets = {'<': '>', '{': '}', '[': ']', '(': ')'}
OPENING = '<{[('
CLOSING = '>}])'

def main(s):
	stack = []
	res = 0
	for c in s:
		if c in OPENING:
			stack.append(c)
		else:
			if stack:
				top = stack.pop()
				if top in OPENING:
					if brackets[top] != c:
						res += 1
					continue
			return 'Impossible'
	return res if not stack else 'Impossible'
print(main(s))


import sys
s = input()
stack = []
c = 0
brackets = {')': '(', ']': '[', '}': '{', '>': '<'}
for char in s:
	if char in brackets.values():
		stack.append(char)
	elif char in brackets.keys():
		if stack == []:
			print('Impossible')
			sys.exit()
		if brackets[char] != stack.pop():
			c = c + 1
if len(stack) != 0:
	print('Impossible')
	sys.exit(0)
print(c)


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')


s = list(input())
x = list('<>{}[]()')
l = [0] * 4
d = {}
k = 0
(o, c) = (0, 0)
f = 1
ans = 0
for t in s:
	y = x.index(t)
	yy = y // 2
	if y % 2 == 0:
		if f:
			k += 1
		o += 1
		d[k] = yy
		f = 1
	else:
		if not f:
			k -= 1
		if k <= 0:
			print('Impossible')
			exit()
		c += 1
		f = 0
		if not d[k] == yy:
			ans += 1
print(ans if o == c else '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))


try:

	def ad(expr):
		stack = []
		l = 0
		for char in expr:
			if char in ['(', '{', '[', '<']:
				stack.append(char)
			else:
				if not stack:
					return 'Impossible'
				current_char = stack.pop()
				if current_char == '(':
					if char != ')' and char == '}' or char == ']' or char == '>':
						l += 1
				if current_char == '{':
					if char != '}' and char == ')' or char == ']' or char == '>':
						l += 1
				if current_char == '[':
					if char != ']' and char == '}' or char == ')' or char == '>':
						l += 1
				if current_char == '<':
					if char != '>' and char == '}' or char == ')' or char == ']':
						l += 1
		if stack:
			return 'Impossible'
		return l
	s = input()
	print(ad(s))
except:
	pass


def p1(s):
	stack = []
	n = len(s)
	dic = {')': '(', '}': '{', ']': '[', '>': '<'}
	cnt = 0
	for x in s:
		if x not in dic:
			stack.append(x)
		elif not stack:
			return 'Impossible'
		elif dic[x] != stack.pop():
			cnt += 1
		else:
			pass
	if not stack:
		return cnt
	else:
		return 'Impossible'
s = list(input())
print(p1(s))


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


opening = set(['(', '<', '[', '{'])
closing = set([')', '>', ']', '}'])

def im_noob(s):
	o = c = boom = 0
	for i in s:
		if i in opening:
			o += 1
			boom += 1
		else:
			c += 1
			boom -= 1
		if boom < 0:
			return 'Impossible'
	if o != c:
		return 'Impossible'
	if boom != 0:
		return 'Impossible'
	ans = 0
	stack = []
	for i in s:
		if i in opening:
			if i == '[':
				stack.append(']')
			elif i == '<':
				stack.append('>')
			elif i == '{':
				stack.append('}')
			elif i == '(':
				stack.append(')')
		elif i != stack[len(stack) - 1]:
			ans += 1
			stack.pop()
		else:
			stack.pop()
	return ans
s = input()
print(im_noob(s))


s = input()
cnt = 0
closing = ['>', '}', ']', ')']
opening = ['<', '{', '[', '(']
oc = 0
cc = 0
for i in s:
	if i in opening:
		oc += 1
	else:
		cc += 1
if s[0] in closing or len(s) & 1 or oc != cc:
	print('Impossible')
else:
	stack = []
	for i in s:
		if i in closing:
			if len(stack) == 0:
				print('Impossible')
				exit(0)
			if opening[closing.index(i)] == stack[-1]:
				stack.pop()
			else:
				cnt += 1
				stack.pop()
		elif i in opening:
			stack.append(i)
	print(cnt)


bracket = input()
stack = []
bracketType = {'[': (0, ']'), '(': (0, ')'), '<': (0, '>'), '{': (0, '}'), ']': (1,), ')': (1,), '>': (1,), '}': (1,)}
res = 0
for b in bracket:
	if bracketType.get(b) == None:
		break
	elif bracketType.get(b)[0] == 0:
		stack.append(b)
	elif bracketType.get(b)[0] == 1:
		if len(stack) == 0:
			res = 'Impossible'
			break
		elif b != bracketType[stack.pop()][1]:
			res += 1
if len(stack):
	print('Impossible')
else:
	print(res)


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')


import sys
s = input()
stack = []
ans = 0
brackets = {'>': '<', '}': '{', ']': '[', ')': '('}
for c in s:
	if c in '>}])':
		if not stack:
			print('Impossible')
			exit()
		if stack[-1] != brackets[c]:
			ans += 1
		stack.pop()
	else:
		stack.append(c)
if len(stack):
	print('Impossible')
else:
	print(ans)


def opposto(s):
	if s == ')':
		return '('
	elif s == ']':
		return '['
	elif s == '}':
		return '{'
	else:
		return '<'

def f(s):
	n = [0] * 10 ** 6
	checker = 0
	cont = 0
	pos = 0
	for c in s:
		if c in ['(', '[', '{', '<']:
			n[checker] = c
			checker += 1
			pos += 1
		elif checker == 0:
			return 'Impossible'
		elif n[checker - 1] == opposto(c):
			checker -= 1
		else:
			checker -= 1
			cont += 1
	if pos == len(s) - pos:
		return cont
	else:
		return 'Impossible'
s = str(input())
print(f(s))


di = {')': '(', '>': '<', ']': '[', '}': '{'}
stack = []
s = list(input())
flag = 0
c = 0
for i in s:
	if i in ['(', '<', '[', '{']:
		stack.append(i)
	elif len(stack) != 0:
		x = stack.pop()
		if x != di[i]:
			c += 1
	else:
		stack = [0]
		break
if len(stack) == 0:
	print(c)
else:
	print('Impossible')


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)


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])


from sys import argv, exit

def rstr():
	return input()

def rint():
	return int(input())

def rints():
	return [int(i) for i in input().split(' ')]

def prnt(*args):
	if '-v' in argv:
		print(*args)
op = ['[', '{', '(', '<']
cl = [']', '}', ')', '>']
oppo = {']': '[', '}': '{', '>': '<', ')': '('}
oppo.update(zip(op, cl))
s = rstr()
opd = {c: 0 for c in op}
shtack = []
opi = 0
count = 0
for c in s:
	if c in cl:
		prnt(shtack)
		if not shtack:
			print('Impossible')
			exit(0)
		elif shtack[-1] == oppo[c]:
			shtack.pop()
		else:
			count += 1
			prnt(c, count)
			shtack.pop()
	else:
		shtack.append(c)
if shtack:
	print('Impossible')
	exit(0)
print(count)


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()
stack = []
count = 0
length = len(S)
flag = 0
if length % 2:
	flag = 1
else:
	for i in range(length):
		if S[i] == '<' or S[i] == '(' or S[i] == '{' or (S[i] == '['):
			stack.append(S[i])
		elif stack != []:
			if S[i] == '>' and stack.pop() != '<':
				count += 1
			elif S[i] == ')' and stack.pop() != '(':
				count += 1
			elif S[i] == '}' and stack.pop() != '{':
				count += 1
			elif S[i] == ']' and stack.pop() != '[':
				count += 1
			if flag:
				break
		else:
			flag = 1
			break
if flag != 0 or len(stack) != 0:
	print('Impossible')
else:
	print(count)


n = input()
res = []
cnt = 0
for i in n:
	if i in '(<[{':
		res.append(i)
	else:
		if not res:
			print('Impossible')
			break
		l = res.pop()
		if l + i not in ('[]', '()', '<>', '{}'):
			cnt += 1
else:
	if res:
		print('Impossible')
	else:
		print(cnt)


import sys

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def rinput():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
n = input()
a = ['[', '<', '{', '(', ']', '>', '}', ')']
k = 0
s = []
for i in range(len(n)):
	if a.index(n[i]) > 3:
		if not s:
			s = 1
			break
		if s.pop() != a.index(n[i]) - 4:
			k += 1
	else:
		s += [a.index(n[i])]
if s:
	print('Impossible')
else:
	print(k)


s = str(input())
a = []
v = 0
k = 0
map = {')': '(', ']': '[', '}': '{', '>': '<'}
for _ in range(len(s)):
	if s[_] == '<' or s[_] == '(' or s[_] == '{' or (s[_] == '['):
		a.append(s[_])
	elif len(a) == 0:
		print('Impossible')
		k = 1
		break
	elif a[-1] == map[s[_]]:
		a.pop(-1)
	else:
		a.pop(-1)
		v += 1
if k == 0 and len(a) == 0:
	print(v)
elif k == 0:
	print('Impossible')


def main():
	s = input()
	open_paren = '<([{'
	close = {']': '[', '>': '<', ')': '(', '}': '{'}
	stack = []
	ans = 0
	imp = False
	for c in s:
		if c in open_paren:
			stack.append(c)
		else:
			if not stack:
				imp = True
				break
			if close[c] != stack[-1]:
				ans += 1
			stack.pop()
	imp = imp or len(stack) != 0
	print('Impossible' if imp else ans)
main()


d = {'(': ')', '[': ']', '{': '}', '<': '>'}
(st, k) = ([], 0)
for i in input():
	if i in d:
		st.append(i)
	elif st:
		if d[st[-1]] != i:
			k += 1
		st.pop()
	else:
		print('Impossible')
		exit()
if st:
	print('Impossible')
	exit()
print(k)


import math
import sys, string
input = sys.stdin.readline
import random
from collections import deque, defaultdict
import bisect
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
d = defaultdict(int)
s = input().strip()
x = []
ans = 0
for i in range(len(s)):
	if s[i] == '[' or s[i] == '(' or s[i] == '{' or (s[i] == '<'):
		x.append(s[i])
	else:
		if len(x) == 0:
			print('Impossible')
			exit()
		if s[i] == ']':
			if x[-1] == '[':
				if len(x) == 0:
					print('Impossible')
					exit()
				x.pop()
			else:
				x.pop()
				ans += 1
		elif s[i] == '}':
			if x[-1] == '{':
				if len(x) == 0:
					print('Impossible')
					exit()
				x.pop()
			else:
				ans += 1
				x.pop()
		elif s[i] == '>':
			if x[-1] == '<':
				if len(x) == 0:
					print('Impossible')
					exit()
				x.pop()
			else:
				ans += 1
				x.pop()
		elif x[-1] == '(':
			if len(x) == 0:
				print('Impossible')
				exit()
			x.pop()
		else:
			x.pop()
			ans += 1
if len(x) != 0:
	print('Impossible')
else:
	print(ans)


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()


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()

def fun():
	t = ['[', '<', '{', '(']
	t1 = [']', '>', '}', ')']
	res = []
	summ = 0
	for i in range(len(s)):
		try:
			if s[i] in t:
				res.append(s[i])
			elif s[i] in t1:
				d = len(res) - 1
				if t.index(res[d]) != t1.index(s[i]):
					summ += 1
				res.pop(d)
		except:
			print('Impossible')
			break
	else:
		if len(res) == 0:
			print(summ)
		else:
			print('Impossible')
fun()


SYMBOLS = {'}': '{', ']': '[', ')': '(', '>': '<'}
(SYMBOLS_L, SYMBOLS_R) = (SYMBOLS.values(), SYMBOLS.keys())
arr = []
num = 0
left = 0
right = 0
flag = True
s = input()
for c in s:
	if c in SYMBOLS_L:
		arr.append(c)
		left += 1
	elif c in SYMBOLS_R:
		right += 1
		if len(arr) == 0:
			flag = False
			break
		elif arr[-1] == SYMBOLS[c]:
			arr.pop()
		else:
			num += 1
			arr.pop()
if right != left:
	flag = False
if flag:
	print(num)
else:
	print('Impossible')


s = list(input())

def isopen(c):
	return c == '<' or c == '{' or c == '[' or (c == '(')

def match(a, b):
	return a == '<' and b == '>' or (a == '{' and b == '}') or (a == '[' and b == ']') or (a == '(' and b == ')')

def isRbs():
	br = []
	if isopen(s[0]) == False:
		print('Impossible')
		return False
	count = 0
	for c in s:
		open = isopen(c)
		if open == True:
			br.append(c)
		elif len(br) > 0 and open == False:
			b = br.pop()
			if match(b, c) == False:
				count += 1
	if len(br) == 0:
		print(count)
	else:
		print('Impossible')
if len(s) % 2 != 0:
	print('Impossible')
else:
	isRbs()


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())
l = []
a = '>}])'
b = '<{[('
r = 0
for i in minp():
	if i in a:
		if len(l) == 0:
			print('Impossible')
			exit(0)
		elif b[a.find(i)] != l.pop():
			r += 1
	else:
		l.append(i)
if len(l) == 0:
	print(r)
else:
	print('Impossible')


import sys
stack = []
count = 0
lr = {')': '(', '>': '<', ']': '[', '}': '{'}
for char in input():
	if char in lr.values():
		stack.append(char)
	elif char in lr.keys():
		if stack == []:
			print('Impossible')
			sys.exit()
		if lr[char] != stack.pop():
			count += 1
if len(stack) != 0:
	print('Impossible')
	sys.exit()
print(count)


def solve(s: str):
	stack = []
	answer = 0
	for c in s:
		if c in '([{<':
			stack.append(c)
		else:
			if not stack:
				print('Impossible')
				return
			b = stack[-1]
			if b == '(' and c != ')' or (b == '[' and c != ']') or (b == '{' and c != '}') or (b == '<' and c != '>'):
				answer += 1
			stack.pop()
	print('Impossible' if stack else answer)
s = input()
solve(s)


st = input()
c = 0
b = r = s = l = 0
for i in st:
	if i in ['[', '<', '{', '(']:
		c += 1
	else:
		c -= 1
		if c < 0:
			break
ans = 0
if c != 0:
	print('Impossible')
else:
	stack = []
	for i in st:
		if i in ['[', '<', '{', '(']:
			stack.append(i)
		elif stack[-1] == '(' and i == ')':
			stack.pop()
			continue
		elif stack[-1] == '<' and i == '>':
			stack.pop()
			continue
		elif stack[-1] == '{' and i == '}':
			stack.pop()
			continue
		elif stack[-1] == '[' and i == ']':
			stack.pop()
			continue
		else:
			stack.pop()
			ans += 1
	print(ans)


from functools import cmp_to_key
from collections import deque, Counter
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def si():
	return str(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def lsi():
	return list(map(str, inp().split()))

def print_list(lista, space=' '):
	print(space.join(map(str, lista)))

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)
MOD = 10 ** 9 + 7
maxN = 5
FACT = [0] * maxN
INV_FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def inverseFactorials():
	n = len(INV_FACT)
	INV_FACT[n - 1] = inverse(FACT[n - 1])
	for i in range(n - 2, -1, -1):
		INV_FACT[i] = multiply(INV_FACT[i + 1], i + 1)

def coeffBinom(n, k):
	if n < k:
		return 0
	return multiply(FACT[n], multiply(INV_FACT[k], INV_FACT[n - k]))

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path
s = si()
n = len(s)
stack = list()
op = ['<', '(', '[', '{']
cl = ['>', ')', ']', '}']
match = {'<': '>', '(': ')', '[': ']', '{': '}'}
flag = True
count = 0
for i in range(n):
	if s[i] in op:
		stack.append(s[i])
	elif len(stack) == 0:
		flag = False
	else:
		last = stack.pop()
		if s[i] != match[last]:
			count += 1
if stack:
	flag = False
if flag == False:
	print('Impossible')
else:
	print(count)


from collections import deque
s = list(input())
d = deque()
r = 0
for i in range(len(s)):
	if s[i] in {'<', '{', '[', '('}:
		d.appendleft(s[i])
	else:
		if len(d) == 0:
			print('Impossible')
			exit()
		v = d.popleft()
		if v == '[' and s[i] != ']' or (v == '{' and s[i] != '}') or (v == '<' and s[i] != '>') or (v == '(' and s[i] != ')'):
			r += 1
if len(d) == 0:
	print(r)
else:
	print('Impossible')


def getResult(s):
	if not s:
		return 'Impossible'
	dic = {'(': ')', '[': ']', '{': '}', '<': '>'}
	res = 0
	stack = []
	for x in list(s):
		if x in dic:
			stack.append(x)
		elif len(stack) == 0:
			return 'Impossible'
		else:
			cur = stack.pop()
			if dic[cur] != x:
				res += 1
	return res if len(stack) == 0 else 'Impossible'
s = input()
print(str(getResult(s)))


import sys
s = input()
q = []
c = 0
for x in s:
	if x == '[' or x == '{' or x == '(' or (x == '<'):
		q.append(x)
	elif len(q) > 0 and (ord(x) == ord(q[-1]) + 2 or (x == ')' and q[-1] == '(')):
		q.pop(-1)
	elif len(q) > 0:
		q.pop(-1)
		c += 1
	else:
		print('Impossible')
		sys.exit(0)
print(c if len(q) == 0 else 'Impossible')


import sys
INF = 10 ** 18 + 3

def main():
	opening = '<{[('
	closing = '>}])'
	s = input()
	stack = []
	res = 0
	for (i, sym) in enumerate(s):
		if sym in opening:
			kind = opening.find(sym)
			stack.append(kind)
		else:
			kind = closing.find(sym)
			if not stack:
				res = -1
				break
			if stack[-1] != kind:
				res += 1
			del stack[-1]
	print('Impossible' if res == -1 or stack else res)

def set_input(file):
	global input
	input = lambda : file.readline().rstrip()

def set_output(file):
	global print
	lprint = print

	def print(*args, **kwargs):
		kwargs['file'] = kwargs.get('file', file)
		return lprint(*args, **kwargs)
is_mine = 'MINE' in sys.argv
set_input(open('input.txt', 'r') if is_mine else sys.stdin)
set_output(sys.stdout if is_mine else sys.stdout)
main()


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


import sys
s = input()
stack = []
piar = {'{': '}', '(': ')', '<': '>', '[': ']'}
ans = 0
for ch in s:
	if ch in piar.keys():
		stack.append(ch)
	else:
		if len(stack) == 0:
			print('Impossible')
			sys.exit()
		if piar[stack.pop()] != ch:
			ans += 1
if len(stack) != 0:
	print('Impossible')
	sys.exit()
print(ans)


IMPOSSIBLE = 'Impossible'
scopes = {'{': '}', '(': ')', '[': ']', '<': '>'}
stack = []
swap = 0
for i in input():
	if i in scopes:
		stack.append(i)
	elif stack:
		if scopes[stack[-1]] != i:
			swap += 1
		stack.pop()
	else:
		print(IMPOSSIBLE)
		break
else:
	print(swap if not stack else IMPOSSIBLE)


st = input()
cnt = 0
a = []
di = {')': '(', '>': '<', ']': '[', '}': '{'}
for i in st:
	if i in ['(', '<', '[', '{']:
		a.append(i)
	elif a != []:
		x = a.pop()
		if x != di[i]:
			cnt += 1
	else:
		a = [-1]
		break
if a == []:
	print(cnt)
else:
	print('Impossible')


s = input()
sc = s
sc = sc.replace('<', '(').replace('[', '(').replace('{', '(')
sc = sc.replace('>', ')').replace(']', ')').replace('}', ')')

def chec(ss):
	c = 0
	for i in ss:
		if i == '(':
			c += 1
		if i == ')':
			c -= 1
		if c < 0:
			return False
	return c == 0
if chec(sc):
	l = []
	ans = 0
	for i in s:
		if i in '({[<':
			l.append(i)
		else:
			if i == ')':
				if l[-1] in '{[<':
					ans += 1
			if i == '}':
				if l[-1] in '([<':
					ans += 1
			if i == ']':
				if l[-1] in '{(<':
					ans += 1
			if i == '>':
				if l[-1] in '{[(':
					ans += 1
			l.pop()
	print(ans)
else:
	print('Impossible')


a = input()
s = []
replacements = 0
flag = 0
for i in range(len(a)):
	if a[i] in '({[<':
		s.append(a[i])
	else:
		if len(s) == 0:
			flag = 1
			break
		top = s.pop()
		if a[i] == '>' and top != '<':
			replacements += 1
		if a[i] == ')' and top != '(':
			replacements += 1
		if a[i] == ']' and top != '[':
			replacements += 1
		if a[i] == '}' and top != '{':
			replacements += 1
if len(s) > 0 or flag == 1:
	print('Impossible')
else:
	print(replacements)


s = input()
arr = []
l = len(s)
flag = False
cnt = 0
open = ['{', '[', '<', '(']
close = ['}', ']', '>', ')']
dic = {'{': '}', '[': ']', '<': '>', '(': ')'}
for i in range(l):
	if s[i] in open:
		arr.append(s[i])
	else:
		if arr == []:
			flag = True
			break
		if dic[arr[-1]] != s[i]:
			cnt += 1
		del arr[-1]
if flag or arr != []:
	print('Impossible')
else:
	print(cnt)


import re
import sys
exit = sys.exit
from bisect import bisect_left as bsl, bisect_right as bsr
from collections import Counter, defaultdict as ddict, deque
from functools import lru_cache
cache = lru_cache(None)
from heapq import *
from itertools import *
from math import inf
from pprint import pprint as pp
enum = enumerate
ri = lambda : int(rln())
ris = lambda : list(map(int, rfs()))
rln = sys.stdin.readline
rl = lambda : rln().rstrip('\n')
rfs = lambda : rln().split()
cat = ''.join
catn = '\n'.join
mod = 1000000007
d4 = [(0, -1), (1, 0), (0, 1), (-1, 0)]
d8 = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]

def solve(s):
	mp = dict('<> {} [] ()'.split())
	ans = 0
	stk = []
	for c in s:
		if c in mp:
			stk.append(mp[c])
		else:
			if not stk:
				return -1
			if stk[-1] != c:
				ans += 1
			stk.pop()
	if stk:
		return -1
	return ans
s = rl()
ans = solve(s)
if ans == -1:
	print('Impossible')
else:
	print(ans)


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')


def check_open(char):
	if char in '<{[(':
		return 1
	return 0

def find_type(char):
	if char in '()':
		return 0
	elif char in '[]':
		return 1
	elif char in '{}':
		return 2
	else:
		return 3
s = input()
stack = []
impossible = 0
count = 0
for char in s:
	if check_open(char):
		stack.append(char)
	else:
		if len(stack) == 0:
			impossible = True
			break
		if check_open(stack[-1]):
			if find_type(char) != find_type(stack[-1]):
				count += 1
			stack.pop()
		else:
			impossible = True
			break
if len(stack) != 0:
	impossible = True
if impossible:
	print('Impossible')
else:
	print(count)


s = input()
n = len(s)
op = {'<': 0, '{': 1, '[': 2, '(': 3}
cl = {'>': 0, '}': 1, ']': 2, ')': 3}
stack = []
flag = True
swaps = 0
for i in range(n):
	if s[i] in op:
		stack.append(s[i])
	elif stack:
		if op[stack.pop()] != cl[s[i]]:
			swaps += 1
	else:
		flag = False
		break
if len(stack) != 0:
	flag = False
print(swaps) if flag else print('Impossible')


s = input()
stack = []
res = 0
for c in s:
	if c in '(<[{':
		stack.append(c)
	else:
		if not stack:
			print('Impossible')
			break
		last = stack.pop()
		if last + c not in ('[]', '()', '<>', '{}'):
			res += 1
else:
	if stack:
		print('Impossible')
	else:
		print(res)


s = list(input())
d = {'(': ')', '[': ']', '<': '>', '{': '}'}
stack = []
cnt = 0
for elem in s:
	if elem in d.keys():
		stack.append(elem)
	else:
		if not stack:
			print('Impossible')
			exit()
		lb = stack.pop()
		if elem != d[lb]:
			cnt += 1
if not stack:
	print(cnt)
else:
	print('Impossible')


def stacks(brackets):
	opening = ['[', '{', '(', '<']
	closing = ['}', '{', '(', '<']
	stack = []
	changes = 0
	for b in brackets:
		if b in opening:
			stack.append(b)
		else:
			if len(stack) == 0:
				return -1
			last_brackets = stack.pop()
			if b == ']':
				if last_brackets != '[':
					changes += 1
			elif b == '}':
				if last_brackets != '{':
					changes += 1
			elif b == ')':
				if last_brackets != '(':
					changes += 1
			elif b == '>':
				if last_brackets != '<':
					changes += 1
			else:
				return -1
	if stack:
		return -1
	else:
		return changes
_in = input()
brackets = []
for b in _in:
	brackets.append(str(b))
v = stacks(brackets)
if v == -1:
	print('Impossible')
else:
	print(v)


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 sys import stdin, stdout

class SOLVE:

	def solve(self):
		R = stdin.readline
		W = stdout.write
		s = R()[:-1]
		(brackets, cnt, check) = ([], 0, 0)
		for i in range(len(s)):
			if s[i] in ['(', '<', '{', '[']:
				brackets.append(s[i])
				check += 1
			else:
				if len(brackets) == 0:
					W('Impossible\n')
					return 0
				if s[i] == ')':
					if brackets[-1] != '(':
						cnt += 1
				elif s[i] == '>':
					if brackets[-1] != '<':
						cnt += 1
				elif s[i] == '}':
					if brackets[-1] != '{':
						cnt += 1
				elif s[i] == ']':
					if brackets[-1] != '[':
						cnt += 1
				check -= 1
				brackets.pop()
			if check < 0:
				W('Impossible\n')
				return 0
		if check:
			W('Impossible\n')
			return 0
		W('%d\n' % cnt)
		return 0

def main():
	s = SOLVE()
	s.solve()
main()


import sys

def rbs(mystr):
	stack = []
	kuohao = {'<': '>', '{': '}', '[': ']', '(': ')'}
	count = 0
	for x in mystr:
		if x in kuohao:
			stack.append(x)
		elif len(stack) == 0:
			return 'Impossible'
		elif kuohao[stack.pop()] != x:
			count += 1
		else:
			pass
	if len(stack) == 0:
		return count
	else:
		return 'Impossible'
mystr = input()
print(rbs(mystr))


s = input()
d = ['<', '{', '[', '(']
d2 = ['>', '}', ']', ')']
a = []
k = 0
sum1 = 0
sum2 = 0
for i in s:
	if i in d:
		sum1 += 1
		a.append(d.index(i))
	else:
		sum2 += 1
		if len(a) == 0:
			k = 'Impossible'
			break
		elif a[-1] == d2.index(i):
			a.pop()
		elif a[-1] != d2.index(i):
			a.pop()
			k += 1
if sum1 != sum2:
	print('Impossible')
else:
	print(k)


s = input()
open_b = ['<', '{', '[', '(']
close_b = ['>', '}', ']', ')']
stack = []
d = {open_b[i]: close_b[i] for i in range(4)}
stack = []
ans = 0
for i in range(len(s)):
	stack.append(s[i])
	if len(stack) >= 2 and stack[-1] in close_b and (stack[-2] in open_b):
		if d[stack[-2]] != stack[-1]:
			ans = ans + 1
		stack.pop()
		stack.pop()
if len(stack):
	print('Impossible')
	exit()
print(ans)


s = input()

def check_str(s):
	brackets = {'<': '>', '{': '}', '[': ']', '(': ')'}
	res = 0
	stack = []
	for c in s:
		if c in brackets:
			stack.append(c)
		else:
			if stack:
				top = stack.pop()
				if top in brackets:
					if brackets[top] != c:
						res += 1
					continue
			return 'Impossible'
	if stack:
		return 'Impossible'
	return res
print(check_str(s))


s = input().strip()
braces = {'<': '>', '>': '<', '{': '}', '}': '{', '[': ']', ']': '[', '(': ')', ')': '('}
stack = []
answer = 0
for char in s:
	if char in '(<{[':
		stack.append(char)
	elif char in ')>}]':
		if not stack:
			print('Impossible')
			exit()
		lastBrace = stack.pop()
		if char != braces[lastBrace]:
			answer += 1
if not stack:
	print(answer)
else:
	print('Impossible')


import sys
from math import *

def input():
	return sys.stdin.readline().strip()
q = []
s = '>}])'
a = '<{[('
w = 0
for i in input():
	if i in s:
		if len(q) == 0:
			print('Impossible')
			exit(0)
		elif a[s.find(i)] != q.pop():
			w += 1
	else:
		q.append(i)
if len(q) == 0:
	print(w)
else:
	print('Impossible')


stk = []
ops = 0
f = 1
l = list(input())
for i in l:
	if i in '{<([':
		stk.append(i)
	else:
		if not stk:
			f = 0
			break
		c = stk[-1]
		if c + i in ['[]', '{}', '<>', '()']:
			stk.pop()
		else:
			ops += 1
			stk.pop()
if f == 1 and (not stk):
	print(ops)
else:
	print('Impossible')


s = input()
n = len(s)
br = {'<': '>', '{': '}', '[': ']', '(': ')'}
stack = []
flag = True
swaps = 0
for i in range(n):
	if s[i] in br:
		stack.append(s[i])
	elif stack:
		if br[stack.pop()] != s[i]:
			swaps += 1
	else:
		flag = False
		break
if len(stack) != 0:
	flag = False
print(swaps) if flag else print('Impossible')


def process(S):
	flip = {'(': ')', '[': ']', '{': '}', '<': '>'}
	other = {flip[x]: x for x in flip}
	for x in other:
		flip[x] = other[x]
	d = []
	answer = 0
	for x in S:
		if x in '([{<':
			d.append(x)
		else:
			if len(d) == 0:
				return [False, 0]
			x2 = flip[x]
			if x2 != d[-1]:
				answer += 1
			d.pop()
	if len(d) == 0:
		return [True, answer]
	else:
		return [False, 0]
S = input()
(a1, a2) = process(S)
if a1:
	print(a2)
else:
	print('Impossible')


s = input()
stack = []
open = ['<', '{', '(', '[']
close = ['>', '}', ')', ']']
ans = 0
for i in range(len(s)):
	if s[i] in open:
		stack.append(s[i])
	else:
		if len(stack) == 0:
			print('Impossible')
			exit()
		head = stack.pop()
		k = close.index(s[i])
		if head != open[k]:
			ans += 1
if len(stack) > 0:
	print('Impossible')
	exit()
print(ans)


import io, os
input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline
stack = []
c = 0
opts = {'(': 0, ')': 1, '<': 2, '>': 3, '[': 4, ']': 5, '{': 6, '}': 7}
for s in input():
	if s not in opts:
		break
	v = opts[s]
	if v & 1:
		if not stack:
			print('Impossible')
			exit()
		x = stack.pop()
		if x != v:
			c += 1
	else:
		stack.append(v + 1)
if stack:
	print('Impossible')
	exit()
print(c)


s = input()
flag = 0
stack = []
op = ['<', '{', '[', '(']
ans = 0
for i in range(len(s)):
	if s[i] in op:
		flag += 1
	else:
		flag -= 1
	if flag < 0:
		print('Impossible')
		break
	if s[i] in op:
		stack.append(s[i])
	elif s[i] == '>' and stack.pop() != '<':
		ans += 1
	elif s[i] == '}' and stack.pop() != '{':
		ans += 1
	elif s[i] == ']' and stack.pop() != '[':
		ans += 1
	elif s[i] == ')' and stack.pop() != '(':
		ans += 1
else:
	if flag != 0:
		print('Impossible')
	else:
		print(ans)