CF1004F.Sonya and Bitwise OR

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

索尼娅有一个由 $n$ 个整数组成的数组 $a_1, a_2, \ldots, a_n$，以及一个非负整数 $x$。她需要执行 $m$ 个查询，查询分为两类：

• $1$ $i$ $y$：将第 $i$ 个元素替换为值 $y$，即执行操作 $a_{i} := y$；
• $2$ $l$ $r$：求满足 $l\leq L\leq R\leq r$ 的区间对 $(L, R)$ 的个数，使得区间 $[L, R]$ 内所有整数的按位或（bitwise OR）值至少为 $x$（注意：$x$ 在所有查询中均为常数）。

你能帮助索尼娅完成所有查询吗？

按位或（bitwise OR）是一种作用于两个非负整数的二元运算。要计算两个数的按位或，需先将这两个数写成二进制形式；结果的二进制表示中，每一位为 $1$ 当且仅当两个数在该位上至少有一个为 $1$。例如，$10$ OR $19$ = $1010_2$ OR $10011_2$ = $11011_2$ = $27$。

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

第一行包含三个整数 $n$、$m$ 和 $x$（$1\leq n, m\leq 10^5$，$0\leq x \lt 2^{20}$）—— 分别表示数字个数、查询次数以及所有查询中使用的常数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0\leq a_i \lt 2^{20}$）—— 表示数组中的数字。

接下来的 $m$ 行每行描述一个查询。每行具有以下两种格式之一：

• $1$ $i$ $y$（$1\leq i\leq n$，$0\leq y \lt 2^{20}$），表示将 $a_{i}$ 替换为 $y$；
• $2$ $l$ $r$（$1\leq l\leq r\leq n$），表示需要找出区间 $[l, r]$ 内满足“子数组中所有数的按位或（bitwise OR）值至少为 $x$”的子数组个数。

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

对于每个类型为 2 的查询，输出满足条件的子数组个数：该子数组内所有数的按位或（bitwise OR）结果至少为 $x$。

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

在第一个例子中，给定数组 $[0, 3, 6, 1]$ 和如下查询：

1. 在区间 $[1\ldots4]$ 上，可选择的数对有 $(1, 3)$、$(1, 4)$、$(2, 3)$、$(2, 4)$ 和 $(3, 4)$；
2. 在区间 $[3\ldots4]$ 上，可选择的数对为 $(3, 4)$；
3. 将第一个数替换为 $7$，操作后数组变为 $[7, 3, 6, 1]$；
4. 在区间 $[1\ldots4]$ 上，可选择的数对有 $(1, 1)$、$(1, 2)$、$(1, 3)$、$(1, 4)$、$(2, 3)$、$(2, 4)$ 和 $(3, 4)$；
5. 在区间 $[1\ldots3]$ 上，可选择的数对有 $(1, 1)$、$(1, 2)$、$(1, 3)$ 和 $(2, 3)$；
6. 在区间 $[1\ldots1]$ 上，可选择的数对为 $(1, 1)$；
7. 将第三个数替换为 $0$，操作后数组变为 $[7, 3, 0, 1]$；
8. 在区间 $[1\ldots4]$ 上，可选择的数对有 $(1, 1)$、$(1, 2)$、$(1, 3)$ 和 $(1, 4)$。

在第二个例子中，给定数组 $[6, 0, 3, 15, 2]$ 和如下查询：

1. 在区间 $[1\ldots5]$ 上，可选择的数对有 $(1, 3)$、$(1, 4)$、$(1, 5)$、$(2, 4)$、$(2, 5)$、$(3, 4)$、$(3, 5)$、$(4, 4)$ 和 $(4, 5)$；
2. 将第四个数替换为 $4$，操作后数组变为 $[6, 0, 3, 4, 2]$；
3. 在区间 $[1\ldots5]$ 上，可选择的数对有 $(1, 3)$、$(1, 4)$、$(1, 5)$、$(2, 4)$、$(2, 5)$、$(3, 4)$ 和 $(3, 5)$；
4. 在区间 $[3\ldots5]$ 上，可选择的数对为 $(3, 4)$ 和 $(3, 5)$；
5. 在区间 $[1\ldots4]$ 上，可选择的数对有 $(1, 3)$、$(1, 4)$、$(2, 4)$ 和 $(3, 4)$。