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

def bfs(r):
    q = deque()
    q.append(r)
    dist = [-1] * (n + 1)
    dist[r] = 0
    parent = [-1] * (n + 1)
    p = []
    H = [[] for _ in range(n + 1)]
    while q:
        i = q.popleft()
        di = dist[i]
        p.append(i)
        for j in G[i]:
            if dist[j] == -1:
                dist[j] = di + 1
                parent[j] = i
                q.append(j)
    return H, dist, parent, p

def euler_tour(r, G):
    s = []
    s.append(r)
    now = [0] * (n + 1)
    t = 1
    t1, t2 = [-1] * (n + 1), [-1] * (n + 1)
    v = []
    while s:
        i = s[-1]
        if t1[i] == -1:
            v.append(i)
            t1[i] = t
            t += 1
        if now[i] == len(G[i]):
            t2[i] = t
            t += 1
            s.pop()
        else:
            s.append(G[i][now[i]])
            now[i] += 1
    return t1, t2, v

def slide_min(n, k, a):
    ans = []
    s = deque()
    for i in range(n):
        ai = a[i]
        while s:
            if a[s[-1]] >= ai:
                s.pop()
            else:
                break
        s.append(i)
        while s:
            if s[0] + k <= i:
                s.popleft()
            else:
                break
        if (i + 1) // k:
            ans.append(a[s[0]])
    return ans

def make_sparse_table(a):
    table = []
    s, l = a, 1
    table.append(s)
    while 2 * l <= len(a):
        s = slide_min(len(s), l + 1, s)
        table.append(s)
        l *= 2
    return table

def get_min(l, r, table):
    d = len(bin(r - l + 1)) - 3
    ans = min(table[d][l], table[d][r - pow2[d] + 1])
    return ans

n, r = map(int, input().split())
a = list(map(int, input().split()))
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
H, dist, dp0, p1 = bfs(r)
t1, t2, v = euler_tour(r, H)
mdp0 = [0] + list(a)
md = max(dist)
x = [[[] for _ in range(md + 1)] for _ in range(18)]
dp1, mdp1 = list(dp0), list(mdp0)
l0, r0 = [], []
p0 = []
d = 0
c = -1
d0 = []
d00 = []
for i in p1:
    c += 1
    if d < dist[i]:
        c, d = 0, dist[i]
        d0.append(d00)
        d00 = []
    p0.append(c)
    d00.append(i)
d0.append(d00)
for i in range(18):
    xi = x[i]
    l0i, r0i = [n + 1] * (n + 1), [-1] * (n + 1)
    for j, k in zip(p1, p0):
        xi[dist[j]].append(mdp0[j])
        if dp0[j] ^ -1:
            l0i[dp0[j]] = min(l0i[dp0[j]], k)
            r0i[dp0[j]] = max(r0i[dp0[j]], k)
    l0.append(l0i)
    r0.append(r0i)
    for j in range(1, n + 1):
        dp1[j] = dp0[dp0[j]]
        mdp1[j] = mdp0[j]
    for j in range(1, n + 1):
        if dp0[j] ^ -1:
            mdp1[dp0[j]] = min(mdp0[dp0[j]], mdp0[j])
    dp0, dp1 = dp1, dp0
    mdp0, mdp1 = mdp1, mdp0
pow2 = [1]
for _ in range(20):
    pow2.append(2 * pow2[-1])
m = int(input())
ans = []
last = 0
d = [0] * (n + 1)
for i, j in zip(p1, p0):
    d[i] = j
ok = [[0] * (md + 1) for _ in range(18)]
ts = []
inf = pow(10, 9) + 7
for _ in range(m):
    p, q = map(int, input().split())
    xi = (p + last) % n + 1
    ki = (q + last) % n
    ki += 1
    l, r = d[xi], d[xi]
    xl, xr = xi, xi
    dx = dist[xi]
    i = 0
    ans0 = inf
    while ki:
        if ki & pow2[i]:
            ki ^= pow2[i]
            if not ok[i][dx]:
                ts.append(make_sparse_table(x[i][dx]))
                ok[i][dx] = len(ts)
            ans0 = min(ans0, get_min(l, r, ts[ok[i][dx] - 1]))
            if not ki:
                break
            l, r = l0[i][xl], r0[i][xr]
            dx += pow2[i]
            xl, xr = d0[dx][l], d0[dx][r]
        i += 1
    ans.append(ans0)
    last = ans0
sys.stdout.write("\n".join(map(str, ans)))