#include <fstream>
#include <iostream>
#include <math.h>
#include <cstdio>
using namespace std;
 long long int eq[4]={1,0,0,1};

long long int* multiply(long long int c1[], long long int c2[],int r){
    long long int *c = new long long int[4];
    c[0] = (c1[0]*c2[0] + c1[1]*c2[2]) % r;
    c[1] = (c1[0]*c2[1] + c1[1]*c2[3]) % r;
    c[2] = (c1[2]*c2[0] + c1[3]*c2[2]) % r;
    c[3] = (c1[2]*c2[1] + c1[3]*c2[3]) % r;
    return c;
}



void build(long long int t[][4], long long int a[][4], long long int i, long long int tree_left, long long int tree_right,  int r){
    if (tree_left == tree_right){
        return;
    }
    if (tree_right - tree_left == 1){
        t[i][0]= a[tree_left][0];
        t[i][1]= a[tree_left][1];
        t[i][2]= a[tree_left][2];
        t[i][3]= a[tree_left][3];
    }else{
        long long int tree_middle = (tree_left + tree_right) / 2;
        build (t, a, 2 * i + 1, tree_left, tree_middle, r);
        build (t, a, 2 * i + 2, tree_middle, tree_right, r);
        t[i][0]=multiply(t[2 * i + 1], t[2 * i + 2], r)[0];
		t[i][1]=multiply(t[2 * i + 1], t[2 * i + 2], r)[1];
		t[i][2]=multiply(t[2 * i + 1], t[2 * i + 2], r)[2];
		t[i][3]=multiply(t[2 * i + 1], t[2 * i + 2], r)[3];
    }
    return;
}

long long int* d_proizv(long long int t[][4], long long int i, long long int l, long long int r__, long long int a, long long int b,int r){
    if (r__ < a || b < l){

		return eq;
    }
    if (l >= a && r__ <= b){
        return t[i];
    }
    long long int m = l - (l - r__) / 2;
    return multiply(d_proizv(t, 2 * i + 1, l, m, a, b, r), d_proizv( t, 2 * i + 2, m + 1, r__, a, b, r), r);
}

 long long int step_2( long long int n){
     int i = 1;
    while(i < n){
        i *= 2;
    }
    return i*2;
}

int main() {
		ios_base::sync_with_stdio(false);
		ifstream fin("crypto.in");
    ofstream fout("crypto.out");
long long int r, n, m, l, r_;
    fin >> r >> n >> m;
    long long int k = step_2(n);
    long long int tr[k/2][4];
    for ( int i = 0; i < k/2; i++){
        if (i >= n){
            tr[i][0]=1;
            tr[i][1]=0;
            tr[i][2]=0;
            tr[i][3]=1;
        }else{
            fin >> tr[i][0] >> tr[i][1]>>tr[i][2] >> tr[i][3];
         }
    }
    long long int tree[k - 1][4];
    build(tree, tr, 0, 0, k/2, r);
     for (long long int i = 0; i < m; i++){
        fin >> l >> r_;
        if (l==r_) {
        	fout<<tr[l-1][0]<<" "<<tr[l-1][1]<<"\n"<<tr[l-1][2]<<" "<<tr[l-1][3]<<"\n";
		} else {

        fout<<d_proizv(tree, 0, 0, k/2 - 1, l - 1, r_ - 1,  r)[0]<<" ";
        fout<<d_proizv(tree, 0, 0, k/2 - 1, l - 1, r_ - 1, r)[1]<<"\n";
        fout<<d_proizv(tree, 0, 0, k/2 - 1, l - 1, r_ - 1,  r)[2]<<" ";
        fout<<d_proizv(tree, 0, 0, k/2 - 1, l - 1, r_ - 1,  r)[3]<<"\n";}
   }
fin.close();
fout.close();
}