시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

Having seen Ash Ketchum’s success in becoming the very best, Mr. Panda wants to follow his footsteps and becomes the very best too! To do so, he wants to catch as many different types of Pokémon as possible to fill up his Pokédex and become the very best. However, there are many other Pokémon trainers in his way and he has to defeat them in order to reach his goal.

Mr. Panda and the Pokémon live in a world which can be represented by a R × C grid with R rows and C columns and Mr. Panda can only go from one square to another if they are adjacent. The top left square is labelled as (1, 1) and the bottom right square is labelled as (C, R). Each grid square has a Pokémon trainer that Mr. Panda will have to battle in order to pass through that grid square and obtain the Pokémon that is owned by that trainer. Each Pokémon trainer has his/her own level relative to the other trainers which determines which Pokémon trainer is the best. We assume all Pokémon trainers have different levels (to ensure a clear winner for every battle). The Pokémon trainer in square (j, i) has level Lij and he/she uses a Pokémon of type Pij for the battle.

To make things even more difficult, the world is constantly changing so the Pokémon trainers will sometimes change the type of Pokémon they battle with in order to increase their chances of winning. Because of this, Mr. Panda wants to plan when is the best time to begin his expedition. At certain points in time, he wants to know how many types of Pokémon he will be able to obtain if he starts off at square (Xq, Yq) and is only able to defeat Pokémon trainers of level at most Lq. Remember, he cannot pass through a grid square if he cannot defeat the Pokémon trainer there. Defeating a Pokémon type more than once with different Pokémon trainers will only count as one type of Pokémon.

입력

The first line of input contains three positive integers R, C and Q. It is guaranteed that R×C ≤ 50000.

It is followed by 2R + Q lines.

  • The first R lines of input will each contain C integers. The j-th integer on the i-th line represents Lij. It is guaranteed that 1 ≤ Lij ≤ 109 and that all the values will be distinct.
  • The next R lines of input will each contain C integers. The j-th integer on the i-th line represents Pij. It is guaranteed that 1 ≤ Pij ≤ 50000.
  • The last Q lines contain 4 integers each, representing a query.
    • If the first integer of the line is 1, it represents a type 1 query and the next 3 integers represent Xq, Yq, Pq. This means that the trainer at (Xq, Yq) changed to use Pokémon of type Pq instead. It is guaranteed that 1 ≤ Pq ≤ 50000.
    • If the first integer of the line is 2, it represents a type 2 query and the next 3 integers represent Xq, Yq, Lq. This means that Mr. Panda wants to know, if he starts at square (Xq, Yq) and is only able to defeat Pokémon trainers of level at most Lq, how many different types of Pokémon he will be able to obtain. It is guaranteed that 1 ≤ Lq ≤ 109.

출력

For each query of type 2, output one line with a single integer, the number of types of Pokémon Mr. Panda will be able to obtain.

제한

  • 1 ≤ R ≤ 50000
  • 1 ≤ Q ≤ 100000

예제 입력 1

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

예제 출력 1

1
2
0
1

예제 입력 2

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

예제 출력 2

2
4
0
3

예제 입력 3

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

예제 출력 3

1
2
0
2

예제 입력 4

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

예제 출력 4

2
4
0
3

For the first type 2 query, Mr. Panda can only catch Pokémon of types 3 and 6 by defeating the Pokémon trainers with levels 1, 2, 3 and 4.

For the second type 2 query, Mr. Panda can catch all types of Pokémon as he can defeat all Pokémon trainers except the one with level 11.

For the third type 2 query, Mr. Panda cannot defeat the trainer at the starting square so he cannot go anywhere and thus cannot catch any Pokémon.

For the fourth type 2 query, Mr. Panda can catch 3 types of Pokémon since the trainer at (2, 2) is now using a Pokémon of type 7.