Little $y^\infty$ saw a problem:

Given a sequence $A$ of length $n$, there are $q$ operations of four types:

1. For all $i \in [l, r]$, change $A_i$ to $A_i + x$.

2. For all $i \in [l, r]$, change $A_i$ to $x$.

3. For all $i \in [l, r]$, change $A_i$ to $\lfloor\sqrt{A_i}\rfloor$.

4. For all $i \in [l, r]$, query the sum of $A_i$.

It is guaranteed that $x > 0$.

As a math competition contestant, little $y^\infty$ solved this problem instantly; it only requires writing a segment tree.

Here is his detailed approach, which is roughly similar to the approach for UOJ#228. Basic Data Structure Practice Problem.

A segment tree is a binary tree where each node represents an interval, looking roughly like this:

Maintain the minimum value, maximum value, and interval sum on each node. Since this problem (the one you are looking at) does not ask for the specific values of these, you can assume they remain consistent with the current sequence.

Each node has a tag tuple $(a, b)$. If $a=0$, it is an assignment tag, meaning all numbers in this interval should be assigned the value $b$. If $a=1$, it is an interval addition tag, meaning all numbers in this interval should be increased by $b$ ($x' = ax + b$). Initially, the tags on all non-leaf nodes are $(1, 0)$, and the tags on leaf nodes are $(0, A_i)$.

Clearly, these tags are additive. The result of adding tag $(a_1, b_1)$ to tag $(a_2, b_2)$ is:

$$\begin{equation}\left\{\begin{array}{lr}(0,b_2)&a_2=0;\\(a_1,b_1+b_2)&a_2=1.\\\end{array}\right.\end{equation}$$

When pushing down a node's tag, first add the node's tag to the tags of its left and right children respectively, then set the node's tag to $(1, 0)$.

To add $k$ to the interval $[l, r]$ at node $[L, R]$: if $l \leq L \leq R \leq r$, add a tag $(1, k)$ to this node. Otherwise, push down the node's tag first, then recurse into children that intersect with $[l, r]$. Whenever there is an operation 1, add $k$ to the interval $[l, r]$ at node $[1, n]$.

Interval assignment is similar, except the added tag is $(0, k)$. Whenever there is an operation 2, modify the interval $[l, r]$ to $k$ at node $[1, n]$.

To perform square root on the interval $[l, r]$ at node $[L, R]$: if $l \leq L \leq R \leq r$ and $max - min \leq 1$, add a tag $(0, \lfloor\sqrt{min}\rfloor)$ to this node when $\lfloor\sqrt{max}\rfloor - \lfloor\sqrt{min}\rfloor = 0$, or add a tag $(1, \lfloor\sqrt{min}\rfloor - min)$ when it equals 1. Otherwise, push down the node's tag first, then recurse into children that intersect with $[l, r]$. Whenever there is an operation 3, perform the square root on the interval $[l, r]$ at node $[1, n]$.

Clearly, the time complexity of this is amortized $O(h \log \log A)$, where $h$ is the height of the segment tree and $A$ is the range of values.

Little $y^\infty$ is very curious about what the tags on each node are. However, as a math competition contestant, he is not good at writing competitive programming code. He decided to ask you for help: can you answer his questions?

Please write a program that maintains a segment tree for the sequence $A$, supporting the following 4 operations:

1. Add $k$ to the interval $[l, r]$ at node $[1, n]$.

2. Modify the interval $[l, r]$ to $k$ at node $[1, n]$.

3. Perform square root on the interval $[l, r]$ at node $[1, n]$.

4. Query the tag on node $[l, r]$.

Input

The first line contains an integer $T$, representing the test case number.

The second line contains two integers $n, q$, representing the length of sequence $A$ and the number of operations, respectively.

The next line contains $n$ integers, representing the initial values of sequence $A$.

The next line contains $n-1$ integers, giving the split positions $mid$ for all non-leaf nodes of the segment tree in pre-order traversal. That is, the left and right children of node $[l, r]$ are $[l, mid]$ and $[mid+1, r]$ respectively. It is not difficult to see that a segment tree on $[1, n]$ is uniquely determined by this information.

The next $q$ lines each describe an operation. The first number $opt$ indicates the operation type.

If $opt=1$, it indicates an operation 1, followed by three integers $l, r, k$.

If $opt=2$, it indicates an operation 2, followed by three integers $l, r, k$.

If $opt=3$, it indicates an operation 3, followed by two integers $l, r$.

If $opt=4$, it indicates an operation 4, followed by two integers $l, r$.

Output

For each operation 4, output two integers $a, b$ on a single line, representing the tag $(a, b)$ on node $[l, r]$.

Examples

Input 1

0
6 7
1 1 1 1 1 1
5 1 3 2 4
2 2 5 2
4 2 5
1 2 4 1
4 2 5
4 2 3
4 4 4
4 5 5

Output 1

0 2
1 0
0 3
0 3
0 2

Constraints

There are 20 test cases in total, each worth 5 points.

Property 1: When splitting the segment tree, $mid=l$ or $mid=r-1$.

Property 2: Operations only target a single node; that is, for each operation, the operation range is exactly one of the nodes in the segment tree.

For all test cases: $n = q = 10^5$, $A_i \leq 10^8$. Operation 1 guarantees $k \leq 10^3$. Operation 2 guarantees $k \leq 10^8$.