Khôi phục cấu trúc

Cho một chuỗi ký tự $s$ chỉ bao gồm các ký tự mở và đóng thuộc bốn loại cặp ký hiệu: <>, \\, [], (). Trong đó, các ký hiệu mở là <, \, [, (; các ký hiệu đóng là >, \, ], ).

Tại mỗi bước, bạn được phép thay thế một ký hiệu bất kỳ bằng một ký hiệu khác có cùng vai trò: ký hiệu mở chỉ có thể đổi thành một ký hiệu mở khác, ký hiệu đóng chỉ có thể đổi thành một ký hiệu đóng khác. Ví dụ, bạn có thể đổi ký hiệu < thành \, nhưng không thể đổi thành ) hoặc >.

Một chuỗi được gọi là chuỗi lồng hợp lệ nếu thỏa mãn quy tắc sau:

• Chuỗi rỗng là một chuỗi lồng hợp lệ.
• Nếu $s_1$ và $s_2$ là các chuỗi lồng hợp lệ, thì các chuỗi <$s_1$>$s_2$, \$s_1$\$s_2$, [$s_1$]$s_2$, ($s_1$)$s_2$ cũng là các chuỗi lồng hợp lệ.

Ví dụ, chuỗi [\()\<>] là một chuỗi lồng hợp lệ, trong khi các chuỗi (]\\ và \() không phải là chuỗi lồng hợp lệ.

Yêu cầu: Hãy tìm số lượt thay thế ít nhất để biến đổi chuỗi $s$ thành một chuỗi lồng hợp lệ.

Dữ liệu vào

Dòng duy nhất chứa chuỗi ký tự $s$ ($1 ≤ |{}s|{} ≤ 10^6$) không rỗng, chỉ gồm các ký tự mở và đóng thuộc bốn loại cặp ký hiệu đã nêu.

Kết quả

Nếu không thể biến đổi $s$ thành một chuỗi lồng hợp lệ, in ra Impossible.

Ngược lại, in ra một số nguyên duy nhất là số thao tác thay thế ít nhất cần thực hiện.

Chấm điểm

Subtask 1 (30 points). $|s| ≤ 300$

Subtask 2 (70 points). 1 $≤ |{}$s| $≤ 10^6$

Ví dụ

Input

<[}>

Output

1

Ghi chú

Trong ví dụ trên, ta có thể thay thế ký hiệu \ bằng ], chuỗi trở thành <[]>. Chuỗi này là một chuỗi lồng hợp lệ và chỉ cần đúng 1 lần thay thế.