Background

Translated from ROI 2018 Day1 T1. Добыча радия (Extraction of radium).

Problem Description

You are given an $n \times m$ matrix $a$, and all numbers in the matrix are pairwise distinct.
Then there are $q$ updates. Each update changes one value to a larger value. It is guaranteed that after each update, all numbers in the matrix are still pairwise distinct.

After each update, compute how many numbers in the matrix are both the maximum in their row and the maximum in their column.

Input Format

The first line contains three integers $n$, $m$, $q$, representing the size of the matrix and the number of updates.
The next $n$ lines each contain $m$ integers, describing the matrix.
The next $q$ lines each contain three integers $x$, $y$, $t$, meaning to change the element in row $x$ and column $y$ to $t$.

Output Format

Output $q$ lines, each containing one integer, representing after each update how many numbers in the matrix satisfy the condition.

2 3 3
1 4 3
6 5 2
2 2 9
1 3 5
2 2 10

1
2
2

Hint

Constraints: For all testdata, $1 \leq a(i,j) \leq 10^7$, $1 \leq t \leq 10^7$, $1 \leq n, m, q \leq 2 \times 10^5$.

Translated by ChatGPT 5