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.

### Input

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) \mod n) + 1$, and $k_i = (q_i + last) \mod n$ .

### Output

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