Quaternion inverse

A quaternion extends the complex numbers. It is written with three imaginary units $i$, $j$, $k$ that satisfy $i^2 = j^2 = k^2 = ijk = -1$, so it has four real components. This problem deals only with the quaternions in the set below, called restricted quaternions.

$a + bi + cj + dk \qquad (a, b, c, d \text{ are integers with } 0 \le a, b, c, d < M)$

Because of the relations among $i$, $j$, $k$, the product of two ordinary quaternions is the following.

The product of two restricted quaternions is defined as the product of the same two quaternions taken as ordinary quaternions, with every integer component replaced by its remainder modulo $M$.

Given $M$ and a restricted quaternion $A$, find the restricted quaternion $B$ with $AB = 1$.

The first line has two natural numbers $M$ and $T$ ($1 \le T \le 100000$), separated by a space. $M$ is prime, so its only divisors are 1 and itself, and $2 \le M \le 100000$.

Each of the next $T$ lines has four integers $a$, $b$, $c$, $d$ ($0 \le a, b, c, d < M$) separated by spaces, and they describe $A = a + bi + cj + dk$.

For each $A$, print on one line the four integers $a$, $b$, $c$, $d$ of the restricted quaternion $B = a + bi + cj + dk$ with $AB = 1$, separated by spaces. At most one such $B$ exists, so the answer is unique. If there is no such $B$, print 0 four times, separated by spaces.