Quaternion inverse Batch Compilation commands

**사원수(Quaternion)**는 복소수를 확장해 만든 수 체계이다. 사원수는 $i^{2} = j^{2} = k^{2} = ijk = - 1$을 만족하는 세 복소수 $i, j, k$를 이용해 표현되어 네 개의 실수 성분을 가지는데, 우리는 앞으로 아래 집합에 속하는 사원수만을 고려할 것이다. 이를 제한된 사원수라고 하자.

a + bi + cj + dk (a, b, c, d는 0 이상 M 미만의 정수)

다음으로 두 사원수의 곱셈에 관하여 생각해 보자. $i, j, k$ 사이의 성질 때문에, 두 일반적인 사원수를 곱하면 아래와 같은 결과가 나온다.

(a1 + b1i + c1j + d1k) × (a2 + b2i + c2j + d2k)  = (a1a2 - b1b2 - c1c2 - d1d2) + (a1b2 + b1a2 + c1d2 - d1c2) i  + (a1c2 - b1d2 + c1a2 + d1b2) j + (a1d2 + b1c2 - c1b2 + d1a2) k

우리는 두 제한된 사원수를 곱한 결과를 이 두 사원수를 일반적인 사원수로 취급하여 곱하였을 때의 결과에서 각 정수 성분을 $M$으로 나눈 나머지로 치환한 것으로 생각할 것이다. $M$과 제한된 사원수 $A$가 주어질 때, $AB = 1$이 되는 제한된 사원수 $B$ 중 하나를 구하여라.

입력 형식

첫 번째 줄에 자연수 $M$과 $T$ ($1 \le T \le 100,000$)가 공백으로 구분되어 주어진다. $M$은 소수이다. (즉 약수가 1과 자기 자신밖에 없다.)

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

쉬운 문제에서는 $2 \le M \le 7$인 입력이 주어진다.

어려운 문제에서는 $2 \le M \le 100,000$인 입력이 주어진다.

출력 형식

각 $A$가 주어질 때마다, $AB = 1$을 만족하는 $B = a + bi + cj + dk$들 중 하나를 나타내는 네 개의 정수 $a, b, c, d$를 공백으로 구분하여 $T$ 줄에 걸쳐 출력하면 된다. 만약 이런 $B$가 존재하지 않으면 0을 공백으로 구분하여 네 번 출력하면 된다.

입력

5 3
2 3 2 1
3 1 3 2
3 2 4 1

출력

4 4 1 3
1 3 4 1
0 0 0 0