序列操作

题目背景

育华学校编程编程社团开展序列操作实践项目，成员需对非负整数序列执行按位或更新与区间求和操作，以此锻炼对位运算特性及高效数据处理的掌握，模拟真实编程竞赛中需结合算法优化应对大规模数据的场景。

现有长度为 $n$ 的非负整数序列 $\{a\}$ ，需进行 $q$ 次操作，操作分两类：

按位或操作：给定非负整数 $x$ ，序列所有元素执行 $a_i \leftarrow a_i \text{ OR } x$ （元素与 $x$ 按位或后更新自身）。
区间求和操作：给定区间 $[l, r]$ （ $1 \leq l \leq r \leq n$ ），输出该区间元素和 $\sum_{i=l}^r a_i$ 。

第一行：两个整数 $n$ （序列长度）、 $q$ （操作次数）。
第二行： $n$ 个非负整数，为初始序列 $a_1, a_2, \dots, a_n$ 。
接下来 $q$ 行：每行表示一个操作，操作 1 格式为 1 x ，操作 2 格式为 2 l r 。

对每个操作 2，输出一行整数，为对应区间的和。

测试点编号	$n$ 范围	$q$ 范围	特殊性质描述
1-2	$1 \leq n \leq 500$	$1 \leq q \leq 500$
3-4	$1 \leq n \leq 10000$	$1 \leq q \leq 10000$
5-6	$1 \leq n \leq 10000$	$1 \leq q \leq 10000$	操作2的区间固定为全序列；
7-8	$1 \leq n \leq 20000$	$1 \leq q \leq 20000$
9-10	$1 \leq n \leq 20000$	$1 \leq q \leq 20000$	$a_i$ 全为0
11-12	$1 \leq n \leq 25000$	$1 \leq q \leq 25000$
13-14	$1 \leq n \leq 5 \times 10^4$	$1 \leq q \leq 5 \times 10^4$	无操作1
15-16	$1 \leq n \leq 10^5$	$1 \leq q \leq 10^5$	操作1全部相同值
17-18	$1 \leq n \leq 1.5 \times 10^5$	$1 \leq q \leq 1.5 \times 10^5$
19-20	$1 \leq n \leq 2 \times 10^5$	$1 \leq q \leq 2 \times 10^5$

全部测试数据： $1 \leq n, q \leq 2 \times 10^5$ ， $0 \leq a_i, x \leq 10^9$

在下列比赛中: