说明

给定整数 $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 \dots r_i] = k_i$，如果 $t_i = 2$ 则 $\max a[l_i \dots 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$。

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 2
0 3 0 0

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

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

提示

样例 1 解释

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

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

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

样例 2 解释

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

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

评分标准

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

题目来源：Charlie Yang

翻译由 DeepSeek 完成