暂无测试数据。

这个呢，实在有点复杂，也不难，就是不想写了，有心人帮忙搞下数据吧。
题目描述
LYC是一个很无聊的同志。
话说有一天，他开始玩一种简化版俄罗斯方块（不会消除）。他找来了一区间，其中有初始的一些方块堆积。LYC又找来了很多图形木块，有矩形，有等腰三角形，等腰梯形三种形状（注意如果有倾斜的直线，将其放在坐标轴上）。如下图所
示：（一为空 繁为实）
矩形
繁繁繁繁繁
繁繁繁繁繁
繁繁繁繁繁
等腰三角形（你可以认为是一个上底为一的等腰梯形）
一一繁一一
一繁繁繁一
繁繁繁繁繁
等腰梯形
一一一一一
一繁繁繁一
繁繁繁繁繁
或者，如果某图形很宽，请对所有点的纵坐标下取整，如下图的三角形
一一一一一繁一一一一一
一繁繁繁繁繁繁繁繁繁一
LYC同学会一块一块的把图形向下放，图形堆积好后，不会移动，然后问你一些问题。

输入格式
第一行一个整数n(n<=1e6)表示整个区间的宽度，从1到n；
第二行n个整数，表示每个位置上初始高度。
第三行为一个整数m(m<=1e5)，表示操作数。
然后是m行，每行一个操作，输入一个数t，表示操作类型
操作说明：（注意：放置后不在区间内的部分不予考虑）
1：矩形
输入x,y表示宽度与高度，输入k，表示矩形左下角的放置横坐标。
2：三角形
输入x,y表示宽度与高度，输入k，表示三角形底边左下角放置横坐标。（保证x为奇数）
3：等腰梯形
输入x,z,y表示下底宽度与上底高度与高，输入k，表示等腰梯形左下角放置横坐标。（保证|x-z|为偶数，且z>1）
4:查询
输入l,r表示查询l到r区间堆积的最高高度
输出格式
仅对于4操作，输出一行为答案。

对于图形堆积的说明：
一：原图
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一繁一一一一一一一一一一
一一繁一一一一繁一繁一一一一一繁一一一一
繁一繁一繁繁繁繁繁繁一繁繁繁一繁一繁一一
在上面放一个等腰三角形（[8,12]区间）
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一繁一一一一一一一一一一
一一一一一一一一繁繁繁一一一一一一一一一
一一一一一一一繁繁繁繁繁一一一一一一一一
一一一一一一一一一繁一一一一一一一一一一
一一繁一一一一繁一繁一一一一一繁一一一一
繁一繁一繁繁繁繁繁繁一繁繁繁一繁一繁一一
等腰三角形会在所覆盖区间的最高的一点立足，不会下落，并且将成为新的最高点。
5
1 2 3 2 1
6
1 2 1 1
4 1 5
2 3 3 3
4 2 4
3 3 1 1
4 1 5
输出样例
3
6
6
样例说明
原图
一一一一一
一一一一一
一一一一一
一一繁一一
一繁繁繁一
繁繁繁繁繁
到
一一一一一
一一一一一
一一一一一
繁繁繁一一
一繁繁繁一
繁繁繁繁繁
到
一一一繁一
一一一繁一
一一繁繁繁
繁繁繁一一
一繁繁繁一
繁繁繁繁繁（遵从纵坐标下取整，故并非是几何意义的三角形）
到
一繁一繁一
繁繁繁繁一
一一繁繁繁
繁繁繁一一
一繁繁繁一
繁繁繁繁繁（遵从纵坐标下取整，故并非是几何意义的梯形）
规定
开long long
对于第2,5两个测试点没有2,3操作。
对于30%的数据 m<=100 n<=1000
对于60%的数据 m<=1000 n<=10000
对于100%的数据 m<=100000 n<=100000