给定一个长度为 $n$ 的数组 $a$。你必须执行恰好 $k$ 次操作。 对于每次操作： 首先，选择两个整数 $l, r$ ($1 \le l \le r \le n$)； 然后，将 $a$ 变为 $b$，满足： 对于每个 $i$ ($1 \le i < l$)，$b_i = a_i$； 对于每个 $i$ ($l \le i < r$)，$b_i = a_{i+1}$； $b_r = a_l$； 对于每个 $i$ ($r < i \le n$)，$b_i = a_i$。

求执行 $k$ 次操作后，字典序最大的数组。 如果存在一个下标 $i$ ($1 \le i \le n$)，使得 $x_i > y_i$ 且对于所有 $j$ ($1 \le j < i$)，$x_j = y_j$，则称数组 $x$ 的字典序大于数组 $y$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $n, k$ ($1 \le n, k \le 300000$)。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 300000$)。 所有测试用例的 $n$ 之和不超过 $10^6$。 所有测试用例的 $k$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示执行 $k$ 次操作后字典序最大的数组。

样例

样例输入 1

2
7 3
1 4 2 1 4 2 4
5 2
4 3 5 4 5

样例输出 1

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