解题思路

核心算法

使用贪心策略结合位置映射表，从左到右逐个位置确保放置最优值。

关键观察

1. 字典序最小的本质：要使字典序最小，应该让前面的位置尽可能放置小的数字
2. 最优排列的特征：理想情况下，位置i（0-indexed）应该放置值i+1
3. 贪心策略的正确性：优先处理前面的位置，因为前面位置对字典序的影响更大

题目内容

给定一个长度为 $n$ 的排列 {$a_1,a_2,...,a_n$} 。

你可以进行至多 m 次以下操作：

• 选择两个索引 $i,j$，交换 $a_i$ 与 $a_j$ 。

请输出在经过至多 $m$ 次交换操作后能够得到的字典序最小的排列。

【名词解释】

排列长度为 $n$ 的排列是由 $1$ ~ $n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{ $2,3,1,5,4$ }是一个长度为 $5$ 的排列，而{ $1,2,2$ }和{ $1,3,4$ }都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

字典顺序比较：从数组的第一个元素开始逐个比较，直到找到第一个不同的位置，通过比较这个位置元素的大小得出数组的大小，称为字典顺序比较。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T(1 ≤ T ≤ 10^4)$ ，代表数据组数；

随后对于每组数据，按以下格式输入：

• 第一行输入两个整数

$n,m(1≦n≦2×10^5,1≦m≤10^9)$，分别表示排列长度和允许的交换次数；

• 第二行输入一个长度为 n 的排列

{ $a_1,a_2,...,a_n$ } $(1≤a_i≤n)$ 。

保证所有测试数据中 $n$ 的总和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，在一行上输出一个长度为 $n$ 的排列，表示经过至多 $m$ 次交换操作后得到的字典序最小的排列。

样例1

输入

2
2 1
2 1
3 4
3 2 1

输出

1 2
1 2 3

说明

在第二个测试用例中，可以选择交换 $(i,j)=(1,3)$ ，将排列 { $3,2,1$ }变为{ $1,2,3$ }。