Problem H
Japanese Lottery

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.

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$.
Sample Input 1 | Sample Output 1 |
---|---|
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 |
Sample Input 2 | Sample Output 2 |
---|---|
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 |