你正处于人类首次前往另一个星系的航行中。问题是，这个星系非常遥远，所以你有大把的时间。

你决定利用这段时间学习运行宇宙飞船所需的各种工作。飞船上有 $n$ 个人，每个人担任 $n$ 种不同角色中的一种。每个人恰好是其中一个角色的专家，且每个角色也恰好有一位专家。我们将人编号为 $1$ 到 $n$，角色也编号为 $1$ 到 $n$，使得第 $i$ 个人是第 $i$ 个角色的专家。

每天，我们需要分配人员担任角色，使得每个人都有一个角色，且每个角色都有人担任——换句话说，我们需要选择一个 $1$ 到 $n$ 的排列：$a_1, a_2, \dots, a_n$。

我们希望以这样一种方式分配人员：恰好有 $k$ 个人被分配到他们擅长的角色（以确保飞船能正常飞行），其余 $n - k$ 个人被分配到他们不擅长的角色（以确保他们能学习）。换句话说，必须恰好有 $k$ 个位置 $i$ 满足 $a_i = i$。

这样的分配方式有很多种，重复相同的分配会减慢学习进度，因此在航行的第 $d$ 天，我们将使用按字典序排列的第 $d$ 种分配方式。如果两个分配在第一个不同的人员编号处，该人员所分配的角色编号更小，则该分配在字典序中排在前面。换句话说，存在某个 $i$ 使得 $a_i < b_i$，且对于所有 $j < i$ 都有 $a_j = b_j$。

给定 $n$、$k$ 和 $d$，你需要找到该分配方案。

输入格式

输入文件的第一行包含要解决的测试用例数量 $t$，$1 \le t \le 50$。接下来的 $t$ 行，每行包含 3 个整数：$n$、$k$ 和 $d$，其中 $1 \le n \le 500$，$0 \le k \le n$，且 $d$ 在 $1$ 到满足恰好有 $k$ 个人担任其专家角色的 $n$ 人分配方案总数之间（含边界）。

输出格式

对于每个测试用例，输出一行包含相应的分配方案。该行应包含 $n$ 个以空格分隔的整数，每个整数在 $1$ 到 $n$ 之间。

样例

输入 1

8
4 1 1
4 1 2
4 1 3
4 1 4
4 1 5
4 1 6
4 1 7
4 1 8

输出 1

1 3 4 2
1 4 2 3
2 3 1 4
2 4 3 1
3 1 2 4
3 2 4 1
4 1 3 2
4 2 1 3