You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Phoenix loves playing with bits — specifically, by using the bitwise operations AND, OR, and XOR. He has $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, and will perform $$$q$$$ of the following queries:

1. replace all numbers $$$a_i$$$ where $$$l \le a_i \le r$$$ with $$$a_i$$$ AND $$$x$$$;
2. replace all numbers $$$a_i$$$ where $$$l \le a_i \le r$$$ with $$$a_i$$$ OR $$$x$$$;
3. replace all numbers $$$a_i$$$ where $$$l \le a_i \le r$$$ with $$$a_i$$$ XOR $$$x$$$;
4. output how many distinct integers $$$a_i$$$ where $$$l \le a_i \le 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 Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le q \le 10^5$$$) — the number of integers and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le 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 \le t \le 4$$$) — the type of query.

If $$$t \in \{1, 2, 3\}$$$, then three integers $$$l_i$$$, $$$r_i$$$, and $$$x_i$$$ will follow ($$$0 \le l_i, r_i, x_i < 2^{20}$$$; $$$l_i \le r_i$$$).

Otherwise, if $$$t=4$$$, two integers $$$l_i$$$ and $$$r_i$$$ will follow ($$$0 \le l_i \le r_i < 2^{20}$$$).

It is guaranteed that there is at least one query where $$$t=4$$$.

## Output Format
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$$$.

Now solve the problem and return the code.