import java.io.*;
import java.util.*;
public class pokemonmaster {
// --- DSU Merge Tree Structures ---
static class MergeNode {
int id; // if leaf: original cell id; if internal: -1
int mergeLevel; // for internal nodes: level at which union occurred
int left, right; // indices of left/right children (-1 if none)
int tin, tout; // Euler tour time interval
}
static MergeNode[] mergeTree; // will hold up to 2*N nodes
static int mergeTreeSize; // current number of nodes in mergeTree
static int[] cellToLeaf; // maps original cell id to its leaf node index in mergeTree
// DSU (without path compression, for easier rollback) used in merge tree construction.
static class DSU {
int[] par, sz, nodeId;
DSU(int n) {
par = new int[n];
sz = new int[n];
nodeId = new int[n];
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
nodeId[i] = i; // initially, each cell is its own merge tree node
}
}
int find(int a) {
while (a != par[a])
a = par[a];
return a;
}
}
static class Cell {
int id, level;
}
static int R, C, N; // grid dimensions and total number of cells
// --- Euler Tour Variables ---
static int timer;
static int[] ET; // Euler tour: maps Euler index to original cell id
static int[] nodeAtET; // Euler tour: maps Euler index to merge tree leaf index
// --- Binary Lifting (parent pointers for merge tree) ---
static int[] parentMT; // parent pointer for each mergeTree node
// --- Mo's Algorithm with Modifications ---
static class MoQuery {
int L, R, time, idx; // query on Euler interval [L, R) at update time, original query index
MoQuery(int L, int R, int time, int idx) {
this.L = L;
this.R = R;
this.time = time;
this.idx = idx;
}
}
static class UpdateOp {
int pos, prevVal, newVal;
UpdateOp(int pos, int prevVal, int newVal) {
this.pos = pos;
this.prevVal = prevVal;
this.newVal = newVal;
}
}
// For input queries: type, X, Y, and value (P for update or L for query)
static class Query {
int t, X, Y, v;
Query(int t, int X, int Y, int v) {
this.t = t;
this.X = X;
this.Y = Y;
this.v = v;
}
}
// Global variables for Mo’s algorithm (dynamic distinct queries)
static int BS; // block size
static ArrayList<MoQuery> moQueries = new ArrayList<>();
static ArrayList<UpdateOp> updates = new ArrayList<>();
static final int MAXP = 50000 + 5;
static int[] freq = new int[MAXP];
static int curDistinct = 0;
static int[] currET; // current Euler Tour array (Pokémon types) of size N
// Global pointers for current Mo window.
static int globalCurL = 0, globalCurR = 0;
// --- Functions for Mo's algorithm ---
static void addPos(int pos) {
int val = currET[pos];
freq[val]++;
if (freq[val] == 1) {
curDistinct++;
}
}
static void removePos(int pos) {
int val = currET[pos];
freq[val]--;
if (freq[val] == 0) {
curDistinct--;
}
}
// When applying an update, we adjust frequency counts only if the updated index lies in the current window.
static void applyUpdate(int updIdx) {
UpdateOp op = updates.get(updIdx);
int pos = op.pos;
if (pos >= globalCurL && pos < globalCurR) {
removePos(pos);
currET[pos] = op.newVal;
addPos(pos);
} else {
currET[pos] = op.newVal;
}
}
static void rollbackUpdate(int updIdx) {
UpdateOp op = updates.get(updIdx);
int pos = op.pos;
if (pos >= globalCurL && pos < globalCurR) {
removePos(pos);
currET[pos] = op.prevVal;
addPos(pos);
} else {
currET[pos] = op.prevVal;
}
}
// --- DSU Merge Tree Construction ---
static void buildMergeTree(int[] cellLevel) {
// Initialize mergeTree with capacity 2*N and create leaves for all cells.
mergeTree = new MergeNode[2 * N];
cellToLeaf = new int[N];
for (int i = 0; i < N; i++) {
mergeTree[i] = new MergeNode();
mergeTree[i].id = i;
mergeTree[i].mergeLevel = 0;
mergeTree[i].left = -1;
mergeTree[i].right = -1;
mergeTree[i].tin = 0;
mergeTree[i].tout = 0;
cellToLeaf[i] = i;
}
mergeTreeSize = N;
int nextNode = N;
// Build an array of cells and sort them by level.
Cell[] cells = new Cell[N];
for (int i = 0; i < N; i++) {
cells[i] = new Cell();
cells[i].id = i;
cells[i].level = cellLevel[i];
}
Arrays.sort(cells, new Comparator<Cell>() {
public int compare(Cell a, Cell b) {
return Integer.compare(a.level, b.level);
}
});
DSU dsu = new DSU(N);
boolean[] active = new boolean[N];
int[] dr = { 1, -1, 0, 0 };
int[] dc = { 0, 0, 1, -1 };
// Activate cells in increasing order of level and union with active neighbors.
for (Cell cell : cells) {
int id = cell.id;
active[id] = true;
int r = id / C, c = id % C;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C)
continue;
int nb = nr * C + nc;
if (!active[nb])
continue;
int ra = dsu.find(id), rb = dsu.find(nb);
if (ra == rb)
continue;
if (dsu.sz[ra] < dsu.sz[rb]) {
int temp = ra;
ra = rb;
rb = temp;
}
// Create a new merge tree node representing the union.
mergeTree[nextNode] = new MergeNode();
mergeTree[nextNode].id = -1;
mergeTree[nextNode].mergeLevel = cell.level;
mergeTree[nextNode].left = dsu.nodeId[ra];
mergeTree[nextNode].right = dsu.nodeId[rb];
mergeTree[nextNode].tin = 0;
mergeTree[nextNode].tout = 0;
dsu.par[rb] = ra;
dsu.sz[ra] += dsu.sz[rb];
dsu.nodeId[ra] = nextNode;
nextNode++;
}
}
mergeTreeSize = nextNode;
}
// --- Iterative Euler Tour on the Merge Tree ---
// This DFS assigns tin and tout values to each mergeTree node.
static void buildEulerTour() {
timer = 0;
int root = mergeTreeSize - 1; // the final merge node is the root.
class Frame {
int node, state;
Frame(int node, int state) {
this.node = node;
this.state = state;
}
}
Stack<Frame> stack = new Stack<>();
stack.push(new Frame(root, 0));
while (!stack.isEmpty()) {
Frame top = stack.peek();
int node = top.node;
if (top.state == 0) {
mergeTree[node].tin = timer;
top.state = 1;
if (mergeTree[node].left != -1) {
stack.push(new Frame(mergeTree[node].left, 0));
continue;
}
}
if (top.state == 1) {
top.state = 2;
if (mergeTree[node].right != -1) {
stack.push(new Frame(mergeTree[node].right, 0));
continue;
}
}
if (mergeTree[node].left == -1 && mergeTree[node].right == -1) {
timer++;
}
mergeTree[node].tout = timer;
stack.pop();
}
ET = new int[N];
nodeAtET = new int[N];
// Each leaf corresponds to one original cell.
for (int i = 0; i < N; i++) {
int leaf = cellToLeaf[i];
ET[mergeTree[leaf].tin] = i;
nodeAtET[mergeTree[leaf].tin] = leaf;
}
}
// --- Build Parent Pointers for Binary Lifting ---
static void buildParentMT() {
parentMT = new int[mergeTreeSize];
Arrays.fill(parentMT, -1);
for (int i = 0; i < mergeTreeSize; i++) {
if (mergeTree[i].left != -1) {
parentMT[mergeTree[i].left] = i;
parentMT[mergeTree[i].right] = i;
}
}
}
// Given a leaf (merge tree node index) and a level threshold L, return the DSU component node.
static int getComponentNode(int leaf, int L, int[] gridLevel) {
int orig = mergeTree[leaf].id; // original cell id
if (gridLevel[orig] > L)
return -1;
int cur = leaf;
while (parentMT[cur] != -1) {
int par = parentMT[cur];
if (mergeTree[par].mergeLevel <= L)
cur = par;
else
break;
}
return cur;
}
// --- Main Function ---
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
int Q = Integer.parseInt(st.nextToken());
N = R * C;
int[] gridLevel = new int[N];
int[] gridType = new int[N];
// Read grid levels.
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
gridLevel[i * C + j] = Integer.parseInt(st.nextToken());
}
}
// Read Pokémon types.
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
gridType[i * C + j] = Integer.parseInt(st.nextToken());
}
}
// Read queries.
Query[] queriesInput = new Query[Q];
for (int i = 0; i < Q; i++) {
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
int X = Integer.parseInt(st.nextToken());
int Y = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
queriesInput[i] = new Query(t, X, Y, v);
}
// Build DSU merge tree based on grid connectivity and levels.
buildMergeTree(gridLevel);
buildEulerTour();
buildParentMT();
// Prepare the base Euler Tour array: for each leaf corresponding to cell i, assign its Pokémon type.
currET = new int[N];
int[] baseET = new int[N];
for (int i = 0; i < N; i++) {
int cellId = ET[i];
baseET[i] = gridType[cellId];
currET[i] = baseET[i];
}
int updCount = 0;
int[] ans = new int[Q];
// Process queries in input order.
// For type 1 queries, record the update and update our current state.
for (int i = 0; i < Q; i++) {
Query query = queriesInput[i];
if (query.t == 1) {
int cell = (query.Y - 1) * C + (query.X - 1);
int leaf = cellToLeaf[cell];
int pos = mergeTree[leaf].tin;
int prevVal = currET[pos];
updates.add(new UpdateOp(pos, prevVal, query.v));
currET[pos] = query.v;
updCount++;
} else { // query.t == 2
int cell = (query.Y - 1) * C + (query.X - 1);
if (gridLevel[cell] > query.v) {
moQueries.add(new MoQuery(0, 0, updCount, i));
} else {
int leaf = cellToLeaf[cell];
int comp = getComponentNode(leaf, query.v, gridLevel);
if (comp == -1) {
moQueries.add(new MoQuery(0, 0, updCount, i));
} else {
int Lpos = mergeTree[comp].tin;
int Rpos = mergeTree[comp].tout;
moQueries.add(new MoQuery(Lpos, Rpos, updCount, i));
}
}
}
}
// Reset currET to the base state (time 0) for Mo's algorithm.
for (int i = 0; i < N; i++) {
currET[i] = baseET[i];
}
// Setup Mo's algorithm.
BS = Math.max(1, (int) Math.pow(N, 2.0 / 3));
Collections.sort(moQueries, new Comparator<MoQuery>() {
public int compare(MoQuery a, MoQuery b) {
int blockA = a.L / BS, blockB = b.L / BS;
if (blockA != blockB)
return blockA - blockB;
int blockRA = a.R / BS, blockRB = b.R / BS;
if (blockRA != blockRB)
return blockRA - blockRB;
return a.time - b.time;
}
});
Arrays.fill(freq, 0);
curDistinct = 0;
globalCurL = 0;
globalCurR = 0;
int curL = 0, curR = 0, curT = 0;
// Process each Mo query.
for (MoQuery q : moQueries) {
while (curT < q.time) {
applyUpdate(curT);
curT++;
}
while (curT > q.time) {
curT--;
rollbackUpdate(curT);
}
while (curR < q.R) {
addPos(curR);
curR++;
}
while (curR > q.R) {
curR--;
removePos(curR);
}
while (curL < q.L) {
removePos(curL);
curL++;
}
while (curL > q.L) {
curL--;
addPos(curL);
}
globalCurL = curL;
globalCurR = curR;
ans[q.idx] = curDistinct;
}
// Output answers for type-2 queries in their original order.
for (int i = 0; i < Q; i++) {
if (queriesInput[i].t == 2) {
out.println(ans[i]);
}
}
out.flush();
out.close();
}
}
