| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 43 | 29 | 28 | 66.667% |
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:
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