#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define v2i vector<vi>
#define v3i vector<v2i>
#define quicksilver ios_base::sync_with_stdio(0), cin.tie(0)
const int N = 2e5 + 5;
int r, n, n_, m;
int x[2][2];
int **IDENTITY;
int ***st;
void f(int sti, int **a, int **b)
{
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
{
for (int k = 0; k < 2; k++)
st[sti][i][j] = (st[sti][i][j] + a[i][k] * b[k][j]);
st[sti][i][j] %= r;
}
}
void f1(int sti, int ll, int rr, int ix, int **v)
{
if (ll == rr)
f(sti, v, IDENTITY);
else
{
int m = (ll + rr) >> 1;
if (ix <= m)
f1(2 * sti + 1, ll, m, ix, v);
else
f1(2 * sti + 2, m + 1, rr, ix, v);
f(sti, st[2 * sti + 1], st[2 * sti + 2]);
}
}
int **f2(int sti, int ll, int rr, int lq, int rq)
{
int **C = new int *[2];
C[0] = new int[2];
C[1] = new int[2];
if (rr < lq || rq < ll)
{
C[0][0] = IDENTITY[0][0];
C[0][1] = IDENTITY[0][1];
C[1][0] = IDENTITY[1][0];
C[1][1] = IDENTITY[1][1];
return C;
}
else if (lq <= ll && rr <= rq)
{
C[0][0] = st[sti][0][0];
C[0][1] = st[sti][0][1];
C[1][0] = st[sti][1][0];
C[1][1] = st[sti][1][1];
return C;
}
else
{
int m = (ll + rr) >> 1;
int **A = f2(2 * sti + 1, ll, m, lq, rq);
int **B = f2(2 * sti + 2, m + 1, rr, lq, rq);
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
{
C[i][j] = 0;
for (int k = 0; k < 2; k++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]);
C[i][j] %= r;
}
return C;
}
}
signed main()
{
quicksilver;
cin >> r >> n >> m;
IDENTITY = new int *[2];
IDENTITY[0] = new int[2], IDENTITY[1] = new int[2];
IDENTITY[0][0] = IDENTITY[1][1] = 1;
IDENTITY[0][1] = IDENTITY[1][0] = 0;
st = new int **[4 * N];
for (int i = 0; i < 4 * N; i++)
{
st[i] = new int *[2];
st[i][0] = new int[2], st[i][1] = new int[2];
st[i][0][0] = st[i][0][1] = st[i][1][0] = st[i][1][1] = 0;
}
n_ = 1 << (__lg(n) + 1);
if ((n & (n - 1)) == 0)
n_ >>= 1;
int **x = new int *[2];
x[0] = new int[2], x[1] = new int[2];
for (int i = 0; i < n; i++)
{
cin >> x[0][0] >> x[0][1] >> x[1][0] >> x[1][1];
f1(0, 0, n_ - 1, i, x);
}
cout << "\n\n\n";
for (int i = 0; i < m; i++)
{
int l, r;
cin >> l >> r;
l--, r--;
int **R = new int *[2];
R[0] = new int[2], R[1] = new int[2];
int **RT = f2(0, 0, n_ - 1, l, r);
cout << RT[0][0] << ' ' << RT[0][1] << '\n';
cout << RT[1][0] << ' ' << RT[1][1] << '\n';
cout << '\n';
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+CiNkZWZpbmUgdjJpIHZlY3Rvcjx2aT4KI2RlZmluZSB2M2kgdmVjdG9yPHYyaT4KI2RlZmluZSBxdWlja3NpbHZlciBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApLCBjaW4udGllKDApCgpjb25zdCBpbnQgTiA9IDJlNSArIDU7CmludCByLCBuLCBuXywgbTsKaW50IHhbMl1bMl07CmludCAqKklERU5USVRZOwppbnQgKioqc3Q7Cgp2b2lkIGYoaW50IHN0aSwgaW50ICoqYSwgaW50ICoqYikKewogICAgZm9yIChpbnQgaSA9IDA7IGkgPCAyOyBpKyspCiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCAyOyBqKyspCiAgICAgICAgewogICAgICAgICAgICBmb3IgKGludCBrID0gMDsgayA8IDI7IGsrKykKICAgICAgICAgICAgICAgIHN0W3N0aV1baV1bal0gPSAoc3Rbc3RpXVtpXVtqXSArIGFbaV1ba10gKiBiW2tdW2pdKTsKCiAgICAgICAgICAgIHN0W3N0aV1baV1bal0gJT0gcjsKICAgICAgICB9Cn0KCnZvaWQgZjEoaW50IHN0aSwgaW50IGxsLCBpbnQgcnIsIGludCBpeCwgaW50ICoqdikKewogICAgaWYgKGxsID09IHJyKQogICAgICAgIGYoc3RpLCB2LCBJREVOVElUWSk7CiAgICBlbHNlCiAgICB7CiAgICAgICAgaW50IG0gPSAobGwgKyBycikgPj4gMTsKICAgICAgICBpZiAoaXggPD0gbSkKICAgICAgICAgICAgZjEoMiAqIHN0aSArIDEsIGxsLCBtLCBpeCwgdik7CiAgICAgICAgZWxzZQogICAgICAgICAgICBmMSgyICogc3RpICsgMiwgbSArIDEsIHJyLCBpeCwgdik7CgogICAgICAgIGYoc3RpLCBzdFsyICogc3RpICsgMV0sIHN0WzIgKiBzdGkgKyAyXSk7CiAgICB9Cn0KCmludCAqKmYyKGludCBzdGksIGludCBsbCwgaW50IHJyLCBpbnQgbHEsIGludCBycSkKewogICAgaW50ICoqQyA9IG5ldyBpbnQgKlsyXTsKICAgIENbMF0gPSBuZXcgaW50WzJdOwogICAgQ1sxXSA9IG5ldyBpbnRbMl07CiAgICBpZiAocnIgPCBscSB8fCBycSA8IGxsKQogICAgewogICAgICAgIENbMF1bMF0gPSBJREVOVElUWVswXVswXTsKICAgICAgICBDWzBdWzFdID0gSURFTlRJVFlbMF1bMV07CiAgICAgICAgQ1sxXVswXSA9IElERU5USVRZWzFdWzBdOwogICAgICAgIENbMV1bMV0gPSBJREVOVElUWVsxXVsxXTsKCiAgICAgICAgcmV0dXJuIEM7CiAgICB9CiAgICBlbHNlIGlmIChscSA8PSBsbCAmJiByciA8PSBycSkKICAgIHsKICAgICAgICBDWzBdWzBdID0gc3Rbc3RpXVswXVswXTsKICAgICAgICBDWzBdWzFdID0gc3Rbc3RpXVswXVsxXTsKICAgICAgICBDWzFdWzBdID0gc3Rbc3RpXVsxXVswXTsKICAgICAgICBDWzFdWzFdID0gc3Rbc3RpXVsxXVsxXTsKCiAgICAgICAgcmV0dXJuIEM7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgaW50IG0gPSAobGwgKyBycikgPj4gMTsKICAgICAgICBpbnQgKipBID0gZjIoMiAqIHN0aSArIDEsIGxsLCBtLCBscSwgcnEpOwogICAgICAgIGludCAqKkIgPSBmMigyICogc3RpICsgMiwgbSArIDEsIHJyLCBscSwgcnEpOwoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IDI7IGkrKykKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCAyOyBqKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIENbaV1bal0gPSAwOwogICAgICAgICAgICAgICAgZm9yIChpbnQgayA9IDA7IGsgPCAyOyBrKyspCiAgICAgICAgICAgICAgICAgICAgQ1tpXVtqXSA9IChDW2ldW2pdICsgQVtpXVtrXSAqIEJba11bal0pOwoKICAgICAgICAgICAgICAgIENbaV1bal0gJT0gcjsKICAgICAgICAgICAgfQoKICAgICAgICByZXR1cm4gQzsKICAgIH0KfQoKc2lnbmVkIG1haW4oKQp7CiAgICBxdWlja3NpbHZlcjsKICAgIGNpbiA+PiByID4+IG4gPj4gbTsKICAgIElERU5USVRZID0gbmV3IGludCAqWzJdOwogICAgSURFTlRJVFlbMF0gPSBuZXcgaW50WzJdLCBJREVOVElUWVsxXSA9IG5ldyBpbnRbMl07CiAgICBJREVOVElUWVswXVswXSA9IElERU5USVRZWzFdWzFdID0gMTsKICAgIElERU5USVRZWzBdWzFdID0gSURFTlRJVFlbMV1bMF0gPSAwOwoKICAgIHN0ID0gbmV3IGludCAqKls0ICogTl07CiAgICBmb3IgKGludCBpID0gMDsgaSA8IDQgKiBOOyBpKyspCiAgICB7CiAgICAgICAgc3RbaV0gPSBuZXcgaW50ICpbMl07CiAgICAgICAgc3RbaV1bMF0gPSBuZXcgaW50WzJdLCBzdFtpXVsxXSA9IG5ldyBpbnRbMl07CiAgICAgICAgc3RbaV1bMF1bMF0gPSBzdFtpXVswXVsxXSA9IHN0W2ldWzFdWzBdID0gc3RbaV1bMV1bMV0gPSAwOwogICAgfQoKICAgIG5fID0gMSA8PCAoX19sZyhuKSArIDEpOwogICAgaWYgKChuICYgKG4gLSAxKSkgPT0gMCkKICAgICAgICBuXyA+Pj0gMTsKCiAgICBpbnQgKip4ID0gbmV3IGludCAqWzJdOwogICAgeFswXSA9IG5ldyBpbnRbMl0sIHhbMV0gPSBuZXcgaW50WzJdOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQogICAgewogICAgICAgIGNpbiA+PiB4WzBdWzBdID4+IHhbMF1bMV0gPj4geFsxXVswXSA+PiB4WzFdWzFdOwoKICAgICAgICBmMSgwLCAwLCBuXyAtIDEsIGksIHgpOwogICAgfQoKICAgIGNvdXQgPDwgIlxuXG5cbiI7CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspCiAgICB7CiAgICAgICAgaW50IGwsIHI7CiAgICAgICAgY2luID4+IGwgPj4gcjsKICAgICAgICBsLS0sIHItLTsKCiAgICAgICAgaW50ICoqUiA9IG5ldyBpbnQgKlsyXTsKICAgICAgICBSWzBdID0gbmV3IGludFsyXSwgUlsxXSA9IG5ldyBpbnRbMl07CiAgICAgICAgaW50ICoqUlQgPSBmMigwLCAwLCBuXyAtIDEsIGwsIHIpOwoKICAgICAgICBjb3V0IDw8IFJUWzBdWzBdIDw8ICcgJyA8PCBSVFswXVsxXSA8PCAnXG4nOwogICAgICAgIGNvdXQgPDwgUlRbMV1bMF0gPDwgJyAnIDw8IFJUWzFdWzFdIDw8ICdcbic7CiAgICAgICAgY291dCA8PCAnXG4nOwogICAgfQoKICAgIHJldHVybiAwOwp9