// Problem: C. A-B Palindrome
// Contest: Codeforces - Codeforces Round #713 (Div. 3)
// URL: https://codeforces.com/contest/1512/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define hh "\n"
#define fi first
#define se second
#define pi acos(-1.0)
#define inf 2147483647
#define llf 9223372036854775807
#define For(i,a) for(auto &i:a)
#define mapa(a,b) make_pair(a,b)
#define rt(s) {cout<<s;return ;}
#define r0(s) {cout<<s;return 0;}
#define tty template <typename T>
#define mm(a,b) memset(a,b, sizeof(a));
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define ROF(i,a,b) for(int i=a;i>=b;--i)
#define cout(n) cout<<fixed<<setprecision(n)
#define cf int _t;cin>>_t;while (_t--) solve();
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
tty T gcd (T a, T b) {while (b ^= a ^= b ^= a %= b);  return a;}
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;}
//#define nc getchar
tty inline void read(T &sum) {char ch = nc();T tf = 0;sum = 0;while((ch < '0' || ch > '9') && (ch != '-')) ch = nc();tf = ((ch == '-') && (ch = nc()));while(ch >= '0' && ch <= '9') sum = sum * 10+ (ch - 48), ch = nc();(tf) && (sum = -sum);}
tty inline void write(T x){if(x==0) {putchar('0');return;} char F[200];T tmp=x>0?x:-x ;if(x<0)putchar('-') ;T cnt=0 ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]) ;}
tty inline T ksc(T x, T y, T mod){return ( x * y - (ll) ( (long double) x / mod*y )*mod + mod ) % mod;}
tty inline T exgcd(T a, T b, T &x, T &y) {if (!b) {x = 1,y=0;return a;}T d = exgcd(b, a % b, x, y);T t = x;x=y;y=t-(a/b)*y;return d;}

tty inline void rmqmin(T f[][20],T n){for (int i = 1; i <= n; i++)cin >> f[i][0];for (int j = 1; j <= 20; j++)for (int i = 1; i <= n; i++)if (i + (1 << j) - 1 <= n)f[i][j] = min(f[i][j - 1], f[i + (1 << (j-1))][j - 1]);}
tty inline T zymin(T f[][20],T z,T y){int x=int (log(y-z+1)/log(2));return min(f[z][x],f[y-(1<<x)+1][x]);}
tty inline void rmqmax(T f[][20], T n, int i1) {for (int i = 1; i <= n; i++)cin >> f[i][0];for (int j = 1; j <= 20; j++)for (int i = 1; i <= n; i++)if (i + (1 << j) - 1 <= n)f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}
tty inline T zymax(T f[][20],T z,T y){int x=int (log(y-z+1)/log(2));return max(f[z][x],f[y-(1<<x)+1][x]);}

tty inline T rotatex(T x,T y,T ang,T ox=0,T oy=0){return (x-ox)*cos(ang)-(y-oy)*sin(ang)+ox;}
tty inline T rotatey(T x,T y,T ang,T ox=0,T oy=0){return (x-ox)*sin(ang)+(y-oy)*cos(ang)+oy;}
//-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

int a[502],vis[502];
void solve()
{
	mm(a,0)
    mm(vis,0);
    int n,z,y,s,minn=0,maxx=0;
    cin>>n>>z>>y>>s;
    FOR(i,1,y-z+1) minn+=i;
    ROF(i,n,n-y+z) maxx+=i;
    if(s<=maxx&&s>=minn)
    {
        int l=(y-z+1);
        int mid=s/l;
        int mod=s%l;
        if(l&1)
        {
            a[z+(y-z)/2]=mid;
            vis[a[z+(y-z)/2]]=1;
            FOR(i,z,z+(y-z)/2-1)
            {
                a[i]=mid-(z+(y-z)/2-i);
                vis[a[i]]=1;
            }
            FOR(i,z+(y-z)/2+1,y)
            {
                a[i]=mid+i-(z+(y-z)/2);
                vis[a[i]]=1;
            }
            FOR(i,z,y)
            {
            	ROF(j,mod,1)
            	{
            		if(a[i]+j<=n&&!vis[a[i]+j])
                	{
                    	vis[a[i]]=0;
                    	a[i]=a[i]+j;
                    	vis[a[i]]=1;
                    	mod-=j;
                    	break;
                	}
            	}
            	if(mod==0) break;
            }
            int x=1;
            FOR(i,1,n)
            {
                if(a[i]) continue;
                FOR(j,x,n)
                    if(!vis[j]){a[i]=j,x=j+1;break;}
            }
        }else
        {
            FOR(i,z,z+(y-z)/2)
            {
                a[i]=mid-(z+(y-z)/2-i)-1;
                vis[a[i]]=1;
            }
            FOR(i,z+(y-z)/2+1,y)
            {
                a[i]=mid+i-(z+(y-z)/2);
                vis[a[i]]=1;
            }
            FOR(i,z,y)
            {
            	ROF(j,mod,1)
            	{
            		if(a[i]+j<=n&&!vis[a[i]+j])
                	{
                    	vis[a[i]]=0;
                    	a[i]=a[i]+j;
                    	vis[a[i]]=1;
                    	mod-=j;
                    	break;
                	}
            	}
            	if(mod==0) break;
            }
            int x=1;
            FOR(i,1,n)
            {
                if(a[i]) continue;
                FOR(j,x,n)
                    if(!vis[j]){a[i]=j,x=j+1;break;}
            }
        }
        FOR(i,1,n) cout<<a[i]<<" ";
    }else cout<<-1;
    cout<<hh;
}

int main()
{
    IOS;cf
    return 0;
}




























### Prompt

Your task is to create a cpp solution to the following problem:

A permutation is a sequence of n integers from 1 to n, in which all the numbers occur exactly once. For example, [1], [3, 5, 2, 1, 4], [1, 3, 2] are permutations, and [2, 3, 2], [4, 3, 1], [0] are not.

Polycarp was given four integers n, l, r (1 ≤ l ≤ r ≤ n) and s (1 ≤ s ≤ (n (n+1))/(2)) and asked to find a permutation p of numbers from 1 to n that satisfies the following condition: 

  * s = p_l + p_{l+1} + … + p_r. 



For example, for n=5, l=3, r=5, and s=8, the following permutations are suitable (not all options are listed): 

  * p = [3, 4, 5, 2, 1]; 
  * p = [5, 2, 4, 3, 1]; 
  * p = [5, 2, 1, 3, 4]. 

But, for example, there is no permutation suitable for the condition above for n=4, l=1, r=1, and s=5.

Help Polycarp, for the given n, l, r, and s, find a permutation of numbers from 1 to n that fits the condition above. If there are several suitable permutations, print any of them.

Input

The first line contains a single integer t (1 ≤ t ≤ 500). Then t test cases follow.

Each test case consist of one line with four integers n (1 ≤ n ≤ 500), l (1 ≤ l ≤ n), r (l ≤ r ≤ n), s (1 ≤ s ≤ (n (n+1))/(2)).

It is guaranteed that the sum of n for all input data sets does not exceed 500.

Output

For each test case, output on a separate line: 

  * n integers — a permutation of length n that fits the condition above if such a permutation exists; 
  * -1, otherwise. 



If there are several suitable permutations, print any of them.

Example

Input


5
5 2 3 5
5 3 4 1
3 1 2 4
2 2 2 2
2 1 1 3


Output


1 2 3 4 5 
-1
1 3 2 
1 2 
-1

### Response

```cpp
// Problem: C. A-B Palindrome
// Contest: Codeforces - Codeforces Round #713 (Div. 3)
// URL: https://codeforces.com/contest/1512/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define hh "\n"
#define fi first
#define se second
#define pi acos(-1.0)
#define inf 2147483647
#define llf 9223372036854775807
#define For(i,a) for(auto &i:a)
#define mapa(a,b) make_pair(a,b)
#define rt(s) {cout<<s;return ;}
#define r0(s) {cout<<s;return 0;}
#define tty template <typename T>
#define mm(a,b) memset(a,b, sizeof(a));
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define ROF(i,a,b) for(int i=a;i>=b;--i)
#define cout(n) cout<<fixed<<setprecision(n)
#define cf int _t;cin>>_t;while (_t--) solve();
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
tty T gcd (T a, T b) {while (b ^= a ^= b ^= a %= b);  return a;}
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;}
//#define nc getchar
tty inline void read(T &sum) {char ch = nc();T tf = 0;sum = 0;while((ch < '0' || ch > '9') && (ch != '-')) ch = nc();tf = ((ch == '-') && (ch = nc()));while(ch >= '0' && ch <= '9') sum = sum * 10+ (ch - 48), ch = nc();(tf) && (sum = -sum);}
tty inline void write(T x){if(x==0) {putchar('0');return;} char F[200];T tmp=x>0?x:-x ;if(x<0)putchar('-') ;T cnt=0 ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]) ;}
tty inline T ksc(T x, T y, T mod){return ( x * y - (ll) ( (long double) x / mod*y )*mod + mod ) % mod;}
tty inline T exgcd(T a, T b, T &x, T &y) {if (!b) {x = 1,y=0;return a;}T d = exgcd(b, a % b, x, y);T t = x;x=y;y=t-(a/b)*y;return d;}

tty inline void rmqmin(T f[][20],T n){for (int i = 1; i <= n; i++)cin >> f[i][0];for (int j = 1; j <= 20; j++)for (int i = 1; i <= n; i++)if (i + (1 << j) - 1 <= n)f[i][j] = min(f[i][j - 1], f[i + (1 << (j-1))][j - 1]);}
tty inline T zymin(T f[][20],T z,T y){int x=int (log(y-z+1)/log(2));return min(f[z][x],f[y-(1<<x)+1][x]);}
tty inline void rmqmax(T f[][20], T n, int i1) {for (int i = 1; i <= n; i++)cin >> f[i][0];for (int j = 1; j <= 20; j++)for (int i = 1; i <= n; i++)if (i + (1 << j) - 1 <= n)f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}
tty inline T zymax(T f[][20],T z,T y){int x=int (log(y-z+1)/log(2));return max(f[z][x],f[y-(1<<x)+1][x]);}

tty inline T rotatex(T x,T y,T ang,T ox=0,T oy=0){return (x-ox)*cos(ang)-(y-oy)*sin(ang)+ox;}
tty inline T rotatey(T x,T y,T ang,T ox=0,T oy=0){return (x-ox)*sin(ang)+(y-oy)*cos(ang)+oy;}
//-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

int a[502],vis[502];
void solve()
{
	mm(a,0)
    mm(vis,0);
    int n,z,y,s,minn=0,maxx=0;
    cin>>n>>z>>y>>s;
    FOR(i,1,y-z+1) minn+=i;
    ROF(i,n,n-y+z) maxx+=i;
    if(s<=maxx&&s>=minn)
    {
        int l=(y-z+1);
        int mid=s/l;
        int mod=s%l;
        if(l&1)
        {
            a[z+(y-z)/2]=mid;
            vis[a[z+(y-z)/2]]=1;
            FOR(i,z,z+(y-z)/2-1)
            {
                a[i]=mid-(z+(y-z)/2-i);
                vis[a[i]]=1;
            }
            FOR(i,z+(y-z)/2+1,y)
            {
                a[i]=mid+i-(z+(y-z)/2);
                vis[a[i]]=1;
            }
            FOR(i,z,y)
            {
            	ROF(j,mod,1)
            	{
            		if(a[i]+j<=n&&!vis[a[i]+j])
                	{
                    	vis[a[i]]=0;
                    	a[i]=a[i]+j;
                    	vis[a[i]]=1;
                    	mod-=j;
                    	break;
                	}
            	}
            	if(mod==0) break;
            }
            int x=1;
            FOR(i,1,n)
            {
                if(a[i]) continue;
                FOR(j,x,n)
                    if(!vis[j]){a[i]=j,x=j+1;break;}
            }
        }else
        {
            FOR(i,z,z+(y-z)/2)
            {
                a[i]=mid-(z+(y-z)/2-i)-1;
                vis[a[i]]=1;
            }
            FOR(i,z+(y-z)/2+1,y)
            {
                a[i]=mid+i-(z+(y-z)/2);
                vis[a[i]]=1;
            }
            FOR(i,z,y)
            {
            	ROF(j,mod,1)
            	{
            		if(a[i]+j<=n&&!vis[a[i]+j])
                	{
                    	vis[a[i]]=0;
                    	a[i]=a[i]+j;
                    	vis[a[i]]=1;
                    	mod-=j;
                    	break;
                	}
            	}
            	if(mod==0) break;
            }
            int x=1;
            FOR(i,1,n)
            {
                if(a[i]) continue;
                FOR(j,x,n)
                    if(!vis[j]){a[i]=j,x=j+1;break;}
            }
        }
        FOR(i,1,n) cout<<a[i]<<" ";
    }else cout<<-1;
    cout<<hh;
}

int main()
{
    IOS;cf
    return 0;
}




























```