#D948. Phoenix and Bits
Phoenix and Bits
Phoenix and Bits
Phoenix loves playing with bits — specifically, by using the bitwise operations AND, OR, and XOR. He has n integers a_1, a_2, ..., a_n, and will perform q of the following queries:
- replace all numbers a_i where l ≤ a_i ≤ r with a_i AND x;
- replace all numbers a_i where l ≤ a_i ≤ r with a_i OR x;
- replace all numbers a_i where l ≤ a_i ≤ r with a_i XOR x;
- output how many distinct integers a_i where l ≤ a_i ≤ r.
For each query, Phoenix is given l, r, and x. Note that he is considering the values of the numbers, not their indices.
Input
The first line contains two integers n and q (1 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ q ≤ 10^5) — the number of integers and the number of queries, respectively.
The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i < 2^{20}) — the integers that Phoenix starts with.
The next q lines contain the queries. For each query, the first integer of each line is t (1 ≤ t ≤ 4) — the type of query.
If t ∈ {1, 2, 3}, then three integers l_i, r_i, and x_i will follow (0 ≤ l_i, r_i, x_i < 2^{20}; l_i ≤ r_i).
Otherwise, if t=4, two integers l_i and r_i will follow (0 ≤ l_i ≤ r_i < 2^{20}).
It is guaranteed that there is at least one query where t=4.
Output
Print the answer for each query where t=4.
Examples
Input
5 6 5 4 3 2 1 1 2 3 2 4 2 5 3 2 5 3 4 1 6 2 1 1 8 4 8 10
Output
3 2 1
Input
6 7 6 0 2 3 2 7 1 0 4 3 2 6 8 4 4 0 7 3 2 5 3 1 0 1 2 4 0 3 4 2 7
Output
5 1 2
Note
In the first example:
- For the first query, 2 is replaced by 2 AND 2 = 2 and 3 is replaced with 3 AND 2 = 2. The set of numbers is {1, 2, 4, 5}.
- For the second query, there are 3 distinct numbers between 2 and 5: 2, 4, and 5.
- For the third query, 2 is replaced by 2 XOR 3 = 1, 4 is replaced by 4 XOR 3 = 7, and 5 is replaced by 5 XOR 3 = 6. The set of numbers is {1, 6, 7}.
- For the fourth query, there are 2 distinct numbers between 1 and 6: 1 and 6.
- For the fifth query, 1 is replaced by 1 OR 8 = 9. The set of numbers is {6, 7, 9}.
- For the sixth query, there is one distinct number between 8 and 10: 9.
inputFormat
outputFormat
output how many distinct integers a_i where l ≤ a_i ≤ r.
For each query, Phoenix is given l, r, and x. Note that he is considering the values of the numbers, not their indices.
Input
The first line contains two integers n and q (1 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ q ≤ 10^5) — the number of integers and the number of queries, respectively.
The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i < 2^{20}) — the integers that Phoenix starts with.
The next q lines contain the queries. For each query, the first integer of each line is t (1 ≤ t ≤ 4) — the type of query.
If t ∈ {1, 2, 3}, then three integers l_i, r_i, and x_i will follow (0 ≤ l_i, r_i, x_i < 2^{20}; l_i ≤ r_i).
Otherwise, if t=4, two integers l_i and r_i will follow (0 ≤ l_i ≤ r_i < 2^{20}).
It is guaranteed that there is at least one query where t=4.
Output
Print the answer for each query where t=4.
Examples
Input
5 6 5 4 3 2 1 1 2 3 2 4 2 5 3 2 5 3 4 1 6 2 1 1 8 4 8 10
Output
3 2 1
Input
6 7 6 0 2 3 2 7 1 0 4 3 2 6 8 4 4 0 7 3 2 5 3 1 0 1 2 4 0 3 4 2 7
Output
5 1 2
Note
In the first example:
- For the first query, 2 is replaced by 2 AND 2 = 2 and 3 is replaced with 3 AND 2 = 2. The set of numbers is {1, 2, 4, 5}.
- For the second query, there are 3 distinct numbers between 2 and 5: 2, 4, and 5.
- For the third query, 2 is replaced by 2 XOR 3 = 1, 4 is replaced by 4 XOR 3 = 7, and 5 is replaced by 5 XOR 3 = 6. The set of numbers is {1, 6, 7}.
- For the fourth query, there are 2 distinct numbers between 1 and 6: 1 and 6.
- For the fifth query, 1 is replaced by 1 OR 8 = 9. The set of numbers is {6, 7, 9}.
- For the sixth query, there is one distinct number between 8 and 10: 9.
样例
6 7
6 0 2 3 2 7
1 0 4 3
2 6 8 4
4 0 7
3 2 5 3
1 0 1 2
4 0 3
4 2 7
5
1
2