В прямоугольной комнате размером n на m метров расположено k датчиков, датчик номер i расположен в точке с координатами (xi, yi). Все датчики расположены в различных точках, находящихся строго внутри прямоугольника.
Противоположные углы комнаты находятся в точках с координатами (0, 0) и (n, m). Стены комнаты расположены параллельно осям координат.
В момент времени 0, из точки (0, 0) в направлении точки (1, 1) выпускается лазерный луч. Луч летит со скоростью 
метров в секунду. Таким образом, луч окажется в точке (1, 1) ровно через одну секунду после старта.
При столкновении со стеной луч отражается по закону, что угол падения равен углу отражения. При попадании луча в любой из четырёх углов комнаты он останавливается.
Определите для каждого датчика первый момент времени, когда луч пройдет сквозь точку, содержащую этот датчик. Для датчиков, через которые луч не пройдёт, выведите - 1.
Выходные данные
Выведите k целых чисел, i-е из которых должно равняться времени в секундах, через которое луч пройдёт через i-й датчик, или - 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). В этом примере луч остановится в точке (0, 4) через 12 секунд после вылета. За это время он отразится от стен в точках (3, 3), (2, 4), (0, 2), (2, 0) и (3, 1).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 4
1 1
1 2
2 1
2 2
|
1
-1
-1
2
|
|
2
|
3 4 6
1 1
2 1
1 2
2 2
1 3
2 3
|
1
-1
-1
2
5
-1
|
|
3
|
7 4 5
1 3
2 2
5 1
5 3
4 3
|
13
2
9
5
-1
|