Description

阿弥陀签（Amida-kuji）是一种在日本流行的彩票游戏，可以用来将 $w$ 个奖品分配给 $w$ 个人。 该游戏由 $w$ 条竖直的线段（称为“腿”）和一些连接相邻腿的水平横杆组成。 每个人从腿的顶部出发，奖品放在腿的底部。 为了确定第 $i$ 个人获得哪个奖品，需要从第 $i$ 条腿的顶部出发，遇到横杆时就切换到相邻的腿，一直走到最底部。 你可以在下图（图 J.1）中看到这个游戏以及如何追踪路径。

:::align{center} 草莓采摘游戏，图片来自 Nanao Wagatsuma :::

你希望通过移除一些横杆，使得对于每个 $i$，第 $i$ 个人都能获得第 $i$ 个奖品。 由于你不想被发现，你希望移除的横杆数量尽可能少。

:::align{center}

图 J.1：阿弥陀签游戏的可视化。第一个人最终连接到第三个奖品。这也是样例输入 2 在所有连接加上后、未移除任何连接时的状态。要让第 $i$ 个人连接到第 $i$ 个奖品，只需移除第 2、3 条腿之间的两根横杆，以及第 3、4 条腿之间最上方的一根横杆。这是唯一的最优解。 :::

在本题中，初始游戏没有任何横杆。 然后，横杆会被逐个添加或移除。 每次变化后，你都需要计算，当前状态下，最少需要移除多少根横杆，才能使得对于每个 $i$，第 $i$ 个人获得第 $i$ 个奖品。 注意，通过移除所有横杆总是可以实现这一目标。

Input Format

输入包含：

• 一行，包含三个整数 $w, h, q$（$2 \leq w \leq 20$，$1 \leq h, q \leq 2 \cdot 10^5$），分别表示腿的数量、腿的高度和操作次数。
• 接下来 $q$ 行，每行包含三个整数 $y, x_1, x_2$（$1 \leq y \leq h$，$1 \leq x_1, x_2 \leq w$），表示在高度 $y$ 处、腿 $x_1$ 和 $x_2$ 之间添加或移除一根横杆。如果该位置已有横杆，则移除；否则添加。保证 $x_1$ 和 $x_2$ 是相邻的，即 $|x_1 - x_2| = 1$。

保证任意时刻所有横杆在同一高度的位置都不同。

Output Format

每次操作后，输出一个整数，表示当前状态下，最少需要移除多少根横杆，才能使得对于每个 $i$，第 $i$ 个人获得第 $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

Hint

由 ChatGPT 4.1 翻译