#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define fi first
#define se second
#define _UN using namespace
using namespace std;
const int MAXN=1e5+10,INF=0x3f3f3f3f;
int n,qn1,qn2; long k,B[MAXN],D[MAXN],S[MAXN],S1[MAXN];
long sum(long* s,int l,int r){ assert(l<=r); return (s[r]-(l?s[l-1]:0)+n)%n; }
long qry(int l,int r,int op){
    if(l>r) return 0;
    if(op==1) return (sum(S1,l,r)-(l-1)*sum(S,l,r)%n+n)%n;
    else return ((r+1)*sum(S,l,r)-sum(S1,l,r)+n)%n;
}
long calc(int x,int y){
    if(x<0||y<0) return 0;
    if(x>=y) return (sum(S,0,x-y)+qry(x-y+1,x,-1)+qry(n-y,n-1,1))%n;
    else     return (D[0]+sum(S,n-(y-x),n-1)+qry(1,x,-1)+qry(n-y,n-(y-x)-1,1))%n;
}
long qpow(long x,long p){
    long r=1;
    for(; p; p>>=1,x=x*x%n){
        if(p&1) r=r*x%n;
    }
    return r;
}
void case_main(){
    cin>>n>>k>>qn1>>qn2;
    RNG(i,0,n-1) cin>>B[i],B[i]=B[i]%n;
    long s=accumulate(B,B+n,0l)%n;
    RNG(i,0,n-1) D[0]=(D[0]+i*B[(n-i+1)%n])%n;
    RNG(i,1,n-1) D[i]=(D[i-1]+s)%n;
    RNG(i,0,n) D[i]=qpow(D[i],k),S[i]=((!i?0:S[i-1])+D[i])%n,S1[i]=((!i?0:S1[i-1])+i*D[i])%n;
    RNG(_,1,qn1){
        int op,x1,y1,x2,y2; cin>>op>>x1>>y1>>x2>>y2;
        cout<<((calc(x1-1,y1-1)-calc(x1-1,y2)-calc(x2,y1-1)+calc(x2,y2)+2*n)%n)<<"\n";
    }
}
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
//  freopen("travel.in","r",stdin);
//  freopen("travel.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int cas; cin>>cas;
    RNG(_,1,cas) case_main();
}