时间限制：1000ms $\enspace$ 空间限制：512MB

题目背景

所谓开拓，就是沿着前人未尽的道路，走出更遥远的距离。

题目描述

列车组的面前有 $n$ 个拦路的怪物，其中第 $i$ 个怪物的攻击力为 $a_i$，为了践行开拓之道，列车组需要击败它们。然而，由于宇宙射线的影响，怪物的攻击力可能会发生变化，因此，列车组需要你帮助他们统计怪物的攻击力。

为了帮助列车组，你需要完成一个程序，支持以下操作：

• 操作 1：你需要告诉列车组第 $l$ 个到第 $r$ 个怪物的攻击力之和。
• 操作 2：由于宇宙射线的影响，第 $l$ 个到第 $r$ 个怪物的攻击力均增加了 $2^x \operatorname{mod} y$，即 $2^x$ 对 $y$ 取模。

幸运的是，由于宇宙射线并没有很频繁，所以操作 2 的数量很少。

输入格式

第一行 $2$ 个整数 $n,m$，代表怪物的数量与操作数量。

第二行 $n$ 个整数，第 $i$ 个整数代表第 $i$ 个怪物的初始攻击力 $a_i$。

接下来 $m$ 行，每行首先会给出一个整数代表操作类型。

• 若该整数为 $1$，则代表本次操作为操作 1，本行会再给出 $2$ 个整数 $l,r$，代表操作 1 的两个参数。
• 若该整数为 $2$，则代表本次e操作为操作 2，本行会再给出 $4$ 个整数 $l,r,x,y$，代表操作 2 的四个参数。

输出格式

对于每次操作 $1$，输出一行一个整数，代表你统计出的怪物攻击力之和。

输入输出样例

见下发文件（点击下载）。

数据范围及约定

对于 $40\%$ 的数据，满足 $1\le n,m\le 1000,1\le x\le 30$。

对于另外 $20\%$ 的数据，满足 $1\le n,m \le 1000$。

对于另外 $20\%$ 的数据，满足 $1\le x\le 30$。

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^5,1\le x,y\le 10^9,1\le a_i\le 10^9$，操作 2 的数量不超过 $100$ 次。

温馨提示：某些变量的值可能会超出 int 的存储范围。

后记

An unending dream!