RMQ
题号：NC21414
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

按位或运算：处理两个长度相同的二进制数，两个相应的二进位中只要有一个为1，该位的结果值为1。例如5 or 3 = 7 

        0101（十进制5）
     OR 0011（十进制3）
      = 0111（十进制7）
—— 引用自 位运算——维基百科
小姐姐想要一种数据结构，支持如下操作：
对于一个整数数组：    
1. 给定L和R，输出[L,R]中元素的和
2. 给定L，R和X，将[L,R]中每个元素与X进行按位或运算
3. 数组索引从1开始
按位或在C\C++、Java、Python中为'|'运算符

输入描述:

第一行为两个整数 n 和 m，表示数组元素个数和操作的次数
第二行有n个整数，第i个表示数组array中第i个元素的值array[i]
接下来m行，每行只有两种可能：
1. SUM L R
表示对[L,R]的元素求和并输出
2. OR L R X
表示对[L,R]的每一个元素与X进行按位或运算，L、R为base 1的数字序号
数据满足：




输出描述:

对于每个SUM操作，在一行内输出该操作的结果。
示例1

输入

复制 
5 3
1 2 3 4 5
SUM 1 4
OR 2 5 10
SUM 1 4

输出

复制 
10
36

说明

在第一个SUM操作时数组a为[1, 2, 3, 4, 5]，因此[1,4]和为10

在第二个SUM操作时数组a为[1, 10, 11, 14, 15]，因此[1,4]和为36