Problem Description

Little Z is a smart elementary school student. He built a tree using plastic tubes and clay. Each piece of clay is connected to a downward plastic tube, some of which are connected to two upward plastic tubes, while others are connected to colorful balls.

However, this craft soon toppled over due to imbalance. So, Little Z consulted his classmate, Little C. Having read about the principle of balance in a scale in an encyclopedia, Little C knows that if the difference in load weight between the two tubes connected upward from any piece of clay exceeds the weight of a ball, the craft will topple over. Since the balls are relatively heavy, the weight of the clay and plastic tubes can be ignored.

Since moving the balls requires time to disassemble and fix, Little C hopes to move the balls the least number of times to balance the craft. Can you help her?

Input Format

A single line describing the tree in an in-order traversal manner, where 'B' represents a ball.

Output Format

Output a number indicating the minimum number of balls that need to be moved to balance it, or output "impossible" if no matter how many balls are moved, it cannot be balanced.

Sample Input and Output

Sample Input #1

((B)())

Sample Output #1

0

Sample Input #2

((((B)(B))((B)()))(B))

Sample Output #2

impossible

Sample Input #3

(()(((B)(B))(B)))

Sample Output #3

1

Notes

[Data Scale]

For 15% of the data, the input file does not exceed 25 bytes.

For 50% of the data, the input file does not exceed 250 bytes.

For 100% of the data, the input file does not exceed 5000 bytes.

(PS: 1 byte ≈ 1 character)

[Time and Space Limits]

0.1s/128M

见题面 Input 部分

见题面 Output 部分