Jengaism

젠가(Jenga)는 $1 \times 1 \times 3$ 크기의 블록으로 탑을 쌓는 유명한 게임입니다. 처음에 이 탑은 $18$개의 층으로 이루어지며, 각 층은 나란히 놓인 블록 $3$개로 구성됩니다. 인접한 두 층의 블록은 서로 직각을 이루도록 놓이므로, 각 블록은 바로 위층과 바로 아래층의 블록 $3$개 모두와 맞닿습니다. 실제 게임의 모습은 아래 그림과 같습니다.

게임은 각 플레이어가 탑의 어딘가에서 블록 하나를 빼내어 맨 위에 다시 올려놓는 방식으로 진행됩니다. 목표는 탑을 무너뜨리지 않고 이 동작을 계속하는 것입니다. 블록은 항상 완성된 가장 높은 층보다 아래에서만 빼내며, 맨 위층은 (물론 직각 방향으로) 완성된 뒤에야 새로운 층을 시작합니다.

젠가 게임의 이동을 순서대로 입력받아, 탑(또는 그 일부)이 무너지거나 넘어지는 순간을 판정하는 프로그램을 작성하세요.

어떤 구조물은 그 무게중심을 바닥 평면에 수직으로 투영한 점이 지지점들의 볼록 껍질(convex hull) 바깥에 놓일 때 넘어집니다. 무게중심이 볼록 껍질의 경계(모서리) 위에 정확히 놓이는 경우에는 안정한 것으로 간주합니다.

첫째 줄에 이동의 수 $N$이 주어집니다. 이어지는 $N$개의 줄에는 한 줄에 하나씩 이동이 주어지며, 각 줄에는 공백 하나로 구분된 두 위치가 있습니다. 첫 번째는 빼낼 블록의 위치이고, 두 번째는 그 블록을 다시 놓을 위치입니다. 위치는 층을 나타내는 숫자와, 그 층 안에서의 자리(왼쪽에서 오른쪽, 또는 앞에서 뒤)를 나타내는 문자 A–C로 표기합니다. 예를 들어 처음 상태에서 탑의 맨 위층은 18A, 18B, 18C 블록으로 이루어져 있습니다. 아래 그림은 앞면과 오른쪽 면에서 바라본 두 시점으로 각 블록에 이름을 붙인 것입니다.

위치 $L$의 블록을 빼낸 뒤 탑이 무너지면 The tower collapses after removing L을 출력합니다.

위치 $L$에 블록을 놓은 뒤 탑이 무너지면 The tower collapses after placing L을 출력합니다.

모든 이동이 탑을 무너뜨리지 않고 성공적으로 실행되면 The tower never collapses를 출력합니다.