You are given three integers $$$n$$$, $$$m$$$, and $$$k$$$, where $$$m \cdot k \lt 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$$$.

Input

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 \lt n$$$, $$$1 \le k \lt n$$$, $$$1 \le m \cdot k \lt n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

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.

Note

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.

Arcology On Permafrost

Examples