该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出一个数列，你需要进行下面两种操作：

1. 将某个区间的每一个数减去它的 $\text{lowbit}$ .
2. 求某个区间的所有数之和.

（$\text{lowbit(x)}$ 表示数字 $x$ 的二进制最低位）

例如 $lowbit(14)=lowbit((1110)_2)=(10)_2=2$

详细解释：https://www.cnblogs.com/fusiwei/p/11752540.html

输入格式

第一行两个整数 $n$ , $q$ 分别代表数组的长度和操作的次数.

第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表数组 $A$ 的第 $i$ 个元素.

接下来 $q$ 行，每一行三个数字 $op$, $l$, $r$ 分别代表此次操作的类型，和区间范围 $[l,r]$.

若 $op=1$ ，则将 $a_i$ ( $i\in\{l,l+1,l+2,\dots,r\}$ ) 减去它的 $\text{lowbit}$.

若 $op=2$ ，输出 $\sum_{i=l}^ra_i$.

输出格式

对于每个 $op=2$ 的操作，输出一行一个整数.

样例 #1

样例输入 #1

5 4
5 4 3 2 1
1 1 3
2 1 5
1 2 5
2 1 5

样例输出 #1

9
4

提示

第一个 $op=1$ 操作之后，数组 $A$ 变成了 $\text{4,0,2,2,1}$.

故第一次查询结果为 $4+0+2+2+1=9$.

第二个 $op=1$ 操作之后，数组 $A$ 变成了 $\text{4,0,0,0,0}$.

故第二次查询结果为 $4+0+0+0+0=4$.

数据范围:

对于 $50\%$ 的数据：$1\leq n,q\leq 2000$ 对于 $100\%$ 的数据：

• $1\leq n,q\leq 2\times 10^5$
• $0\leq a_i\leq 10^9$
• $op \in\{1,2\}$
• $1\leq l,r\leq n$