Fancy Formulas

You are given a prime $p$ and a pair of integers $(a, b)$ such that their sum is not divisible by $p$. In one operation, you can do one of the following:

• Replace $(a, b)$ with $(2a \bmod p, (b+p-a) \bmod p)$
• Replace $(a, b)$ with $((a+p-b) \bmod p, 2b \bmod p)$

You have to answer $q$ queries. In the $i$-th query, find the smallest number of operations needed to transform the pair $(a_i, b_i)$ into the pair $(c_i, d_i)$, or determine that it is impossible.

Note that the order of numbers matters. For example, for $p = 3$, the distance between $(1, 2)$ and $(2, 1)$ is $1$, not $0$.

The first line contains two integers $p$ and $q$ ($2 \le p \le 10^9 + 7$, $p$ is prime, $1 \le q \le 10^5$): the prime and the number of queries to answer.

The $i$-th of the next $q$ lines contains four integers $a_i$, $b_i$, $c_i$, $d_i$ ($0 \le a_i, b_i, c_i, d_i < p$, and $a_i+b_i$ is not divisible by $p$).

For each query, if it is impossible to transform $(a_i, b_i)$ into $(c_i, d_i)$, output $-1$. Otherwise, output the smallest number of operations required to achieve this goal.