Problem H
Japanese Lottery

Strawberry picking game, photo by Nanao Wagatsuma

You want to manipulate the lottery in such a way that the $i$th person gets the $i$th prize, for every $i$, by removing some horizontal bars. Since you do not want to get caught, you want to remove as few bars as possible.

Figure 1: Visualization of an Amida-kuji game. The first person is connected to the third prize. This is also Sample Input 2 after all connections are added and before any connection is removed. To connect the $i$th person to the $i$th prize, it suffices to remove both horizontal bars between legs $2$ and $3$ and the topmost horizontal bar between legs $3$ and $4$. This is the only minimal solution.

For this problem, the initial game configuration has no horizontal bars. Then, horizontal bars are added one by one or are removed again. After each change, you want to know the minimum number of horizontal bars that need to be removed such that the $i$th prize is assigned to the $i$th person for each $i$. Note that this is always possible by removing all horizontal bars.

Input

The input consists of:

• One line with three integers $w, h$ and $q$ ($2 \leq w \leq 20$, $1\leq h,q \leq 2\cdot 10^5$), the number of legs, the height of the legs, and the number of changes.

• $q$ lines, each containing three integers $y, x_{1}$ and $x_{2}$ ($1\leq y \leq h$, $1\leq x_{1}, x_{2} \leq w$), describing a change where a horizontal bar is added or removed at height $y$ between legs $x_1$ and $x_2$. If there is already a horizontal bar at this position, it will be removed. Otherwise the bar will be added. It is guaranteed that the two legs are adjacent, i.e. $|x_{1}-x_{2}|=1$.

It is guaranteed that all horizontal bars have different heights at every moment.

Output

After each change, output a single integer, the minimum number of horizontal bars that need to be removed in the game with the currently existing bars such that the $i$th prize is assigned to the $i$th person for each $i$.

4 6 7
1 1 2
2 3 4
4 3 4
5 1 2
6 3 4
3 2 3
6 3 4

1
2
1
0
1
2
1

5 9 12
1 3 4
2 1 2
3 2 3
4 4 5
5 2 1
6 4 3
7 2 3
8 4 3
9 4 5
6 4 3
7 2 3
1 3 4

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