#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

struct splitmix64_hash {
	static unsigned long long splitmix64(unsigned long long x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	unsigned long long operator()(unsigned long long x) const {
		static const unsigned long long FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

template<class T, class U, class H = splitmix64_hash> using hash_map = gp_hash_table<T, U, H>;
template<class T, class H = splitmix64_hash> using hash_set = hash_map<T, null_type, H>;

template<class T>
class wavelet {
public:
	wavelet(T* from, T* to, T L, T R) : low(L), high(R) {
		if(low == high || from >= to) {
			return;
		}
		T mid = low + (high - low) / 2;
		auto f = [mid](T x) {
			return x <= mid;
		};
		a.reserve(to - from + 1);
		a.push_back(0);
		for(auto it = from; it != to; ++it) {
			a.push_back(a.back() + f(*it));
		}
		auto p = stable_partition(from, to, f);
		l = new wavelet(from, p, low, mid);
		r = new wavelet(p, to, mid + 1, high);
	}

	// return kth smallest element in [L, R]
	T kth(int L, int R, int k) {
		if(L > R) {
			return 0;
		}
		if(low == high) {
			return low;
		}
		int lb = a[L - 1];
		int rb = a[R];
		int lhs = rb - lb;
		if(k <= lhs) {
			return l->kth(lb + 1, rb, k);
		}
		return r->kth(L - lb, R - rb, k - lhs);
	}

	// return number of elements in [L, R] <= k
	int leq(int L, int R, T k) {
		if(L > R || k < low) {
			return 0;
		}
		if(high <= k) {
			return R - L + 1;
		}
		int lb = a[L - 1];
		int rb = a[R];
		return l->leq(lb + 1, rb, k) + r->leq(l - lb, r - rb, k);
	}

	// return number of elements in [L, R] == k
	int count(int L, int R, T k) {
		if(L > R || k < low || k > high) {
			return 0;
		}
		if(low == high) {
			return R - L + 1;
		}
		int lb = a[L - 1];
		int rb = a[R];
		T mid = low + (high - low) / 2;
		if(k <= mid) {
			return l->count(lb + 1, rb, k);
		}
		return r->count(L - lb, R - rb, k);
	}

	~wavelet() {
		delete l;
		delete r;
	}

private:
	T low, high;
	wavelet* l;
	wavelet* r;
	vector<T> a;
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	int* a = new int[n];
	vector<int> xs(n);
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
		xs[i] = a[i];
	}
	sort(xs.begin(), xs.end());
	hash_map<int, int> mp;
	for(int i = 0; i < n; ++i) {
		int id = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
		mp[id] = a[i];
		a[i] = id;
	}
	wavelet<int> T(a, a + n, 0, n - 1);
	while(q--) {
		int l, r, k;
		cin >> l >> r >> k;
		cout << mp[T.kth(l, r, k)] << "\n";
	}
	return 0;
}

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

const int M = 1e9 + 7;

const int N = 20;

int dp[1 << N][N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<tuple<int, int, int>> edges(m);
	for(int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		edges[i] = {u, v, (1 << u) | (1 << v)};
	}
	vector<pair<int, int>> masks;
	for(int i = 0; i < (1 << n); ++i) {
		int j = __builtin_popcount(i);
		if(j >= 2) {
			masks.emplace_back(j, i);
		}
	}
	sort(masks.begin(), masks.end());
	dp[1][0] = 1;
	for(int id = 0; id < (int) masks.size(); ++id) {
		int mask = masks[id].second;
		for(auto& [u, v, c] : edges) {
			if((mask & c) == c) {
				dp[mask][v] = (dp[mask][v] + dp[mask ^ (1 << v)][u]) % M;
			}
		}
	}
	cout << dp[(1 << n) - 1][n - 1] << "\n";
	return 0;
}

225536 225537 225538 225539 225540 225541 225542 225543 0

184080417060 184081637148 179787767989 179788418039 179795209691 179795875231 179796326312 179796852574

184080417060 184081637148 184082735285 184083385335 184090176987 184090842527 184091293608 184091819870

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

const int N = 1e6 + 5;

bool isprime[N];
vector<int> prime;
int mobius[N];
int phi[N];
int phi_pref[N];

void init() {
	fill(isprime, isprime + N, true);
	isprime[0] = isprime[1] = false;
	mobius[1] = 1;
	phi[1] = 1;
	for(int i = 2; i < N; ++i) {
		if(isprime[i]) {
			prime.push_back(i);
			mobius[i] = -1;
			phi[i] = i - 1;
		}
		for(auto& p : prime) {
			if(p * i >= N) {
				break;
			}
			isprime[p * i] = false;
			mobius[p * i] = mobius[p] * mobius[i];
			phi[p * i] = phi[p] * phi[i];
			if(i % p == 0) {
				mobius[p * i] = 0;
				phi[p * i] = phi[i] * p;
				break;
			}
		}
	}
	for(int i = 1; i < N; ++i) {
		phi_pref[i] = phi_pref[i - 1] + phi[i];
	}
}

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	init();
	int n;
	while(cin >> n && n) {
		long long ans = 0;
		for(int i = 1, j; i <= n; i = j) {
			int p = n / i;
			j = n / p + 1;
			ans += 1LL * p * (p - 1) / 2 * (phi_pref[j - 1] - phi_pref[i - 1]);
		}
		cout << ans << "\n";
	}
	return 0;
}

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

using ll = long long;

const int N = 100;

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	mt19937_64 rnd(atoi(argv[1]));

	auto next = [&](ll x) {
		return rnd() % x;
	};

	auto randRange = [&](ll a, ll b) {
		return a + rnd() % (b - a + 1);
	};

	int n = randRange(2, N);
	int q = randRange(1, N);

	cout << n << " " << q << "\n";

	for(int i = 0; i < n; ++i)
		cout << randRange(0, 2147483647) << " \n"[i == n - 1];

	vector<int> a(1), b(n - 1);

	iota(b.begin(), b.end(), 1);
	random_shuffle(b.begin(), b.end(), next);

	while(!b.empty()) {
		int u = a[next((int) a.size())];
		int v = b.back();
		if(next(2) == 1)
			swap(u, v);

		cout << u + 1 << " " << v + 1 << "\n";

		a.push_back(b.back());
		b.pop_back();
	}

	for(int i = 0; i < q; ++i)
		cout << randRange(1, n) << " " << randRange(1, n) << "\n";
	
	return 0;
}

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

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;

	vector<int> a(n);
	for(auto& x : a)
		cin >> x;

	vector<vector<int>> adj(n);
	for(int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	vector<int> parent(n);
	vector<int> depth(n);
	function<void(int, int)> dfs = [&](int u, int p) {
		parent[u] = p;
		depth[u] = (u == 0 ? 0 : depth[p] + 1);
		for(int& v : adj[u]) {
			if(v == p)
				continue;
			dfs(v, u);
		}
	};

	dfs(0, -1);

	while(q--) {
		int u, v;
		cin >> u >> v;
		--u, --v;

		if(depth[u] < depth[v])
			swap(u, v);

		set<int> s;
		s.insert(a[u]);
		s.insert(a[v]);

		while(depth[u] > depth[v]) {
			u = parent[u];
			s.insert(a[u]);
		}

		while(u != v) {
			u = parent[u];
			v = parent[v];
			s.insert(a[u]);
			s.insert(a[v]);
		}

		cout << s.size() << "\n";
	}
	return 0;
}

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

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;

	vector<int> a(n);
	for(auto& x : a)
		cin >> x;

	vector<int> b(a);
	sort(b.begin(), b.end());
	for(auto& x : a)
		x = lower_bound(b.begin(), b.end(), x) - b.begin();

	vector<vector<int>> adj(n);
	for(int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	vector<vector<int>> dp(n, vector<int>(20));
	vector<int> depth(n);
	vector<int> in(n), out(n);
	vector<int> order;
	order.reserve(n * 2);
	function<void(int, int)> dfs = [&](int u, int p) {
		dp[u][0] = (u == 0 ? 0 : p);
		depth[u] = (u == 0 ? 0 : depth[p] + 1);
		in[u] = (int) order.size();
		order.push_back(u);

		for(int& v : adj[u])
			if(v != p)
				dfs(v, u);

		out[u] = (int) order.size();
		order.push_back(u);
	};

	dfs(0, -1);
	
	for(int x = 1; x < 20; ++x)
		for(int i = 0; i < n; ++i)
			dp[i][x] = dp[dp[i][x - 1]][x - 1];

	auto lift = [&](int u, int step) -> int {
		int r = 0;
		while(step) {
			if(step & 1)
				u = dp[u][r];
			step >>= 1;
			r <<= 1;
		}
		return u;
	};

	auto lca = [&](int x, int y) -> int {
		if(depth[x] < depth[y])
			swap(x, y);

		x = lift(x, depth[x] - depth[y]);

		if(x == y)
			return x;

		for(int i = 19; i >= 0; --i) {
			int new_x = dp[x][i];
			int new_y = dp[y][i];

			if(new_x != new_y) {
				x = new_x;
				y = new_y;
			}
		}

		assert(dp[x][0] == dp[y][0]);
		return dp[x][0];
	};

	vector<tuple<int, int, int, int>> qry(q);
	for(int i = 0; i < q; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;

		if(depth[u] > depth[v])
			swap(u, v);

		int z = lca(u, v);

		if(u == z)
			qry[i] = {in[u], in[v], -1, i};
		else
			qry[i] = {out[u], in[v], z, i};
	}

	const int m = sqrt(n * 2) + 1;
	sort(qry.begin(), qry.end(), [&](const tuple<int, int, int, int>& x, const tuple<int, int, int, int>& y) {
		if(get<0>(x) / m == get<0>(y) / m)
			return (get<0>(x) / m & 1 ? get<1>(x) > get<1>(y) : get<1>(x) < get<1>(y));

		return get<0>(x) < get<0>(y);
	});

	vector<int> occurrence(n);
	vector<int> cnt((int) b.size());
	int counter = 0;

	auto add = [&](int u) {
		++occurrence[u];
		if(occurrence[u] % 2 == 0) {
			--cnt[a[u]];

			if(cnt[a[u]] == 0)
				--counter;
		} else {
			++cnt[a[u]];

			if(cnt[a[u]] == 1)
				++counter;
		}
	};

	auto remove = [&](int u) {
		--occurrence[u];
		if(occurrence[u] % 2 == 0) {
			--cnt[a[u]];

			if(cnt[a[u]] == 0)
				--counter;
		} else {
			++cnt[a[u]];

			if(cnt[a[u]] == 1)
				++counter;
		}
	};

	vector<int> ans(q);
	int l = 0, r = 0;
	add(order[0]);
	for(int i = 0; i < q; ++i) {
		int L, R, z, id;
		tie(L, R, z, id) = qry[i];

		while(l < L) {
			remove(order[l]);
			++l;
		}
		while(l > L) {
			--l;
			add(order[l]);
		}
		while(r < R) {
			++r;
			add(order[r]);
		}
		while(r > R) {
			remove(order[r]);
			--r;
		}

		if(z != -1)
			add(z);

		ans[id] = counter;

		if(z != -1)
			remove(z);
	}
	for(auto& x : ans)
		cout << x << "\n";
	return 0;
}