描述

ZLY有N条船，排成一列
每条船有价值V_i
船的价值可能变化
ZLY不时的地想知道[L, R]区间内船的最大价值
所以请你帮忙
ZLY答应事成之后给你\(1234567890^0\)-1条船

输入

第一行一个数N
第二行N个正整数V_1、V_2、...、V_N
第三行一个数M
接下来M行
每行三或四个正整数O、L、R、(X)
若O==0则存在X，表示[L, R]区间内船只价值+=X
若O==1则不存在X，表示询问[L, R]区间内船只价值最大值

输出

对于每个询问，输出一行一个整数，为询问区间内的船只价值最大值

样例

输入

1
1
2
0 1 1 2
1 1 1

输出

3

范围

40% N,M<=10
90% N,M<=10000
100% 1<=N,M<=\(10^5\) 1<=L<=R<=N 1<=V_i<=\(10^6\) 1<=X<=1000

限制

1000ms
128M