나도 최고가 되고 싶다!

애쉬 케첨이 최고의 트레이너가 된 것처럼, 미스터 판다도 그의 발자취를 따라 최고가 되려고 한다. 그는 도감을 채우기 위해 가능한 한 많은 종류의 포켓몬을 잡고 싶어 한다. 가는 길에는 다른 트레이너들이 있어서, 목표에 닿으려면 그들을 이겨야 한다.

미스터 판다와 포켓몬은 $R \times C$ 격자로 이루어진 세계에 산다. 미스터 판다는 인접한 칸으로만 이동할 수 있다. 왼쪽 위 칸은 $(1, 1)$이고, 오른쪽 아래 칸은 $(C, R)$이다.

각 칸에는 트레이너가 한 명씩 있다. 미스터 판다가 그 칸을 지나가려면 트레이너를 이겨야 하고, 이기면 그 트레이너의 포켓몬을 얻는다. 트레이너마다 레벨이 서로 다르며, 레벨이 높은 트레이너가 더 강하다. $(j, i)$ 칸의 트레이너는 레벨 $L_{ij}$이고, 타입 $P_{ij}$의 포켓몬으로 배틀한다.

트레이너는 이길 확률을 높이려고 사용하는 포켓몬의 타입을 가끔 바꾼다. 미스터 판다는 원정을 언제 시작하는 것이 좋을지 계획하고 싶어 한다. 특정 시점마다 그는 이렇게 묻는다. $(X_q, Y_q)$ 칸에서 출발해 레벨이 $L_q$ 이하인 트레이너만 이길 수 있다면, 얻을 수 있는 포켓몬 타입은 몇 종류인가? 이기지 못하는 트레이너의 칸은 지나갈 수 없다. 같은 타입을 여러 트레이너에게서 얻어도 한 종류로 센다.

첫 줄에 양의 정수 $R$, $C$, $Q$가 주어진다. $R \times C \le 50000$이 보장된다. 이어서 $2R + Q$줄이 입력된다.

처음 $R$줄에는 각 줄마다 $C$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 $L_{ij}$이며, $1 \le L_{ij} \le 10^9$이다. 모든 값은 서로 다르다.

다음 $R$줄에는 각 줄마다 $C$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 $P_{ij}$이며, $1 \le P_{ij} \le 50000$이다.

마지막 $Q$줄에는 각각 4개의 정수로 된 질의가 주어진다.

• 첫 정수가 1이면 1번 질의이며, 이어지는 세 정수는 $X_q$, $Y_q$, $P_q$이다. $(X_q, Y_q)$ 칸의 트레이너가 타입 $P_q$의 포켓몬을 사용하도록 바뀐다. $1 \le P_q \le 50000$이다.
• 첫 정수가 2이면 2번 질의이며, 이어지는 세 정수는 $X_q$, $Y_q$, $L_q$이다. 미스터 판다가 $(X_q, Y_q)$ 칸에서 출발해 레벨이 $L_q$ 이하인 트레이너만 이길 수 있을 때, 얻을 수 있는 포켓몬 타입의 수를 구한다. $1 \le L_q \le 10^9$이다.

2번 질의마다 미스터 판다가 얻을 수 있는 포켓몬 타입의 수를 한 줄에 하나씩 출력한다.

• $1 \le R \le 50000$
• $1 \le Q \le 100000$