P21233 [CodeChef] PERMGCD
普及-
题目描述

Chef is interested in the sum of [GCD]s of all prefixes of a permutation of the integers ${1, 2, \ldots, N$}.

Formally, for $a permutation P = [P_{1}, P_{2}, \ldots, P_{N}]$ of ${1, 2, \ldots, N$},$a function F_{i} = \gcd(A_{1}, A_{2}, A_{3}, \ldots, A_{i}).$ Chef is interested in the value of $F_{1} + F_{2} + \ldots + F_{N}$.

Now, Chef wants to find a permutation of ${1, 2, \ldots, N$} which has the given sum equal to X. Please help Chef find one such permutation. In case there is no such permutation, print -1. In case of multiple answers, any of them will be accepted.

A permutation of ${1, 2, \ldots, N$} is a sequence of numbers from 1 to N in which each number occurs exactly once.

------ Input Format ------

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of a single line containing two space separated integers N and X denoting the length of required permutation and the required sum of GCDs of all prefixes respectively.

------ Output Format ------

  • If there is a valid permutation that satisfies the required condition, then:
  • In a single line, output N space-separated integers denoting the required permutation permutation.
  • If there is no permutation, print -1 in a single line.

------ Constraints ------

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 1000$
$1 ≤ X ≤ 2\cdot N - 1$
- The sum of $N$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------
4
1 1
2 1
4 6
3 5

----- Sample Output 1 ------
1
-1
2 4 3 1
3 2 1

----- explanation 1 ------
Test case $1$: The only possible permutation has a sum of $1$, as required.

Test case $2$: The two permutations of length $2$ are:
- $[1, 2]$ with a value of $1 + 1 = 2$
- $[2, 1]$ with a value of $2 + 1 = 3$

None of them have a sum of $X = 1$, so we output $-1$.

Test case $3$: For $P = [2, 4, 3, 1]$, we have:
- $F_{1} = 2$
- $F_{2} = \gcd(2, 4) = 2$
- $F_{3} = \gcd(2, 4, 3) = 1$
- $F_{4} = \gcd(2, 4, 3, 1) = 1$

The sum of these values is $6$, as required.

输入格式

见题面

输出格式

见题面

样例输入
4 1 1 2 1 4 6 3 5
样例输出
1 -1 2 4 3 1 3 2 1