小王的工作任务分配（hard ver.）
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

小王就职于一家充满活力的创意公司，公司日常运营中会同时开展多个创意项目。这些项目各自具有独特的挑战维度，可抽象为一系列数值来代表其难度层级。小王肩负着灵活管理这些项目难度层级的任务，同时还要按需统计特定项目组合的难度总值，以便为团队资源分配和项目推进节奏提供数据支撑。在这个过程中，他会收到来自上级的不同指令，以应对多变的项目需求。
（本题easy和hard的区别在于，hard ver.内存限制变小，easy ver.没有opt = 1）
每组数据集合涵盖一个长度为 n 的项目难度数组 a（数组元素下标从 1 起有序编排），以及 m 条操作指令。操作指令具体分为以下两类：
调整指令（opt = 1)：将数组 a 中第 x 个项目对应的难度层级数值更新为 k，即执行 a[x] = k 操作；
统计指令（opt = 2)：从下标为 L 的项目起始，按照每隔 y 个项目的规律选取项目，到项目R结束（包括起始项目 ），统计这些项目的难度层级数值总和。

输入描述:

每个测试文件仅包含一组测试数据。
首行包含两个整数 n 和 m（1 \le n, m \le 2 \times 10^5），分别表示项目数量和操作指令数量；
第二行包含 n 个整数，表示初始的项目难度数组 a（1 \le a_i \le 10^9）；
接下来 m 行，每行首先有一个整数 opt（），代表一条操作指令。
对于opt = 1: 输入x, k（ 1 \le x \le n， 1 \le k \le 10^9）。
对于opt = 2: 输入 L，R，y（1 \le L \le R \le n，1 \le x \le n）。

本题强制在线，所有输入的 x, k, L, R, y 均需要异或 lastans, 其定义为上一次操作 2 的答案对 2^{31}取模的结果，若之前没有操作 2，则 lastans = 0。请注意上面的数据范围均为解密后数值的数据范围，加密后的实际输入可能超过这个范围。
请注意此题的内存限制
此题的数据量较大，注意常数优化

输出描述:

对于每组数据中的每条统计指令（opt = 2），输出一行结果，为按照指令要求统计得到的项目难度层级数值总和。
示例1

输入

复制 
5 4
1 2 3 4 5
2 1 5 2
1 11 10
2 11 12 10
2 9 12 9

输出

复制 
9
8
11

备注: