题目描述

以下内容摘自第一卷第五章「乾坤一掷」：

......突然间，他看到了这道题目的「关键」。

所谓「关键」，就是一切交汇的节点。

不倒翁的重心。

建筑物的支撑点。

只要在合适的地方施加压力。

那么，看起来高不可攀的「结构」，就会在转瞬之间———

「轰然倒塌」。

他开始飞快地敲打键盘。

噼里啪啦。噼里啪啦。

「在搞些什么呀，这个小子。」

「是做不出题目，想要干扰别人吗？」

「这种手段可真下作啊！」

对周围的非议浑然不觉。

噼里啪啦。噼里啪啦。

他继续敲打着键盘。

出现在屏幕上的代码飞快增长着。

如此这般又过了五分钟。

「...成了。」

第一步，成功。

他把鼠标移动到「编译运行」按钮上面。

既能把代码转化为程序，又能对其加以检验。

这是一举两得的操作。

「咔哒」

黑底白字的窗口跳了出来。

第二步，成功。

这道题目的「样例数据」十分简单。

一个两位数而已。

他小心地按动键盘，输入这个数字。

然后按下回车键。

另一个白色的数字映入眼帘。

和样例的答案分毫不差。

第三步，成功。

但他没有丝毫放松。

「接下来...才是决定成败的时候！」

没错。

仅仅过了样例，不代表做出了这道题目。

这是信息学学员的「常识」。

摆在他面前的，还有凶险得多的——

「系统测试」。

这次比赛是IOI赛制。

所有参赛选手都看得见他人的提交和得分。

是满座皆惊，还是自取其辱——

「没有退路可以走了。」

他打开提交页面。

复制，粘贴，提交。

跳转到了评测页面。

页面上的灰色小圆圈飞快地转动着。

评测机也在飞快运行着。

CPU处理一条条指令。

内存读取一个个数据。

信息以光速在电路中传导着。

这次提交开始吸引众人的目光。

「这小子想挑战这道题吗？」

「真勇敢哪。可惜，单纯的勇气是无法做出题目来的。」

这是颠扑不破的事实。

评测机还在飞快运行着。

第一个测试点，通过！

第二个测试点，通过！

第三个测试点，通过！

「...过了三个点？想必，是写的暴力算法吧。」

「拿保底分数也是技能之一嘛。哈哈。」

第四个测试点，通过！

第五个测试点，通过！

第六个测试点，通过！

这已经超出了单纯的「暴力」所能达到的范畴。

众人的神色变得凝重起来。

第七个测试点，通过！

第八个测试点，通过！

第九个测试点，通过！

「怎么可能？竟然一连过了九个测试点！」

「难道说...他抓住了题目的「关键」吗？」

「不要这么快就下结论。还有一组特意构造过的数据。」

风暴的中心最为平静。

他坐在自己的座位上，死死的盯着不停转动的灰色圆圈。

一秒。

两秒。

三秒。

——圆圈变了颜色。

从灰色，变成了绿色。

「Accepted」。

不容置疑的结果。

1就是1。0就是0。

太阳东升西落。

他过了这道题。

这些都是「客观事实」。

沉默如同暴风雨一般扩展开来。

他却已经打开了另一道题的题面。

---

当然，你不看上面的内容也不影响AC此题。这道题题意非常简单，给定长度为 $n$ 的数列，和 $n$ 次操作，其中操作分为区间加法和询问区间内小于某个值 $x$ 的前驱（比其小的最大元素）。

输入格式

第一行输入一个数字 $n$。

第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$，以空格隔开。

接下来输入 $n$ 行询问，每行输入四个数字 $\mathrm{opt}$、$l$、$r$、$c$，以空格隔开。

若 $\mathrm{opt} = 0$，表示将位于 $[l, r]$ 的之间的数字都加 $c$。

若 $\mathrm{opt} = 1$，表示询问 $[l, r]$ 中 $c$ 的前驱的值（不存在则输出 $-1$）。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

样例输入

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

样例输出

3
-1

数据范围与提示

对于 $100\%$ 的数据，$ 1 \leq n \leq 100000, -2^{31} \leq \mathrm{others}$、$\mathrm{ans} \leq 2^{31}-1$。

---

友情提示1

送分题

友情提示2

后台数据存在梯度，可以选择暴力骗分，预计得分 XX