Askhat là một doanh nhân đầy triển vọng. Anh ấy nhanh chóng nhận ra rằng lập trình là một công việc không mang lại lợi nhuận, vì vậy anh ấy quyết định mở một trang trại gà.

Trang trại của anh ấy bao gồm $n$ con gà được xếp thành một hàng. Con gà thứ $i$ có thể ăn tối đa $a_i$ hạt. Có $m$ máng ăn, mỗi máng được mô tả bởi các số nguyên $l_j, r_j, c_j$. Máng ăn thứ $j$ có thể cho con gà thứ $i$ ăn nếu $l_j \le i \le r_j$, và máng này có $c_j$ hạt.

Hóa ra mọi công việc kinh doanh đều có những cạm bẫy riêng, trong trường hợp này là sự kiểm soát việc cho gà ăn, đại diện bởi Ildar. Anh ta tuyên bố rằng mọi trang trại gà đáng kính đều phải có một con gà đại diện. Nghĩa là, phải tồn tại một con gà $i$ sao cho $l_j \le i \le r_j$ đúng với mọi máng ăn $j$. Tất cả các máng ăn không tuân thủ quy tắc này phải bị loại bỏ.

Bây giờ Askhat yêu cầu bạn tìm, với mỗi $i$, số lượng hạt tối đa có thể cho gà ăn nếu chúng ta chỉ giữ lại những máng ăn có thể cho con gà $i$ ăn.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 10^4$) — số lượng bộ dữ liệu kiểm tra. Tiếp theo là mô tả của các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n, m$ ($1 \le n, m \le 10^5$) — số lượng gà và số lượng máng ăn tương ứng.

Dòng tiếp theo chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — số lượng hạt mà các con gà có thể ăn.

Mỗi dòng trong số $m$ dòng tiếp theo chứa ba số nguyên $l_j, r_j, c_j$ ($1 \le l_j \le r_j \le n, 0 \le c_j \le 10^9$) — mô tả của máng ăn thứ $j$.

Đảm bảo rằng tổng của $n$ và tổng của $m$ cho tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra $n$ số nguyên — câu trả lời cho bài toán.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2 5 2 0