색깔 있는 뱀

바이타자르는 몇 년 전 낡은 휴대폰으로 뱀 게임을 즐겼다. 지금은 프로그래머로 일하며, 그 추억으로 이 게임의 새 버전을 직접 만들고 싶어 한다. 2022년인 지금은 색을 더하고 훨씬 큰 컴퓨터 화면으로 옮기려고 한다. 당신이 할 일은 이 게임의 모듈 하나를 작성하는 것이다.

게임은 한 변이 $m$인 정사각형 보드에서 진행된다. 보드는 $m$개의 행과 $m$개의 열로 나뉘어 총 $m^2$개의 칸이 있다. 행은 위에서 아래로 1부터 $m$까지, 열은 왼쪽에서 오른쪽으로 1부터 $m$까지 번호를 매긴다. 색은 0부터 $m^2-1$까지 번호를 매긴다.

게임이 시작되면 1행 1열 칸에는 머리만 있는 뱀이 있다. 머리의 색은 0이다. 보드에는 $p$개의 간식이 놓여 있다. 각 간식은 한 칸을 차지하며 색을 가진다. 간식의 색은 같을 수 있다.

플레이어는 매 시간 단위마다 머리를 위, 아래, 왼쪽, 오른쪽 중 한 칸으로 옮긴다. 나머지 몸통은 머리를 따라간다. 움직이기 전에 머리가 차지하던 칸은 이제 두 번째 조각이 차지하고, 두 번째 조각이 차지하던 칸은 세 번째 조각이 차지하는 식이다. 머리는 바로 뒤에 있는 첫 번째 몸통 조각의 칸으로 되돌아갈 수 없으므로 뱀은 뒤로 돌아서지 못한다. 머리가 보드 밖으로 나가거나 뱀의 다른 조각이 있는 칸에 들어가면 플레이어는 진다.

머리가 간식이 있는 칸으로 움직이면 뱀이 간식을 먹는다. 간식은 보드에서 사라지고, 뱀은 조각 하나만큼 길어진다. 이때 머리는 먹은 간식의 색을 받고, 움직임을 마친 뒤 그 칸에 위치한다. 이 움직임에서는 나머지 몸통 조각들이 움직이지 않는다.

움직이는 동안 뱀이 보드 밖으로 나가지 않고, 자기 몸의 조각이 있는 칸에 들어가지 않는다고 가정해도 된다.

첫 줄에는 세 정수 $m$, $p$, $n$이 주어진다. 각각 보드의 한 변 길이, 보드에 놓인 간식의 개수, 처리할 명령의 개수다.

다음 $p$개의 줄에는 세 정수 $w_i$, $k_i$, $c_i$가 주어진다. 이는 $w_i$행 $k_i$열 칸에 색 $c_i$인 간식이 하나 있다는 뜻이다. 여기서 $1 \le w_i, k_i \le m$이고 $0 \le c_i \le m^2-1$이다. 모든 $(w_i, k_i)$ 쌍은 서로 다르며, 뱀의 시작 위치인 (1, 1)과 같지 않다.

다음 $n$개의 줄에는 명령이 주어진다. 명령은 G, D, L, P 중 하나의 글자이거나, 글자 Z와 두 정수 $w'_j$, $k'_j$로 이루어진다. G는 머리가 위로, D는 아래로, L은 왼쪽으로, P는 오른쪽으로 움직였다는 뜻이다. Z w' k' 명령은 현재 시점에 $w'$행 $k'$열 칸을 차지하는 뱀 조각의 색을 묻는 질의다. 질의가 최소 하나는 있다고 가정해도 된다.

각 질의마다 한 줄에 정수 하나를 출력한다. 질의한 칸을 그 시점에 차지하는 뱀 조각의 색을 $[0, m^2-1]$ 범위의 정수로 출력한다. 그 시점에 해당 칸을 차지하는 뱀 조각이 없으면 -1을 출력한다.