该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

在一个 $n \times m$ 的二维整数格点矩形区域内（格点坐标范围为 $1 \le x \le n, 1 \le y \le m$），依次放入 $k$ 个小球。

每个小球 $i$ 的初始状态由初始位置 $(x_i, y_i)$ 和初始速度向量 $(v_{x_i}, v_{y_i})$ 定义，其中 $v_{x_i}, v_{y_i} \in \{-1, 1\}$。小球在离散的时间步中运动。在每一个时间步中，小球尝试根据当前速度移动到下一个位置，具体的移动逻辑如下：

1. 碰撞判定：对于每一个维度，独立判断在该维度上是否即将运动到台球桌外。
   • 如果 $1 \le x + v_x \le n$，则水平速度 $v_x$ 保持不变。
   • 如果 $x + v_x < 1$ 或 $x + v_x > n$，则该维度的方向发生改变，即 $v_x \leftarrow -v_x$。
   • 垂直维度 $y$ 同理：如果 $y + v_y < 1$ 或 $y + v_y > m$，则 $v_y \leftarrow -v_y$。
2. 位置更新：在确定了最终的速度方向后，小球移动到新位置 $(x + v_x, y + v_y)$。

可以前往样例解释以进一步理解具体的运动逻辑。

不同小球之间相互独立，即使处于同一位置也不会发生碰撞。小球会无限运动下去。对于每个 $i \in \{1, 2, \dots, k\}$，请你求出：在第 $i$ 个小球放下后，在无限时间里，至少被一个小球经过的格点数量总和

Input

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试数据的组数。

对于每组测试数据：

• 第一行包含三个整数 $n, m, k$（$2 \le n, m \le 10^6, 1\le k\le 10^6$），分别表示网格的宽度、高度和小球的数量。
• 接下来 $k$ 行，第 $i$ 行包含四个整数 $x_i, y_i, v_{x_i}, v_{y_i}$（$1 \le x_i \le n, 1 \le y_i \le m, v_{x_i}, v_{y_i} \in \{-1, 1\}$），表示第 $i$ 个小球的初始位置和速度方向。

数据保证所有测试数据的 $\sum n, \sum m, \sum k$ 均不超过 $10^6$。

Output

对于每组测试数据，输出一行 $k$ 个整数，第 $i$ 个整数表示加入前 $i$ 个小球后，被经过的格点总数。

Samples

1
3 3 3
2 1 1 1
1 1 1 1
3 1 1 -1

4 7 9

Notes

在 $3 \times 3$ 的网格中：

1. 第 1 个球从 $(2, 1)$ 出发，速度为 $(1, 1)$：
   • $(2, 1) \to (3, 2)$ （撞右墙，$v_x$ 变为 $-1$） $\to (2, 3)$ （撞上墙，$v_y$ 变为 $-1$） $\to (1, 2)$ （撞左墙，$v_x$ 变为 $1$） $\to (2, 1)$。
   • 轨迹点集：$\{(2,1), (3,2), (2,3), (1,2)\}$，共 4 个点。
2. 第 2 个球从 $(1, 1)$ 出发，速度为 $(1, 1)$：
   • $(1, 1) \to (2, 2) \to (3, 3)$ （双向撞墙，$v_x, v_y$ 均取反） $\to (2, 2) \dots$
   • 轨迹点集：$\{(1,1), (2,2), (3,3)\}$。
   • 前两个球的并集为 $\{(2,1), (3,2), (2,3), (1,2), (1,1), (2,2), (3,3)\}$，共 7 个点。
3. 第 3 个球从 $(3, 1)$ 出发，速度为 $(1, -1)$：
   • $(3, 1) \to (2, 2) \to (1, 3) \to (2, 2) \dots$
   • 轨迹点集：$\{(3,1), (2,2), (1,3)\}$。注意 $(2,2)$ 之前已被小球 2 经过。
   • 前三个球的并集包含网格内所有 9 个格点。