题目描述

此方在餐厅吃饭，他发现旁边的人发出了很大的噪声。

对于每个座位 $k$ 发出的噪声，$i$ 位置接收到的噪声为 $\max(0,j-a_k\times\operatorname{abs}(i-k))$，$a_k$ 为噪声的衰退系数，$j$ 为初始噪声，具体定义见下文。

对于每个位置受到的噪声，为所有位置发出噪声到达这个位置后的最大值。

但是，管理人员为了减少噪声，在一些地方修建了降噪设备，如果一个位置 $i$ 满足 $b_i=1$，那么这个位置初始有一个降噪设备。而对于降噪设备，在噪声到达其左边第一个和右边第一个遇见的降噪设备后，衰退系数会变为原来的 $2$ 倍。形式化地，设对于位置 $k$ 传达到位置 $i$ 接触到的第一个降噪设备位置为 $x$，那么位置 $i$ 接收到的噪声为 $\max(0,j-a_k\times\operatorname{abs}(k-x)-2a_k\times\operatorname{abs}(i-x))$。

注意：一个降噪设备只会影响到它修建后产生的噪声。

降噪设备有一个不足，就是如果降噪设备的位置发出了噪声，那么该位置的降噪设备会被立刻摧毁，即不会对这次和以后发出的噪声产生效果。

所以，在某些时刻，管理人员会在一些位置上新增修建降噪设备。

现在在 $m$ 个单位时间内，每个时间可能发生三种事件。

• 输入格式为 1 i j，代表 $i$ 座位的人发出了响度 $j$ 的声音。

• 输入格式为 2 i，代表求 $i$ 座位的人受到的噪声。

• 输入格式为 3 i，代表管理人员在位置 $i$ 上新增修建了一个降噪设备，如果这个位置原来就有降噪设备，则本次操作无效。当然，因为一个降噪设备只会影响到它修建后产生的噪声，所以在一个曾发出噪声的位置新增修建降噪设备，不会使得这个降噪设备被立即摧毁。

输入格式

第一行，座位数 $n$ 和事件数 $m$。

第二行，共 $n$ 个数，为 $a_i$，代表第 $i$ 个座位的人发出的噪声的衰退系数。

第三行，共 $n$ 个数，为 $b_i$，其为 $1$ 代表这个位置有降噪设备，否则没有。

接下来 $m$ 行，每行一个事件。

在事件中，先输入事件编号。然后 $i$（记 $las$ 为上一次输出的答案，初始为 $0$）要进行变换得到真实的输入。$i$ 应变成 $((i+las-1)\bmod n)+1$。

输出格式

对于操作 $2$ 进行输出，输出后换行。

3 2
1 1 1
0 0 0
1 1 5
2 3

3

5 5
1 2 3 4 1
1 1 0 0 1
1 1 6
1 2 8
3 1
1 1 10
2 5

6

8 5
1 2 2 1 1 2 3 1
0 0 0 0 0 0 0 0
1 1 3
2 3
3 2
1 2 4
2 5

1
0

提示

样例解释

对于前 $2$ 个样例，变化后的输入与原输入相同。

对于第 $1$ 个样例，唯一的贡献来自于位置 $1$ 产生的 $5$ 点噪音，到达位置 $3$ 时的噪音为 $\max(0,5-(3-1)\times 1)=3$。

本题目采用捆绑测试。

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^5,1\le a_i\le 10^9,b_i\in\{0,1\},1\le i\le n,1\le j\le 10^9$。