大小为 n × m 米的矩形房间内有 k 个传感器。第 i 个传感器位于点 (xi, yi)。所有传感器都严格位于矩形内的不同点。
房间的对角位于点 (0, 0) 和 (n, m)。房间的墙壁与坐标轴平行。
在时刻 0,从点 (0, 0) 向点 (1, 1) 的方向释放激光。射线以每秒 $$\sqrt{2}$$ 米的速度传播。因此,射线将在开始后恰好一秒内到达点 (1, 1)。
当光线遇到墙壁时,根据入射角等于反射角的规则进行反射。如果光线到达四个角中的任何一个,它就会立即停止。
对于每个传感器,您必须确定光线穿过该传感器所在点的第一个时刻。如果光线永远不会穿过该点,则为此类传感器打印 - 1。
输入
输入的第一行包含三个整数 n、m 和 k (2 ≤ n, m ≤ 100 000, 1 ≤ k ≤ 100 000) - 房间墙壁的长度和传感器的数量。
以下 k 行中的每一行都包含两个整数 xi 和 yi (1 ≤ xi ≤ n - 1, 1 ≤ yi ≤ m - 1) - 传感器的坐标。确保没有两个传感器位于同一点。
输出
打印 k 个整数。其中第 i 个应该等于光线首次穿过第 i 个传感器所在点时的秒数,如果这种情况永远不会发生,则为 - 1。
示例
输入 #1
3 3 4 1 1 1 2 2 1 2 2
输出 #1
1 -1 -1 2
输入 #2
3 4 6 1 1 2 1 1 2 2 2 1 3 2 3
输出 #2
1 -1 -1 2 5 -1
输入 #3
7 4 5 1 3 2 2 5 1 5 3 4 3
输出 #3
13 2 9 5 -1
注意
在第一个示例中,光线将因此穿过点 (0, 0)、(1, 1)、(2, 2)、(3, 3)。这样,3秒后就会停在(3, 3)点。
在第二个示例中,光线将因此穿过以下点:(0, 0)、(1, 1)、(2, 2)、(3, 3)、(2, 4)、(1, 3)、(0, 2)、(1, 1)、(2, 0)、(3, 1)、(2, 2)、(1, 3)、(0, 4). 12 秒后,射线将停在点 (0, 4)。它将反映在点 (3, 3)、(2, 4)、(0, 2)、(2, 0) 和 (3, 1) 处。