Under construction

Still being built. Things may change

I want to be the very best too!

Time limit5sMemory limit512 MB

Summary
Count distinct Pokémon types reachable from a start cell through trainers of level at most L, with point updates that change a cell's type.
Level

Hard9 of 10

Topics
Graph, Union-find, Hash map, Divide and conquer
Solved
No attempts yet

Problem

Ash Ketchum became the very best, and Mr. Panda wants to follow in his footsteps. He wants to catch as many different types of Pokémon as possible to fill his Pokédex. Other trainers stand in his way, and he has to defeat them to reach his goal.

Mr. Panda and the Pokémon live in a world shaped like an R×CR \times C grid. Mr. Panda can only move from one square to an adjacent square. The top left square is (1,1)(1, 1) and the bottom right square is (C,R)(C, R).

Each square has a trainer. To pass through a square, Mr. Panda must defeat its trainer, and then he obtains that trainer's Pokémon. Every trainer has a different level, and the trainer with the higher level is stronger. The trainer in square (j,i)(j, i) has level LijL_{ij} and battles with a Pokémon of type PijP_{ij}.

Trainers sometimes switch the type of Pokémon they use to improve their chances of winning. Mr. Panda wants to plan when to start his expedition. At certain times he asks: if he starts at square (Xq,Yq)(X_q, Y_q) and can only defeat trainers of level at most LqL_q, how many different Pokémon types can he obtain? He cannot pass through a square whose trainer he cannot defeat. Obtaining the same type from several trainers counts as one type.

Input

The first line contains three positive integers RR, CC, and QQ. It is guaranteed that R×C≤50000R \times C \le 50000. Then 2R+Q2R + Q lines follow.

The first RR lines each contain CC integers. The jj-th integer on the ii-th line is LijL_{ij}, where 1≤Lij≤1091 \le L_{ij} \le 10^9. All values are distinct.

The next RR lines each contain CC integers. The jj-th integer on the ii-th line is PijP_{ij}, where 1≤Pij≤500001 \le P_{ij} \le 50000.

The last QQ lines are queries, each with 4 integers.

  • If the first integer is 1, the query is type 1 and the next three integers are XqX_q, YqY_q, PqP_q. The trainer at (Xq,Yq)(X_q, Y_q) changes to use Pokémon of type PqP_q, where 1≤Pq≤500001 \le P_q \le 50000.
  • If the first integer is 2, the query is type 2 and the next three integers are XqX_q, YqY_q, LqL_q. Mr. Panda starts at (Xq,Yq)(X_q, Y_q) and can only defeat trainers of level at most LqL_q, where 1≤Lq≤1091 \le L_q \le 10^9. Find the number of different Pokémon types he can obtain.

Output

For each query of type 2, output one line containing the number of Pokémon types Mr. Panda can obtain.

Constraints

  • 1≤R≤500001 \le R \le 50000
  • 1≤Q≤1000001 \le Q \le 100000

Examples4

  1. Example 1

    Input
    1 5 5
1 2 3 4 5
1 1 2 1 2
2 2 1 2
2 1 1 4
2 4 1 3
1 3 1 1
2 3 1 4
    Expected output
    1
2
0
1

  2. Example 2

    Input
    1 5 5
1 2 3 4 5
3 4 3 2 5
2 3 1 3
2 1 1 5
2 4 1 2
1 4 1 4
2 3 1 5
    Expected output
    2
4
0
3

  3. Example 3

    Input
    3 3 5
1 4 3
11 2 7
5 10 6
1 1 1
2 1 2
1 2 1
2 2 1 6
2 2 3 10
2 3 2 3
1 2 2 2
2 2 1 4
    Expected output
    1
2
0
2

  4. Example 4

    Input
    3 3 5
1 4 3
11 2 7
5 10 6
6 3 3
4 6 4
9 4 9
2 2 1 6
2 2 3 10
2 3 2 3
1 2 2 7
2 2 1 4
    Expected output
    2
4
0
3