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.