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

string num, num2;
long long dp[2][20][20 * 9];
int casio[2][20][20 * 9], cas = 1;
long long yo(int x,int pos,int sum){
	if(sum < 0) return 0;
	if(pos<0){
		return sum == 0;
	} long long &res=dp[x][pos][sum]; int &cs=casio[x][pos][sum];
	if(~res && (x==0 || cs==cas))return res; cs=cas; res=0;
	for(int i = 0, en = (x ? num[pos]-'0' : 9); i <= en; i++) {
		res += yo(x&&i==en, pos - 1, sum - i);
	} return res;
}

long long get(long long n, long long x){
	if(n == 0) return 0;
	num = to_string(n);
	reverse(num.begin(), num.end());
	if(x > (int)num.size() * 9) return 0;
	cas++; long long ans = yo(1, num.size()-1, x);
	return ans;
}

void dfs(int x, int pos, int sum, long long k) {
	if(sum < 0) return;
	if(pos < 0) return;
	for(int i = 0, en = (x ? num[pos]-'0' : 9); i <= en; i++) {
		long long res = yo(x&&i==en, pos - 1, sum - i);
		if(res >= k) {
			num2 += ('0' + i);
			dfs(x&&i==en, pos - 1, sum - i, k);
			return;
		} else {
			k -= res;
		}
	}
}

long long kth(long long n, long long x, long long k) {
	if(get(n, x) >= k) {
		num2 = "";
		dfs(1, num.size()-1, x, k);
		long long ans = stoll(num2.c_str());
		return ans;
	} else {
		return -1;
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
	memset(dp,-1,sizeof dp);
	int t; cin >> t; while(t--) {
		long long l, r, k, x; cin >> l >> r >> k >> x;
		k += get(l - 1, x);
		long long ans = kth(r, x, k);
		cout << ans << '\n';
	}
	return 0;
}

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

const int mx = 1e5 + 5;
int cnt[mx];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, ma = 0; cin >> n;
	for(int i = 1; i <= n; i++){
		int x; cin >> x;
		ma = max(ma, ++cnt[x]);
	}
	int x = min(n / 2, n - ma);
	x += n - 2 * x;
	cout << x << '\n';
	return 0;
}

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

const int mx = 2e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> g[mx];
int get(int x, int l, int r) {
	return (int)(upper_bound(g[x].begin(), g[x].end(), r) - lower_bound(g[x].begin(), g[x].end(), l));
}
int arr[10 * mx];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		int x; cin >> x;
		arr[i] = x;
		g[x].push_back(i);
	}
	while(q--) {
		int l, r; cin >> l >> r;
		int len = (r - l + 1);
		int a = 0, b = 0;
		for(int it = 0; it <= 30; it++) {
			a = max(a, get(arr[l + rng() % len], l, r));
			if(n - len) {
				int x = 1 + rng() % (n - len);
				if(x >= l) x += len;
				b = max(b, (int) g[arr[x]].size() - get(arr[x], l, r));
			}
		}
		int ans = 0;
		ans += min(len / 2, len - a) + min((n - len) / 2, (n - len) - b);
		ans += (n - 2 * ans);
		cout << ans << '\n';
	}
	return 0;
}

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

const int mx = 1e5 + 5;
int phi[mx], nod[mx];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int i = 0; i < mx; i++) phi[i] = i;
	for(int i = 2; i < mx; i++) {
		if(phi[i] == i) {
			phi[i] = i - 1;
			for(int j = i + i; j < mx; j += i) {
				phi[j] = phi[j] / i * (i - 1);
			}
		}
	}
	for(int i = 1; i < mx; i++) {
		for(int j = i; j < mx; j += i) {
			nod[j]++;
		}
	}
	int t; cin >> t; while(t--) {
		int n; cin >> n;
		cout << 1LL * nod[n] * phi[n] << '\n';
	}
	return 0;
}

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

int n;
struct segtree {
	static const int maxn = 2e5 + 10;
	int tree[maxn << 2] = {0};
	void update(int pos, int v, int node = 1, int l = 1, int r = n) {
		if (r < pos || l > pos) return;
		if (pos == l && pos == r) {
			tree[node] = v;
			return;
		} int mid = l + r >> 1;
		update(pos, v, node << 1, l, mid);
		update(pos, v, node << 1 | 1, mid + 1, r);
		tree[node] = max(tree[node << 1] , tree[node << 1 | 1]);
	}
	int query(int i, int j, int node = 1, int l = 1, int r = n) {
		if (l > r || r < i || l > j) return -1;
		if (i <= l && r <= j) {
			return tree[node];
		} int mid = l + r >> 1;
		return max(query(i, j, node << 1, l, mid) , query(i, j, node << 1 | 1, mid + 1, r));
	}
} sg;

const int mx = 2e5 + 10;
vector<int> g[mx];
int arr[mx], tim, st[mx], en[mx], lvl[mx], sp[21][mx];
void dfs(int u, int p = 0) {
	st[u] = ++tim;
	lvl[u] = lvl[p] + 1;
	sp[0][u] = p;
	for(int i = 1; i <= 20; i++) sp[i][u] = sp[i - 1][sp[i - 1][u]];
	for(int v: g[u]) {
		if(v != p) {
			dfs(v, u);
		}
	}
	en[u] = tim;
}
inline bool is_parent(int a, int b) { return st[a] <= st[b] && en[b] <= en[a]; }
int lca(int a, int b) {
	for(int i = 20; i >= 0; i--) {
		if((1 << i) <= b) a = sp[i][a], b -= (1 << i);
	}
	return a;
}
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t; while(t--) {
		cin >> n;
		for(int i = 1; i <= n; i++) cin >> arr[i];
		for(int i = 1; i < n; i++) {
			int u, v; cin >> u >> v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		dfs(1);
		for(int i = 1; i <= n; i++) sg.update(st[i], arr[i]);
		int q; cin >> q; while(q--) {
			int ty; cin >> ty;
			if(ty == 1) {
				int u, x; cin >> u >> x;
				sg.update(st[u], x);
			} else {
				int u, v; cin >> u >> v;
				if(u == v) {
					cout << sg.query(1, n) << '\n';
				} else if(is_parent(v, u)) {
					u = lca(u, lvl[u] - lvl[v] - 1);
					cout << max(sg.query(1, st[u] - 1), sg.query(en[u] + 1, n)) << '\n';
				} else {
					cout << sg.query(st[v], en[v]) << '\n';
				}
			}
		}
		for(int i = 1; i <= n; i++) g[i].clear();
		tim = 0;
	}
	return 0;
}

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

const int mod = 1e9 + 7, mx = 1e5 + 10;
int f[mx];
int power(int a, int b) {
	int x = 1;
	while (b) {
		if (b & 1) x = 1LL * x * a % mod;
		a = 1LL * a * a % mod;
		b >>= 1;
	} return x;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	f[0] = 1;
	for(int i = 1; i < mx; i++) f[i] = 1LL * f[i - 1] * i % (mod - 1);
	int t; cin >> t; while(t--) {
		int a, b, n; cin >> a >> b >> n;
		cout << power(n, f[min(a, b)]) << '\n';
	}
	return 0;
}

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

const int mx = 2e5 + 10;
vector<int> g[mx];
int tim, st[mx], en[mx], lvl[mx], sp[21][mx], par[mx];
int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }
void dfs(int u, int p = 0) {
	st[u] = ++tim;
	lvl[u] = lvl[p] + 1;
	sp[0][u] = p;
	for(int i = 1; i <= 20; i++) sp[i][u] = sp[i - 1][sp[i - 1][u]];
	for(int v: g[u]) {
		if(v != p) {
			dfs(v, u);
		}
	}
	en[u] = tim;
}
inline bool is_parent(int a, int b) { return st[a] <= st[b] && en[b] <= en[a]; }
inline int distance(int a, int b) {
	if(lvl[a] > lvl[b]) swap(a, b);
	if(is_parent(a, b)) {
		return lvl[b] - lvl[a];
	}
	int ans = 0;
	for(int i = 20; i >= 0; i--) {
		if(lvl[sp[i][b]] >= lvl[a]) {
			ans += (1 << i);
			b = sp[i][b];
		}
	}
	for(int i = 20; i >= 0; i--) {
		if(sp[i][a] != sp[i][b]) {
			ans += (2 << i);
			a = sp[i][a];
			b = sp[i][b];
		}
	}
	if(a != b) ans += 2;
	return ans;
}
int lca(int a, int b) {
	for(int i = 20; i >= 0; i--) {
		if((1 << i) <= b) a = sp[i][a], b -= (1 << i);
	}
	return a;
}
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t; while(t--) {
		int n, m; cin >> n >> m;
		vector<pair<int, int>> nodes(n + 1);
		vector<int> diameter(n + 1);
		vector<array<int, 3>> query(m);
		for(auto &[id, u, v]: query) {
			cin >> id >> u;
			if(id == 1) {
				cin >> v;
				g[u].push_back(v);
				g[v].push_back(u);
			}
		}
		dfs(1);
		for(int i = 1; i <= n; i++) {
			par[i] = i;
			nodes[i] = {i, i};
		}
		for(auto &[id, u, v]: query) {
			if(id == 1) {
				u = find(u);
				v = find(v);
				tie(diameter[v], nodes[v]) = max({
					make_pair(diameter[u], nodes[u]),
					make_pair(diameter[v], nodes[v]),
					make_pair(distance(nodes[u].first, nodes[v].first), make_pair(nodes[u].first, nodes[v].first)),
					make_pair(distance(nodes[u].first, nodes[v].second), make_pair(nodes[u].first, nodes[v].second)),
					make_pair(distance(nodes[u].second, nodes[v].second), make_pair(nodes[u].second, nodes[v].second)),
					make_pair(distance(nodes[u].second, nodes[v].first), make_pair(nodes[u].second, nodes[v].first)),
				});
				par[u] = v;
			} else {
				v = find(u);
				int d1 = distance(nodes[v].first, u);
				int d2 = distance(nodes[v].second, u);
				if(d1 > d2) cout << d1 << ' ' << nodes[v].first << '\n';
				else cout << d2 << ' ' << nodes[v].second << '\n';
			}
		}
		for(int i = 1; i <= n; i++) g[i].clear();
		tim = 0;
	}
	return 0;
}

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

const int mx = 1e5 + 5;
int a[mx];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	set<int> st;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		if(a[i] > 1) {
			st.insert(i);
		}
	}
	while(q--) {
		int t; cin >> t;
		if(t == 1) {
			int x, y; cin >> x >> y;
			st.erase(x);
			if(y > 1) st.insert(x);
		} else {
			int l, r; cin >> l >> r;
			auto it = st.lower_bound(l);
			if(it == st.end() || *it > r) {
				cout << ((r - l) & 1 ? "Second": "First") << '\n';
			} else {
				cout << ((*it - l) & 1 ? "Second": "First") << '\n';
			}
		}
	}
	return 0;
}

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

const int mx = 5e5 + 10;
vector<int> d[mx];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int i = 1; i < mx; i++) {
		for(int j = i; j < mx; j += i) {
			d[j].push_back(i);
		}
	}
	int t; cin >> t; while(t--) {
		int a, b, m1, m2; cin >> a >> b >> m1 >> m2;
		int g = abs(__gcd(a - m1, b - m2));
		if(g == 0) {
			cout << max(a, b) + 1 << '\n';
		} else {
			auto it = upper_bound(d[g].begin(), d[g].end(), max(m1, m2));
			if(it == d[g].end() || a % (*it) != m1 || b % (*it) != m2) {
				cout << -1 << '\n';
			} else {
				cout << *it << '\n';
			}
		}
	}
	return 0;
}

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

const int mx = 1e5 + 5;
int n, m, k;
int c[mx], p[mx], vis[mx];
vector<int> g[mx];
int dfs(int u) {
	vis[u] = 1;
	int ret = c[u];
	for(int v: g[u]) {
		if(!vis[v]) {
			ret += dfs(v);
		}
	}
	return ret;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t; while(t--) {
		cin >> n >> m >> k;
		memset(c, 0, sizeof c);
		for(int i = 1, x; i <= n; i++) {
			cin >> x;
			c[x]++;
			g[i].clear();
		}
		for(int i = 1; i <= n; i++) cin >> p[i];
		for(int i = 1, u, v; i <= m; i++) {
			cin >> u >> v;
			g[v].push_back(u);
		}
		vector<int> a(n);
		iota(a.begin(), a.end(), 1);
		sort(a.begin(), a.end(), [](int i, int j) { return p[i] > p[j]; });
		long long res = 0;
		memset(vis, 0, sizeof vis);
		for(int i: a) {
			if(vis[i]) continue;
			int cnt = dfs(i);
			int x = min(cnt, k);
			k -= x;
			res += 1LL * p[i] * x;
		}
		cout << res << '\n';
	}
	return 0;
}

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

const int mod = 1e9 + 7;

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<tuple<int, int, int>> a(n);
	for(int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		a[i] = {i, x + y, 0};
	}
	sort(a.begin(), a.end(), [](tuple<int, int, int> &x, tuple<int, int, int> &y) {
		return get<1>(x) < get<1>(y);
	});
	int i = 0, cur = 1, nxt = 2;
	for(auto &[ind, j, ans]: a) {
		while(i < j) i++, tie(cur, nxt) = make_pair(nxt, (2LL * (i + 1) * nxt + 1LL * i * cur) % mod);
		ans = cur;
	}
	sort(a.begin(), a.end());
	for(auto &[ind, j, ans]: a) {
		cout << ans << '\n';
	}
	return 0;
}

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

const int mx = 1e6 + 10, mod = 1e9 + 7;
int n, m;
int a[mx], dl[mx], dr[mx];

int power(int a, int b) {
	int r = 1; while(b) {
		if(b & 1) r = 1LL * r * a % mod;
		a = 1LL * a * a % mod;
		b >>= 1;
	}
	return r;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++) cin >> a[i];
	sort(a + 1, a + 1 + m);
	for(int i = 1, x[2] = {}; i <= m; i++) {
		int g = a[i] - 1 - a[i - 1];
		x[i & 1] ^= g;
		dl[i] = x[i & 1];
	}
	a[m + 1] = n;
	for(int i = 1, x[2] = {}, j = m; i <= m; i++, j--) {
		int g = a[j + 1] - 1 - a[j];
		x[i & 1] ^= g;
		dr[j] = x[i & 1];
	}
	int total = 0, win = 0;
	for(int i = 0, j = 1; i < n; i++) {
		while(a[j] <= i) j++;
		total++;
		int x = 0;
		if(1 <= j - 1 && j - 1 <= m) x ^= dl[j - 1];
		if(1 <= j && j <= m) x ^= dr[j];
		win += !!x;
	}
	cout << 1LL * win * power(total, mod - 2) % mod << '\n';
	return 0;
}