题目描述

OIVillage 是一个风景秀美的乡村，为了更好的利用当地的旅游资源，吸引游客，推动经济发展，xkszltl 决定修建了一条铁路将当地 $n$ 个最著名的经典连接起来，让游客可以通过火车从铁路起点（$1$ 号景点）出发，依次游览每个景区。为了更好的评价这条铁路，xkszltl 为每一个景区都哦赋予了一个美观度，而一条旅行路径的价值就是它所经过的景区的美观度之和。不过，随着天气与季节的变化，某些景点的美观度也会发生变化。

xkszltl 希望为每位旅客提供最佳的旅行指导，但是由于游客的时间有限，不一定能游览全部景区，然而他们也不希望旅途过于短暂，所以每个游客都希望能在某一个区间内的车站结束旅程，而 xkszltl 的任务就是为他们选择一个终点使得旅行线路的价值最大。可是当地的景点与前来观光的旅客实在是太多了，xkszltl 无法及时完成任务，于是找到了准备虐杀 NOI2011 的你，希望你能帮助他完成这个艰巨的任务。

输入格式

第一行给出一个整数 $n$，接下来一行给出 $n$ 的景区的初始美观度。

第三行给出一个整数 $m$，接下来 $m$ 行每行为一条指令：

1. 0 x y k：表示将 $x$ 到 $y$ 这段铁路边上的景区的美观度加上 $k$；
2. 1 x y：表示有一名旅客想要在 $x$ 到 $y$ 这段（含 $x$ 与 $y$）中的某一站下车，你需要告诉他最大的旅行价值。

输出格式

对于每个询问，输出一个整数表示最大的旅行价值。

样例输入

5
1 8 -8 3 -7
3
1 1 5
0 1 3 6
1 2 4

样例输出

9
22

数据规模与约定

对于 $20\%$ 的数据，$n,m\le 3\times 10^3$；

对于 $40\%$ 的数据，$n,m\le 3\times 10^4$；

对于 $50\%$ 的数据，$n,m\le 5\times 10^4$；

另外 $20\%$ 的数据，$n,m\le 10^5$，修改操作 $\le 20$；

对于 $100\%$ 的数据，$n,m\le 10^5$。