AT_abc426_f [ABC426F] Clearance

AtCoder 社のオンラインショップでは現在 $ N $ 個の商品を取り扱っており、商品 $ i $ の在庫は残り $ A_i $ 個です。 以下の $ Q $ 件の注文を順に処理してください。そのうち $ i $ 件目は次の通りです。 - 商品 $ l_i,l_i+1,\dots,r_i $ を $ k_i $ 個ずつ買う。但し、 $ k_i $ 個未満の商品はあるだけ全て買う。この注文で買われた商品の個数の合計を答えよ。 $ i

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ Q $ $ l_1 $ $ r_1 $ $ k_1 $ $ l_2 $ $ r_2 $ $ k_2 $ $ \vdots $ $ l_Q $ $ r_Q $ $ k_Q $

$ Q $ 行出力せよ。 そのうち $ i $ 行目には、 $ i $ 件目の注文で買われた商品の個数の合計を答えよ。

### Sample Explanation 1 この入力には $ 5 $ 件の注文が含まれます。 - はじめ、各商品の在庫は (商品 $ 1 $ から順に) $ 2,6,4,5,7,5 $ 個です。 - $ 1 $ 件目の注文は $ l_1 = 1, r_1 = 6, k_1 = 1 $ です。 - この注文で各商品は $ 1,1,1,1,1,1 $ 個、合計 $ 6 $ 個買われます。 - その後、各商品の在庫は $ 1,5,3,4,6,4 $ 個になります。 - $ 2 $ 件目の注文は $ l_2 = 3, r_2 = 5, k_2 = 4 $ です。 - この注文で各商品は $ 0,0,3,4,4,0 $ 個、合計 $ 11 $ 個買われます。 - その後、各商品の在庫は $ 1,5,0,0,2,4 $ 個になります。 - $ 3 $ 件目の注文は $ l_3 = 4, r_3 = 4, k_3 = 1 $ です。 - この注文で各商品は $ 0,0,0,0,0,0 $ 個、合計 $ 0 $ 個買われます。 - その後、各商品の在庫は $ 1,5,0,0,2,4 $ 個になります。 - $ 4 $ 件目の注文は $ l_4 = 2, r_4 = 5, k_4 = 1 $ です。 - この注文で各商品は $ 0,1,0,0,1,0 $ 個、合計 $ 2 $ 個買われます。 - その後、各商品の在庫は $ 1,4,0,0,1,4 $ 個になります。 - $ 5 $ 件目の注文は $ l_5 = 1, r_5 = 6, k_5 = 100 $ です。 - この注文で各商品は $ 1,4,0,0,1,4 $ 個、合計 $ 10 $ 個買われます。 - その後、各商品の在庫は $ 0,0,0,0,0,0 $ 個になります。 ### Constraints - 入力は全て整数 - $ 1 \le N \le 3 \times 10^5 $ - $ 1 \le A_i \le 10^{15} $ - $ 1 \le Q \le 3 \times 10^5 $ - $ 1 \le l_i \le r_i \le N $ - $ 1 \le k_i \le 10^9 $