#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;
v3i st(4 * N, v2i(2, vi(2, 0)));
v2i IDENTITY(2, vi(2, 0));
v2i C(2, vi(2, 0));
v2i R(2, vi(2, 0));
v2i x(2, vi(2));
void f(int sti, v2i a, v2i 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, v2i 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]);
}
}
v2i f2(int sti, int ll, int rr, int lq, int rq)
{
if (rr < lq || rq < ll)
return IDENTITY;
else if (lq <= ll && rr <= rq)
return st[sti];
else
{
int m = (ll + rr) >> 1;
v2i A = f2(2 * sti + 1, ll, m, lq, rq);
v2i 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[0][0] = IDENTITY[1][1] = 1;
n_ = 1 << (__lg(n) + 1);
if ((n & (n - 1)) == 0)
n_ >>= 1;
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);
}
for (int i = 0; i < m; i++)
{
int l, r;
cin >> l >> r;
l--, r--;
R = f2(0, 0, n_ - 1, l, r);
cout << R[0][0] << ' ' << R[0][1] << '\n';
cout << R[1][0] << ' ' << R[1][1] << '\n';
cout << '\n';
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+CiNkZWZpbmUgdjJpIHZlY3Rvcjx2aT4KI2RlZmluZSB2M2kgdmVjdG9yPHYyaT4KI2RlZmluZSBxdWlja3NpbHZlciBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApLCBjaW4udGllKDApCgpjb25zdCBpbnQgTiA9IDJlNSArIDU7CmludCByLCBuLCBuXywgbTsKdjNpIHN0KDQgKiBOLCB2MmkoMiwgdmkoMiwgMCkpKTsKdjJpIElERU5USVRZKDIsIHZpKDIsIDApKTsKdjJpIEMoMiwgdmkoMiwgMCkpOwp2MmkgUigyLCB2aSgyLCAwKSk7CnYyaSB4KDIsIHZpKDIpKTsKCnZvaWQgZihpbnQgc3RpLCB2MmkgYSwgdjJpIGIpCnsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMjsgaSsrKQogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgMjsgaisrKQogICAgICAgIHsKICAgICAgICAgICAgZm9yIChpbnQgayA9IDA7IGsgPCAyOyBrKyspCiAgICAgICAgICAgICAgICBzdFtzdGldW2ldW2pdID0gKHN0W3N0aV1baV1bal0gKyBhW2ldW2tdICogYltrXVtqXSk7CgogICAgICAgICAgICBzdFtzdGldW2ldW2pdICU9IHI7CiAgICAgICAgfQp9Cgp2b2lkIGYxKGludCBzdGksIGludCBsbCwgaW50IHJyLCBpbnQgaXgsIHYyaSB2KQp7CiAgICBpZiAobGwgPT0gcnIpCiAgICAgICAgZihzdGksIHYsIElERU5USVRZKTsKICAgIGVsc2UKICAgIHsKICAgICAgICBpbnQgbSA9IChsbCArIHJyKSA+PiAxOwogICAgICAgIGlmIChpeCA8PSBtKQogICAgICAgICAgICBmMSgyICogc3RpICsgMSwgbGwsIG0sIGl4LCB2KTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIGYxKDIgKiBzdGkgKyAyLCBtICsgMSwgcnIsIGl4LCB2KTsKCiAgICAgICAgZihzdGksIHN0WzIgKiBzdGkgKyAxXSwgc3RbMiAqIHN0aSArIDJdKTsKICAgIH0KfQoKdjJpIGYyKGludCBzdGksIGludCBsbCwgaW50IHJyLCBpbnQgbHEsIGludCBycSkKewogICAgaWYgKHJyIDwgbHEgfHwgcnEgPCBsbCkKICAgICAgICByZXR1cm4gSURFTlRJVFk7CiAgICBlbHNlIGlmIChscSA8PSBsbCAmJiByciA8PSBycSkKICAgICAgICByZXR1cm4gc3Rbc3RpXTsKICAgIGVsc2UKICAgIHsKICAgICAgICBpbnQgbSA9IChsbCArIHJyKSA+PiAxOwogICAgICAgIHYyaSBBID0gZjIoMiAqIHN0aSArIDEsIGxsLCBtLCBscSwgcnEpOwogICAgICAgIHYyaSBCID0gZjIoMiAqIHN0aSArIDIsIG0gKyAxLCByciwgbHEsIHJxKTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCAyOyBpKyspCiAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgMjsgaisrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBDW2ldW2pdID0gMDsKICAgICAgICAgICAgICAgIGZvciAoaW50IGsgPSAwOyBrIDwgMjsgaysrKQogICAgICAgICAgICAgICAgICAgIENbaV1bal0gPSAoQ1tpXVtqXSArIEFbaV1ba10gKiBCW2tdW2pdKTsKCiAgICAgICAgICAgICAgICBDW2ldW2pdICU9IHI7CiAgICAgICAgICAgIH0KCiAgICAgICAgcmV0dXJuIEM7CiAgICB9Cn0KCnNpZ25lZCBtYWluKCkKewogICAgcXVpY2tzaWx2ZXI7CiAgICBjaW4gPj4gciA+PiBuID4+IG07CiAgICBJREVOVElUWVswXVswXSA9IElERU5USVRZWzFdWzFdID0gMTsKCiAgICBuXyA9IDEgPDwgKF9fbGcobikgKyAxKTsKICAgIGlmICgobiAmIChuIC0gMSkpID09IDApCiAgICAgICAgbl8gPj49IDE7CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICB7CiAgICAgICAgY2luID4+IHhbMF1bMF0gPj4geFswXVsxXSA+PiB4WzFdWzBdID4+IHhbMV1bMV07CgogICAgICAgIGYxKDAsIDAsIG5fIC0gMSwgaSwgeCk7CiAgICB9CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspCiAgICB7CiAgICAgICAgaW50IGwsIHI7CiAgICAgICAgY2luID4+IGwgPj4gcjsKICAgICAgICBsLS0sIHItLTsKCiAgICAgICAgUiA9IGYyKDAsIDAsIG5fIC0gMSwgbCwgcik7CiAgICAgICAgY291dCA8PCBSWzBdWzBdIDw8ICcgJyA8PCBSWzBdWzFdIDw8ICdcbic7CiAgICAgICAgY291dCA8PCBSWzFdWzBdIDw8ICcgJyA8PCBSWzFdWzFdIDw8ICdcbic7CiAgICAgICAgY291dCA8PCAnXG4nOwogICAgfQoKICAgIHJldHVybiAwOwp9