# PROBLEM LINK:

**Setter:** tejas_adm

**Testers:** utkarsh_25dec, iceknight1093

# DIFFICULTY:

1328

# PREREQUISITES:

None

# PROBLEM:

Find a permutation of [1, N], so that the sum of prefix-GCDs is exactly X.

# EXPLANATION:

GCD of positive numbers is always \ge 1. So the sum of N of the prefix-GCDs is going to be \ge N. So, if X < N, there is no answer, and hence output -1.

For all other cases, we can construct a permutation. We see from the input constraints that X is guaranteed to be \le 2*N - 1. So, we can place a suitable element at the first, and then a 1, and the rest in any order. In such a case, the GCD of all prefixes except the very first is 1. So, the first element has to be X-(N-1). So the permutation is [X-(N-1), 1, 2, 3, \dots, N], taking care that the first element isnâ€™t repeated twice.

# TIME COMPLEXITY:

Time complexity is O(N).

# SOLUTION:

## Editorialist's Solution

```
#include <iostream>
using namespace std;
int T, n, x;
int main() {
cin>>T;
while(T--)
{
cin>>n>>x;
if(x<n)
{
cout<<-1<<"\n";
continue;
}
x -= (n-1);
cout<<x<<" ";
for(int i=1;i<=n;i++)
{
if(i==x)
continue;
cout<<i<<" ";
}
cout<<"\n";
}
return 0;
}
```

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n, x;
cin >> n >> x;
if(x < n) {
cout << "-1\n";
continue;
}
int now = 1, done = x - n + 1;
cout << done << " ";
for(int i = 1; i < n; i++) {
if(now == done) now++;
cout << now << " ";
now++;
}
cout << "\n";
}
}
```

## Tester's Solution

```
for _ in range(int(input())):
n, k = map(int, input().split())
if k < n:
print(-1)
else:
print(k-n+1, *range(1, k-n+1), *range(k-n+2, n+1))
```