Manhattan Permutations
Contest: Codeforces Round 953 (Div. 2)
Difficulty rating: 1300
Tags: constructive algorithms, data structures, greedy, implementation, math

Let's call the Manhattan value of a permutation$$$^{\dagger}$$$ $$$p$$$ the value of the expression $$$|p_1 - 1| + |p_2 - 2| + \ldots + |p_n - n|$$$.

For example, for the permutation $$$[1, 2, 3]$$$, the Manhattan value is $$$|1 - 1| + |2 - 2| + |3 - 3| = 0$$$, and for the permutation $$$[3, 1, 2]$$$, the Manhattan value is $$$|3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4$$$.

You are given integers $$$n$$$ and $$$k$$$. Find a permutation $$$p$$$ of length $$$n$$$ such that its Manhattan value is equal to $$$k$$$, or determine that no such permutation exists.

$$$^{\dagger}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^{4}$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^{5}, 0 \le k \le 10^{12}$$$) — the length of the permutation and the required Manhattan value.

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

Output format:
For each test case, if there is no suitable permutation, output "No". Otherwise, in the first line, output "Yes", and in the second line, output $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — a suitable permutation.

If there are multiple solutions, output any of them.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the permutation $$$[3, 1, 2]$$$ is suitable, its Manhattan value is $$$|3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4$$$.

In the second test case, it can be proven that there is no permutation of length $$$4$$$ with a Manhattan value of $$$5$$$.

In the third test case, the permutation $$$[1,2,3,4,5,6,7]$$$ is suitable, its Manhattan value is $$$|1-1|+|2-2|+|3-3|+|4-4|+|5-5|+|6-6|+|7-7|=0$$$.

Example input:
8
3 4
4 5
7 0
1 1000000000000
8 14
112 777
5 12
5 2

Example output:
Yes
3 1 2
No
Yes
1 2 3 4 5 6 7
No
Yes
8 2 3 4 5 6 1 7
No
Yes
5 4 3 1 2
Yes
2 1 3 4 5

Editorial:
Notice that if $$$k$$$ is odd, then there is no solution. Also notice that the maximum $$$max_k$$$ is achieved with the permutation $$$[n, n - 1, n - 2, ..., 1]$$$, so if $$$k > max_k$$$, then there is also no solution. It is claimed that for any other $$$k$$$, a solution exists.
Let's consider what happens if we swap $$$x$$$ and $$$1$$$ in the identity permutation. The Manhattan value for such a permutation will be equal to $$$|x - 1| + |x - 1| = 2 \cdot |x - 1|$$$. Then any even $$$k$$$ from $$$0$$$ to $$$2 \cdot (n - 1)$$$ can be achieved. If $$$k > 2 \cdot (n - 1)$$$, let's swap $$$1$$$ and $$$n$$$ elements. Notice that we have reduced the problem to a smaller size of $$$(n - 2)$$$, just now the indices start from $$$2$$$ instead of $$$1$$$. Now we can do exactly the same as with the identity permutation, i.e., swap $$$2$$$ with some $$$x$$$ ($$$x > 1$$$ and $$$x < n$$$). The value of the permutation will change by $$$|x - 2| \cdot 2$$$, so any even $$$k$$$ from $$$0$$$ to $$$2 \cdot (n - 1) + 2 \cdot (n - 3)$$$ can be achieved. Notice that if we continue to do this further, in the end we will get the permutation $$$[n, n - 1, ..., 1]$$$, and we have proved that any even $$$k$$$ from $$$0$$$ to $$$max_k$$$ is achievable. Hence, it is clear how to reconstruct the permutation itself in $$$O(n)$$$ time.