Educational Codeforces Round 4 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

expression parsing

math

*1400

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Replace To Make Regular Bracket Sequence

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/01/2023 21:09:50 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|