#include <iostream>
#include <fstream>

using namespace std;

int **identityMatrix;
int ***t;

int **matrixTwoByTwoMultiplication(int remainder, int **first, int **second) {
    int **result = new int *[2];
    for (size_t i = 0; i < 2; ++i) {
        result[i] = new int[2];
        for (size_t j = 0; j < 2; ++j) {
            result[i][j] = i == j ? 1 : 0;
        }
    }
    result[0][0] = (((first[0][0] * second[0][0])) + ((first[0][1] * second[1][0]))) % remainder;
    result[0][1] = (((first[0][0] * second[0][1])) + ((first[0][1] * second[1][1]))) % remainder;
    result[1][0] = (((first[1][0] * second[0][0])) + ((first[1][1] * second[1][0]))) % remainder;
    result[1][1] = (((first[1][0] * second[0][1])) + ((first[1][1] * second[1][1]))) % remainder;
    return result;
}

int **query(int remainder, int index, int l, int r, int a, int b) {
    if ((a > r) || (b < l)) {
        return identityMatrix;
    } else if ((l >= a) && (r <= b)) {
        return t[index];
    }
    int m = l + (r - l) / 2;
    return matrixTwoByTwoMultiplication(remainder, query(remainder, 2 * index + 1, l, m, a, b),
                                        query(remainder, 2 * index + 2, m + 1, r, a, b));
}

int main() {
    ifstream anxiety("crypto.in");
    int remainder, n, m;
    anxiety >> remainder >> n >> m;
    string blank;

    identityMatrix = new int *[2];
    for (size_t i = 0; i < 2; ++i) {
        identityMatrix[i] = new int[2];
        for (size_t j = 0; j < 2; ++j) {
            identityMatrix[i][j] = i == j ? 1 : 0;
        }
    }

    //buildExtendedArray
    int power = 1;
    while (power < n) {
        power *= 2;
    }
    t = new int **[2 * power - 1];
    for (size_t i = 0; i < 2 * power - 1; ++i) {
        t[i] = new int *[2];
        for (size_t j = 0; j < 2; ++j) {
            t[i][j] = new int[2];
            for (size_t k = 0; k < 2; ++k) {
                t[i][j][k] = 0;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        int f, s;
        anxiety >> f >> s;
        t[power + i - 1][0][0] = f;
        t[power + i - 1][0][1] = s;
        anxiety >> f >> s;
        t[power + i - 1][1][0] = f;
        t[power + i - 1][1][1] = s;
    }
    //filling in with identity matrices
    for (int i = n; i < power; ++i) {
        t[power + i - 1] = identityMatrix;
    }
    int i = power - 2;
    while (i > -1) {
        t[i] = matrixTwoByTwoMultiplication(remainder, t[2 * i + 1], t[2 * i + 2]);
        i--;
    }

    ofstream depression("crypto.out");
    for (i = 0; i < m; ++i) {
        int a, b;
        anxiety >> a >> b;
        int **result = query(remainder, 0, 0, power - 1, a - 1, b - 1);
        depression << result[0][0] << " " << result[0][1] << endl;
        depression << result[1][0] << " " << result[1][1] << endl;
        depression << "" << endl;
        for (int j = 0; j < 2; ++j) {
            delete[] result[j];
        }
        delete[] result;
    }

    anxiety.close();
    depression.close();
    for (i = 0; i < 2 * power - 1; ++i) {
        for (int j = 0; j < 2; ++j) {
            delete[] t[i][j];
        }
        delete[] t[i];
    }
    delete[] t;
    for (i = 0; i < 2; ++i) {
        delete[] identityMatrix[i];
    }
    delete[] identityMatrix;

    return 0;
}