Fancy Formulas

소수 $p$와 두 정수의 쌍 $(a, b)$가 주어지며, $a+b$는 $p$로 나누어떨어지지 않는다. 한 번의 연산으로 다음 중 하나를 할 수 있다.

• $(a, b)$를 $(2a \bmod p, (b+p-a) \bmod p)$로 바꾼다.
• $(a, b)$를 $((a+p-b) \bmod p, 2b \bmod p)$로 바꾼다.

$q$개의 질의에 답해야 한다. $i$번째 질의에서는 쌍 $(a_i, b_i)$를 쌍 $(c_i, d_i)$로 바꾸는 데 필요한 최소 연산 횟수를 구하거나, 불가능하다면 불가능함을 판정한다.

두 수의 순서는 중요하다. 예를 들어 $p = 3$일 때 $(1, 2)$와 $(2, 1)$ 사이의 거리는 $0$이 아니라 $1$이다.

첫째 줄에 두 정수 $p$와 $q$가 주어진다 ($2 \le p \le 10^9 + 7$, $p$는 소수, $1 \le q \le 10^5$). $p$는 소수이고 $q$는 답해야 하는 질의의 수이다.

다음 $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$을 출력한다. 그렇지 않으면 목표를 달성하는 데 필요한 최소 연산 횟수를 출력한다.