무지개 황금의 땅

아주 먼 옛날 드림타임에 호주는 R행 C열로 이루어진 평평한 격자였고, 모든 칸이 땅이었다. 행은 북쪽에서 남쪽으로 1번부터 R번까지, 열은 서쪽에서 동쪽으로 1번부터 C번까지 번호가 매겨졌다. 행 r, 열 c에 있는 칸은 (r, c)로 쓴다.

어느 날 거대한 무지개 뱀이 (sr, sc)에서 땅 위로 올라와 호주를 가로질러 움직였고, 미끄러지며 지나간 칸은 모두 강이 되었다. 뱀은 M번 연속으로 움직였다. 각 이동은 현재 위치의 바로 북(N), 남(S), 동(E), 서(W)쪽 칸으로 가며, 그 칸을 강으로 바꾼다. 출발점 (sr, sc)도 강이 되었다.

수백만 년이 지난 지금, 여러분은 뱀이 만든 강을 기념하기 위해 칸들로 이루어진 직사각형 블록을 사려고 한다. 블록 안의 땅 칸마다 서로 다른 색을 고른다. 가능한 한 많은 색을 쓰고 싶지만, 블록 안에서 서로 인접한 땅 칸의 쌍은 반드시 같은 색이어야 한다. 두 칸이 변을 공유하면 인접한 것이다. 블록 밖의 땅 칸과 블록 안의 강 칸에는 색을 고르지 않는다.

뱀의 이동 기록이 주어질 때, Q개의 직사각형 블록 각각에 대해 땅 칸에 고를 수 있는 서로 다른 색의 최대 개수를 구하라.

$0 \le M \le 100,000$

$R, C, Q \ge 1$