Time Limit

Problem Statement

Positive integers $K, N$ are given from the input. Initially, a sequence of $2 \times 2$ matrices $X^{(1)}, \dots, X^{(N)}$ is given from the input as $2\times 2$ matrices $A^{(1)}, \dots, A^{(N)}$.
Process the following $Q$ queries in order and output the results.

Each query is a 4-tuple $(i, Y, L, R)$ consisting of an integer $i$ with $1 \leq i \leq N$, a $2\times 2$ matrix $Y$, and integers $L, R$ satisfying $1 \leq L \leq R \leq N$.
Process this query as follows:

1. Assign $Y$ to the matrix $X^{(i)}$.
2. Compute the matrix product $Z = X^{(L)} \cdots X^{(R)} = \begin{pmatrix}a & b \\ c & d\end{pmatrix}$, and find the remainders $a', b', c', d'$ of $a, b, c, d$ divided by $K$ (hereafter called the result of the query).

Here, the remainder of an integer divided by $K$ is always at least $0$ and less than $K$.

Input

$K \ N$
$A^{(1)}_{1, 1} \ A^{(1)}_{1, 2}$
$A^{(1)}_{2, 1} \ A^{(1)}_{2, 2}$
$\vdots$
$A^{(N)}_{1, 1} \ A^{(N)}_{1, 2}$
$A^{(N)}_{2, 1} \ A^{(N)}_{2, 2}$
$Q$
$i_1 \ L_1 \ R_1$
$Y^{(1)}_{1, 1} \ Y^{(1)}_{1, 2}$
$Y^{(1)}_{2, 1} \ Y^{(1)}_{2, 2}$
$\vdots$
$i_Q \ L_Q \ R_Q$
$Y^{(Q)}_{1, 1} \ Y^{(Q)}_{1, 2}$
$Y^{(Q)}_{2, 1} \ Y^{(Q)}_{2, 2}$

$2 \leq K < 2^{31},$
$1 \leq N \leq 10^5,$
$1 \leq Q \leq 10^5,$
$1 \leq i_q \leq N,$
$1 \leq L_q \leq R_q \leq N$
$-10^8 \leq A^{(n)}_{i, j}, \, Y^{(n)}_{i, j} \leq 10^8$ are integers.

Let $A^{(n)} = \begin{pmatrix} A^{(n)}_{1, 1} & A^{(n)}_{1, 2} \\ A^{(n)}_{2, 1} & A^{(n)}_{2, 2}\end{pmatrix}, \ Y^{(q)} = \begin{pmatrix} Y^{(q)}_{1, 1} & Y^{(q)}_{1, 2} \\ Y^{(q)}_{2, 1} & Y^{(q)}_{2, 2}\end{pmatrix}$.
The $q$-th query is $(i_q, Y^{(q)}, L_q, R_q)$.

Output

For each $q$ in order, output the result of the query $a', b', c', d'$ obtained after processing the queries up to the $q$-th in order, in the form

$a' \ b' \\ c' \ d'$

Sample

100 3
1 2
3 4
1 3
5 7
2 4
1 3
2
2 2 3
3 1
-18 5
1 1 2
9 2
8 3

7 15
69 43
91 19
70 23

7 15
69 43

91 19
70 23