An Easy Matrix Problem

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}$$

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$.

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

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

0
1
3
2

2020 Multi-University Training Contest 5