F. Sonya 与按位或
时间限制：每个测试点 $4$ 秒
内存限制：$512$ 兆字节

Sonya 有一个由 $n$ 个整数组成的数组 $a_1, a_2, \dots, a_n$，以及一个非负整数 $x$。她需要执行 $m$ 个查询，查询有两种类型：

1. 1 i y：将第 $i$ 个元素替换为 $y$，即执行 $a_i := y$；
2. 2 l r：求满足 $l \le L \le R \le r$ 且区间 $[L, R]$ 内所有整数的按位或结果至少为 $x$ 的区间对 $(L, R)$ 的数量（注意 $x$ 对所有查询是固定的）。

请帮助 Sonya 执行所有查询。

按位或是对两个非负整数进行的一种二元运算。计算两个数的按位或时，需要将两个数写成二进制形式，结果在二进制下，某一位是 $1$ 当且仅当至少一个数的这一位是 $1$。例如，$10$ OR $19 = 1010_2$ OR $10011_2 = 11011_2 = 27$。

输入格式
第一行包含三个整数 $n, m, x$（$1 \le n, m \le 10^5$，$0 \le x < 2^{20}$）——数组长度、查询次数和常数 $x$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < 2^{20}$）。

接下来的 $m$ 行每行描述一个查询，格式如下：

• 1 i y（$1 \le i \le n$，$0 \le y < 2^{20}$）：将 $a_i$ 替换为 $y$；
• 2 l r（$1 \le l \le r \le n$）：查询区间 $[l, r]$ 内所有子数组的按位或结果是否 $\ge x$。

输出格式
对于每个类型 $2$ 的查询，输出一个整数——满足条件的子数组个数。

样例输入 1

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

样例输出 1

5
1
7
4
1
4

样例输入 2

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

样例输出 2

9
7
2
4

样例 1 解释

初始数组为 $[0, 3, 6, 1]$：

• 查询 $[1, 4]$：符合条件的子数组为 $(1,3), (1,4), (2,3), (2,4), (3,4)$，共 $5$ 个；
• 查询 $[3, 4]$：只有 $(3,4)$，共 $1$ 个；
• 将 $a_1$ 替换为 $7$，数组变为 $[7, 3, 6, 1]$；
• 查询 $[1, 4]$：符合条件的子数组有 $(1,1), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$，共 $7$ 个；
• 查询 $[1, 3]$：符合条件的子数组有 $(1,1), (1,2), (1,3), (2,3)$，共 $4$ 个；
• 查询 $[1, 1]$：只有 $(1,1)$，共 $1$ 个；
• 将 $a_3$ 替换为 $0$，数组变为 $[7, 3, 0, 1]$；
• 查询 $[1, 4]$：符合条件的子数组有 $(1,1), (1,2), (1,3), (1,4)$，共 $4$ 个。

样例 2 解释

初始数组 $[6, 0, 3, 15, 2]$：

• 查询 $[1, 5]$：符合条件的子数组有 $(1,3), (1,4), (1,5), (2,4), (2,5), (3,4), (3,5), (4,4), (4,5)$，共 $9$ 个；
• 将 $a_4$ 替换为 $4$，数组变为 $[6, 0, 3, 4, 2]$；
• 查询 $[1, 5]$：符合条件的子数组有 $(1,3), (1,4), (1,5), (2,4), (2,5), (3,4), (3,5)$，共 $7$ 个；
• 查询 $[3, 5]$：符合条件的子数组有 $(3,4), (3,5)$，共 $2$ 个；
• 查询 $[1, 4]$：符合条件的子数组有 $(1,3), (1,4), (2,4), (3,4)$，共 $4$ 个。