Wszystkie drogi prowadzą do „Sole” (jedynego), czyli „SoleMap” – nawigacji nowej generacji od Hyundai AutoEver.

Każdy z nas przynajmniej raz widział kogoś, kto podczas jazdy w nieznane miejsce pogubił się na rozwidleniu lub zajął niewłaściwy pas ruchu. Nawet z nawigacją, w nieznanym terenie często trudno jest błyskawicznie przełożyć obraz z ekranu na rzeczywistą drogę. SoleMap to nawigacja nowej generacji, którą buduje Hyundai AutoEver, aby rozwiązać te problemy kierowców. Nazwa SoleMap łączy przymiotnik „Sole” (oznaczający „jedyny”) ze słowem „Map” (mapa), podkreślając ideę integracji. Celem jest wprowadzenie SoleMap do użytku w nawigacjach samochodowych przed końcem 2024 roku.

Strukturę dróg w Krainie Linii Prostej można opisać jako $N$ miast ułożonych w linii prostej, gdzie dla każdego $1 \leq i \leq (N-1)$ miasto $i$ oraz miasto $(i+1)$ są połączone bezpośrednio drogą dwukierunkową o $w_{i}$ pasach ruchu. W Krainie Linii Prostej codziennie przemieszcza się $x_{j}$ pojazdów z miasta $u_{j}$ do miasta $v_{j}$. Łącznie każdego dnia po drogach porusza się $\sum_{j} x_{j}$ pojazdów. Choć trasa przejazdu jest unikalna, czas podróży zależy od wybranego pasa ruchu – można jechać szybciej lub utknąć w korku. Dlatego dotychczasowe nawigacje, które nie rozróżniały pasów ruchu, nie były zbyt pomocne.

Prezydent Krainy Linii Prostej, Kipa, wprowadził pilotażowo SoleMap. Wiadomość o tym, że nawigacja precyzyjnie wskazuje najszybszą drogę z uwzględnieniem pasów ruchu, szybko się rozniosła i wkrótce wszystkie nawigacje w kraju zostały zastąpione przez SoleMap. Obawiając się, czy nagły wzrost liczby kierowców korzystających z własnych aut nie doprowadzi do zniszczenia dróg, Kipa zlecił firmie Hyundai AutoEver obliczenie wartości zwanej „obciążeniem drogi”.

Na szczęście Kipa, który przed objęciem urzędu prezydenta studiował matematykę i inżynierię, ściśle zdefiniował obciążenie drogi, aby pracownicy nie musieli głowić się nad tworzeniem wskaźników od zera. Dla każdej drogi obciążenie drogi definiuje się jako minimalną sumę kwadratów liczby pojazdów na każdym pasie ruchu, przy założeniu, że $c$ pojazdów korzystających codziennie z danej drogi zostanie optymalnie rozdzielonych na $w$ pasów ruchu.

Na przykład, jeśli dla danej drogi $c = 4$ oraz $w = 3$, pojazdy można rozdzielić na pasy w następujący sposób:

• Wszystkie $4$ pojazdy na jednym pasie: $4^{2} + 0^{2} + 0^{2} = 16$
• $3$ pojazdy na jednym pasie, $1$ pojazd na drugim: $3^{2} + 1^{2} + 0^{2} = 10$
• $2$ pojazdy na jednym pasie, $2$ pojazdy na drugim: $2^{2} + 2^{2} + 0^{2} = 8$
• $2$ pojazdy na jednym pasie, $1$ pojazd na drugim, $1$ pojazd na trzecim: $2^{2} + 1^{2} + 1^{2} = 6$

Wartość minimalna, czyli $6$, stanowi obciążenie drogi.

Jako programista SoleMap, oblicz obciążenie każdej drogi na podstawie sytuacji drogowej w Krainie Linii Prostej i zawalcz o awans!

Wejście

W pierwszej linii podano liczbę miast $N$ oraz liczbę informacji o ruchu pojazdów $M$, oddzielone spacją ($2 \leq N \leq 500000$; $1 \leq M \leq 500000$).

W drugiej linii podano $(N-1)$ liczb całkowitych $w_{1}, w_{2}, \cdots, w_{N-1}$, oddzielonych spacjami ($1 \leq w_{i} \leq 10^{9}$). Oznacza to, że dla każdego $1 \leq i \leq (N-1)$ droga łącząca miasto $i$ z miastem $(i+1)$ ma $w_{i}$ pasów ruchu.

W kolejnych $M$ liniach podano informacje o sytuacji drogowej. Dla każdego $1 \leq j \leq M$, w $(j+2)$-giej linii podano $u_{j}, v_{j}, x_{j}$ oddzielone spacjami ($1 \leq u_{j} < v_{j} \leq N$; $1 \leq x_{j} \leq 10^{9}$). Oznacza to, że codziennie $x_{j}$ pojazdów przemieszcza się z miasta $u_{j}$ do miasta $v_{j}$.

Suma wszystkich podanych $x_{j}$ nie przekracza $10^{9}$.

Wyjście

Wypisz $(N-1)$ linii.

Dla każdego $1 \leq i \leq (N-1)$, w $i$-tej linii wypisz obciążenie drogi łączącej miasto $i$ z miastem $(i+1)$.

Przykład

Wejście 1

4 2
1 3 4
1 3 3
2 4 1

Wyjście 1

9
6
1

Uwagi

Liczbę pojazdów korzystających codziennie z danej drogi można obliczyć następująco:

• Droga między miastem $1$ a $2$: $3 + 0 = 3$ pojazdy
• Droga między miastem $2$ a $3$: $3 + 1 = 4$ pojazdy
• Droga między miastem $3$ a $4$: $0 + 1 = 1$ pojazd

Obciążenie każdej drogi oblicza się następująco:

• Obciążenie drogi między miastem $1$ a $2$: dostępny jest tylko jeden pas, więc $3^{2} = 9$
• Obciążenie drogi między miastem $2$ a $3$: jak wyjaśniono wcześniej, wynosi $6$
• Obciążenie drogi między miastem $3$ a $4$: jest tylko jeden pojazd, więc niezależnie od wybranego pasa, $1^{2} + 0^{2} + 0^{2} + 0^{2} = 1$