#P6587. 超超的序列 加强

超超的序列 加强

题目背景

孙1超总是喜欢疯言疯语,有一天,他随口说出了一串序列,又想对某几个特定位置的值进行修改和求和。由于孙1超十分菜,所以他来找你帮助。

请不要抄题解。

题目描述

给定序列 aa,并且给出两种操作:

  • 1 x y v:将所有 aia_i 的值加上 vv,其中 iy(mod2x)i\equiv y\pmod {2^x}
  • 2 x y:询问所有 aia_i 的和,其中 iy(mod2x)i\equiv y\pmod {2^ x}

本题强制在线。

输入格式

第一行 n,mn,m 两个整数。

第二行 nn 个整数,第 ii 个表示 aia_i

接下来若干行,每行给出若干个整数:

op=1op=1 时,opop' 的后三个整数依次为该操作的 x,y,vx,y,v

op=2op=2 时,opop' 的后两个个整数依次为该操作的 x,yx,y

其中保证没有多余的数输入。

每次操作的 op=(lastans+op)mod2+1op=(\operatorname{lastans}+op')\bmod 2+1

其中 lastans\rm lastans 表示上一个输出的答案,若之前没有询问,则 lastans=0\rm lastans=0

输出格式

输出每次询问的结果。

5 3
1 2 3 4 6
1 2 1
1 1 1 3
2 0 0
7
25

提示

样例解释

对于样例 1:

  • 第一个操作 op=2op=2,需要计算贡献的 ii1,51,5,答案为 77
  • 第二个操作 op=1op=1, 需要加上 33ii1,3,51,3,5,将 a1,a3,a5a_1,a_3,a_5 加上 33
  • 第三个操作 op=2op=2, 需要计算贡献的 ii1,2,3,4,51,2,3,4,5,答案为 2525

数据范围

  • 对于 10%10\% 的数据,1n,m1031\le n,m \leq 10^3
  • 对于 70%70\% 的数据,每一个操作后面有一个换行。
  • 对于 100%100\% 的数据,1n,m2×1051\le n,m \leq 2\times10^50ai,y,v,op<1070 \leq a_i,y,v,op'<10^7
  • 对于操作 1 和 2,0x200\leq x \leq 200y<2x0 \le y < 2^x