크리스마스트리 방울 옮기기

곧 크리스마스트리를 장식할 때가 온다. 심사위원들은 트리에 방울을 어떻게 매달아야 가장 좋은지를 벌써부터 따지고 있다. 한 가지에는 모두 동의한다. 방울은 트리의 가지마다 고르게 퍼져 있어야 한다.

이 문제에서 다루는 트리는 이진 크리스마스트리다. 트리는 줄기 하나에서 시작해 두 개의 부분 트리로 갈라진다. 각 부분 트리는 다시 두 개의 더 작은 부분 트리로 갈라질 수 있고, 이런 갈라짐이 계속 이어진다. 더 갈라지지 않는 부분 트리를 잔가지라고 한다. 잔가지 하나에는 방울을 최대 한 개까지 매달 수 있다.

장식을 끝낸 트리의 방울 분포가 고르다는 것은 다음 조건이 성립한다는 뜻이다.

(부분) 트리가 두 개의 더 작은 부분 트리 $t_1$과 $t_2$로 갈라지는 모든 지점에서, 왼쪽 부분 트리에 있는 방울 수 $N(t_1)$과 오른쪽 부분 트리에 있는 방울 수 $N(t_2)$가 같거나 정확히 1만큼 차이 난다. 즉 $|N(t_1) - N(t_2)| \le 1$이다.

심사위원들은 신이 나서 방울을 잔가지 아무 곳에나 매달았다. 더 매달 방울이 없어지자 뒤로 물러나 결과를 살펴봤다. 대부분은 방울 분포가 고르지 않았다. 그래서 방울 몇 개를 다른 잔가지로 옮겨 이를 바로잡기로 했다.

트리의 구조와 방울의 처음 위치가 주어지면, 위 조건을 만족하는 고른 분포를 만들기까지 옮겨야 하는 방울의 최소 개수를 구하라.

방울을 새로 추가하거나 트리에서 아예 떼어내는 것은 허용되지 않는다. 트리를 바꾸는 방법은 방울을 다른 잔가지로 옮기는 것뿐이다.

입력은 여러 줄로 이루어진다. 각 줄에 장식을 끝낸 트리 하나의 설명이 주어지고, 입력의 끝까지 모든 줄을 처리한다.

트리 설명은 부분 트리 설명을 재귀적으로 이어 붙인 형태다. (부분) 트리는 다음 세 가지 형태 중 하나의 문자열로 나타낸다.

• 문자열 ()는 방울이 없는 잔가지다.
• 문자열 (B)는 방울이 하나 매달린 잔가지다.
• 문자열 (t1t2)는 두 개의 더 작은 부분 트리 t1과 t2로 갈라지는 (부분) 트리다. t1과 t2는 각각 위 세 형태 중 하나이며, 두 설명 사이에 공백은 없다.

트리 하나에 들어 있는 잔가지는 2개 이상 1000개 이하다.

트리 하나마다 한 줄을 출력한다.

방울을 고르게 나눌 수 있으면 조건을 만족하기까지 옮겨야 하는 방울의 최소 개수를 출력한다.

고르게 나눌 수 없으면 impossible을 출력한다.