Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-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

F. Sonya and Bitwise OR

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputSonya has an array $$$a_1, a_2, \ldots, a_n$$$ consisting of $$$n$$$ integers and also one non-negative integer $$$x$$$. She has to perform $$$m$$$ queries of two types:

- $$$1$$$ $$$i$$$ $$$y$$$: replace $$$i$$$-th element by value $$$y$$$, i.e. to perform an operation $$$a_{i}$$$ := $$$y$$$;
- $$$2$$$ $$$l$$$ $$$r$$$: find the number of pairs ($$$L$$$, $$$R$$$) that $$$l\leq L\leq R\leq r$$$ and bitwise OR of all integers in the range $$$[L, R]$$$ is at least $$$x$$$ (note that $$$x$$$ is a constant for all queries).

Can you help Sonya perform all her queries?

Bitwise OR is a binary operation on a pair of non-negative integers. To calculate the bitwise OR of two numbers, you need to write both numbers in binary notation. The result is a number, in binary, which contains a one in each digit if there is a one in the binary notation of at least one of the two numbers. For example, $$$10$$$ OR $$$19$$$ = $$$1010_2$$$ OR $$$10011_2$$$ = $$$11011_2$$$ = $$$27$$$.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$x$$$ ($$$1\leq n, m\leq 10^5$$$, $$$0\leq x<2^{20}$$$) — the number of numbers, the number of queries, and the constant for all queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i<2^{20}$$$) — numbers of the array.

The following $$$m$$$ lines each describe an query. A line has one of the following formats:

- $$$1$$$ $$$i$$$ $$$y$$$ ($$$1\leq i\leq n$$$, $$$0\leq y<2^{20}$$$), meaning that you have to replace $$$a_{i}$$$ by $$$y$$$;
- $$$2$$$ $$$l$$$ $$$r$$$ ($$$1\leq l\leq r\leq n$$$), meaning that you have to find the number of subarrays on the segment from $$$l$$$ to $$$r$$$ that the bitwise OR of all numbers there is at least $$$x$$$.

Output

For each query of type 2, print the number of subarrays such that the bitwise OR of all the numbers in the range is at least $$$x$$$.

Examples

Input

4 8 7

0 3 6 1

2 1 4

2 3 4

1 1 7

2 1 4

2 1 3

2 1 1

1 3 0

2 1 4

Output

5

1

7

4

1

4

Input

5 5 7

6 0 3 15 2

2 1 5

1 4 4

2 1 5

2 3 5

2 1 4

Output

9

7

2

4

Note

In the first example, there are an array [$$$0$$$, $$$3$$$, $$$6$$$, $$$1$$$] and queries:

- on the segment [$$$1\ldots4$$$], you can choose pairs ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$2$$$, $$$3$$$), ($$$2$$$, $$$4$$$), and ($$$3$$$, $$$4$$$);
- on the segment [$$$3\ldots4$$$], you can choose pair ($$$3$$$, $$$4$$$);
- the first number is being replacing by $$$7$$$, after this operation, the array will consist of [$$$7$$$, $$$3$$$, $$$6$$$, $$$1$$$];
- on the segment [$$$1\ldots4$$$], you can choose pairs ($$$1$$$, $$$1$$$), ($$$1$$$, $$$2$$$), ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$2$$$, $$$3$$$), ($$$2$$$, $$$4$$$), and ($$$3$$$, $$$4$$$);
- on the segment [$$$1\ldots3$$$], you can choose pairs ($$$1$$$, $$$1$$$), ($$$1$$$, $$$2$$$), ($$$1$$$, $$$3$$$), and ($$$2$$$, $$$3$$$);
- on the segment [$$$1\ldots1$$$], you can choose pair ($$$1$$$, $$$1$$$);
- the third number is being replacing by $$$0$$$, after this operation, the array will consist of [$$$7$$$, $$$3$$$, $$$0$$$, $$$1$$$];
- on the segment [$$$1\ldots4$$$], you can choose pairs ($$$1$$$, $$$1$$$), ($$$1$$$, $$$2$$$), ($$$1$$$, $$$3$$$), and ($$$1$$$, $$$4$$$).

In the second example, there are an array [$$$6$$$, $$$0$$$, $$$3$$$, $$$15$$$, $$$2$$$] are queries:

- on the segment [$$$1\ldots5$$$], you can choose pairs ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$1$$$, $$$5$$$), ($$$2$$$, $$$4$$$), ($$$2$$$, $$$5$$$), ($$$3$$$, $$$4$$$), ($$$3$$$, $$$5$$$), ($$$4$$$, $$$4$$$), and ($$$4$$$, $$$5$$$);
- the fourth number is being replacing by $$$4$$$, after this operation, the array will consist of [$$$6$$$, $$$0$$$, $$$3$$$, $$$4$$$, $$$2$$$];
- on the segment [$$$1\ldots5$$$], you can choose pairs ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$1$$$, $$$5$$$), ($$$2$$$, $$$4$$$), ($$$2$$$, $$$5$$$), ($$$3$$$, $$$4$$$), and ($$$3$$$, $$$5$$$);
- on the segment [$$$3\ldots5$$$], you can choose pairs ($$$3$$$, $$$4$$$) and ($$$3$$$, $$$5$$$);
- on the segment [$$$1\ldots4$$$], you can choose pairs ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$2$$$, $$$4$$$), and ($$$3$$$, $$$4$$$).

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 21:00:04 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|