Description

给定一棵叶子带权值二叉树，保证每个非叶子结点都有两个儿子，权值只能是 $0$ 或 $1$。

你可以进行以下操作若干次：选中两个叶子，交换它们的权值。

定义一颗子树的权值为子树内所有叶子的权值之和。

你希望通过以上操作使得任意非叶子结点的左子树权值和右子树权值相差不超过 $1$。

求达成以上目标需要的最少操作次数。

Input Format

一行一个字符串 $T$，以中序遍历的方式描述了这棵树，B 表示彩球。

形式化的，$T$ 的 CFG（上下文无关文法）定义为：

<T> := (<T><T>) | (B) | ()

Output Format

输出一个数字，表示最少移动多少个彩球就能使它平衡，或输出 impossible，表示如何移动多少个都无法平衡。

输出一个数字，表示至少需要多少次操作，或输出 impossible，表示不可能达成目标。

((B)())

0

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

impossible

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

1

Hint

【样例解释】

【数据规模】

设 $N$ 为字符串 $T$ 的长度。

对于 $15\%$ 的数据，$N \le 25$。

对于 $50\%$ 的数据，$N \le 250$。

对于 $100\%$ 的数据，$2 \le N \le 5000$。