Quaternion inverse Batch 컴파일 명령

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

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

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

입력 형식

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

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

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

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

출력 형식

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