You are given a rooted tree consisting of *n* vertices. Each vertex has a number written on it; number *a*<sub class="lower-index">*i*</sub> is written on vertex *i*.

Let's denote *d*(*i*, *j*) as the distance between vertices *i* and *j* in the tree (that is, the number of edges in the shortest path from *i* to *j*). Also let's denote the *k*-blocked subtree of vertex *x* as the set of vertices *y* such that both these conditions are met:
 -  *x* is an ancestor of *y* (every vertex is an ancestor of itself); -  *d*(*x*, *y*) ≤ *k*. 
You are given *m* queries to the tree. *i*-th query is represented by two numbers *x*<sub class="lower-index">*i*</sub> and *k*<sub class="lower-index">*i*</sub>, and the answer to this query is the minimum value of *a*<sub class="lower-index">*j*</sub> among such vertices *j* such that *j* belongs to *k*<sub class="lower-index">*i*</sub>-blocked subtree of *x*<sub class="lower-index">*i*</sub>.

Write a program that would process these queries quickly!

Note that the queries are given in a modified way.
The first line contains two integers *n* and *r* (1 ≤ *r* ≤ *n* ≤ 100000) — the number of vertices in the tree and the index of the root, respectively.

The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — the numbers written on the vertices.

Then *n* - 1 lines follow, each containing two integers *x* and *y* (1 ≤ *x*, *y* ≤ *n*) and representing an edge between vertices *x* and *y*. It is guaranteed that these edges form a tree.

Next line contains one integer *m* (1 ≤ *m* ≤ 10<sup class="upper-index">6</sup>) — the number of queries to process.

Then *m* lines follow, *i*-th line containing two numbers *p*<sub class="lower-index">*i*</sub> and *q*<sub class="lower-index">*i*</sub>, which can be used to restore *i*-th query (1 ≤ *p*<sub class="lower-index">*i*</sub>, *q*<sub class="lower-index">*i*</sub> ≤ *n*).

*i*-th query can be restored as follows:

Let *last* be the answer for previous query (or 0 if *i* = 1). Then *x*<sub class="lower-index">*i*</sub> = ((*p*<sub class="lower-index">*i*</sub> + *last*) *mod* *n*) + 1, and *k*<sub class="lower-index">*i*</sub> = (*q*<sub class="lower-index">*i*</sub> + *last*) *mod* *n*.
none
5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3
2
5
3 3
1 3 2
1 2
1 3
2
2 3
1 1
2
1
1 1
1
1
1 1
1
#define NDEBUG

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

#pragma region debug

#ifndef NDEBUG
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	return os << '(' << p.first << ", " << p.second << ')';
}

template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}

template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	os << '[';
	if (v.size()) {
		os << *v.begin();
		for (auto i = ++v.begin(); i != v.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const deque<T> &d) {
	os << '[';
	if (d.size()) {
		os << *d.begin();
		for (auto i = ++d.begin(); i != d.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, stack<T> s) {
	os << '[';
	if (s.size()) {
		int n = s.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = s.top();
			s.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
	}
	return os << "]>";
}

template<typename T>
ostream &operator<<(ostream &os, queue<T> q) {
	os << '[';
	if (q.size()) {
		int n = q.size();
		vector<T> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = q.front();
			q.pop();
		}
		os << v[n - 1];
		for (int i = n - 2; i >= 0; i--) 
			os << ", " << v[i];
	}
	return os << "]>";
}

template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &a) {
	os << '[';
	if (N) {
		os << *a.begin();
		for (auto i = ++a.begin(); i != a.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = ++s.begin(); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = ++s.begin(); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = ++s.begin(); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = ++m.begin(); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const unordered_map<T1, T2> &m) {
	os << '[';
	if (m.size()) {
		os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
		for (auto i = ++m.begin(); i != m.end(); i++)
			os << ", " << '(' << i->first << " : " << i->second << ')';
	}
	return os << ']';
}

map<char, string> _dbg_dict {
	{'1', "--------------------------------"},
	{'2', "================================"},
	{'3', "≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡"},
	{'4', "################################"},
	{'*', "********************************"},
	{'_', "_"},
	{'<', "<!---- "},
	{'>', " ----!>"},
	{'(', "(!==== "},
	{')', "==== !)"},
	{'[', "[!≡≡≡≡ "},
	{']', " ≡≡≡≡!]"},
	{'{', "{!#### "},
	{'}', " ####!}"},
	{'c', "checkpoint "},
	{'l', "line "},
	{'n', "\n"},
	{'t', "\t"}
};

template<typename T>
void _dbg_print(string var, const T &a) { cerr << var << " = " << a << '\n'; }

void _dbg_print(string var, const char *a) {
	int n = strlen(a);
	for (int i = 0; i < n; i++) 
		cerr << (i < n - 1 && a[i] == '_' && _dbg_dict.find(a[i + 1]) != _dbg_dict.end() ? _dbg_dict[a[++i]] : string(1, a[i]));
}

#define dbg1(a) _dbg_print(#a, a);
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define dbg9(a, b, c, d, e, f, g, h, i) dbg1(a) dbg8(b, c, d, e, f, g, h, i)
#define dbg10(a, b, c, d, e, f, g, h, i, j) dbg1(a) dbg9(b, c, d, e, f, g, h, i, j)
#define dbg11(a, b, c, d, e, f, g, h, i, j, k) dbg1(a) dbg10(b, c, d, e, f, g, h, i, j, k)
#define dbg12(a, b, c, d, e, f, g, h, i, j, k, l) dbg1(a) dbg11(b, c, d, e, f, g, h, i, j, k, l)
#define dbg13(a, b, c, d, e, f, g, h, i, j, k, l, m) dbg1(a) dbg12(b, c, d, e, f, g, h, i, j, k, l, m)
#define dbg14(a, b, c, d, e, f, g, h, i, j, k, l, m, n) dbg1(a) dbg13(b, c, d, e, f, g, h, i, j, k, l, m, n)
#define dbg15(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) dbg1(a) dbg14(b, c, d, e, f, g, h, i, j, k, l, m, n, o)
#define dbg16(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) dbg1(a) dbg15(b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _16, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg16, dbg15, dbg14, dbg13, dbg12, dbg11, dbg10, dbg9, dbg8, \
	dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define dbg(...)
#endif

#pragma endregion debug

#pragma region y_combinator

#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

#endif

#pragma endregion y_combinator

#pragma region tree_depth

#ifndef TREE_DEPTH_HPP
#define TREE_DEPTH_HPP

namespace tree {
	vector<int> depth(const vector<vector<int>> &tree, int s = 0) {
		int n = tree.size();
		vector<int> dep(n);

		auto dfs = y_combinator([&](auto dfs, int u, int p = -1) -> void {
			for (int v : tree[u]) {
				if (v == p)
					continue;
				dep[v] = dep[u] + 1;
				dfs(v, u);
			}
		});

		dep[s] = 0;
		dfs(s);
		return dep;
	}
}

#endif

#pragma endregion tree_depth

#pragma region euler_tour

#ifndef EULER_TOUR_HPP
#define EULER_TOUR_HPP

namespace tree {
	pair<vector<int>, vector<int>> euler_tour(const vector<vector<int>> &tree, int s = 0) {
		int n = tree.size();
		vector<int> ltime(n), rtime(n);
		int time = -1;

		auto dfs = y_combinator([&](auto dfs, int u, int p = -1) -> void {
			ltime[u] = ++time;
			for (int v : tree[u]) {
				if (v == p)
					continue;
				dfs(v, u);
			}
			rtime[u] = time;
		});

		dfs(s);
		return make_pair(ltime, rtime);
	}
}

#endif

#pragma endregion euler_tour

struct merge_sort_tree {
	int n;
	vector<vector<pair<int, int>>> tree;
	vector<vector<int>> prefix_min;

	merge_sort_tree(int _n, const vector<pair<int, int>> &A) { 
		n = _n;
		tree.resize(4 * n);
		prefix_min.resize(4 * n);
		build(1, 0, n - 1, A);
	}

	void build(int t, int tl, int tr, const vector<pair<int, int>> &A) {
		if (tl == tr) {
			tree[t].resize(1, A[tl]);
			prefix_min[t].resize(1, A[tl].second);
			return;
		}
		int tm = (tl + tr) / 2;
		build(t * 2, tl, tm, A);
		build(t * 2 + 1, tm + 1, tr, A);

		merge(tree[t * 2].begin(), tree[t * 2].end(), tree[t * 2 + 1].begin(), tree[t * 2 + 1].end(), back_inserter(tree[t]));
		int n = tree[t].size();
		prefix_min[t].resize(n);
		prefix_min[t][0] = tree[t][0].second;
		for (int i = 1; i < n; i++)
			prefix_min[t][i] = min(prefix_min[t][i - 1], tree[t][i].second);
	}

	int query(int l, int r, int k, int t, int tl, int tr) {
		if (r < tl || tr < l)
			return INT_MAX;
		if (l <= tl && tr <= r) {
			dbg("_1\n", tl, tr);
			int idx = upper_bound(tree[t].begin(), tree[t].end(), make_pair(k, INT_MAX)) - tree[t].begin() - 1; 
			return idx < 0 ? INT_MAX : prefix_min[t][idx];
		}
		int tm = (tl + tr) / 2;
		return min(query(l, r, k, t * 2, tl, tm), query(l, r, k, t * 2 + 1, tm + 1, tr));
	}

	int query(int l, int r, int k) { return query(l, r, k, 1, 0, n - 1); }
};

int main() {
	int N, S;
	cin >> N >> S;
	S--;
	vector<int> A(N);
	for (int &a : A)
		cin >> a;
	vector<vector<int>> T(N);
	for (int i = 1; i < N; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		T[u].push_back(v);
		T[v].push_back(u);
	}

	auto dep = tree::depth(T, S);
	auto [ltime, rtime] = tree::euler_tour(T, S);

	dbg(dep, ltime, rtime)

	vector<pair<int, int>> B(N);
	for (int u = 0; u < N; u++) 
		B[ltime[u]] = {dep[u], A[u]};
	
	merge_sort_tree mst(N, B);

	int Q;
	cin >> Q;
	int prev = 0;
	while (Q--) {
		int u, k;
		cin >> u >> k;
		u = (u + prev) % N;
		k = (k + prev) % N;
		dbg("_2\n", u, k);
		prev = mst.query(ltime[u], rtime[u], dep[u] + k);
		cout << prev << '\n';
	}
}