# Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) C. Ray Tracing

C. Ray Tracing

There are k sensors located in the rectangular room of size n × m meters. The i-th sensor is located at point (xi, yi). All sensors are located at distinct points strictly inside the rectangle.

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

At the moment 0, from the point (0, 0) the laser ray is released in the direction of point (1, 1). The ray travels with a speed of meters per second. Thus, the ray will reach the point (1, 1) in exactly one second after the start.

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

For each sensor you have to determine the first moment of time when the ray will pass through the point where this sensor is located. If the ray will never pass through this point, print  - 1 for such sensors.

Input

The first line of the input contains three integers nm and k (2 ≤ n, m ≤ 100 000, 1 ≤ k ≤ 100 000) — lengths of the room‘s walls and the number of sensors.

Each of the following k lines contains two integers xi and yi (1 ≤ xi ≤ n - 1, 1 ≤ yi ≤ m - 1) — coordinates of the sensors. It‘s guaranteed that no two sensors are located at the same point.

Output

Print k integers. The i-th of them should be equal to the number of seconds when the ray first passes through the point where the i-th sensor is located, or  - 1 if this will never happen.

Examples

input

`3 3 41 11 22 12 2`

output

`1-1-12`

input

`3 4 61 12 11 22 21 32 3`

output

`1-1-125-1`

input

`7 4 51 32 25 15 34 3`

output

```13295-1

```然后就可以枚举光线路径斜线上的传感仪更新答案，再更新光线撞墙的坐标和光线方向，直到光线到达角落。
```
```#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 10;
vector< pair<int, int> > va[maxn], vb[maxn];
ll ans[maxn];
int main()
{
int n, m, k;
memset(ans, 0x3f, sizeof(ans));
scanf("%d %d %d", &n, &m, &k);
for(int i = 1; i <= k; i++) {
int x, y;
scanf("%d %d", &x, &y);
va[x+y].emplace_back(i, x);
vb[x-y+m].emplace_back(i, x);
}

int x = 0, y = 0; //定义初始坐标
int dx = 1, dy = 1; //定义初始方向
ll t = 0; //定义初始时间
while(true) {
if(dx == dy) {
for(auto p:vb[x-y+m]) {
ans[p.first] = min(ans[p.first], t + abs(p.second - x));
}
}
else {
for(auto p:va[x+y]) {
ans[p.first] = min(ans[p.first], t + abs(p.second - x));
}
}
int time = 0x3f3f3f3f;
if(dx == -1) time = min(time, x);
else time = min(time, n - x);
if(dy == -1) time = min(time, y);
else time = min(time, m - y);
x = x + time * dx;
y = y + time * dy;
t = time + t;
bool flag1 = (x == 0 || x == n);
bool flag2 = (y == 0 || y == m);
if(flag1 && flag2) break;
if(flag1) dx = -dx;
if(flag2) dy = -dy;
}
for(int i = 1; i <= k; i++) {
if(ans[i] == 0x3f3f3f3f3f3f3f3f) puts("-1");
else printf("%I64d\n", ans[i]);
}
}```

## Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) C 模拟 题意:给的是一个矩形,然后√2 的速度走,如果走到边上就正常反射,走到角上,暂停反射,我们知道要不循环要不暂停,记录走到的点最短时间 /************************************************************************* > File Name: c.cpp > Author: opas_chenxin > Mail: [email protected] > Created Time: 2016年10月08日

## Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) A

Description You are given names of two days of the week. Please, determine whether it is possible that during some non-leap year the first day of some month was equal to the first day of the week you are given, while the first day of the next month w

## Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) B

Description You are given a table consisting of n rows and m columns. Numbers in each row form a permutation of integers from 1 to m. You are allowed to pick two elements in one row and swap them, but no more than once for each row. Also, no more tha

## 模拟。。。 Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) C ## Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) E - Goods transportation 最大流转最小割转dp

E - Goods transportation 思路:这个最大流-> 最小割->dp好巧妙哦. #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PII pair<int, int> #define PLI pair<LL, int> #define ull unsigned long lo

## Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) G - Xor-matic Number of the Graph 线性基好题

G - Xor-matic Number of the Graph 上一道题的加强版本,对于每个联通块需要按位算贡献. #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PII pair<int, int> #define PLI pair<LL, int> #define ull unsigned lo