给定一个质数 $p$ 和一对整数 $(a, b)$，使得它们的和不能被 $p$ 整除。在一次操作中，你可以执行以下操作之一：

• 将 $(a, b)$ 替换为 $(2a \pmod p, (b + p - a) \pmod p)$
• 将 $(a, b)$ 替换为 $((a + p - b) \pmod p, 2b \pmod p)$

你需要回答 $q$ 个询问。对于第 $i$ 个询问，求出将数对 $(a_i, b_i)$ 变换为数对 $(c_i, d_i)$ 所需的最少操作次数，或者确定这是不可能的。

注意，数字的顺序很重要。例如，对于 $p = 3$，$(1, 2)$ 和 $(2, 1)$ 之间的距离是 $1$，而不是 $0$。

输入格式

第一行包含两个整数 $p$ 和 $q$ ($2 \le p \le 10^9 + 7$，$p$ 是质数，$1 \le q \le 10^5$)：表示质数和询问次数。

接下来的 $q$ 行中，第 $i$ 行包含四个整数 $a_i, b_i, c_i, d_i$ ($0 \le a_i, b_i, c_i, d_i < p$，且 $a_i + b_i$ 不能被 $p$ 整除)。

输出格式

对于每个询问，如果无法将 $(a_i, b_i)$ 变换为 $(c_i, d_i)$，输出 $-1$。否则，输出实现该目标所需的最少操作次数。

样例

样例输入 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