题号：NC200051
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
有一个长度为n的序列，有q次操作，每次操作执行下面两种操作之一
1 L R：区间[L, R]内每个数除以2（如果除完后不为整数，那么向下取整）
2 L R：查询区间[L, R]的和
输入描述:
第一行输入一个n和一个q (1 <= n, q <= 100000)
第二行输入n个数，第i个数为a[i] （1 <= a[i] <= 1e9）
接下来q行每行输入一种操作（1 <= L <= R <= n）
输出描述:
对于每次操作3输出一行一个数表示答案
示例1
输入
复制
5 3
1 2 3 4 5
2 1 3
1 1 2
2 1 3