Description

在一个 $1*m$ 的画布中，最初每个方格都是没有颜色的（用 $0$ 表示）。

小明先后进行了 $q$ 次操作，每次操作都会给一段连续的方格涂上特定的颜色，这些方格原来的颜色会被覆盖掉。

请你给出最终每个方格的颜色。

Format

Input

第一行一个整数 $t( 1 \leq t \leq 10^5)$ ，表示测试用例数量。

对于每个测试用例，

第一行 $2$ 个整数 $m,q(1 \leq m,q \leq 2*10^5)$

第 $2$ 行到第 $q+1$ 行，每行 $3$ 个整数 $ l,r,c( 1 \leq l \leq r \leq m , 1 \leq c \leq 10^9 ) $ ，分别表示每次操作的左端点、右端点、涂上的颜色。操作按照先后次序逐行给出。

所有测试用例 $m$ 的和不大于 $2*10^5$ ， $q$ 的和不大于 $2*10^5$

Output

对于每个测试用例，输出一行 $m$ 个整数，表示每个方格的颜色。

Samples

2
5 5
1 1 5
3 3 3
4 4 2
5 5 1
2 2 4
5 2
1 3 100
3 4 50

5 4 3 2 1
100 100 50 50 0

Limitation

Time Limit: 1 second

Memory Limit: 256 MiB