H - Gardening Diary

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

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

1. 区間 $[L_j, R_j]$ の植物に薬剤をまく。これによって、区間 $[L_j, R_j]$ の植物の長さがすぐに $X_j$ 伸びる。
2. 区間 $[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)$
• 入力はすべて整数

小課題

1. (50点) $1 \leq N, \: D \leq 1000$
2. (50点) $L_j = R_j \; (1 \leq j \leq D)$
3. (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
Copy

出力例

5
6
10
Copy

1 日目は、植物の長さは

3 5 4 4 5 2
Copy

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

3 6 5 5 6 2
Copy

3 日目は

3 6 5 5 10 2
Copy

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