J. Магические часы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ученые из Пилтовера заполучили очень загадочные магические часы. Странный ход стрелок натолкнул их на мысль, что в этих часах могут быть зашифрованы важные сведения.

Часы состоят из циферблата на $$$60 \cdot 12 \cdot t$$$ делений, пронумерованных от $$$0$$$ до $$$720t - 1$$$ по часовой стрелке включительно, а также, собственно, из минутной и часовой стрелок. Каждую $$$\frac{1}{t}$$$-ю минуты (назовем этот интервал времени тиком) минутная стрелка проходит $$$12$$$ делений, а часовая — $$$1$$$. Таким образом, на обычных часах с таким устройством за один час, то есть за $$$60$$$ минут, минутная стрелка проходит весь круг, а часовая — $$$\frac{1}{12}$$$-ю круга.

Странность часов заключается в том, что когда на очередном тике минутная стрелка должна обогнать или догнать часовую, она телепортируется в начало. Таким образом, если минутная стрелка указывает на деление номер $$$m$$$, а часовая — на $$$h$$$, и расстояние между ними равно $$$d = (h - m) \bmod (720t)$$$ делений, то если $$$0 \lt d \lt 12$$$, после следующего тика минутная стрелка окажется на нулевом делении (тогда как часовая спокойно продолжит свой ход).

Хеймердингер выдвинул $$$q$$$ теорий относительно природы и способностей таких часов, и для проверки $$$i$$$-й теории нужно научиться отвечать, через сколько времени стрелки из состояния $$$s_{i, 1}$$$ перейдут в состояние $$$s_{i, 2}$$$.

Входные данные

В первой строке ввода через пробел даны два целых числа $$$t$$$ и $$$q$$$ — $$$\frac{1}{720}$$$-я количества делений на часах и количество запросов ($$$1 \leqslant t \leqslant 1500$$$; $$$1 \leqslant q \leqslant 10^6$$$).

В $$$i$$$-й из следующих $$$q$$$ строк дано описание $$$i$$$-го запроса, состоящее из четырех целых чисел $$$h_1$$$, $$$m_1$$$, $$$h_2$$$ и $$$m_2$$$, разделенных пробелами — номеров делений, на которые указывают часовая и минутная стрелка в начальном и конечном состояниях, соответственно ($$$0 \leqslant h_{1,2}, m_{1,2} \lt 720t$$$).

Выходные данные

Выведите $$$q$$$ строк — ответы на все запросы Хеймердингера, каждый в своей строке.

В качестве ответа на запрос выведите минимальное число тиков, спустя которое часы перейдут из состояния $$$(h_1, m_1)$$$ в состояние $$$(h_2, m_2)$$$, либо «-1» (без кавычек), если часы никогда не придут во второе состояния, стартуя из указанного начального.

Примеры
Входные данные
1 4
0 0 1 12
0 0 60 0
11 0 12 0
12 0 13 0
Выходные данные
1
60
1
-1
Входные данные
2 5
1201 1317 588 396
658 1196 102 84
442 8 1246 1200
79 0 739 0
355 286 98 72
Выходные данные
827
-1
-1
660
5503