← 返回题目列表

Codeforces · 724/C

C. 光线追踪

中文机器翻译题面 查看原题

大小为 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) 处。