すべての地図は「ただ一つ（Sole）」に通じる、現代オートエバーの次世代ナビゲーション地図「SoleMap」

初めて行く道を運転する際、分かれ道を間違えたり、車線を間違えて困っている人を見た経験が誰にでもあるでしょう。ナビゲーションがあっても、初めての道ではナビゲーションの画面と実際の道路を頭の中で即座に照らし合わせるのが難しい場合が多いです。SoleMapは、このようなドライバーの不便を解消するために現代オートエバーが構築中の次世代ナビゲーション地図です。「ただ一つの」という意味を持つ形容詞「Sole」に地図（Map）を加え、統合の意味を強調した名前です。SoleMapは2024年内の実用ナビゲーション搭載を目指しています。

直線国の道路構造は、$N$個の都市が一列に並んでおり、すべての $1 \leq i \leq (N-1)$ について、$i$番目の都市と $(i+1)$番目の都市が双方向の $w_{i}$車線道路で直接つながっている形と考えられます。この直線国には毎日、$u_{j}$番目の都市から $v_{j}$番目の都市まで移動する車両が $x_{j}$台あります。したがって、直線国では毎日合計 $\sum_{j} x_{j}$台の車両が移動します。直線国の移動経路は唯一ですが、どの車線を利用するかによって、より速く移動できたり、渋滞のために遅く移動したりすることがあります。そのため、車線の区別なく経路だけを案内する既存のナビゲーションはあまり役に立ちませんでした。

直線国の大統領キーパは、既存のナビゲーションとは明確に区別されるSoleMapを試験導入しました。すると、ナビゲーションが車線単位で最も速い道を正確に教えてくれるという噂が広まり、結局直線国のすべてのナビゲーションがSoleMapになりました。SoleMapのせいで自家用車の利用者が急増し、道路が崩壊しないか心配したキーパは、現代オートエバーに「道路負担」という値を計算するよう指示しました。

幸いなことに、キーパは就任前に数学と工学を深く学んでいたため、実務者が自ら有意義な指標を作り出すために頭を悩ませる必要がないよう、道路負担を厳密に定義してくれました。各道路に対する道路負担とは、毎日その道路を利用する車両の数 $c$ に対して、$c$台の車両を $w$個の車線が適切に分担したとき、各車線を通過する車両台数の二乗の和の最小値です。

例えば、ある道路に対して $c = 4, w = 3$ の場合、以下のように車線が車両を分担できます。

• 1つの車線に4台の車両がすべて通る場合、$4^{2} + 0^{2} + 0^{2} = 16$
• 1つの車線に3台の車両が、別の1つの車線に残りの1台の車両が通る場合、$3^{2} + 1^{2} + 0^{2} = 10$
• 1つの車線に2台の車両が、別の1つの車線に残りの2台の車両が通る場合、$2^{2} + 2^{2} + 0^{2} = 8$
• 1つの車線に2台の車両が、別の1つの車線に1台の車両が、残りの1つの車線に残りの1台の車両が通る場合、$2^{2} + 1^{2} + 1^{2} = 6$

このうち最小値である $6$ が道路負担となります。

SoleMapのプログラマーであるあなたが、直線国の交通状況が与えられたとき、各道路の道路負担を計算して昇進のチャンスを狙ってみましょう！

入力

1行目に直線国の都市の数 $N$ と、直線国を移動する車両情報を表す整数 $M$ が空白を挟んで与えられます。($2 \leq N \leq 500000$; $1 \leq M \leq 500000$)

2行目に $(N-1)$ 個の整数 $w_{1}, w_{2}, \cdots, w_{N-1}$ が空白を挟んで与えられます。($1 \leq w_{i} \leq 10^{9}$) これは各 $1 \leq i \leq (N-1)$ について、$i$番目の都市と $(i+1)$番目の都市を結ぶ道路が $w_{i}$車線であることを意味します。

続く $M$ 行に直線国の交通状況情報が与えられます。各 $1 \leq j \leq M$ について、$(j+2)$行目に $u_{j}, v_{j}, x_{j}$ が空白を挟んで与えられます。($1 \leq u_{j} < v_{j} \leq N$; $1 \leq x_{j} \leq 10^{9}$) これは毎日 $u_{j}$番目の都市から $v_{j}$番目の都市へ移動する車両が $x_{j}$台あることを意味します。

与えられるすべての $x_{j}$ の合計は $10^{9}$ を超えません。

出力

$(N-1)$ 行を出力します。

各 $1 \leq i \leq (N-1)$ について、$i$行目には $i$番目の都市と $(i+1)$番目の都市を結ぶ道路の道路負担を出力します。

入出力例

入力 1

4 2
1 3 4
1 3 3
2 4 1

出力 1

9
6
1

注記

以下のように、毎日道路を利用する車両の数を計算できます。

• 1番目の都市と2番目の都市を結ぶ道路：$3 + 0 = 3$台
• 2番目の都市と3番目の都市を結ぶ道路：$3 + 1 = 4$台
• 3番目の都市と4番目の都市を結ぶ道路：$0 + 1 = 1$台

以下のように各道路の道路負担を計算できます。

• 1番目の都市と2番目の都市を結ぶ道路の道路負担：車線が1つしかないため、$3^{2} = 9$
• 2番目の都市と3番目の都市を結ぶ道路の道路負担：前述の通り $6$
• 3番目の都市と4番目の都市を結ぶ道路の道路負担：車が1台しかないため、どの車線を走っても $1^{2} + 0^{2} + 0^{2} + 0^{2} = 1$