Sonya 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 \lt 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 \lt 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 \lt 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$$$.

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

Idx	Name	Rating
A	Sonya and Hotels	900
B	Sonya and Exhibition	1300
C	Sonya and Robots	1400
D	Sonya and Matrix	2300
E	Sonya and Ice Cream	2400
F	Sonya and Bitwise OR	2600

Codeforces Round 495 (Div. 2)