An Easy Matrix Problem

Problem Description

You are given an array $b[0..n-1]$ of length $n$ and array $a_i = i, i \in [0,n-1]$. Denote $Shift(p,i)$ as an array built from $p$ by \textbf{right cyclicly shifting} for $i$ elements. For example, if $n$ = $3$ and $p$ = $a$, $Shift(p,1)$ = $2,0,1$, and if $n$ = $5$ and $p$ = $a$, $Shift(p,3)$ = $2,3,4,0,1$. We define two $n \times n$ matrixes $A$ and $B$, the $i$-th row of $A$ is $Shift(a,i)$ and the $i$-th row of $B$ is $Shift(b,i)$, $\forall i \in [0,n-1]$. We define a $n\times n$ matrix $C = A\times B$. This problem contains two sections. For the first section: You have to answer $m$ queries: $0$ $p_x$ $p_y$ $q_x$ $q_y$, you should print ($\sum_{i=p_x}^{q_x}\sum_{j=p_y}^{q_y}C_{i,j}^t$) mod $n$, here $t$ meaning the $t$-th power is a parameter fixed for one test case. For the second section: You have to answer $q$ queries, and there might be $3$ types: $1$ $i$ $k$ $v$, the $i$-th row of $C$ $+=k \times Shift(a,v)$. $2$ $j$ $k$ $v$, the $j$-th column of $C$ $+=k \times Shift(a,v)$. $3$ $p_x$ $p_y$ $q_x$ $q_y$, you should print ($\sum_{i=p_x}^{q_x}\sum_{j=p_y}^{q_y}C_{i,j}$) mod $n$. Here $a+=b$ denotes that perform $a_i=a_i+b_i, \forall i \in [0,n-1]$. See examples for better understanding. In the example , the initial matrix $C$:

$$\begin{bmatrix} {30}&{20}&{15}&{15}&{20}\\ {20}&{30}&{20}&{15}&{15}\\ {15}&{20}&{30}&{20}&{15}\\ {15}&{15}&{20}&{30}&{20}\\ {20}&{15}&{15}&{20}&{30}\\ \end{bmatrix}$$

After the first update operation, the matrix $C$ will become:

$$\begin{bmatrix} {30}&{20}&{15}&{15}&{20}\\ {20}&{30}&{20}&{15}&{15}\\ {23}&{20}&{32}&{24}&{21}\\ {15}&{15}&{20}&{30}&{20}\\ {20}&{15}&{15}&{20}&{30}\\ \end{bmatrix}$$

After the second update operation, the matrix $C$ will become:

$$\begin{bmatrix} {30}&{20}&{24}&{15}&{20}\\ {20}&{30}&{32}&{15}&{15}\\ {23}&{20}&{32}&{24}&{21}\\ {15}&{15}&{23}&{30}&{20}\\ {20}&{15}&{21}&{20}&{30}\\ \end{bmatrix}$$

Input

The first line contains a single integer $T$ ($1\leq T \leq 3000$) denoting the number of test cases. For each test case, the first line contains $4$ single integers $n$,$t$,$m$,$q$ ($1\leq n,m,q \leq 10^{5}$,$1\leq t \leq 10^{18}$). The second line contains $n$ integers $b_i$, $i \in [0,n-1]$. Each of the next $m$ lines contains $5$ integers: $0$ $p_x$ $p_y$ $q_x$ $q_y$($0\leq$ $p_x$,$p_y$,$q_x$,$q_y$ $\leq n-1$). Each of the next $q$ lines contains $4$ or $5$ integers: $1$ $i$ $k$ $v$, $2$ $j$ $k$ $v$, $3$ $p_x$ $p_y$ $q_x$ $q_y$, ($0\leq$ $p_x$,$p_y$,$q_x$,$q_y$,$k$,$v$,$i$,$j$ $\leq n-1$). It is guaranteed that $\sum n \le 5 \times 10^5$, $\sum m \le 5 \times 10^5$, $\sum q \le 5 \times 10^5$, and $p_x \le q_x,p_y \le q_y$.

Output

For each query of type $0$ and type $3$, output the only line containing just one integer denoting the answer.

Sample Input

1
5 3 1 5
0 4 3 2 1
0 0 0 4 4
1 2 2 1
2 2 3 2
3 1 1 3 3
3 0 0 4 1
3 0 2 4 2

Sample Output

0
1
3
2

Source

2020 Multi-University Training Contest 5