채굴장

부지에서 유용한 광물이 발견되었다. 주인은 새 자동 굴착 시스템을 설치하고 가동해서 이 부지를 채굴장으로 바꿀 계획이다.

이 시스템은 한 번에 구덩이 하나를 판다. 구덩이의 시작점은 채굴장 시작점으로부터 $S_i$미터, 끝점은 $E_i$미터 떨어진 곳이며, 깊이는 $H_i$미터이다.

채굴장은 광물 채굴을 시작하기 전과 후 모두에 대해, 채굴장을 따라 해발 높이를 나타내는 2차원 도면으로 그릴 수 있다.

이 시스템은 굴착 명령을 수행하며 동작한다. 각 명령은 구간 $[S_i, E_i]$의 높이를 $H_i$미터만큼 낮춘다. 그림 1은 명령 두 개를 수행한 뒤의 높이를 보여준다. 첫 번째 명령은 $[0; 2]$ 구간을, 두 번째 명령은 $[1; 3]$ 구간을 파며, 각각 깊이 1미터의 구덩이를 만든다. 첫 번째 명령으로 파낸 부분은 초록색(흑백 인쇄본에서는 밝은 회색), 두 번째 명령으로 파낸 부분은 파란색(흑백 인쇄본에서는 회색)이다.

그림 1.

주인은 시스템에 내릴 굴착 명령을 이미 알고 있다. 시작하기 전에, 모든 명령을 수행한 뒤 채굴장이 어떤 모습일지 알고 싶어 한다.

모든 굴착 명령을 수행한 뒤 채굴장의 높이를 구하시오.

첫째 줄에 채굴장의 길이 $N$과 명령의 개수 $K$가 주어진다.

둘째 줄에는 $N$개의 정수 $A_i$가 주어진다. $A_i$는 채굴장 시작점으로부터 $i$미터 떨어진 지점의 처음 해발 높이이다. 첫 번째 값은 시작점으로부터 0미터 지점의 높이이다.

이어서 $K$개의 줄에 각각 정수 $S_i$, $E_i$, $H_i$가 주어진다. 이는 $i$번째 굴착 명령의 시작점, 끝점, 깊이이다.

모든 명령을 수행한 뒤 채굴장 시작점으로부터 $i$미터 지점의 높이를 $i$번째 수로 하여 $N$개의 수를 출력한다.

최종 높이는 음수가 될 수도 있다.

$0 \le S_i \le E_i < N \le 250\,000$

$1 \le K \le 250\,000$

$-1\,000 \le A_i, H_i \le 1\,000$