311220: CF1951F. Inversion Composition

F. Inversion Compositiontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputMy Chemical Romance - Disenchantedඞ

You are given a permutation $p$ of size $n$, as well as a non-negative integer $k$. You need to construct a permutation $q$ of size $n$ such that $\operatorname{inv}(q) + \operatorname{inv}(q \cdot p) = k {}^\dagger {}^\ddagger$, or determine if it is impossible to do so.

${}^\dagger$ For two permutations $p$ and $q$ of the same size $n$, the permutation $w = q \cdot p$ is such that $w_i = q_{p_i}$ for all $1 \le i \le n$.

${}^\ddagger$ For a permutation $p$ of size $n$, the function $\operatorname{inv}(p)$ returns the number of inversions of $p$, i.e. the number of pairs of indices $1 \le i < j \le n$ such that $p_i > p_j$.

Input

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 3 \cdot 10^5, 0 \le k \le n(n - 1)$) — the size of $p$ and the target number of inversions.

The second line of each test case contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, $p_i$'s are pairwise distinct) — the given permutation $p$.

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

Output

For each test case, print on one line "YES" if there exists a permutation $q$ that satisfies the given condition, or "NO" if there is no such permutation.

If the answer is "YES", on the second line, print $n$ integers $q_1, q_2, \ldots, q_n$ that represent such a satisfactory permutation $q$. If there are multiple such $q$'s, print any of them.

ExampleInput

5
3 4
2 3 1
5 5
2 3 5 1 4
6 11
5 1 2 3 4 6
9 51
3 1 4 2 5 6 7 8 9
1 0
1

Output

YES
3 2 1
NO
NO
YES
1 5 9 8 7 6 4 3 2
YES
1

Note

In the first test case, we have $q \cdot p = [2, 1, 3]$, $\operatorname{inv}(q) = 3$, and $\operatorname{inv}(q \cdot p) = 1$.

In the fourth test case, we have $q \cdot p = [9, 1, 8, 5, 7, 6, 4, 3, 2]$, $\operatorname{inv}(q) = 24$, and $\operatorname{inv}(q \cdot p) = 27$.

题目大意：
给定一个大小为n的排列p以及一个非负整数k，构造一个大小为n的排列q，使得q的逆序数加上q与p的逆序数之和等于k，或者判断这是不可能的。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数n和k（1≤n≤3×10^5，0≤k≤n(n−1)）——排列p的大小和目标逆序数。
每个测试用例的第二行包含n个整数p_1, p_2, …, p_n（1≤p_i≤n，p_i互不相同）——给定的排列p。
保证所有测试用例的n之和不超过3×10^5。

输出数据格式：
对于每个测试用例，如果存在满足给定条件的排列q，则在一行中打印“YES”，否则打印“NO”。
如果答案为“YES”，在第二行打印n个整数q_1, q_2, …, q_n，代表这样一个满意的排列q。如果有多个这样的q，打印其中任意一个。题目大意： 给定一个大小为n的排列p以及一个非负整数k，构造一个大小为n的排列q，使得q的逆序数加上q与p的逆序数之和等于k，或者判断这是不可能的。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数n和k（1≤n≤3×10^5，0≤k≤n(n−1)）——排列p的大小和目标逆序数。 每个测试用例的第二行包含n个整数p_1, p_2, …, p_n（1≤p_i≤n，p_i互不相同）——给定的排列p。 保证所有测试用例的n之和不超过3×10^5。 输出数据格式： 对于每个测试用例，如果存在满足给定条件的排列q，则在一行中打印“YES”，否则打印“NO”。 如果答案为“YES”，在第二行打印n个整数q_1, q_2, …, q_n，代表这样一个满意的排列q。如果有多个这样的q，打印其中任意一个。