기둥 | cho.sh

문제

바이테아자르는 큰 창고의 관리 책임자다. 혹독한 겨울에 대비해 창고 바닥 아래에 난방 배관을 설치하기로 했다.

창고 평면도는 가로와 세로가 모두 짝수인 n × m 크기의 직사각형이고, 한 변의 길이가 1인 정사각형 칸으로 나뉜다. 대부분의 칸은 창고 공간이지만, 일부 칸은 건물 구조를 받치는 거대한 기둥이 차지한다. 각 기둥은 평면도에서 칸 네 개로 이루어진 2 × 2 정사각형을 차지한다. 기둥은 빽빽하게 놓이지 않아서, 어느 두 기둥의 중심도 유클리드 거리로 6 이상 떨어져 있다. 또한 각 기둥의 중심은 창고의 바깥 벽 각각에서 3 이상 떨어져 있다.

난방은 창고 바닥 아래에 설치하는 배관 하나로 한다. 배관은 기둥이 차지한 칸을 제외한 모든 칸의 중심을 지나야 한다. 배관의 각 구간은 창고 벽 중 하나와 평행해야 하고, 방향은 칸의 중심에서만 바꿀 수 있다. 배관은 시작한 곳에서 끝나야 한다. 그 지점에서 식은 물을 밖으로 내보내고 뜨거운 물을 배관에 넣는다.

바이테아자르는 창고 안의 배관 경로를 계획해 달라고 부탁했다. 이를 돕기 위해 평면도에 직교 좌표계를 도입했다. x좌표는 구간 [0, n]에, y좌표는 구간 [0, m]에 속한다. 모든 칸의 중심 좌표는 k ∈ ℕ에 대해 k + 1/2 꼴의 수다.

입력

첫째 줄에 창고의 크기와 기둥의 수를 나타내는 세 정수 n, m, f가 주어진다 (1 ≤ n, m ≤ 1,000이고 n과 m은 짝수). 다음 f개 줄에는 i번째 기둥의 중심 좌표를 나타내는 두 정수 $x_i$ , $y_i$ 가 주어진다 (0 ≤ $x_i$ ≤ n, 0 ≤ $y_i$ ≤ m).

출력

첫째 줄에 바이테아자르의 요구대로 바닥 난방을 설치할 수 있으면 TAK(예), 없으면 NIE(아니오)를 출력한다. 답이 TAK이면 둘째 줄에 배관 경로를 nm - 4f개의 글자로 이루어진 문자열로 출력한다. 배관은 좌표가 (1/2, 1/2)인 점에서 시작한다. 벡터 [0, 1]만큼의 이동은 G, [0, -1]은 D, [1, 0]은 P, [-1, 0]은 L로 표기한다.

올바른 경로는 여러 개일 수 있으므로, 아래 규칙으로 정해지는 경로 하나만 정답으로 인정한다. 중심이 (x + 1/2, y + 1/2)인 칸을 칸 (x, y)라 한다 (0 ≤ x < n, 0 ≤ y < m). 중심이 (a, b)인 기둥은 칸 (a-1, b-1), (a, b-1), (a-1, b), (a, b)를 차지한다. 기둥이 차지하지 않은 칸을 빈 칸이라 한다.

행을 {0, 1}, {2, 3}, ..., {m-2, m-1}의 쌍으로 묶는다. 행 쌍 {2k, 2k+1}에서 칸 (c, 2k)와 (c, 2k+1) 중 하나라도 기둥이 차지하면 열 c는 그 행 쌍에서 막힌 열이다. 막히지 않은 열의 극대 연속 구간 [a, b]와 행 쌍의 두 행이 만드는 2 × (b - a + 1) 직사각형을 띠라 한다. 각 띠에 대해 그 테두리를 한 바퀴 도는 회로의 간선을 모두 선택한다. 즉, 띠 안에서 같은 행의 이웃한 두 칸을 잇는 간선 전부와, 열 a와 열 b에서 두 행의 칸을 잇는 세로 간선 두 개를 선택한다.
어느 띠에도 속하지 않는 빈 칸은, 중심의 y좌표가 짝수인 기둥의 바로 아래 행과 바로 위 행에만 가로로 이웃한 두 칸의 쌍으로 나타난다. 그 두 칸을 잇는 간선을 선택한다.
k ≥ 1인 행 쌍 {2k, 2k+1}의 각 띠에 대해, 그 띠의 가장 왼쪽 열을 a라 하자. 간선 (a, 2k)-(a+1, 2k)와 (a, 2k-1)-(a+1, 2k-1)의 선택을 취소하고, 간선 (a, 2k-1)-(a, 2k)와 (a+1, 2k-1)-(a+1, 2k)를 선택한다.
2단계의 각 칸 쌍 (c, y), (c+1, y)에 대해, 이 쌍이 기둥 바로 아래에 있으면 (즉 (c, y+1)을 기둥이 차지하면) 간선 (c, y-1)-(c+1, y-1)의 선택을 취소하고 간선 (c, y-1)-(c, y)와 (c+1, y-1)-(c+1, y)를 선택한다. 기둥 바로 위에 있으면 간선 (c, y+1)-(c+1, y+1)의 선택을 취소하고 간선 (c, y)-(c, y+1)과 (c+1, y)-(c+1, y+1)을 선택한다.

선택된 간선은 모든 빈 칸을 정확히 한 번씩 지나는 닫힌 경로 하나를 이룬다. 이 경로를 칸 (0, 0)에서 시작해 첫 이동이 P가 되는 방향으로 한 바퀴 돌며 출력한다.

힌트

예제 출력은 다음 그림에 해당한다.