28609번 - Магические часы 다국어

문제

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

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

Странность часов заключается в том, что когда на очередном тике минутная стрелка должна обогнать или догнать часовую, она телепортируется в начало. Таким образом, если минутная стрелка указывает на деление номер $m,ドル а часовая --- на $h,ドル и расстояние между ними равно $d = (h - m) \bmod (720t)$ делений, то если 0ドル < d < 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} < 720t$).

출력

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

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

제한

힌트