J. Magical Clock
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Scientists have acquired very mysterious magical clock. The strange movement of the hands led them to believe that important information might be encoded in that clock.

The clock consists of a dial with $$$60 \cdot 12 \cdot t$$$ divisions, numbered from $$$0$$$ to $$$720t - 1$$$ clockwise, as well as the minute and hour hands. Every $$$\frac{1}{t}$$$-th minute (let's call this time interval a tick), the minute hand moves $$$12$$$ divisions, while the hour hand moves $$$1$$$ division. Thus, on a regular clock with this mechanism, in one hour (that is, in $$$60$$$ minutes) the minute hand completes a full circle, while the hour hand completes $$$\frac{1}{12}$$$ of a circle.

The peculiarity of this clock is that when at the next tick the minute hand is supposed to overtake or catch up with the hour hand, it teleports back to the start. Therefore, if the minute hand points to division number $$$m$$$, and the hour hand points to $$$h$$$, and the distance between them is $$$d = (h - m) \bmod (720t)$$$ divisions, then if $$$0 \lt d \lt 12$$$, after the next tick, the minute hand will be at the zero division (while the hour hand continues its movement).

Scientists have proposed $$$q$$$ theories regarding the nature and capabilities of such clock, and to verify the $$$i$$$-th theory, one needs to learn how long it takes for the hands to transition from state $$$s_{i, 1}$$$ to state $$$s_{i, 2}$$$. Find the answer for each such query.

Input

The first line of input contains two integers $$$t$$$ and $$$q$$$ — the $$$\frac{1}{720}$$$-th number of divisions on the clocks and the number of queries ($$$1 \leq t \leq 1500$$$; $$$1 \leq q \leq 5 \cdot 10^5$$$).

The $$$i$$$-th of the following $$$q$$$ lines contains the description of the $$$i$$$-th query which consists of four integers $$$h_1$$$, $$$m_1$$$, $$$h_2$$$, and $$$m_2$$$ — the numbers of the divisions to which the hour and minute hands point in the initial and final states, respectively ($$$0 \leq h_{1,2}, m_{1,2} \lt 720t$$$).

Output

Output $$$q$$$ lines — the answers to all of the scientists' queries, each on its own line.

As an answer to the query, output the minimum number of ticks after which the clock will transition from state $$$(h_1, m_1)$$$ to state $$$(h_2, m_2)$$$, or "-1" (without quotes) if the clock will never reach the second state starting from the specified initial state.

Examples
Input
1 4
0 0 1 12
0 0 60 0
11 0 12 0
12 0 13 0
Output
1
60
1
-1
Input
2 5
1201 1317 588 396
658 1196 102 84
442 8 1246 1200
79 0 739 0
355 286 98 72
Output
827
-1
-1
660
5503