Given a sequence $a$ of length $n$, you need to perform $m$ operations:

1 l r x: Subtract $x$ from all elements in the range $[l, r]$ that are greater than $x$.

2 l r: Query the sum, minimum value, and maximum value of the range $[l, r]$.

Input

The first line contains two positive integers $n$ and $m$.

The second line contains $n$ positive integers representing the sequence $a$.

Each of the following $m$ lines contains $3$ or $4$ positive integers representing an operation.

This problem is forced online. All input values $l, r, x$ must be XORed with $lastans$, which is defined as the sum of the range from the most recent query operation modulo $2^{20}$. If no query operation has been performed yet, $lastans$ is $0$.

Output

For each operation of type 2, output three space-separated integers representing the answer.

Examples

Input 1

5 5
2 4 5 1 3
1 2 4 3
2 1 5
2 10 12
1 7 3 7
2 5 3

Output 1

9 1 3
6 1 3
4 1 2

Subtasks

Idea: wangziji & Huahua, Solution: wangziji & Huahua, Code: ccz181078, Data: wangziji & Huahua & ccz181078

Note: This problem uses bundled testing. You will only receive points for a subtask if you pass all test cases within that subtask.

For $1\%$ of the data, $n, m \leq 1000$, time limit is 3s.

For another $14\%$ of the data, $a_i \leq 10$, $n, m \leq 2 \times 10^5$, time limit is 3s.

For another $19\%$ of the data, $a_i \leq 1000$, $n, m \leq 2 \times 10^5$, time limit is 3s.

For another $19\%$ of the data, $a_i \leq 2 \times 10^5$, $n, m \leq 2 \times 10^5$, time limit is 3s.

For $100\%$ of the data, $1 \leq n, m \leq 5 \times 10^5$, $1 \leq a_i, x \leq 10^9$.