Все дороги ведут к «Sole» (единственной), навигационная карта нового поколения от Hyundai AutoEver — «SoleMap».

Каждый из нас хотя бы раз видел, как человек, впервые едущий по маршруту, попадает в затруднительное положение из-за того, что свернул не на той развилке или занял не ту полосу. Даже при наличии навигатора бывает сложно соотнести экран устройства с реальной дорогой. SoleMap — это навигационная карта нового поколения, которую разрабатывает Hyundai AutoEver, чтобы решить эти проблемы водителей. Название SoleMap образовано от прилагательного «Sole» (единственный) и слова «Map» (карта), что подчеркивает идею интеграции. Внедрение SoleMap в реальные навигационные системы запланировано на 2024 год.

Дорожную структуру страны «Прямая» можно представить как $N$ городов, расположенных на одной прямой линии, где для каждого $1 \leq i \leq (N-1)$ город $i$ и город $(i+1)$ соединены двусторонней дорогой с $w_{i}$ полосами движения. В этой стране ежедневно перемещаются $x_{j}$ автомобилей из города $u_{j}$ в город $v_{j}$. Таким образом, общее количество автомобилей, перемещающихся по стране каждый день, составляет $\sum_{j} x_{j}$. Хотя маршрут между любыми двумя городами в стране «Прямая» единственный, время в пути может зависеть от того, какие полосы движения используются, из-за возможных заторов. Поэтому обычные навигаторы, которые не учитывают полосы движения, не приносят большой пользы.

Президент страны «Прямая» Кипа ввел в тестовом режиме SoleMap, которая кардинально отличается от существующих навигаторов. Новости о том, что навигатор эффективно подсказывает самый быстрый путь с учетом полос движения, быстро распространились, и в итоге все навигаторы в стране стали использовать SoleMap. Обеспокоенный тем, что из-за SoleMap количество личных автомобилей на дорогах может резко возрасти и привести к разрушению дорожного полотна, Кипа поручил Hyundai AutoEver рассчитать показатель «дорожной нагрузки».

К счастью, до того как стать президентом, Кипа глубоко изучал математику и инженерию, поэтому он строго определил понятие дорожной нагрузки, чтобы специалистам не пришлось ломать голову над созданием значимых метрик. Для каждой дороги дорожная нагрузка определяется следующим образом: если по дороге ежедневно проезжает $c$ автомобилей, а дорога имеет $w$ полос, то нагрузка — это минимально возможная сумма квадратов количества автомобилей на каждой полосе при оптимальном распределении $c$ автомобилей по $w$ полосам.

Например, если для некоторой дороги $c = 4$ и $w = 3$, автомобили могут быть распределены по полосам так:

• Все $4$ автомобиля едут по одной полосе: $4^{2} + 0^{2} + 0^{2} = 16$
• $3$ автомобиля по одной полосе, $1$ автомобиль по другой: $3^{2} + 1^{2} + 0^{2} = 10$
• $2$ автомобиля по одной полосе, $2$ автомобиля по другой: $2^{2} + 2^{2} + 0^{2} = 8$
• $2$ автомобиля по одной полосе, $1$ автомобиль по второй, $1$ автомобиль по третьей: $2^{2} + 1^{2} + 1^{2} = 6$

Минимальное значение, равное $6$, и будет являться дорожной нагрузкой.

Будучи программистом SoleMap, попробуйте рассчитать дорожную нагрузку для каждой дороги, исходя из данных о транспортной ситуации в стране «Прямая», и получите шанс на повышение!

Входные данные

В первой строке через пробел заданы количество городов $N$ и количество записей о транспортных потоках $M$. ($2 \leq N \leq 500000$; $1 \leq M \leq 500000$)

Во второй строке через пробел заданы $(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}$) Это означает, что ежедневно $x_{j}$ автомобилей перемещаются из города $u_{j}$ в город $v_{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$: так как полоса всего одна, $3^{2} = 9$
• Дорожная нагрузка для дороги между городом $2$ и городом $3$: как было показано ранее, $6$
• Дорожная нагрузка для дороги между городом $3$ и городом $4$: так как автомобиль всего один, по какой бы полосе он ни ехал, $1^{2} + 0^{2} + 0^{2} + 0^{2} = 1$