题目背景

Y 同学在掌握了基础的线段树（【模板】线段树 1）之后，开始探索其更高级的应用。他发现，线段树不仅能高效地维护区间信息，其树状结构本身还可以用来优化某些查询。为了验证自己的想法，他设计了下面这个问题。

题目描述

给定一个长度为 $n$ 的数列 $\{a_n\}$，你需要支持以下三种操作：

1. 1 x y k：将区间 $[x, y]$ 内的每个数都加上一个整数 $k$。
2. 2 x y：查询区间 $[x, y]$ 内所有数的和。
3. 3 d：在区间 $[1, n]$ 中，查询使得前缀和 $\sum_{i=1}^{p} a_i \ge d$ 成立的最小的下标 $p$。如果不存在这样的 $p$，则输出 $n+1$。

输入格式

第一行包含两个整数 $n, m$，分别表示数列的长度和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值 $a_i$。

接下来 $m$ 行，每行包含若干个整数，表示一个操作，具体格式如下：

• 1 x y k：表示一个类型 1 的操作。
• 2 x y：表示一个类型 2 的操作。
• 3 d：表示一个类型 3 的操作。

输出格式

对于每个类型 2 和类型 3 的操作，输出一行一个整数，表示查询的结果。

样例

样例输入 #1

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

样例输出 #1

11
8
20
2

提示

样例解释

初始数列为 $a = [1, 5, 4, 2, 3]$。

1. 2 2 4：查询区间 $[2, 4]$ 的和，即 $5+4+2=11$。
2. 1 2 3 2：将 $a_2, a_3$ 加上 $2$。数列变为 $a = [1, 7, 6, 2, 3]$。
3. 2 3 4：查询区间 $[3, 4]$ 的和，即 $6+2=8$。
4. 1 1 5 1：将整个数列的每个数加上 $1$。数列变为 $a = [2, 8, 7, 3, 4]$。
5. 2 1 4：查询区间 $[1, 4]$ 的和，即 $2+8+7+3=20$。
6. 3 6：此时数列为 $[2, 8, 7, 3, 4]$，我们需要找到最小的 $p$ 使得前缀和 $\ge 6$。
   • $p=1$：前缀和为 $2$。
   • $p=2$：前缀和为 $2+8=10$。
   • $10 \ge 6$ 成立，且这是第一个满足条件的。因此最小的 $p$ 为 $2$。输出 $2$。

数据范围与约定

对于所有测试数据，保证：

• $1 \le n, m \le 5 \times 10^5$
• 对于操作 1，有 $1 \le x \le y \le n$，$-10^9 \le k \le 10^9$。
• 对于操作 2，有 $1 \le x \le y \le n$。
• 对于操作 3，有 $-10^{18} \le d \le 10^{18}$。
• 初始时，$-10^9 \le a_i \le 10^9$。
• 保证在任意时刻，数列中所有元素的绝对值之和不超过 $10^{18}$。