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.