지훈이는 수열을 좋아한다. 지금 지훈이는 size 가 N 인 수열을 가지고 놀고 있다. 지훈이는 K 개의 쿼리에 따라 수열을 변화시킬 것인데, 쿼리의 형식 및 작업 과정은 다음과 같다.</p>

• L R X : 수열을 오름차순으로 정렬한 결과를 A[1], A[2], … , A[N]이라 하자. 우선 A[L], A[L+1], … , A[R]에 X 만큼 더한다. 그 결과 수열을 다시 오름차순으로 정렬한다.

쿼리들을 순서대로 모두 수행한 후의 수열을 출력하라.

입력 형식

첫째 줄에 N 과 K 가 띄어쓰기로 구분되어 주어진다. (1 ≤ N ≤ 100000, 1 ≤ K ≤ 1000)</p>

둘째 줄에 절댓값이 10¹⁸ 이하인, 수열을 이루는 N 개의 정수가 주어진다.

셋째 줄부터 K+2 번째 줄까지 쿼리 L R X 가 주어진다. (1 ≤ L ≤ R ≤ N, |X| ≤ 10⁹)

출력 형식

쿼리들을 순서대로 모두 수행한 후의 수열을 출력한다.

예제 입력

7 3
1 2 3 4 5 6 7
1 6 3
2 7 -4
4 5 6

예제 출력

1 2 3 4 5 9 10