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
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m):
    x, s = [0] * (2 * m), [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        u, v = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        x[i], x[i + 1] = u, v
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return G, s

def bfs(s):
    q = [s]
    dist = [inf] * (n + 1)
    dist[s] = 0
    parent = [-1] * (n + 1)
    for k in range(n):
        i = q[k]
        di = dist[i]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
                parent[j] = i
    return q, dist, parent

def f(u, v):
    return u * (n + 1) + v

def get_min(s, t):
    s, t = s + l1, t + l1
    ans = inf
    while s <= t:
        if s % 2 == 0:
            s //= 2
        else:
            ans = min(ans, tree[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = min(ans, tree[t])
            t = (t - 1) // 2
    return ans

n, r = map(int, input().split())
a = [0] + list(map(int, input().split()))
G, s0 = make_graph(n, n - 1)
inf = pow(10, 9) + 1
q, dist, parent = bfs(r)
q = [0] + q
p = [0] * (n + 1)
for i in range(1, n + 1):
    p[q[i]] = i
m0 = max(dist[1:])
l = (m0 + 1).bit_length()
pow2 = [1]
for _ in range(l):
    pow2.append(2 * pow2[-1])
n0 = (n + 1) * l
l0, r0, mi = [inf] * n0, [-inf] * n0, [inf] * n0
for i in range(1, n + 1):
    l0[i], r0[i], mi[i] = p[i], p[i], a[i]
p0 = list(parent)
for i in range(1, l):
    for j in range(1, n + 1):
        if p0[j] == -1:
            continue
        k = p0[j]
        u, v = f(i, k), f(i - 1, j)
        l0[u], r0[u] = min(l0[u], l0[v]), max(r0[u], r0[v])
        mi[u] = min(mi[u], mi[v])
    for j in range(1, n + 1):
        mi[f(i, j)] = min(mi[f(i, j)], mi[f(i - 1, j)])
    p0 = [-1 if p0[j] == -1 else p0[p0[j]] for j in range(n + 1)]
l1 = pow(2, (n0 + 1).bit_length())
l2 = 2 * l1
tree = [inf] * l2
for i in range(l):
    for j in range(1, n + 1):
        tree[f(i, p[j]) + l1] = mi[f(i, j)]
for i in range(l1 - 1, 0, -1):
    tree[i] = min(tree[2 * i], tree[2 * i + 1])
m = int(input())
ans = []
last = 0
for _ in range(m):
    p0, q0 = map(int, input().split())
    x, k = (p0 + last) % n + 1, (q0 + last) % n
    k = min(k, m0 - dist[x])
    if not k:
        ans0 = a[x]
    else:
        d = k.bit_length() - 1
        c = k - pow2[d] + 1
        u, v = x, x
        for i in range(l):
            if c & pow2[i]:
                u, v = q[l0[f(i + 1, u)]], q[r0[f(i + 1, v)]]
        ans0 = min(tree[f(d, x) + l1], get_min(f(d, p[u]), f(d, p[v])))
    ans.append(ans0)
    last = ans0
sys.stdout.write("\n".join(map(str, ans)))