CF893F.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.

给你一棵包含 $n$ 个顶点的有根树。每个顶点上写有一个数字；顶点 $i$ 上写的数字为 $a_i$。

记 $d(i,\,j)$ 为树中顶点 $i$ 与 $j$ 之间的距离（即从 $i$ 到 $j$ 的最短路径所含的边数）。再定义顶点 $x$ 的 $k$-阻塞子树（$k$-blocked subtree）为满足以下两个条件的所有顶点 $y$ 构成的集合：

• $x$ 是 $y$ 的祖先（每个顶点都是自身的祖先）；
• $d(x,\,y) \leq k$。

你将收到关于该树的 $m$ 个查询。第 $i$ 个查询由两个数 $x_i$ 和 $k_i$ 表示，其答案为：在 $x_i$ 的 $k_i$-阻塞子树中所有顶点 $j$ 对应的 $a_j$ 值中的最小值。

请编写一个能快速处理这些查询的程序！

注意：这些查询是以一种修改后的方式给出的。

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 ≤ 109) — 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 ≤ 106) — 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.

第一行包含两个整数 $n$ 和 $r$（$1 \le r \le n \le 100000$）—— 分别表示树中顶点的数量和根节点的编号。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$1 \le a_i \le 10^9$）—— 表示写在各顶点上的数字。

接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x,\,y \le n$），表示顶点 $x$ 与 $y$ 之间存在一条边。保证这些边构成一棵树。

下一行包含一个整数 $m$（$1 \le m \le 10^6$）—— 表示需要处理的查询数量。

随后 $m$ 行，第 $i$ 行包含两个数 $p_i$ 和 $q_i$（$1 \le p_i,\,q_i \le n$），用于还原第 $i$ 个查询。

第 $i$ 个查询可按如下方式还原：

设 $last$ 为上一个查询的答案（若 $i = 1$，则 $last = 0$）。则 $x_i = ((p_i + last)\bmod n) + 1$，且 $k_i = (q_i + last)\bmod n$。

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

输出 $m$ 个整数。其中第 $i$ 个整数必须等于第 $i$ 个查询的答案。