# Subtree Minimum Query

## 题目描述

You are given a rooted tree consisting of $n$ vertices. Each vertex has a number written on it; number $a_{i}$ 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_{i}$ and $k_{i}$ , and the answer to this query is the minimum value of $a_{j}$ among such vertices $j$ such that $j$ belongs to $k_{i}$ -blocked subtree of $x_{i}$ . 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_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{9}$ ) — 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^{6}$ ) — the number of queries to process. Then $m$ lines follow, $i$ -th line containing two numbers $p_{i}$ and $q_{i}$ , which can be used to restore $i$ -th query ( $1<=p_{i},q_{i}<=n$ ). $i$ -th query can be restored as follows: Let $last$ be the answer for previous query (or $0$ if $i=1$ ). Then $x_{i}=((p_{i}+last)modn)+1$ , and $k_{i}=(q_{i}+last)modn$ .

### 输出格式

Print $m$ integers. $i$ -th of them has to be equal to the answer to $i$ -th query.

## 输入输出样例

### 输入样例 #1

5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3


### 输出样例 #1

2
5