Background

The input size of this problem is about 15 MB, and the output size is about 13 MB. Please choose an appropriate input/output method.

Problem Description

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

1 l r x: Decrease by $x$ all elements in the interval $[l,r]$ that are $> x$.

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

Input Format

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

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

Then follow $m$ lines, each containing $3$ or $4$ positive integers, representing one operation.

This problem is forced online: all input $l,r,x$ must be XORed with $lastans$, where $lastans$ is defined as the value of (the interval sum obtained from the previous query operation) modulo $2^{20}$. If there has been no query operation before, then it is $0$.

Output Format

For each operation of type $2$, output one line with three numbers separated by spaces, representing the answer.

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

9 1 3
6 1 3
4 1 2

Hint

Idea: wangziji & 花花 (Huahua), Solution: wangziji & 花花 (Huahua), Code: ccz181078, Data: wangziji & 花花 (Huahua) & ccz181078.

Note: This problem uses bundled testing. Only after you pass all test points in a subtask can you get the score for that subtask.

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

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

For another $19\%$ of the testdata, $a_i\leq 1000$, $n,m\leq 2\times10^5$, and the time limit is 3 s.

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

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

Translated by ChatGPT 5