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 defaultdict
import sys
readline=sys.stdin.readline

class Segment_Tree2:
    def __init__(self,N,M,f,e,lst=None,dynamic=False):
        self.N=N
        self.M=M
        self.f=f
        self.e=e
        if dynamic:
            self.segment_tree=defaultdict(lambda:defaultdict(lambda:e))
        else:
            if lst==None:
                self.segment_tree=[[self.e]*2*self.M for i in range(2*self.N)]
            else:
                assert len(lst)<=self.N
                assert all(len(lst[i])<=self.M for i in range(self.N))
                self.segment_tree=[[self.e]*2*self.M for i in range(self.N)]+[[self.e]*self.M+lst[i]+[self.e]*(self.M-len(lst[i])) for i in range(len(lst))]+[[self.e]*2*self.M for i in range(self.N-len(lst))]
                for i in range(self.N-1,0,-1):
                    for j in range(2*self.M-1,self.M-1,-1):
                        self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])
                for i in range(2*self.N-1,-1,-1):
                    for j in range(self.M-1,0,-1):
                        self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])

    def Build(self,lst):
        assert len(lst)<=self.N
        assert all(len(lst[i] for i in range(self.N))<=self.M)
        for i in range(len(lst)):
            for j in range(len(lst[i])):
                self.segment_tree[i+self.N][j+self.M]=lst[i][j]
        for i in range(self.N-1,0,-1):
            for j in range(2*self.M-1,self.M-1,-1):
                self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])
        for i in range(2*self.N-1,-1,-1):
            for j in range(self.M-1,0,-1):
                self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])

    def Fold(self,LN=None,RN=None,LM=None,RM=None):
        LN+=self.N
        RN+=self.N
        LM+=self.M
        RM+=self.M
        idxN=[]
        idxM=[]
        while LN<RN:
            if LN&1:
                idxN.append(LN)
                LN+=1
            if RN&1:
                RN-=1
                idxN.append(RN)
            LN>>=1
            RN>>=1
        while LM<RM:
            if LM&1:
                idxM.append(LM)
                LM+=1
            if RM&1:
                RM-=1
                idxM.append(RM)
            LM>>=1
            RM>>=1
        retu=self.e
        for i in idxN:
            for j in idxM:
                retu=self.f(retu,self.segment_tree[i][j])
        return retu

    def Fold_Index(self,LN=None,RN=None,LM=None,RM=None):
        if LN==None:
            LN=self.N
        else:
            LN+=self.N
        if RN==None:
            RN=self.N*2
        else:
            RN+=self.N
        if LM==None:
            LM=self.M
        else:
            LM+=self.M
        if RM==None:
            RM=self.M*2
        else:
            RM+=self.M
        if LN==RN and LM==RM:
            return None
        idxN=[]
        idxM=[]
        while LN<RN:
            if LN&1:
                idxN.append(LN)
                LN+=1
            if RN&1:
                RN-=1
                idxN.append(RN)
            LN>>=1
            RN>>=1
        while LM<RM:
            if LM&1:
                idxM.append(LM)
                LM+=1
            if RM&1:
                RM-=1
                idxM.append(RM)
            LM>>=1
            RM>>=1
        v=self.e
        for i in idxN:
            for j in idxM:
                v=self.f(v,self.segment_tree[i][j])
        for i in idxN:
            for j in idxM:
                if v==self.f(v,self.segment_tree[i][j]):
                    break
            else:
                continue
            break
        while i<self.N:
            if self.segment_tree[i<<1][j]==v:
                i<<=1
            else:
                i<<=1
                i|=1
        while j<self.M:
            if self.segment_tree[i][j<<1]==v:
                j<<=1
            else:
                j<<=1
                j|=1
        return i,j

    def __getitem__(self,tpl):
        i,j=tpl
        i+=self.N
        j+=self.M
        return self.segment_tree[i][j]

    def __setitem__(self,tpl,x):
        i,j=tpl
        i+=self.N
        j+=self.M
        self.segment_tree[i][j]=x
        idxN=[i]
        idxM=[j]
        while i>1:
            i>>=1
            idxN.append(i)
        while j>1:
            j>>=1
            idxM.append(j)
        i=idxN[0]
        for j in idxM[1:]:
            self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])
        for i in idxN[1:]:
            for j in idxM:
                self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])

    def __str__(self):
        m=max(len(str(self.segment_tree[i][j])) for i in range(self.N,self.N*2) for j in range(self.M,self.M*2))
        return "\n".join(["["+", ".join(map(lambda s:" "*(m-len(str(s)))+str(s),self.segment_tree[i][self.M:]))+"]" for i in range(self.N,self.N*2)])

class Graph:
    def __init__(self,V,edges=False,graph=False,directed=False,weighted=False,inf=float("inf")):
        self.V=V
        self.directed=directed
        self.weighted=weighted
        self.inf=inf
        if graph:
            self.graph=graph
            self.edges=[]
            for i in range(self.V):
                if self.weighted:
                    for j,d in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j,d))
                else:
                    for j in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j))
        else:
            self.edges=edges
            self.graph=[[] for i in range(self.V)]
            if weighted:
                for i,j,d in self.edges:
                    self.graph[i].append((j,d))
                    if not self.directed:
                        self.graph[j].append((i,d))
            else:
                for i,j in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)

    def SIV_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False):
        seen=[False]*self.V
        finished=[False]*self.V
        if directed_acyclic or cycle_detection or topological_sort:
            dag=True
        if euler_tour:
            et=[]
        if linked_components:
            lc=[]
        if lowlink:
            order=[None]*self.V
            ll=[None]*self.V
            idx=0
        if parents or cycle_detection or lowlink or subtree_size:
            ps=[None]*self.V
        if postorder or topological_sort:
            post=[]
        if preorder:
            pre=[]
        if subtree_size:
            ss=[1]*self.V
        if unweighted_dist or bipartite_graph:
            uwd=[self.inf]*self.V
            uwd[s]=0
        if weighted_dist:
            wd=[self.inf]*self.V
            wd[s]=0
        stack=[(s,0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                x,d=stack.pop()
            else:
                x=stack.pop()
            if not seen[x]:
                seen[x]=True
                stack.append((x,d) if self.weighted else x)
                if euler_tour:
                    et.append(x)
                if linked_components:
                    lc.append(x)
                if lowlink:
                    order[x]=idx
                    ll[x]=idx
                    idx+=1
                if preorder:
                    pre.append(x)
                for y in self.graph[x]:
                    if self.weighted:
                        y,d=y
                    if not seen[y]:
                        stack.append((y,d) if self.weighted else y)
                        if parents or cycle_detection or lowlink or subtree_size:
                            ps[y]=x
                        if unweighted_dist or bipartite_graph:
                            uwd[y]=uwd[x]+1
                        if weighted_dist:
                            wd[y]=wd[x]+d
                    elif not finished[y]:
                        if (directed_acyclic or cycle_detection or topological_sort) and dag:
                            dag=False
                            if cycle_detection:
                                cd=(y,x)
            elif not finished[x]:
                finished[x]=True
                if euler_tour:
                    et.append(~x)
                if lowlink:
                    bl=True
                    for y in self.graph[x]:
                        if self.weighted:
                            y,d=y
                        if ps[x]==y and bl:
                            bl=False
                            continue
                        ll[x]=min(ll[x],order[y])
                    if x!=s:
                        ll[ps[x]]=min(ll[ps[x]],ll[x])
                if postorder or topological_sort:
                    post.append(x)
                if subtree_size:
                    for y in self.graph[x]:
                        if self.weighted:
                            y,d=y
                        if y==ps[x]:
                            continue
                        ss[x]+=ss[y]
        if bipartite_graph:
            bg=[[],[]]
            for tpl in self.edges:
                x,y=tpl[:2] if self.weighted else tpl
                if uwd[x]==self.inf or uwd[y]==self.inf:
                    continue
                if not uwd[x]%2^uwd[y]%2:
                    bg=False
                    break
            else:
                for x in range(self.V):
                    if uwd[x]==self.inf:
                        continue
                    bg[uwd[x]%2].append(x)
        retu=()
        if bipartite_graph:
            retu+=(bg,)
        if cycle_detection:
            if dag:
                cd=[]
            else:
                y,x=cd
                cd=self.Route_Restoration(y,x,ps)
            retu+=(cd,)
        if directed_acyclic:
            retu+=(dag,)
        if euler_tour:
            retu+=(et,)
        if linked_components:
            retu+=(lc,)
        if lowlink:
            retu=(ll,)
        if parents:
            retu+=(ps,)
        if postorder:
            retu+=(post,)
        if preorder:
            retu+=(pre,)
        if subtree_size:
            retu+=(ss,)
        if topological_sort:
            if dag:
                tp_sort=post[::-1]
            else:
                tp_sort=[]
            retu+=(tp_sort,)
        if unweighted_dist:
            retu+=(uwd,)
        if weighted_dist:
            retu+=(wd,)
        if len(retu)==1:
            retu=retu[0]
        return retu

N,r=map(int,readline().split())
r-=1
inf=1<<30
A=list(map(int,readline().split()))
edges=[]
for _ in range(N-1):
    a,b=map(int,readline().split())
    a-=1;b-=1
    edges.append((a,b))
G=Graph(N,edges=edges)
tour,size,depth=G.SIV_DFS(r,preorder=True,subtree_size=True,unweighted_dist=True)
idx=[None]*N
for i in range(N):
    idx[tour[i]]=i
ST=Segment_Tree2(N,N,min,inf,dynamic=True)
for x in range(N):
    ST[idx[x],depth[x]]=A[x]
Q=int(readline())
ans=0
for _ in range(Q):
    p,q=map(int,readline().split())
    x,k=(p+ans)%N,(q+ans)%N
    ans=ST.Fold(idx[x],idx[x]+size[x],depth[x],min(depth[x]+k+1,N))
    print(ans)