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

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

def euler_tour(r):
    s = []
    s.append(r)
    now = [0] * (n + 1)
    t = 1
    t1, t2 = [-1] * (n + 1), [-1] * (n + 1)
    v = []
    d = [[] for _ in range(n + 1)]
    td = [[] for _ in range(n + 1)]
    while s:
        i = s[-1]
        if t1[i] == -1:
            v.append(i)
            t1[i] = t
            d[len(s)].append(i)
            td[len(s)].append(t1[i])
            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, d, td

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)
G, parent, dist = bfs(r)
t1, t2, v, d, td = euler_tour(r)
d0 = [dict() for _ in range(n + 1)]
for i in range(1, n + 1):
    di = d[i]
    for j in range(len(di)):
        d0[i][di[j]] = j
pow2 = [1]
dp0 = list(parent)
dp1 = [0] + list(a)
for _ in range(18):
    pow2.append(2 * pow2[-1])
dp3 = []
for i in range(18):
    dp2 = list(dp1)
    for j in range(1, n + 1):
        if dp0[j] ^ -1:
            dp2[dp0[j]] = min(dp2[dp0[j]], dp1[j])
    if i:
        dp0 = [-1 if not dp0[j] ^ -1 else dp0[dp0[j]] for j in range(n + 1)]
    dp4 = [[] for _ in range(n + 1)]
    for j in range(1, n + 1):
        for k in d[j]:
            dp4[j].append(dp2[k])
    dp3.append(dp4)
    dp1, dp2 = dp2, dp1
ans = []
m = int(input())
last = 0
mt = [[0] * (n + 1) for _ in range(18)]
for _ in range(m):
    p, q = map(int, input().split())
    x = (p + last) % n + 1
    k = (q + last) % n
    h = dist[x]
    l, r = x, x
    ans0 = a[x - 1]
    for i in range(18):
        if not k & pow2[i]:
            continue
        if not mt[i][h]:
            mt[i][h] = make_sparse_table(dp3[i][h])
        dl, dr = d0[h][l], d0[h][r]
        ans0 = min(ans0, get_min(dl, dr, mt[i][h]))
        h += pow2[i]
        if h > n or not d[h]:
            break
        tl, tr = t1[l], t2[r]
        u = bisect.bisect_left(td[h], tl)
        v = bisect.bisect_left(td[h], tr)
        if not u ^ v:
            break
        l, r = d[h][u], d[h][v - 1]
    ans.append(ans0)
    last = ans0
sys.stdout.write("\n".join(map(str, ans)))