Training

Task

The 2026 Foo(1)ball World Cup is approaching, and you, the Head Coach of the Info(1)Cup National Team, are preparing intense training sessions. Unfortunately, the hotel you booked has only one football pitch. After inspection, you find that the pitch has height $N$ meters and width $M$ meters. That would be perfectly fine if $N$ and $M$ had proper proportions. The issue is that $\underline{N \leq 3}$ while $M \leq 200\ 000$.

Each of the $N \times M$ players is placed at a distinct position $(i,j)$ on the pitch, where $1 \le i \le N$ and $1 \le j \le M$. Each player belongs to exactly one team; let $A_{i,j}$ denote the team of the player at position $(i,j)$.

You have two assistants with very different philosophies: Attack and Defense.
They prepared the following game, which is played independently for each team.

• Defense chooses one player of the team who receives the ball first.
• Then, the assistants alternate turns. Attack moves first, followed by Defense, and so on.
• On a turn, the current assistant chooses the player who currently has the ball and tells them to which player the ball should be passed. This player must be from the same team.
• Since the players are not in the best shape, a player may only pass the ball to a teammate who is located either in the same row or in the same column of the pitch.
• Due to exhaustion, if a player receives the ball more than once, they will get injured. The assistants will never choose this option, as it is strongly against the team's interests.
• When the current player has no one to pass the ball to, the assistant whose turn it is loses the game.

Both assistants play optimally.

You want to test how players adapt in different situations, so you perform $Q$ substitutions. Each substitution has the following form:

The player at position $(x,y)$ is assigned to team $t$.

That is, we set $A_{x,y}$ to $t$. (It is possible that $A_{x,y}$ was already equal to $t$.)

Before any substitutions, and after each substitution, determine the number of teams for which Attack wins the game.

Input data

The first line contains $N$ and $M$. The next $N$ lines contain $M$ elements each. On the $i$-th of these lines, the $j$-th value is $A_{i,j}$. The next line contains the value $Q$. The following $Q$ lines each contain three integers: $x$, $y$, and $t$.

Output data

Output $Q + 1$ lines. The first line should contain the number of winning teams for Attack before any substitutions. The $i + 1$-th line should contain the number of winning teams for Attack after the $i$-th substitution.

Constraints and clarifications

• $1 \leq N \leq 3$
• $1 \leq M, Q \leq 200\ 000$
• $1 \leq N \times M \leq 200\ 000$
• $1 \leq A_{i,j} \leq N \times M$
• For every substitution: $1 \leq x \leq N$, $1 \leq y \leq M$, $1 \leq t \leq N \times M$

Example 1

stdin

1 6
1 2 2 1 2 1
3
1 1 2
1 2 3
1 1 3

stdout

0
2
1
3

Explanation

Let's look at the first sample. Before making any substitutions, Defense can win the game for both teams.
For example, let's analyze team $1$:

Suppose Defense gives the ball to the player standing at $(1,4)$. Then, Attack makes the player at $(1,4)$ pass the ball to the player at $(1,1)$.
Now, the only option for Defense is to make the player at $(1,1)$ pass the ball to the player at $(1,6)$.
Since there are no other players in team $1$, the player at $(1,6)$ cannot pass the ball to anyone else.
Since it is Attack's turn, they lose.

After the first substitution, the pitch looks as follows:

2 2 2 1 2 1

For team $1$, if Defense gives the ball to the player at $(1,4)$, Attack can make them pass the ball to $(1,6)$.
Now, there is nowhere to pass the ball. Hence, Attack wins the game for team $1$.

Example 2

stdin

2 4
1 2 3 1
2 2 2 3
3
1 4 2
1 2 1
2 4 1

stdout

2
0
1
0

Example 3

stdin

3 3
3 9 1 
9 3 3
3 9 9
3
2 1 3
2 3 9
3 3 1

stdout

1
0
2
2