给你三个正整数 $$$n$$$、$$$k$$$ 和 $$$q$$$。您还获得 $$$q$$$ 元组 $$$(c, l, r)$$$,其中 $$$1 \leq c \leq 2$$$ 和 $$$1 \leq l \leq r \leq n$$$。
数组 $$$a_1, a_2, \ldots, a_n$$$ 是 最大 如果 $$$0 \leq a_i \leq 10^9$$$ 对于 $$$[1, n]$$$ 中的每个 $$$i$$$ 以及每个给定元组 $$$(c, l, r)$$$,
- 如果 $$$c = 1$$$,则 $$$\min(a_l, a_{l+1}, \ldots, a_r) = k$$$;
- 如果$$$c = 2$$$,则$$$\operatorname{MEX}$$$$$$^{\text{*}}$$$$$$(a_l, a_{l+1}, \ldots, a_r) = k$$$。
请注意,参数 $$$k$$$ 对于所有条件都是相同的。
查找 最大 数组 $$$a_1, a_2, \ldots, a_n$$$,长度为 $$$n$$$。输入的生成方式使得有效数组始终存在。如果有多个可能的数组,则可以打印其中任何一个。
$$$^{\text{*}}$$$整数集合 $$$a_1, a_2, \ldots, a_k$$$ 的最小排除 (MEX) 被定义为集合 $$$a$$$ 中不出现的最小非负整数 $$$x$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$, $$$k$$$, $$$q$$$ ($$$1 \leq k \leq n \leq 100$$$, $$$1 \leq q \leq 100$$$) - 数组的长度 $$$a_1, a_2, \ldots, a_n$$$,元组描述的$$$\min$$$和$$$\operatorname{MEX}$$$计算的结果,以及元组的数量。
然后是 $$$q$$$ 行。第 $$$i$$$ 行包含一个元组 $$$(c, l, r)$$$,它根据语句对 $$$a_l, a_{l+1}, \ldots, a_r$$$ 给出约束。
保证存在与给定输入相对应的有效数组。
请注意,所有测试用例的 $$$n$$$、$$$k$$$ 或 $$$q$$$ 的总和没有限制。
输出
对于每个测试用例,打印一行包含 最大 数组 $$$a_1, a_2, \ldots, a_n$$$。
示例
输入复制
46 2 21 1 32 2 63 3 12 1 33 3 21 1 11 3 33 2 22 1 22 2 3
输出复制
2 5 4 3 0 1 2 0 1 3 3 3 1 0 1
注意
在第一个测试用例中,您必须使用 $$$n = 6$$$、$$$k = 2$$$ 以及元组给出的 $$$q = 2$$$ 约束构建一个最大数组。
- 元组 $$$(1, 1, 3)$$$: $$$\min(a_1, a_2, a_3)$$$ 必须是 $$$2$$$;
- 元组 $$$(2, 2, 6)$$$: $$$\operatorname{MEX}(a_2, a_3, a_4, a_5, a_6)$$$ 必须是 $$$2$$$。
满足所有这些约束并且具有元素 $$$0 \leq a_i \leq 10^9$$$ 的可能数组是 $$$[2, 5, 4, 3, 0, 1]$$$。
在第二个测试用例中,您必须使用 $$$n = 3$$$、$$$k = 3$$$ 以及元组给出的 $$$q = 1$$$ 约束构建一个最大数组。
- 元组 $$$(2, 1, 3)$$$: $$$\operatorname{MEX}(a_1, a_2, a_3)$$$ 必须是 $$$3$$$。
满足此约束且具有元素 $$$0 \leq a_i \leq 10^9$$$ 的可能数组是 $$$[2, 0, 1]$$$。