[ROI 2018] Extraction of radium - Problem

Before mining radium on Mars is possible, a special satellite was launched to measure the radioactivity level on the surface of the planet.

The plateau (flat piece of land) Meridian can be represented as a rectangle with unit squares. We denote the -th square in the -th row as . Both rows and columns are numbered starting from .

As a result of scanning the plateau, we know the level of radioactivity for each unit square. For the unit square it is a positive integer . The accuracy of the measurements is so high that all numbers are different. A unit square is considered suitable for the extraction of radium if its value is the maximum in the -th row and the maximum in the -th column.

The satellite then recorded updates in the radioactivity. The -th update changed the value to a stricly greater value. (The radioactivity on Mars tends to increase.) The new value stays in this unit square forever unless a new update changes the same unit square. After each update, all values are guaranteed to still remain different.

Your task is to write a program that, given the initial values and the list of updates, after each update determines the number of unit squares that are suitable for the extraction of radium.

Input

The first line of the input contains three positive integers , and (, ). Please note that the first constraint is for the product , not for the number of rows and columns separately.

Each of the following lines contains positive integers. The -th integer in the -th of those lines specifies the initial value (, all are different).

The following lines describe the updates. The -th of them contains three integers , and , that denote the change in the level of radioactivity in the unit square to a new value (, , ). It is guaranteed that is strictly greater than the previous level of radioactivity in this square, and that all the radioactivity levels are different after each update.

Output

The output should consist of lines. In the -th line, print a single integer — the number of unit squares suitable for the extraction of radium after the -th update.

Scoring

You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group denotes the sample test(s) from the statement.

给一个 $n \times m$ 的矩阵 $a$ ，矩阵中的数互不相同。接下来有 $q$ 次修改，每次修改会将某个值修改为一个更大的值。保证修改后矩阵中的数仍互不相同。每次修改后，请求出：矩阵中有多少个数，既是它所在行的最大值，又是它所在列的最大值。

输入格式

第一行三个整数 $n$ ， $m$ ， $q$ ，表示矩阵的大小与修改操作的次数。接下来 $n$ 行，每行 $m$ 个整数，表示该矩阵。接下来 $q$ 行，每行三个整数 $x$ ， $y$ ， $t$ ，表示将该矩阵第 $x$ 行，第 $y$ 列的元素改为 $t$ 。

输出格式

$q$ 行，每行一个整数，表示每次修改后，矩阵中有多少个数满足条件。

Problem D: [ROI 2018] Extraction of radium

Description

输入格式

输出格式

Sample Input Copy

Sample Output Copy

HINT