#include<cstdio>#include<iostream>#include<cstring>#include<cmath>#include<algorithm>using namespace std;#define maxn 111111#define lson l, m, rt << 1#define rson m+1, r, rt << 1 | 1int mod;struct Matrix { int d[2][2]; void clearit() { d[0][0] = d[1][1] = 1; d[1][0] = d[0][1] = 0; } Matrix() { clearit(); } Matrix operator + (const Matrix & _m) const { Matrix ans; for(int i=0; i<2; i++) { for(int j=0; j<2; j++) { ans.d[i][j] = 0; for(int k=0; k<2; k++) { ans.d[i][j] = (ans.d[i][j] + d[i][k] * _m.d[k][j]) % mod; } } } return ans; } void printit() { for(int i=0; i<2; i++) { for(int j=0; j<2; j++) { printf("%d%c", d[i][j], j==1?'n':' '); } } }};Matrix tree[maxn<<2];void PushUp(int rt) { tree[rt] = tree[rt<<1] + tree[rt<<1|1];}void build(int l, int r, int rt) { tree[rt].clearit(); if(l == r) { for(int i=0; i<2; i++) { for(int j=0; j<2; j++) { scanf("%d", &tree[rt].d[i][j]); } } return ; } int m = (l + r) >> 1; build(lson); build(rson); PushUp(rt);}Matrix query(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { return tree[rt]; } int m = (l + r) >> 1; Matrix ret; if(L <= m) ret = ret + query(L, R, lson); if(m < R) ret = ret + query(L, R, rson); return ret;}void scanfit(Matrix &m) { for(int i=0; i<2; i++) { for(int j=0; j<2; j++) { scanf("%d", &m.d[i][j]); } }}int main(){ int n, q; int flag = 1; while(scanf("%d%d%d", &mod, &n, &q) == 3){ if(flag == 0) printf("n"); flag = 0; build(1, n, 1); int l, r; for(int i=0; i<q; i++) { scanf("%d%d", &l, &r); Matrix ans = query(l, r, 1, n, 1); ans.printit(); if(i != q-1) printf("n"); } } return 0;}
