SAVE the World (Small)

본 문제와 Large 문제는 점수 계산식과 제한이 다릅니다. "제한" 문단을 참조하세요.

어느 날, 당신을 포함한 총 $n+1$명의 용사가 이세계로 소환되었습니다. 당신은 용사들을 통솔할 수 있는 "지시" 능력을 부여받았습니다. 그러나 용사들이 이세계 곳곳에 흩어져 있어서, 마왕을 토벌하기 전에 모든 용사가 한 곳에 모여야 합니다. 따라서 당신은 용사 모두가 당신이 있는 곳으로 모이도록 "지시"를 내려야 합니다.

이세계는 크기가 무한한 2차원 좌표평면으로 볼 수 있습니다. 당신은 $(0,0)$에 있고, 다른 모든 용사는 서로 다른 정수 좌표 $(x,y)$에 있습니다. $(0,0)$에 있지 않은 용사는 매 시점마다 $\max(|x'-x|,|y'-y|)=1$을 만족하는 $(x',y')$로 이동해야 합니다. 즉, 용사가 $(x,y)$에 있다면 $(x-1,y)$, $(x-1,y-1)$, $(x,y-1)$, $(x+1,y-1)$, $(x+1,y)$, $(x+1,y+1)$, $(x,y+1)$, $(x-1,y+1)$ 중 한 곳으로 이동해야 합니다.

지시는 다음과 같이 내립니다. 매 순간 $(0,0)$에 있지 않은 모든 용사는 인접한 8개의 칸 중 하나로 이동해야 합니다. 키보드의 S 키에 손가락을 올려 두었다고 생각하면 인접한 8개의 칸을 직관적으로 떠올릴 수 있습니다. 용사가 $(x,y)$에 있을 때 인접한 칸 8개에 대응하는 알파벳은 다음과 같습니다.

매 순간 알파벳을 하나씩 골라 문자열로 이어 붙이면 그 용사에 대한 "지시"가 됩니다. 예를 들어 $(1,1)$에 있는 용사에게 지시 $QXX$를 내리면, 용사는 $(0,2)$, $(0,1)$, $(0,0)$을 차례로 지나 최종적으로 $(0,0)$에 도착합니다. 또 $(-1,-1)$에 있는 용사에게 지시 $E$를 내리면, 용사는 한 번에 $(0,0)$에 도착합니다. 용사 전체에 대한 지시는 각 용사와 그 용사의 지시 사이의 일대일 대응으로 정의됩니다.

다만 용사에 대한 사실은 아직 비밀이고 용사를 소집하는 작전도 기밀이므로, 지시를 내릴 때는 다음 제약을 지켜야 합니다.

• 한 용사는 같은 좌표를 2번 이상 지날 수 없습니다. 즉, 어느 순간 용사가 좌표 $u$에서 좌표 $v$로 이동했다면, 그 용사는 좌표 $u$를 다시 방문할 수 없습니다.
• 어느 순간에 2명 이상의 용사가 $(0,0)$을 제외한 어떤 좌표에 동시에 위치할 수 없습니다. 즉, 어느 순간 두 용사 A와 B가 좌표 $v$에 인접한 서로 다른 좌표에 있었다면, 두 용사가 동시에 $v$로 이동하는 것은 불가능합니다. 다만 두 용사가 각각 좌표 $u$와 $v$를 차지하고 있을 때, 어느 순간에 서로 자리를 바꿔 각각 $v$와 $u$로 이동하는 것은 가능합니다.
• 모든 용사는 동시에 현재 순간의 지시에 해당하는 다음 좌표로 이동해야 합니다. 즉, 현재가 순간 $i$라면 $(0,0)$에 있는 용사를 제외한 모든 용사는 자신의 지시에서 $i$번째 알파벳에 해당하는 좌표로 이동해야 합니다.
• 어떤 용사가 $(0,0)$에 도착한 뒤에는 그 용사에게 더 이상 지시를 내리면 안 됩니다.
• 어느 순간에 2명 이상의 용사가 동시에 $(0,0)$으로 이동할 수 없습니다. 즉, 어떤 순간에 $(0,0)$에 도착하는 용사는 반드시 1명이거나 0명이어야 합니다.

예시를 보겠습니다. 당신을 제외한 용사들이 현재 $(1,-1)$, $(1,0)$, $(1,1)$에 있다고 가정합니다. 다음은 정당한 지시의 예입니다.

예시 1. 정당한 지시의 예.

반면 다음 지시들은 제약을 만족하지 않습니다.

예시 2. 순간 1에 두 용사가 동시에 $(1,0)$을 차지하고 있습니다.

예시 3. 순간 1에 두 용사가 동시에 $(0,0)$으로 이동하고 있습니다.

예시 4. 한 용사가 $(1,-1)$을 2번 지나고 있습니다.

다음 지시는 정당합니다. 순간 1에 두 용사가 서로 자리를 바꾸지만, 여전히 이 지시는 정당합니다.

예시 5. 순간 1에 두 용사가 자리를 바꾸었지만, 이 지시는 정당합니다.

과연 당신은 충분히 짧은 시간 안에 모든 용사를 $(0,0)$으로 모을 수 있을까요?

첫 번째 줄에 당신을 제외한 용사의 수 $n$이 주어집니다.

두 번째 줄부터 $n+1$번째 줄까지 각 줄에 용사의 좌표 $x_i$, $y_i$가 공백으로 구분되어 주어집니다.

$i$번째 줄에 $i$번째 용사에게 내릴 지시를 문자열로 출력합니다.

• $1 \le n \le 500$
• $-15 \le x_i,y_i \le 15$
• 각 용사의 위치 $(x_i,y_i)$는 모두 서로 다릅니다.
• $(x_i,y_i) \neq (0,0)$

Small 문제의 각 테스트 케이스에 대한 지시의 점수는 다음과 같습니다.

$10^6 \times V$

이때 코드가 출력한 지시가 정당하고 모든 용사가 $(0,0)$으로 모이는 데 성공하였다면 $V=1$이며, 그렇지 않다면 $V=0$입니다.

Small 문제에는 50개의 테스트 케이스가 있으며, 총점수는 각 테스트 케이스 점수의 합입니다.

Small 문제의 테스트 케이스는 다음의 추가 조건을 따릅니다.

• 40개의 테스트 케이스는 무작위로 생성되었습니다. 생성 방식은 다음과 같습니다. 이 방법은 ${960 \choose n}$가지 가능한 용사 위치의 조합 중 하나를 균등한 확률로 뽑습니다.

  • 우선 960개의 가능한 점을 모두 하나의 배열에 나열합니다.
  • 다음으로 960개 점이 담긴 배열의 순서를 무작위로 섞습니다.
  • 마지막으로 그중 앞의 $n$개를 테스트에 포함되는 점으로 선정합니다.

• 나머지 테스트 케이스에는 입력 자체의 제한 외에 별도의 제한이 없습니다.

출력의 크기가 128MB를 초과하는 경우 채점 결과로 '출력 초과'를 받으니 주의하세요.