ll@N,@B,@Q,P[N*4+4]={1,0,0,1};VI T={1,0,0,1};rep(n,N){ll@a,@b,@c,@d;T={(a*T[0]+b*T[2])%B,(a*T[1]+b*T[3])%B,(c*T[0]+d*T[2])%B,(c*T[1]+d*T[3])%B};rep(i,4)P[n*4+4+i]=T[i];}rep(Q){ll@L,@R,@x,@y,z=((P[R*4]*P[L*4+3]-P[R*4+1]*P[L*4+2])%B*x+(P[R*4+1]*P[L*4]-P[R*4]*P[L*4+1])%B*y)%B,w=((P[R*4+2]*P[L*4+3]-P[R*4+3]*P[L*4+2])%B*x+(P[R*4+3]*P[L*4]-P[R*4+2]*P[L*4+1])%B*y)%B;wt((z+B)%B,(w+B)%B);}