All maps lead to 'Sole', Hyundai AutoEver's next-generation navigation map 'SoleMap'.

Everyone has experienced the frustration of taking a wrong turn or getting into the wrong lane when driving on a route for the first time. Even with a navigation system, it is often difficult to immediately map the navigation screen to the actual road when driving on unfamiliar paths. SoleMap is a next-generation navigation map being built by Hyundai AutoEver to resolve these inconveniences for drivers. SoleMap is a name that emphasizes the meaning of integration by adding 'Map' to the adjective 'Sole', which means 'only one'. SoleMap aims to be installed in actual navigation systems within 2024.

The road structure of Straightland can be thought of as $N$ cities arranged in a straight line, where for every $1 \leq i \leq (N-1)$, city $i$ and city $(i+1)$ are directly connected by a bidirectional $w_{i}$-lane road. In this Straightland, there are $x_{j}$ vehicles moving from city $u_{j}$ to city $v_{j}$ every day. Therefore, a total of $\sum_{j} x_{j}$ vehicles travel in Straightland daily. Although the travel route in Straightland is unique, one might travel faster or slower due to traffic congestion depending on which lane is used. Thus, existing navigation systems that only find routes without distinguishing between lanes were not very helpful.

Kipa, the president of Straightland, piloted SoleMap, which is distinctly different from existing navigation systems. As news spread that the navigation system effectively suggests the fastest route at the lane level, all navigation systems in Straightland eventually became SoleMap. Worried that the roads might collapse due to a sudden increase in private vehicle usage caused by SoleMap, Kipa instructed Hyundai AutoEver to calculate a value called 'road burden'.

Fortunately, because Kipa studied mathematics and engineering deeply before becoming president, he strictly defined the road burden so that practitioners would not have to struggle to create meaningful indicators themselves. For each road, the road burden is the minimum sum of the squares of the number of vehicles passing through each lane when $c$ vehicles, which use the road daily, are appropriately distributed among $w$ lanes.

For example, if $c = 4$ and $w = 3$ for a certain road, the lanes can distribute the vehicles as follows:

• If all $4$ vehicles travel in one lane: $4^{2} + 0^{2} + 0^{2} = 16$
• If $3$ vehicles travel in one lane and the remaining $1$ vehicle travels in another: $3^{2} + 1^{2} + 0^{2} = 10$
• If $2$ vehicles travel in one lane and the remaining $2$ vehicles travel in another: $2^{2} + 2^{2} + 0^{2} = 8$
• If $2$ vehicles travel in one lane, $1$ vehicle in another, and the remaining $1$ vehicle in the last lane: $2^{2} + 1^{2} + 1^{2} = 6$

The minimum value among these, $6$, becomes the road burden.

As a programmer for SoleMap, let's aim for a promotion by calculating the road burden for each road given the traffic situation in Straightland!

Input

The first line contains two integers $N$ and $M$, separated by a space, representing the number of cities in Straightland and the information about vehicles moving in Straightland, respectively. ($2 \leq N \leq 500000$; $1 \leq M \leq 500000$)

The second line contains $(N-1)$ integers $w_{1}, w_{2}, \cdots, w_{N-1}$, separated by spaces. ($1 \leq w_{i} \leq 10^{9}$) This means that for each $1 \leq i \leq (N-1)$, the road connecting city $i$ and city $(i+1)$ has $w_{i}$ lanes.

The next $M$ lines contain information about the traffic situation in Straightland. For each $1 \leq j \leq M$, the $(j+2)$-th line contains $u_{j}, v_{j}, x_{j}$, separated by spaces. ($1 \leq u_{j} < v_{j} \leq N$; $1 \leq x_{j} \leq 10^{9}$) This means that there are $x_{j}$ vehicles traveling from city $u_{j}$ to city $v_{j}$ every day.

The sum of all given $x_{j}$ does not exceed $10^{9}$.

Output

Output $(N-1)$ lines.

For each $1 \leq i \leq (N-1)$, output the road burden of the road connecting city $i$ and city $(i+1)$ on the $i$-th line.

Examples

Input 1

4 2
1 3 4
1 3 3
2 4 1

Output 1

9
6
1

Note

The number of vehicles using the road daily can be calculated as follows:

• Road connecting city $1$ and city $2$: $3 + 0 = 3$ vehicles
• Road connecting city $2$ and city $3$: $3 + 1 = 4$ vehicles
• Road connecting city $3$ and city $4$: $0 + 1 = 1$ vehicle

The road burden for each road can be calculated as follows:

• Road burden of the road connecting city $1$ and city $2$: Since there is only one lane, $3^{2} = 9$
• Road burden of the road connecting city $2$ and city $3$: As explained above, $6$
• Road burden of the road connecting city $3$ and city $4$: Since there is only one vehicle, regardless of which lane it travels in, $1^{2} + 0^{2} + 0^{2} + 0^{2} = 1$