Subtree Minimum Query

6000ms

524288K

Description:

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₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) — 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⁶) — 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.

Sample Input:

Sample Output:

2
5

Informação

Provedor Codeforces

Código CF893F