도넛 드론

도넛 모양 행성을 탐사하는 드론의 시뮬레이션을 만든다. 드론이 움직이는 곳은 토러스 격자, 즉 가로와 세로 양쪽으로 순환하며 이어지는 직사각형 격자다. 격자의 행은 위에서 아래로 $1$번부터 $r$번까지, 열은 왼쪽에서 오른쪽으로 $1$번부터 $c$번까지 번호를 매긴다. 각 칸에는 고도가 하나씩 있고, 고도는 양의 정수다.

드론은 처음에 $1$행 $1$열 칸에 있다. 한 번 이동할 때마다 드론은 세 칸을 본다. 바로 오른쪽 칸, 오른쪽 아래 대각선 칸, 오른쪽 위 대각선 칸이다. 행 번호와 열 번호는 순환하므로 $r$행 아래가 $1$행이고 $c$열 오른쪽이 $1$열이다. 드론은 이 세 칸 중 고도가 가장 높은 칸으로 날아간다.

시뮬레이션 중에는 두 종류의 사건이 일어난다.

• move k: 드론이 $k$번 이동한다.
• change a b e: $a$행 $b$열 칸의 고도가 $e$로 바뀐다.

각 move 사건이 끝난 직후 드론의 위치를 구한다.

어느 시점에서든 같은 열에서 순환하며 연속한 세 칸의 고도는 서로 모두 다르다. 따라서 드론이 날아갈 칸은 언제나 하나로 정해진다.

첫 줄에 격자의 행 개수 $r$과 열 개수 $c$가 주어진다 ($3 \le r, c \le 2000$). 이어지는 $r$개 줄 중 $i$번째 줄에는 $i$행 칸의 처음 고도 $e_{i,1}, e_{i,2}, \ldots, e_{i,c}$가 주어진다 ($1 \le e_{i,j} \le 10^9$).

다음 줄에 사건의 개수 $m$이 주어진다 ($1 \le m \le 5000$). 이어지는 $m$개 줄 중 $j$번째 줄에는 $j$번째 사건이 주어진다. 사건의 형태는 move k ($1 \le k \le 10^9$) 또는 change a b e ($1 \le a \le r$, $1 \le b \le c$, $1 \le e \le 10^9$)다.

입력에 있는 move 사건마다 한 줄씩, 사건이 나온 순서대로 출력한다. $j$번째 move 사건에 해당하는 줄에는 그 사건이 끝난 직후 드론이 있는 칸의 행 번호와 열 번호를 공백 하나로 구분해 출력한다.