409254: GYM103469 F 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.

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

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