7493: An Easy Matrix Problem

You are given an array b[0..n−1] of length n and array ai=i,i∈[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×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), ∀i∈[0,n−1].

We define a n×n matrix C=A×B.

This problem contains two sections.

For the first section:

You have to answer m queries:

0 px py qx qy, you should print (∑qxi=px∑qyj=pyCti,j) 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×Shift(a,v).

2 j k v, the j-th column of C +=k×Shift(a,v).

3 px py qx qy, you should print (∑qxi=px∑qyj=pyCi,j) mod n.

Here a+=b denotes that perform ai=ai+bi,∀i∈[0,n−1].

See examples for better understanding.

The first line contains a single integer T (1≤T≤3000) denoting the number of test cases.

For each test case, the first line contains 4 single integers n,t,m,q (1≤n,m,q≤105,1≤t≤1018).

The second line contains n integers bi, i∈[0,n−1].

Each of the next m lines contains 5 integers:

0 px py qx qy(0≤ px,py,qx,qy ≤n−1).

Each of the next q lines contains 4 or 5 integers:

1 i k v,

2 j k v,

3 px py qx qy,

(0≤ px,py,qx,qy,k,v,i,j ≤n−1).

It is guaranteed that ∑n≤5×105, ∑m≤5×105, ∑q≤5×105, and px≤qx,py≤qy.