문제

길이가 $N$인 수열 $A_1, A_2, \dots, A_N$이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성해 보자.

• l r k: $l \le i \le r$을 만족하는 모든 $i$에 대하여, $A_i$의 값에 $k$를 더한다. ($1 \le l \le r \le N$)

모든 쿼리를 순서대로 처리한 후, 최종적으로 수열의 각 원소가 어떤 값을 가지고 있는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N, Q \le 100,000$)

둘째 줄에 수열 $A$를 구성하는 $N$개의 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($-10^9 \le A_i \le 10^9$)

셋째 줄부터 $Q$개의 줄에 걸쳐 각 쿼리를 나타내는 세 정수 $l, r, k$가 공백으로 구분되어 주어진다. ($-10^9 \le k \le 10^9$)

출력

모든 쿼리를 수행한 후의 최종 수열 $A_1, A_2, \dots, A_N$을 한 줄에 공백으로 구분하여 출력한다.

예제 입력 1

5 3
1 2 3 4 5
1 5 1
2 5 2
3 5 3

예제 출력 1

2 5 9 10 11