CF2084D Arcology On Permafrost

You are given three integers $ n $ , $ m $ , and $ k $ , where $ m \cdot k < n $ . For a sequence $ b $ consisting of non-negative integers, define $ f(b) $ as follows: - You may perform the following operation on $ b $ : - Let $ l $ denote the current length of $ b $ . Choose a positive integer $ 1 \leq i \leq l - k + 1 $ , remove the subarray from index $ i $ to $ i + k - 1 $ and concatenate the remaining parts. In other words, replace $ b $ with $ $$$[b_1, b_2, \ldots, b_{i - 1}, b_{i + k}, b_{i + k + 1}, \ldots, b_l]. $ $

$ f(b) $ is defined as the minimum possible value of $ \\operatorname{mex}(b) $ $$$^{\text{∗}} $ after performing the above operation at most $ m $ times (possibly zero). You need to construct a sequence $ a $ of length $ n $ consisting of non-negative integers, such that: - For all $ 1 \le i \le n $ , $ 0 \le a_i \le 10^9 $ . - Over all such sequences $ a $ , $ f(a) $ is maximized. $ ^{\text{∗}} $ The minimum excluded (MEX) of a collection of integers $ c_1, c_2, \ldots, c_k $ is defined as the smallest non-negative integer $ x $ which does not occur in the collection $ c $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains three integers $ n $ , $ m $ , and $ k $ ( $ 2 \le n \le 2 \cdot 10^5 $ , $ 1 \le m < n $ , $ 1 \le k < n $ , $ 1 \le m \cdot k < n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ). If there are multiple answers, print any of them.

In the first test case, it can be shown that $ f(a) = 1 $ , which is maximized. In the second test case, it can be shown that $ f(a) = 1 $ , which is maximized. $ f(a) = 1 $ since you can perform the following operations: - Choose $ i = 3 $ , remove the subarray from index $ 3 $ to $ 4 $ and concatenate the remaining parts. The sequence $ a $ becomes $ [0, 1, 0] $ . - Choose $ i = 1 $ , remove the subarray from index $ 1 $ to $ 2 $ and concatenate the remaining parts. The sequence $ a $ becomes $ [0] $ . In the third test case, it can be shown that $ f(a) = 2 $ , which is maximized. $ f(a) = 2 $ since you can perform the following operation: - Choose $ i = 2 $ , remove the subarray from index $ 2 $ to $ 5 $ and concatenate the remaining parts. The sequence $ a $ becomes $ [0, 1] $ . In the fourth test case, it can be shown that $ f(a) = 2 $ , which is maximized. In the fifth test case, it can be shown that $ f(a) = 3 $ , which is maximized. In the sixth test case, it can be shown that $ f(a) = 2 $ , which is maximized.