Askhat은 장래가 유망한 사업가입니다. 그는 프로그래밍이 수익성이 없는 사업임을 빠르게 깨닫고, 양계장을 열기로 했습니다.

그의 농장에는 $n$마리의 닭이 일렬로 배치되어 있습니다. $i$번째 닭은 최대 $a_i$개의 곡물을 먹을 수 있습니다. $m$개의 먹이 공급기가 있으며, 각 공급기는 정수 $l_j, r_j, c_j$로 설명됩니다. $j$번째 공급기는 $l_j \le i \le r_j$를 만족하는 $i$번째 닭에게 먹이를 줄 수 있으며, 이 공급기에는 $c_j$개의 곡물이 들어 있습니다.

모든 사업에는 함정이 있는 법인데, 이번 경우에는 Ildar라는 인물이 닭 먹이 관리라는 명목으로 나타났습니다. 그는 모든 훌륭한 양계장에는 닭 대표가 있어야 한다고 주장합니다. 즉, 모든 공급기 $j$에 대해 $l_j \le i \le r_j$를 만족하는 닭 $i$가 존재해야 합니다. 이 규칙을 따르지 않는 모든 공급기는 제거되어야 합니다.

이제 Askhat은 당신에게 각 $i$에 대해, 닭 $i$에게 먹이를 줄 수 있는 공급기만 남겼을 때 닭들이 먹을 수 있는 최대 곡물 수가 얼마인지 구하도록 요청했습니다.

입력

첫 번째 줄에는 테스트 케이스의 수 $t$ ($1 \le t \le 10^4$)가 주어집니다. 각 테스트 케이스에 대한 설명이 이어집니다.

각 테스트 케이스의 첫 번째 줄에는 닭의 수 $n$과 공급기의 수 $m$ ($1 \le n, m \le 10^5$)이 주어집니다.

다음 줄에는 닭이 먹을 수 있는 곡물의 수를 나타내는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)이 주어집니다.

다음 $m$개의 줄에는 $j$번째 공급기를 설명하는 세 정수 $l_j, r_j, c_j$ ($1 \le l_j \le r_j \le n, 0 \le c_j \le 10^9$)가 주어집니다.

모든 테스트 케이스에 대해 $n$의 합과 $m$의 합은 $10^5$를 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 $n$개의 정수를 출력하십시오. 이는 문제에 대한 답입니다.

예제

입력 1

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

출력 1

2 5 2 0