Description

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

Samples

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

5
1
7
4
1
4

5 5 7
6 0 3 15 2
2 1 5
1 4 4
2 1 5
2 3 5
2 1 4

9
7
2
4

Note

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

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

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