사원수의 역원

사원수(quaternion)는 복소수를 확장해 만든 수 체계다. $i^2 = j^2 = k^2 = ijk = -1$을 만족하는 세 허수 단위 $i$, $j$, $k$로 표현하며, 실수 성분을 네 개 가진다. 이 문제에서는 아래 집합에 속하는 사원수만 다루고, 이를 제한된 사원수라고 부른다.

$a + bi + cj + dk \qquad (a, b, c, d\text{는 } 0 \text{ 이상 } M \text{ 미만의 정수})$

$i$, $j$, $k$ 사이의 성질 때문에 보통의 사원수 두 개를 곱하면 아래 결과가 나온다.

제한된 사원수 두 개의 곱은, 이 둘을 보통의 사원수로 보고 곱한 결과에서 각 정수 성분을 $M$으로 나눈 나머지로 바꾼 값으로 정의한다.

$M$과 제한된 사원수 $A$가 주어질 때, $AB = 1$을 만족하는 제한된 사원수 $B$를 구하여라.

첫 줄에 자연수 $M$과 $T$ ($1 \le T \le 100000$)가 공백으로 구분되어 주어진다. $M$은 소수이고, 즉 약수가 1과 자기 자신뿐이며, $2 \le M \le 100000$이다.

이어지는 $T$개의 줄에는 각각 $A$를 나타내는 네 정수 $a$, $b$, $c$, $d$ ($0 \le a, b, c, d < M$)가 공백으로 구분되어 주어진다. 이때 $A = a + bi + cj + dk$이다.

$A$가 주어질 때마다 $AB = 1$을 만족하는 제한된 사원수 $B = a + bi + cj + dk$의 네 정수 $a$, $b$, $c$, $d$를 공백으로 구분해 한 줄에 출력한다. 조건을 만족하는 $B$는 존재하면 하나뿐이므로 답은 유일하다. 그런 $B$가 없으면 0을 공백으로 구분해 네 번 출력한다.