시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB0000.000%

문제

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.

예제 입력 1

5 10
2 1 3 0
2 1 4 4
1 3 4 0
0 2 0 4
3 3 1 2
0 1 0 1
0 3 0 3
0 1 0 1
1 2 4 4
1 0 1 1

예제 출력 1

2
1
2
-1
-1
0
0
0
1
-1