움직이는 로봇

여러 대의 로봇이 무한한 2차원 정수 격자 위에서 움직인다. 각 로봇은 현재 위치와 바라보는 방향을 가지며, 자신만의 유한한 명령 수열을 순서대로 실행하여 이동한다.

위치는 정수 쌍 (x, y)로 나타낸다. 방향은 0, 90, 180, 270도 중 하나이다.

명령은 두 종류이다.

• 회전(Turn): 매개변수 D ∈ {90, 180, 270}를 가지며, 현재 방향 C를 (C + D) mod 360으로 바꾼다.
• 전진(Step): 매개변수가 없으며, 로봇이 현재 방향으로 한 칸 이동한다. 방향 0에서의 한 걸음은 위치를 (1, 0)만큼, 방향 90은 (0, 1)만큼, 방향 180은 (-1, 0)만큼, 방향 270은 (0, -1)만큼 바꾼다.

로봇은 명령을 하나씩 차례로 실행하고, 마지막 명령까지 실행한 뒤의 위치에서 멈춘다. 로봇끼리는 서로 영향을 주지 않으며, 여러 로봇이 같은 칸에 있어도 된다.

로봇들이 출발하기 전에, 임의의 로봇의 명령 수열에서 원하는 명령들을 삭제할 수 있다(남은 명령들은 원래 순서대로 실행된다). 명령을 삭제하여 각 로봇이 멈추는 위치를 바꿀 수 있다. 목표는 삭제하는 명령의 총 개수를 최소로 하면서 모든 로봇이 하나의 공통 위치에서 멈추게 하는 것이다.

로봇은 R대(2 ≤ R ≤ 10)이다. 각 로봇은 자신의 초기 위치와 초기 방향을 가지며, 길이가 최대 50인 명령 수열을 가진다. 가능하다면 다음을 구하여라.

• 모든 로봇이 같은 위치에서 멈추도록 하기 위해 삭제해야 하는 명령의 최소 총 개수
• 그때의 공통 최종 위치

최소를 달성하는 위치가 여러 개라면 사전순으로 가장 작은 위치를 출력한다. 즉 x가 가장 작은 위치, 그중에서도 y가 가장 작은 위치를 출력한다.

첫 번째 줄에 로봇의 수 R (2 ≤ R ≤ 10)이 주어진다. 이어서 R개의 로봇 설명이 주어진다.

각 설명의 첫 줄에는 공백으로 구분된 네 정수 x y C n이 주어진다. 이는 각각 로봇의 초기 위치 (x, y), 초기 방향 C (C ∈ {0, 90, 180, 270}), 명령의 개수 n (1 ≤ n ≤ 50)이다. 다음 n개의 줄에는 명령이 한 줄에 하나씩 주어진다. 전진 명령은 문자 S 하나로 이루어지고, 회전 명령은 문자 T 다음에 공백 하나와 정수 D (D ∈ {90, 180, 270})가 온다.

명령을 삭제하여 모든 로봇을 하나의 공통 위치에서 멈추게 하는 것이 불가능하면 한 줄에 -1을 출력한다.

그렇지 않으면 두 줄을 출력한다. 첫 줄에는 삭제해야 하는 명령의 최소 총 개수를 출력한다. 둘째 줄에는 공백으로 구분된 두 정수, 즉 공통 최종 위치의 x, y 좌표를 출력한다. 최소를 달성하는 위치가 여러 개이면 사전순으로 가장 작은 것(x가 최소, 같으면 y가 최소)을 출력한다.