题目描述

给定整数 $N, Q$ $(1 \leq N, Q \leq 2 \cdot 10^5)$ 以及 $Q$ 个约束，每个约束由四个整数 $t_i, l_i, r_i, k_i$ 表示 $(1 \leq t_i \leq 2, 1 \leq l_i \leq r_i \leq N, 0 \leq k_i \leq 10^9,$ 所有 $k_i$ 互不相同$)$。

构造一个包含 $N$ 个整数的数组 $a$，其中每个元素在 $0$ 到 $10^9$ 之间，使得对于所有 $1 \leq i \leq Q$，当 $t_i=1$ 时满足 $\min a[l_i ... r_i]=k_i$，当 $t_i=2$ 时满足 $\max a[l_i ... r_i]=k_i$。如果存在多个合法的数组，输出任意一个即可。如果不存在合法的数组，输出 $-1$。

输入格式

第一行包含一个整数 $T$ ($1 \leq T \leq 10^4$)，表示独立测试用例的数量。

对于每个测试用例，第一行包含两个整数 $N, Q$。

接下来的 $Q$ 行，每行包含 4 个整数 $t_i, l_i, r_i, k_i$。

保证所有测试用例中 $N$ 的总和与 $Q$ 的总和均不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，如果存在合法的数组，则在一行中输出 $N$ 个由空格分隔的整数 $a_1 \dots a_N$。否则，输出 $-1$。

样例

输入 1

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

输出 1

-1
1 2
0 3 0 0

说明 1

在第一个测试用例中，答案为 $-1$，因为数组的最小值不可能同时为 $1$ 和 $2$。

在第二个测试用例中，样例输出中 $a[1 ... 2]$ 的最小值为 $a[1]=1$，满足第一个约束。由于 $a[2] = 2$，第二个约束也得到满足。

在第三个测试用例中，存在多个解。例如，数组 $[4, 3, 2, 1]$ 也是可以接受的。

输入 2

4
2 2
1 1 2 1
2 1 2 2
3 2
1 1 2 3
2 2 3 1
5 2
1 1 2 3
1 4 5 2
4 4
1 1 4 1
1 2 3 2
2 1 2 5
2 3 4 6

输出 2

1 2
-1
3 3 0 2 2
1 5 2 6

说明 2

在第二个测试用例中，数组 $[3, 5, 1]$ 满足第一个约束但不满足第二个约束。相反，数组 $[3, 1, 1]$ 满足第二个约束但不满足第一个约束。可以证明不存在同时满足这两个约束的数组，因此答案为 $-1$。

对于所有其他测试用例，可以证明所构造的数组满足所有 $Q$ 个约束。

子任务

• 输入 3-4：$N, Q \leq 100$，且同一测试用例中所有 $t_i$ 相等。
• 输入 5-6：同一测试用例中所有 $t_i$ 相等。
• 输入 7-10：$N, Q \leq 100$。
• 输入 11-14：无额外限制。