Background

The problem name was provided by fjy666, background TBD.

Problem Description

You are given a sequence $a$ of length $n$. Please support $m$ operations:

1. Subtract $x$ from the numbers $> x$ in the interval $[l,r]$.
2. Query the count of numbers $\le x$ in the interval $[l,r]$.

Input Format

This problem is strictly online.

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

The second line contains $n$ integers representing $a$.

The next $m$ lines each contain four integers $opt,l,r,x'$, where $opt$ is the operation type. The real $x$ is obtained by taking $x'$ XOR the answer of the most recent operation $2$. If there has been no operation $2$ before, then no XOR is needed, and the real $x$ is simply $x'$.

Output Format

For every operation $2$, output one integer per line as the answer.

10 10
20 10 20 14 4 15 11 20 2 13 
2 5 9 1
1 7 8 2
1 2 3 8
1 4 6 12
2 1 7 9
2 2 7 20
2 3 9 4
2 8 9 7
1 3 10 0
2 8 9 7

0
5
6
2
1
1

5 5
6 10 3 4 7 
1 1 3 3
1 3 4 3
2 3 5 3
1 1 3 11
2 2 3 5

2
2

Hint

Idea: Ntokisq&nzhtl1477, Solution: Ntokisq, Code: Ntokisq, Data: Ntokisq.

Sample Explanation

Sample $1$ before encryption:

10 10
20 10 20 14 4 15 11 20 2 13
2 5 9 1
1 7 8 2
1 2 3 8
1 4 6 12
2 1 7 9
2 2 7 17
2 3 9 2
2 8 9 5
1 3 10 1
2 8 9 6

Sample $2$ before encryption:

5 5
6 10 3 4 7
1 1 3 3
1 3 4 3
2 3 5 3
1 1 3 9
2 2 3 7

Constraints

This problem uses bundled testdata.

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

Hint

If you believe your algorithm has the correct time complexity but the constant factor is too large, you may use an algorithm with the same idea, slightly worse time complexity, but a smaller constant factor.

Translated by ChatGPT 5