给定的字符串 s 由四种左括号和右括号组成:<>、{}、[]、()。有两种类型的括号:开括号和闭括号。您可以用另一个相同类型的支架替换任何支架。例如,您可以将 < 替换为括号 {,但不能将其替换为 ) 或 >。
下面的正则括号序列的定义是众所周知的,因此您可以熟悉它。
让我们定义一个常规括号序列(RBS)。空字符串是 RBS。令 s1 和 s2 为 RBS,则字符串 <s1>s2、{s1}s2、[s1]s2、(s1)s2 也是 RBS。
例如,字符串“[[(){}]<>]”是 RBS,但字符串“[)()”和“][()()”不是。
确定使字符串成为 RBS 的最少替换次数。
输入
唯一一行包含一个非空字符串 s,仅由四种左右括号组成。 s的长度不超过106。
输出
如果不可能从 s print 获得 RBS 则不可能。
否则打印从 s 获取 RBS 所需的最少替换次数。
示例
输入 #1
[<}){}输出 #1
2
输入 #2
{()}[]输出 #2
0
输入 #3
]]
输出 #3
Impossible