B. Cryptography

#include <bits/stdc++.h>
#define Int long long
using namespace std;
#define rg (p << 1) | 1
#define lf (p << 1)

vector< vector<Int> > Ans;
int MOD ,n ,m;

class SegTree {
    private:
        vector< vector<Int> > Identity ;
        vector< vector< vector<Int> > > Seg;

        Int MulMod(Int a ,Int b){
            return 1ll * ( 1ll * (a % MOD) * (b % MOD) ) % MOD;
        }

        vector< vector< Int > > Compain(vector< vector< Int > > a ,vector< vector< Int > > b) {

            vector< vector< Int > > Res(2 ,vector< Int >(2 ,0));
            for(int i = 0 ; i < 2 ; i++)
                for(int j = 0 ; j < 2 ; j++)
                    for(int k = 0 ; k < 2 ; k++)
                        Res[i][j] += 1ll * MulMod(a[i][k] ,b[k][j]);

            return Res;
        }

        void DoIdentity (){
            Identity.assign(2 ,vector< Int >(2 ,0));
            for(int i = 0 ; i < 2 ; i++)
                Identity[i][i] = 1ll;
        }

        void UPD(int i ,vector< vector< Int > > v ,int p ,int L ,int R){
            if( i >  R || i <  L ) return;
            if( L == R ) {
                Seg[p] = v; return;}

            int Mid = (L + R) >> 1;
            UPD(i ,v ,lf ,L ,Mid);
            UPD(i ,v ,rg ,Mid + 1 ,R);
            Seg[p] = Compain(Seg[lf] ,Seg[rg]);
        }

        vector< vector< Int > > QRY(int i ,int j ,int p ,int L ,int R){
            if( i >  R || L >  j ) return Identity;
            if( i <= L && R <= j ) return Seg[p];

            int Mid = (L + R) >> 1;
            vector< vector< Int > > LF = QRY(i ,j ,lf ,L ,Mid);
            vector< vector< Int > > RG = QRY(i ,j ,rg ,Mid + 1 ,R);
            return Compain(LF ,RG);
        }

    public:
        SegTree(int n){
            DoIdentity();
            Seg.assign(4 * n ,Identity );
        }
        void UPD(int i ,vector< vector< Int > > v){
            UPD(i ,v ,1 ,1 ,n);
        }
        vector< vector< Int > > QRY(int L ,int R){
            return QRY(L ,R ,1 ,1 ,n);
        }
};

int main() {
    scanf("%d%d%d" ,&MOD ,&n ,&m);
    SegTree ST(n + 1);

    vector< vector< Int > > V(2 ,vector< Int >(2 ,0));
    for(int idx = 1 ; idx <= n ; idx++){
        for(int i = 0 ; i < 2 ; i++)
            for(int j = 0 ; j < 2 ; j++)
                scanf("%lld" ,&V[i][j]);
        ST.UPD(idx ,V);
    }

    while( m-- ){
            int L ,R; scanf("%d%d" ,&L ,&R);
            Ans = ST.QRY(L ,R);
            for(int i = 0 ; i < 2 ; i++ ,puts(""))
                for(int j = 0 ; j < 2 ; j++)
                    printf("%lld " ,Ans[i][j]);
            puts("");
    }
    return 0;
}