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

그의 농장에는 $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$가 존재해야 합니다. 이 규칙을 따르지 않는 모든 먹이통은 제거되어야 합니다.

이제 아스카트는 당신에게 각 $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