Mirko 是国际象棋和编程的狂热爱好者，但普通的国际象棋很快就让他感到无聊，于是他开始研究车（rook）这一棋子。

他找到了一个 $N$ 行 $N$ 列的棋盘，并在上面放置了 $K$ 个车。

Mirko 的游戏规则如下：

1. 每个车的战力由一个整数决定。
2. 一个车可以“看到”与其处于同一行或同一列的所有格子，但不包括它自己所在的格子。
3. 如果一个格子被所有能“看到”它的车的战力进行按位异或（XOR）运算后的结果大于 0，则称该格子被“攻击”。

注意，车所在的格子也可能被攻击，也可能不被攻击。

最初，Mirko 在棋盘上放置了这些车，并会进行 $P$ 次移动。

在每次移动后，请确定有多少个格子被攻击。

每个车都可以移动到整个棋盘上的任意空闲格子（不仅限于沿行列移动）。

输入格式

输入的第一行包含三个整数 $N, K, P$ ($1 \le N \le 1\,000\,000\,000$, $1 \le K \le 100\,000$, $1 \le P \le 100\,000$)。

接下来的 $K$ 行，每行包含三个整数 $R, C, X$ ($1 \le R, C \le N$, $1 \le X \le 1\,000\,000\,000$)，表示最初在格子 $(R, C)$ 上有一个战力为 $X$ 的车。

接下来的 $P$ 行，每行包含四个整数 $R_1, C_1, R_2, C_2$ ($1 \le R_1, C_1, R_2, C_2 \le N$)，表示一个车从格子 $(R_1, C_1)$ 移动到了格子 $(R_2, C_2)$。

保证在任何时刻，同一个格子上不会同时存在两个车。

输出格式

输出必须包含 $P$ 行，第 $k$ 行包含在进行 $k$ 次移动后被攻击的格子总数。

数据范围

对于占总分 25% 的测试数据，$N$ 和 $K$ 不超过 100。

样例

输入样例 1

2 2 2
1 1 1
2 2 1
2 2 2 1
1 1 1 2

输出样例 1

4
0

输入样例 2

2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2

输出样例 2

4
2

输入样例 3

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

输出样例 3

6
7
7
9

说明

样例 1 解释

在第一次移动后，棋盘上的每个格子都被攻击。

例如，格子 $(1, 1)$ 只能被一个车看到，因此该格子的总异或值为 1。在第二次移动后，没有任何格子被攻击。例如，格子 $(1, 1)$ 可以被两个车看到，因此该格子的总异或值为 0。