Криптография

import java.io.*;
import java.nio.charset.Charset;
import java.nio.charset.StandardCharsets;
import java.util.Scanner;

public class Main {
    private static int r;
    private static int[][] t;
//    private static final int[] neitral = {1, 0, 0, 1};

    private static int[] getMulInRange(int v, int left, int right, int a, int b) {
        if (a > right || b < left) return new int[]{1, 0, 0, 1};
        if (a == left && b == right) return t[v];
        int mid = (left + right) / 2;
        return mul(getMulInRange(v * 2 + 1, left, mid, a, Math.min(b, mid)),
                getMulInRange(v * 2 + 2, mid + 1, right, Math.max(a, mid + 1), b));
    }

    public static void main(String[] args) {
        try (Scanner in = new Scanner(new FileReader("crypto.in"));
             BufferedWriter writer = new BufferedWriter(new FileWriter("crypto.out"))){
            r = in.nextInt();
            int n = in.nextInt();
            int m = in.nextInt();
            int newN = getNewN(n);
            t = new int[newN * 2 - 1][4];
            // build
            for (int i = 0; i < newN * 2 - 1; i++)
                t[i] = new int[]{1, 0, 0, 1};
            for (int i = 0; i < n; i++) {
                int q = newN + i - 1;
                for (int j = 0; j < 4; j++) {
                    int z = in.nextInt();
                    t[q][j] = z;
                }
            }

            for (int i = newN - 2; i >= 0; i--)
                setMul(i);
            //
            for (int i = 0; i < m; i++) {
                int res[] = getMulInRange(0, 0, newN - 1, in.nextInt() - 1, in.nextInt() - 1);
                writer.write(res[0] + " " + res[1] + '\n');
                writer.write(res[2] + " " + res[3] + '\n' + '\n');
            }
        } catch(IOException e){
            e.printStackTrace();
        }
    }

    private static void setMul(int i) {
        t[i] = mul(t[i * 2 + 1], t[i * 2 + 2]);
    }

    private static int getNewN(int n) {
        int res = 1;
        while (res < n)
            res <<= 1;
        return res;
    }

    private static int[] reverse(int[] a) {
        int det = a[0] * a[3] - a[1] * a[2];
        if (det == 0) det = 1;
        int res[] = new int[4];
        res[0] = a[3] / det;
        res[1] = -a[2] / det;
        res[2] = -a[1] / det;
        res[3] = a[0] / det;
        for (int i = 0; i < 4; i++) {
            res[i] %= r;
            if (res[i] < 0) res[i] += r;
        }
        return res;
    }

    private static int[] mul(int[] a, int[] b) {
        int res[] = new int[4];
        res[0] = a[0] * b[0] + a[1] * b[2];
        res[1] = a[0] * b[1] + a[1] * b[3];
        res[2] = a[2] * b[0] + a[3] * b[2];
        res[3] = a[2] * b[1] + a[3] * b[3];
        for (int i = 0; i < 4; i++) {
            res[i] %= r;
            if (res[i] < 0) res[i] += r;
        }
        return res;
    }
}