H - Gardening Diary

実行時間制限：2000 ms
メモリ制限：1073741824 Bytes
配点：150 点
ジャッジ：Batch

不老長寿の Atsuo くんの家には、庭があります！
Atsuo くんの庭には、 $N$ 本の植物が一直線状に植えられている場所があります。
左から $i$ 番目の植物を $P_i$ とし、今日の $P_i$ の長さを $H_i$ とします。また、「区間 $[left, right]$ の植物」とは、すべての $P_i \; (left \leq i \leq right)$ の事を指します。

彼は、明日から $D$ 日間、庭の植物の観察日記を行うことにしました。Atsuo くんが管理のために毎日行うタスクは以下の２種類です。
今日から $j$ 日後について、

区間 $[L_j, R_j]$ の植物に薬剤をまく。これによって、区間 $[L_j, R_j]$ の植物の長さがすぐに $X_j$ 伸びる。
区間 $[A_j, B_j]$ の植物の中で、もっとも長いものを探して、観察日記に長さを記録する。

というタスク二つを、1 → 2 の順番で 1 回ずつ行います。

あなたはすべての $X_j$ の情報を調べ上げたので、今後 $D$ 日間の観察日記の内容を予測してください。

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq H_i \leq 10^9 \; (1 \leq i \leq N)$
$1 \leq D \leq 10^5$
$1 \leq L_j \leq R_j \leq N \; (1 \leq j \leq D)$
$1 \leq A_j \leq B_j \leq N \; (1 \leq j \leq D)$
$1 \leq X_j \leq 10^5 \; (1 \leq j \leq D)$
入力はすべて整数

小課題

(50点) $1 \leq N, \: D \leq 1000$
(50点) $L_j = R_j \; (1 \leq j \leq D)$
(50点) 追加の制約はない。

入力

 $N$ 

 $H_1~H_2~...~H_N$ 

 $D$ 

 $L_1~R_1~X_1~A_1~B_1$ 

 $L_2~R_2~X_2~A_2~B_2$ 

 $\vdots$ 

 $L_D~R_D~X_D~A_D~B_D$

出力

明日から $D$ 日後までに、2 つ目のタスクで記録される数（長さ）を、改行区切りで出力してください。

入出力例

入力例

6
1 3 2 4 5 2
3
1 3 2 1 4
2 5 1 1 5
5 5 4 5 5

出力例

5
6
10

1 日目は、植物の長さは

3 5 4 4 5 2

となっていて、この時区間 $[1, 4]$ の植物で最も長いのは $P_2$ なので、その長さの 5 を出力します。
2 日目は

3 6 5 5 6 2

3 日目は

3 6 5 5 10 2

となるので、同様に 2, 3 日目の答えは 6, 10 となります。