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

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

Часы состоят из циферблата на $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 < 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>> (без кавычек), если часы никогда не придут во второе состояния, стартуя из указанного начального.