/* Priyansh Agarwal*/

#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace chrono;
// using namespace __gnu_pbds;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e18
#define nline "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

#ifdef Priyansh31dec
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
#else
#define debug(x);
#endif

// std::ostream&
// operator<<( std::ostream& dest, __int128_t value )
// {
// 	std::ostream::sentry s( dest );
// 	if ( s ) {
// 		__uint128_t tmp = value < 0 ? -value : value; char buffer[ 128 ];
// 		char* d = std::end( buffer );
// 		do {	-- d; *d = "0123456789"[ tmp % 10 ]; tmp /= 10;} while ( tmp != 0 );
// 		if ( value < 0 ) {-- d; *d = '-';}
// 		int len = std::end( buffer ) - d;
// 		if ( dest.rdbuf()->sputn( d, len ) != len ) {dest.setstate( std::ios_base::badbit );}
// 	}
// 	return dest;
// }

// __int128 read() {
// 	__int128 x = 0, f = 1;
// 	char ch = getchar();
// 	while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
// 	while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
// 	return x * f;
// }

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
// typedef __int128 ell;
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
// void _print(ell t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
// void _print(pbds v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

/*---------------------------------------------------------------------------------------------------------------------------*/
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
bool revsort(ll a, ll b) {return a > b;}
void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) {ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
void google(int t) {cout << "Case #" << t << ": ";}
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))
/*--------------------------------------------------------------------------------------------------------------------------*/
void solve() {
	int t;
	cin >> t;
	while (t--) {
		int n, l, r, s;
		cin >> n >> l >> r >> s;
		set<int> used;
		int k = r - l + 1;
		vector<int> v1;
		int sum = 0;
		for (int i = 0; i < k; i++) {
			v1.pb(i + 1);
			sum += i + 1;
		}
		if (s < sum) {
			cout << -1 << nline;
		} else {
			int counter2 = 0;
			while (sum < s) {
				debug(sum);
				debug(v1);
				int counter = 0;
				for (int i = 0; i < k; i++) {
					int index = k - i - 1;
					int value_here = v1[index];
					int max_allowed = n - i;
					if (value_here < max_allowed) {
						sum += 1;
						v1[index] = v1[index] + 1;
						counter = 1;
						break;
					}
				}
				if (counter == 0) {
					cout << -1 << nline;
					counter2 = 1;
					break;
				}
			}
			if (counter2 == 1)
				continue;
			vector<int> v2(n, -1);
			for (int i = l; i <= r; i++) {
				debug(i);
				v2[i - 1] = v1[i - l];
				used.insert(v2[i - 1]);
			}
			set<int> unused;
			for (int i = 1; i <= n; i++) {
				if (used.count(i) == 0) {
					unused.insert(i);
				}
			}
			debug(unused);
			for (int i = 0; i < n; i++) {
				if (v2[i] == -1) {
					v2[i] = *unused.begin();
					unused.erase(v2[i]);
				}
			}
			for (int i = 0; i < n; i++) {
				cout << v2[i] << " ";
			}
			cout << nline;
		}
	}
}

int main() {
#ifdef Priyansh31dec
	freopen("Error.txt", "w", stderr);
#endif
	fastio();
	auto start1 = high_resolution_clock::now();
	solve();
	auto stop1 = high_resolution_clock::now();
	auto duration = duration_cast<microseconds>(stop1 - start1);
#ifdef Priyansh31dec
	cerr << "Time: " << duration . count() / 1000 << endl;
#endif
}
### Prompt

Construct a CPP code solution to the problem outlined:

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
/* Priyansh Agarwal*/

#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace chrono;
// using namespace __gnu_pbds;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e18
#define nline "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

#ifdef Priyansh31dec
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
#else
#define debug(x);
#endif

// std::ostream&
// operator<<( std::ostream& dest, __int128_t value )
// {
// 	std::ostream::sentry s( dest );
// 	if ( s ) {
// 		__uint128_t tmp = value < 0 ? -value : value; char buffer[ 128 ];
// 		char* d = std::end( buffer );
// 		do {	-- d; *d = "0123456789"[ tmp % 10 ]; tmp /= 10;} while ( tmp != 0 );
// 		if ( value < 0 ) {-- d; *d = '-';}
// 		int len = std::end( buffer ) - d;
// 		if ( dest.rdbuf()->sputn( d, len ) != len ) {dest.setstate( std::ios_base::badbit );}
// 	}
// 	return dest;
// }

// __int128 read() {
// 	__int128 x = 0, f = 1;
// 	char ch = getchar();
// 	while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
// 	while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
// 	return x * f;
// }

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
// typedef __int128 ell;
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
// void _print(ell t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
// void _print(pbds v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

/*---------------------------------------------------------------------------------------------------------------------------*/
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
bool revsort(ll a, ll b) {return a > b;}
void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) {ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
void google(int t) {cout << "Case #" << t << ": ";}
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))
/*--------------------------------------------------------------------------------------------------------------------------*/
void solve() {
	int t;
	cin >> t;
	while (t--) {
		int n, l, r, s;
		cin >> n >> l >> r >> s;
		set<int> used;
		int k = r - l + 1;
		vector<int> v1;
		int sum = 0;
		for (int i = 0; i < k; i++) {
			v1.pb(i + 1);
			sum += i + 1;
		}
		if (s < sum) {
			cout << -1 << nline;
		} else {
			int counter2 = 0;
			while (sum < s) {
				debug(sum);
				debug(v1);
				int counter = 0;
				for (int i = 0; i < k; i++) {
					int index = k - i - 1;
					int value_here = v1[index];
					int max_allowed = n - i;
					if (value_here < max_allowed) {
						sum += 1;
						v1[index] = v1[index] + 1;
						counter = 1;
						break;
					}
				}
				if (counter == 0) {
					cout << -1 << nline;
					counter2 = 1;
					break;
				}
			}
			if (counter2 == 1)
				continue;
			vector<int> v2(n, -1);
			for (int i = l; i <= r; i++) {
				debug(i);
				v2[i - 1] = v1[i - l];
				used.insert(v2[i - 1]);
			}
			set<int> unused;
			for (int i = 1; i <= n; i++) {
				if (used.count(i) == 0) {
					unused.insert(i);
				}
			}
			debug(unused);
			for (int i = 0; i < n; i++) {
				if (v2[i] == -1) {
					v2[i] = *unused.begin();
					unused.erase(v2[i]);
				}
			}
			for (int i = 0; i < n; i++) {
				cout << v2[i] << " ";
			}
			cout << nline;
		}
	}
}

int main() {
#ifdef Priyansh31dec
	freopen("Error.txt", "w", stderr);
#endif
	fastio();
	auto start1 = high_resolution_clock::now();
	solve();
	auto stop1 = high_resolution_clock::now();
	auto duration = duration_cast<microseconds>(stop1 - start1);
#ifdef Priyansh31dec
	cerr << "Time: " << duration . count() / 1000 << endl;
#endif
}
```