题目描述

给定序列 $a_1,\dots,a_n$， $m$ 次操作：

修改操作：给出 $l,r,x$，将 $a_l,a_{l+1},\dots,a_r$ 的值增加 $x$；

查询操作：给出 $l,r,x$，问满足 $l\le i\le r,\;a_i<x$ 的 $i$ 对应 $a_i$ 的历史最大值（即初值和每次修改操作后的值中最大的一个）。

输入格式

第一行两个整数 $n,m$；

接下来一行 $n$ 个整数 $a_1,a_2,\dots,a_n$；

接下来 $m$ 行每行四个整数 $o,l,r,x$，其中 $o=1$ 表示修改操作，$o=2$ 表示查询操作。

输出格式

对每个查询操作，输出一行，表示答案（特别地，如果不存在满足条件的 $i$，则输出 -inf）。

5 10
-53 36 41 55 77
1 1 1 10
2 4 4 79
2 3 3 -28
1 1 5 -29
1 1 3 27
2 2 5 88
2 2 3 24
1 2 2 10
1 1 3 -9
1 2 5 -10

55
-inf
77
-inf

提示

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $0\%$ 的数据，满足 $n,m\le 5000$。

对于另外 $1/3$ 的数据，查询操作保证 $l=1,\;r=n$。

对于另外 $1/3$ 的数据，没有修改操作。

对于 $100\%$ 的数据，满足 $1\le n,m\le 5\times 10^5$，$|a_i|\le 10^9$（仅初始给定的序列保证这个限制），$1\le l\le r\le n$，$|x|\le 10^9$。