Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
H. Phoenix and Bits

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputPhoenix 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:

- replace all numbers $$$a_i$$$ where $$$l \le a_i \le r$$$ with $$$a_i$$$ AND $$$x$$$;
- replace all numbers $$$a_i$$$ where $$$l \le a_i \le r$$$ with $$$a_i$$$ OR $$$x$$$;
- replace all numbers $$$a_i$$$ where $$$l \le a_i \le r$$$ with $$$a_i$$$ XOR $$$x$$$;
- 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

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

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$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/12/2021 15:07:32 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|