자동차

교통 체증은 모든 운전자의 악몽입니다. 차들이 거의, 혹은 전혀 움직이지 못하는 꽉 막힌 도로에 갇히는 것을 좋아하는 사람은 없습니다. 이 체증에서 빠져나갈 길을 찾아 봅시다.

작지만 까다로운 교통 체증을 $6 \times 6$ 격자 위에서 모형화합니다. 자동차와 트럭이 아래 그림처럼 격자의 정수 위치에 놓여 있습니다. 모든 차량의 폭은 $1$칸입니다. 자동차(car)는 길이가 $2$칸이고, 트럭(truck)은 길이가 $3$칸입니다. 각 차량은 가로 방향(동–서) 또는 세로 방향(남–북) 중 하나로 놓여 있습니다.

차량끼리는 서로를 통과할 수 없고, 방향을 바꿀 수 없으며, 격자 밖으로 옆으로 벗어날 수도 없습니다. 차량은 자신의 방향을 따라서만 미끄러질 수 있으며(가로 차량은 동쪽 또는 서쪽으로, 세로 차량은 북쪽 또는 남쪽으로), 빈 공간과 격자 경계가 허락하는 만큼만 움직일 수 있습니다. 한 번의 이동(move)에서는 정확히 한 대의 차량만 미끄러지며, 지나가는 칸이 모두 비어 있다면 한 방향으로 원하는 만큼 여러 칸을 한꺼번에 미끄러질 수 있습니다.

당신의 차는 입력에서 가장 먼저 주어지는 가로 방향 자동차입니다. 목표는 차량들을 이리저리 움직여 당신의 차가 격자의 가장 오른쪽(동쪽) 경계 밖으로 빠져나가게 하는 것입니다. 당신의 차를 동쪽 경계 밖으로 몰아내는 것 자체도 한 번의 이동으로 셉니다. 필요한 이동 횟수의 최솟값을 구하세요.

첫째 줄에 차량의 수를 나타내는 정수 $n$ ($1 \le n \le 10$)이 주어집니다.

이어지는 $n$개의 줄에는 각각 한 대의 차량이 다음 형식으로 주어집니다.

o r c k

• $o$는 차량이 가로 방향이면 h, 세로 방향이면 v입니다.
• $r$과 $c$ ($1 \le r, c \le 6$)는 차량이 차지하는 칸 중 가장 왼쪽 위(북서쪽) 칸의 행과 열입니다. 행은 위에서 아래로 $1$부터 $6$까지, 열은 왼쪽(서쪽)에서 오른쪽(동쪽)으로 $1$부터 $6$까지 번호가 매겨집니다. 가로 차량은 $(r, c)$에서 동쪽으로, 세로 차량은 남쪽으로 뻗어 나갑니다.
• $k$는 자동차이면 c(길이 $2$), 트럭이면 t(길이 $3$)입니다.

가장 먼저 주어지는 차량이 당신의 차이며, 가로 방향 자동차라고 가정해도 됩니다.

당신의 차를 격자의 오른쪽 경계 밖으로 몰아내는 데 필요한 최소 이동 횟수를 출력합니다. 그것이 불가능하다면 대신 The car is trapped.를 출력합니다.