t = int(input())
for i in range(t):
    n, l, r, k = map(int, input().split())
    t = list(map(int, input().split()))
    d = 0
    last = 0
    ans = 10 ** 9
    if l <= k <= r:
        ans = last
    if k > r:
        d = -1
    if k < l:
        d = 1
    for x in t:
        k += d * (x - last)
        last = x
        if l <= k <= r:
            ans = min(ans, last)
        if k > r:
            d = -1
        if k < l:
            d = 1
    if ans == 10 ** 9:
        ans = -1
    print(ans)

t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    b = list(map(int, input().split()))
    
    used = [False for i in range(n)]
    for x in b:
        used[x - 1] = True
    ans = []
    for i in range(n, 0, -1):
        if not used[i - 1]:
            ans.append(i)
    print(*ans)

#include<bits/stdc++.h>

using namespace std;

int n;
vector<int> a;

inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	return true;
}

inline void solve() {
	if (n == 2)
		cout << a[0] + min(1, a[1]) << endl;
	else
		cout << accumulate(a.begin(), a.end(), 0ll) << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int t; cin >> t;
	while (t--) {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

fun main() {
    repeat(readln().toInt()) {
        val (n, m) = readln().split(" ").map { it.toInt() }
        val s = readln().split(" ").map { it.toInt() }
        val d = readln().split(" ").map { it.toInt() }.withIndex().sortedBy { it.value }

        val ans = sortedSetOf<Int>()
        for (curS in s) {
            val pos = -1 - d.binarySearch { if (it.value <= curS) -1 else 1 }
            if (pos > 0)
                ans.add(d[pos - 1].index + 1)
            else {
                println(-1)
                return@repeat
            }
        }
        if (ans.size < n) {
            println(-1)
            return@repeat
        }
        println(ans.size)
        println(ans.joinToString(" "))
    }
}

#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), d(n);
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      d[i] = (i + 1) * (n - i);
    }
    sort(a.begin(), a.end());
    sort(d.begin(), d.end());
    long long ans = 0;
    for (int i = 0; i < n; ++i) ans += a[i] * 1LL * d[n - i - 1];
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;

using li = long long;

map<li, li> dp;

li calc(li n, li k) {
  if (n < k) return 0;
  if (n == k) return 1;
  if (dp.count(n)) return dp[n];
  return dp[n] = calc(n / 2, k) + calc(n - n / 2, k);
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    li n, k;
    cin >> n >> k;
    dp.clear();
    cout << calc(n, k) << endl;  
  }
}

#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t = 1;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x, --x;
    vector<vector<int>> pos(n);
    for (int i = 0; i < n; ++i) pos[a[i]].push_back(i);
    int ans = n;
    for (int i = 0; i < n; ++i) {
      int sz = pos[i].size();
      if (sz < k) continue;
      for (int j = 0; j + k <= sz; ++j)
        ans = min(ans, pos[i][j + k - 1] - pos[i][j] - k + 1);
      for (int j = 1; j < k; ++j) 
        ans = min(ans, pos[i][j - 1] - j + (k - j) + 1);
      ans = min(ans, k);
    }
    if (ans == n) ans = -1;
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;

const int MOD = 998244353;
const int N = 101;
const int M = 2 * N;

int n, k;
int dp[N][N][N];
int C[M][M];

int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  if (x < 0) x += MOD;
  return x;
}

int main() {
  for (int i = 0; i < M; ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++j) {
      C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
    }
  }
  cin >> n >> k;
  dp[0][0][0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= k; ++j) {
      for (int x = 0; x <= k; ++x) {
        for (int y = 0; y <= k; ++y) {
          int nj = j + max(0, y - x);
          if (nj > k) continue; 
          dp[i + 1][nj][y] = add(dp[i + 1][nj][y], dp[i][j][x]);
        }
      }
    }
  }
  int ans = 0;
  for (int j = 0; j <= k; ++j) {
    for (int x = 0; x <= k; ++x) {
      ans = add(ans, dp[n][j][x]);
    }
  }
  for (int sum = 0; sum < k; ++sum) {
    ans = add(ans, -C[sum + n - 1][n - 1]);
  }
  cout << ans << '\n';  
}

#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t = 1;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n - 1);
    for (int& x : a) cin >> x, --x;
    set<int> s({0});
    vector<int> ans(n);
    for (int i = 0; i < n - 1; ++i) {
      if (a[i] == -1) {
      	s.insert(i + 1);
      } else {
        if (s.size() == 1 && *s.begin() == a[i]) {
          ans[i + 1] = i;
        } else {
          bool f = s.count(a[i]);
          for (int x : s) if (x != a[i]) ans[x] = i;
          s.clear();
          if (f) s.insert(a[i]);
          s.insert(i + 1);
        }
      }
    }
    for (int x : s) ans[x] = n - 1;
    for (int i = 0; i < n; ++i) cout << ans[i] << ' ';
    cout << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;

using li = long long;

const li INF = 1e18;
const int N = 51;
const int B = N * N;

int n, k, m;
int a[N];
li x[N];
li dp[N][N][2 * B];

int main() {
  cin >> n >> k >> m;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) cin >> x[i];
  x[n] = x[n - 1];
  for (int i = 0; i < N; ++i) 
    for (int j = 0; j < N; ++j) 
      for (int b = 0; b < 2 * B; ++b) 
        dp[i][j][b] = INF; 
  dp[0][0][B] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= k; ++j) {
      for (int b = 0; b < 2 * B; ++b) {
        if (dp[i][j][b] == INF) continue;
        for (int c = 0; c < N; ++c) {
          int nj = min(k, j + (c >= m));
          int nb = b + a[i] - c;
          if (0 <= nb && nb < 2 * B)
            dp[i + 1][nj][nb] = min(dp[i + 1][nj][nb], dp[i][j][b] + abs(nb - B) * (x[i + 1] - x[i]));
        }
      }
    }
  }
  cout << dp[n][k][B] << endl;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const array<A, 3> &v) {
	out << "[";
	fore(i, 0, 3) {
		if(i) out << " ";
		out << v[i];
	}
	return out << "]";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	fore(i, 0, sz(v)) {
		if(i) out << " ";
		out << v[i];
	}
	return out;
}


const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

int n, k;
string s;

inline bool read() {
	if(!(cin >> n >> k >> s))
		return false;
	return true;
}

vector<int> c, id, lcp;

void suffixArray(string s) {
	s += '$';
	int n = sz(s);
	
	c.assign(n, 0);
	for (int len = 1; len < 2 * n; len <<= 1) {
		int half = len >> 1;
		vector< array<int, 3> > ps(n);
		fore (i, 0, n) {
			if (len == 1)
				ps[i] = {int(s[i]), 0, i};
			else
				ps[i] = {c[i], c[(i + half) % n], i};
		}
		stable_sort(all(ps));
		c[ps[0][2]] = 0;
		fore (i, 1, n)
			c[ps[i][2]] = c[ps[i - 1][2]] + (ps[i][0] != ps[i - 1][0] || ps[i][1] != ps[i - 1][1]);
	}
	c.pop_back();
	fore (i, 0, sz(c))
		c[i]--;
	id.resize(sz(c));
	fore (i, 0, sz(c))
		id[c[i]] = i;
}

void getLcp() {
	lcp.assign(n, 0);
	int l = 0;
	fore (i, 0, n) {
		l = max(0, l - 1);
		if (c[i] == n - 1)
			continue;
		int nxt = id[c[i] + 1];
		while (i + l < n && nxt + l < n && s[i + l] == s[nxt + l])
			l++;
		lcp[i] = l;
	}
}

bool check(int x) {
	int bLen = (n - k) / x;
	
//	cerr << x << " bl = " << bLen << endl;
	
	vector<int> t(n, -1);
	t[id[0]] = 0;
	fore (i, 1, n)
		t[id[i]] = t[id[i - 1]] + (lcp[id[i - 1]] < bLen);
	
	vector<int> d(n, 0);
	vector<int> bst(n, 0);
	int mx = 0;
	for (int i = n - bLen; i >= 0; i--) {
		int j = i + bLen + 1;
		if (j < n)
			bst[t[j]] = max(bst[t[j]], d[j]);
		
		d[i] = 1 + bst[t[i]];
		mx = max(mx, d[i]);
	}
//	cerr << "d = " << d << endl;
	return mx >= x;
}

inline void solve() {
//	cerr << s << endl;
	suffixArray(s);
	getLcp();
	
//	fore (i, 0, n)
//		cerr << lcp[id[i]] << ": " << s.substr(id[i]) << endl;
	
	int rem = n - k;
		
	int mx = -1;
	for (int d = 1; d * d <= rem; d++) {
		if (rem % d != 0)
			continue;
		if (check(d))
			mx = max(mx, d);
		if (d * d != rem && check(rem / d))
			mx = max(mx, rem / d);
	}
	cout << mx << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;

int main() {
  int t = 1;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    auto vals = a;
    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
    int k = vals.size();
    for (int& x : a)
      x = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
    auto b = a;
    sort(b.begin(), b.end());
    vector<vector<int>> g(k);
    for (int i = 0; i < n; ++i) if (a[i] != b[i]) 
      g[a[i]].push_back(b[i]);
    vector<int> lst(k), used(k);
    int vs, es;
    auto dfs = [&](auto dfs, int v) -> void {
      vs += !used[v];
      used[v] = true;
      while (lst[v] < (int)g[v].size()) {
        int u = g[v][lst[v]++];
        ++es;
        dfs(dfs, u);
      }
    };
    int ans = 0;
    for (int i = 0; i < k; ++i) {
      vs = es = 0;
      dfs(dfs, i);
      if (vs == 2) ans += es / 2;
      else if (vs > 2) ans += es - 1;
    }
    cout << ans << '\n';
  }
}