← 返回题目列表

Codeforces · 2084/D

D. 永久冻土生态学

中文机器翻译题面 查看原题

给定三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$,其中 $$$m \cdot k \lt n$$$。

对于由非负整数组成的序列$$$b$$$,定义$$$f(b)$$$如下:

  • 您可以对$$$b$$$执行以下操作:
    • 让 $$$l$$$ 表示 $$$b$$$ 的当前长度。选择一个正整数 $$$1 \leq i \leq l - k + 1$$$,删除索引 $$$i$$$ 到 $$$i + k - 1$$$ 的子数组,并将其余部分连接起来。换句话说,将 $$$b$$$ 替换为 $$$$$$[b_1, b_2, \ldots, b_{i - 1}, b_{i + k}, b_{i + k + 1}, \ldots, b_l]。$$$$$$
  • $$$f(b)$$$ 被定义为 最小值 执行上述操作后 $$$\operatorname{mex}(b)$$$$$$^{\text{*}}$$$ 的可能值 最多 $$$m$$$ 次 (可能为零)。

您需要构造一个由非负整数组成的长度为 $$$n$$$ 的序列 $$$a$$$,这样:

  • 对于所有 $$$1 \le i \le n$$$、$$$0 \le a_i \le 10^9$$$。
  • 在所有此类序列 $$$a$$$ 中,$$$f(a)$$$ 是 最大化.

$$$^{\text{*}}$$$整数集合 $$$c_1, c_2, \ldots, c_k$$$ 的最小排除 (MEX) 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$、$$$1 \le m \lt n$$$、$$$1 \le k \lt n$$$、$$$1 \le m \cdot k \lt n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。

如果有多个答案,请打印其中任何一个。

示例

输入
复制

8
2 1 1
5 2 2
6 1 4
8 2 2
8 1 5
11 3 3
22 6 3
17 2 2

输出
复制

0 0
0 1 0 0 0
0 1 2 2 0 1
0 2 1 0 1 0 8 1
0 1 2 1000000000 1 0 1 2
1 0 0 1 0 2 1 0 2 1 0
0 2 1 0 2 1 0 3 2 1 0 2 1 0 2 1 0 2 1 0 2 1
4 0 2 1 3 4 0 2 1 0 3 4 0 1 2 1 3

注意

在第一个测试用例中,可以证明$$$f(a) = 1$$$,这是最大化的。

在第二个测试用例中,可以证明$$$f(a) = 1$$$,这是最大化的。 $$$f(a) = 1$$$ 因为您可以执行以下操作:

  • 选择 $$$i = 3$$$,删除索引 $$$3$$$ 到 $$$4$$$ 的子数组,并将其余部分连接起来。序列 $$$a$$$ 变为 $$$[0, 1, 0]$$$。
  • 选择$$$i = 1$$$,删除索引$$$1$$$到$$$2$$$的子数组,并将剩余部分连接起来。序列 $$$a$$$ 变为 $$$[0]$$$。

在第三个测试用例中,可以证明$$$f(a) = 2$$$,这是最大化的。 $$$f(a) = 2$$$ 因为您可以执行以下操作:

  • 选择 $$$i = 2$$$,删除索引 $$$2$$$ 到 $$$5$$$ 的子数组,并将其余部分连接起来。序列 $$$a$$$ 变为 $$$[0, 1]$$$。

在第四个测试用例中,可以证明$$$f(a) = 2$$$,这是最大化的。

在第五个测试用例中,可以证明$$$f(a) = 3$$$,这是最大化的。

在第六个测试用例中,可以证明$$$f(a) = 2$$$,这是最大化的。