Ray Tracing

Problem Source

Codeforces Intel Code Challenge Final Round (Div. 1 + Div. 2) C

Problem Description

There are $k$ sensors located in a rectangular room of size $n \times m$ metres. The $i$-th sensor is located at point $(x_i, y_i)$. All sensors are at distinct points strictly inside the rectangle.

Opposite corners of the room are at points $(0, 0)$ and $(n, m)$. The walls of the room are parallel to the coordinate axes.

At time $0$, a laser ray is released from point $(0, 0)$ in the direction of point $(1, 1)$. The ray travels at a speed of $\sqrt{2}$ metres per second, so it reaches point $(1, 1)$ exactly one second after the start.

When the ray meets a wall it is reflected by the rule that the angle of incidence equals the angle of reflection. If the ray reaches any of the four corners, it stops immediately.

For each sensor, determine the first moment in time when the ray passes through the point where that sensor is located. If the ray never passes through that point, print $-1$ for that sensor.

Input Format

The first line contains three integers $n, m, k$ ($2 \leq n, m \leq 100000$, $1 \leq k \leq 100000$): the lengths of the room's walls and the number of sensors.

Each of the following $k$ lines contains two integers $x_i, y_i$ ($1 \leq x_i \leq n - 1$, $1 \leq y_i \leq m - 1$): the coordinates of a sensor. It is guaranteed that no two sensors are at the same point.

Output Format

Print $k$ integers. The $i$-th of them should be the number of seconds when the ray first passes through the position of the $i$-th sensor, or $-1$ if this never happens.

Sample Input 1

3 3 4
1 1
1 2
2 1
2 2

Sample Output 1

1
-1
-1
2

Sample Input 2

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

Sample Output 2

1
-1
-1
2
5
-1

Sample Input 3

7 4 5
1 3
2 2
5 1
5 3
4 3

Sample Output 3

13
2
9
5
-1