F. Subtree Minimum Query

给定一棵包含 #cf_span[n] 个顶点的有根树。每个顶点上写有一个数字，顶点 #cf_span[i] 上写的数字为 #cf_span[ai]。 记 #cf_span[d(i, j)] 为树中顶点 #cf_span[i] 与 #cf_span[j] 之间的距离（即从 #cf_span[i] 到 #cf_span[j] 的最短路径上的边数）。再记顶点 #cf_span[x] 的 _#cf_span[k]-阻塞子树_ 为满足以下两个条件的所有顶点 #cf_span[y] 的集合： 你被给予 #cf_span[m] 个关于该树的查询。第 #cf_span[i] 个查询由两个数 #cf_span[xi] 和 #cf_span[ki] 表示，该查询的答案是所有属于 #cf_span[xi] 的 #cf_span[ki]-阻塞子树的顶点 #cf_span[j] 中，#cf_span[aj] 的最小值。 请编写一个程序，快速处理这些查询！ *注意：查询是以修改后的方式给出的*。 第一行包含两个整数 #cf_span[n] 和 #cf_span[r] (#cf_span[1 ≤ r ≤ n ≤ 100000]) —— 树中顶点的数量和根的编号。 第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109]) —— 写在各顶点上的数字。 接下来 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y] (#cf_span[1 ≤ x, y ≤ n])，表示顶点 #cf_span[x] 和 #cf_span[y] 之间的一条边。保证这些边构成一棵树。 下一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 106]) —— 需要处理的查询数量。 接下来 #cf_span[m] 行，第 #cf_span[i] 行包含两个数 #cf_span[pi] 和 #cf_span[qi]，可用于还原第 #cf_span[i] 个查询 (#cf_span[1 ≤ pi, qi ≤ n])。 第 #cf_span[i] 个查询的还原方式如下： 设 #cf_span[last] 为前一个查询的答案（若 #cf_span[i = 1]，则 #cf_span[last] = 0）。则 #cf_span[xi = ((pi + last) mod n) + 1]，且 #cf_span[ki = (qi + last) mod n]。 请输出 #cf_span[m] 个整数。第 #cf_span[i] 个整数必须等于第 #cf_span[i] 个查询的答案。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[r] (#cf_span[1 ≤ r ≤ n ≤ 100000]) —— 树中顶点的数量和根的编号。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109]) —— 写在各顶点上的数字。接下来 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y] (#cf_span[1 ≤ x, y ≤ n])，表示顶点 #cf_span[x] 和 #cf_span[y] 之间的一条边。保证这些边构成一棵树。下一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 106]) —— 需要处理的查询数量。接下来 #cf_span[m] 行，第 #cf_span[i] 行包含两个数 #cf_span[pi] 和 #cf_span[qi]，可用于还原第 #cf_span[i] 个查询 (#cf_span[1 ≤ pi, qi ≤ n])。第 #cf_span[i] 个查询的还原方式如下：设 #cf_span[last] 为前一个查询的答案（若 #cf_span[i = 1]，则 #cf_span[last] = 0）。则 #cf_span[xi = ((pi + last) mod n) + 1]，且 #cf_span[ki = (qi + last) mod n]。 ## Output 请输出 #cf_span[m] 个整数。第 #cf_span[i] 个整数必须等于第 #cf_span[i] 个查询的答案。 [samples]

**Definitions** Let $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \{1, 2, \dots, n\} $, and root $ r \in V $. Let $ a_i \in \mathbb{Z}^+ $ denote the value written on vertex $ i $, for $ i \in V $. Let $ d(i, j) $ denote the shortest-path distance (number of edges) between vertices $ i $ and $ j $ in $ T $. For a vertex $ x \in V $ and integer $ k \geq 0 $, the **$ k $-blocked subtree** of $ x $ is the set: $$ S(x, k) = \{ y \in V \mid y \text{ is in the subtree of } x \text{ and } d(x, y) \leq k \} $$ **Constraints** 1. $ 1 \leq r \leq n \leq 10^5 $ 2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in V $ 3. $ 1 \leq m \leq 10^6 $ 4. Queries are given as $ (p_i, q_i) $, and the actual query parameters are: $$ x_i = ((p_i + \text{last}) \bmod n) + 1, \quad k_i = (q_i + \text{last}) \bmod n $$ where $ \text{last} $ is the answer to the previous query (0 for the first query). **Objective** For each query $ i \in \{1, \dots, m\} $, compute: $$ \min \{ a_j \mid j \in S(x_i, k_i) \} $$ and output the result.