{"raw_statement":[{"iden":"statement","content":"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_.\n\nLet'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:\n\n*   _x_ is an ancestor of _y_ (every vertex is an ancestor of itself);\n*   _d_(_x_, _y_) ≤ _k_.\n\nYou 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_.\n\nWrite a program that would process these queries quickly!\n\n**Note that the queries are given in a modified way**."},{"iden":"input","content":"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.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the numbers written on the vertices.\n\nThen _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.\n\nNext line contains one integer _m_ (1 ≤ _m_ ≤ 106) — the number of queries to process.\n\nThen _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_).\n\n_i_\\-th query can be restored as follows:\n\nLet _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_."},{"iden":"output","content":"Print _m_ integers. _i_\\-th of them has to be equal to the answer to _i_\\-th query."},{"iden":"example","content":"Input\n\n5 2\n1 3 2 3 5\n2 3\n5 1\n3 4\n4 1\n2\n1 2\n2 3\n\nOutput\n\n2\n5"}],"translated_statement":[{"iden":"statement","content":"给定一棵包含 #cf_span[n] 个顶点的有根树。每个顶点上写有一个数字，顶点 #cf_span[i] 上写的数字为 #cf_span[ai]。\n\n记 #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] 的集合：\n\n你被给予 #cf_span[m] 个关于该树的查询。第 #cf_span[i] 个查询由两个数 #cf_span[xi] 和 #cf_span[ki] 表示，该查询的答案是所有属于 #cf_span[xi] 的 #cf_span[ki]-阻塞子树的顶点 #cf_span[j] 中，#cf_span[aj] 的最小值。\n\n请编写一个程序，快速处理这些查询！\n\n*注意：查询是以修改后的方式给出的*。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[r] (#cf_span[1 ≤ r ≤ n ≤ 100000]) —— 树中顶点的数量和根的编号。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109]) —— 写在各顶点上的数字。\n\n接下来 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y] (#cf_span[1 ≤ x, y ≤ n])，表示顶点 #cf_span[x] 和 #cf_span[y] 之间的一条边。保证这些边构成一棵树。\n\n下一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 106]) —— 需要处理的查询数量。\n\n接下来 #cf_span[m] 行，第 #cf_span[i] 行包含两个数 #cf_span[pi] 和 #cf_span[qi]，可用于还原第 #cf_span[i] 个查询 (#cf_span[1 ≤ pi, qi ≤ n])。\n\n第 #cf_span[i] 个查询的还原方式如下：\n\n设 #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]。\n\n请输出 #cf_span[m] 个整数。第 #cf_span[i] 个整数必须等于第 #cf_span[i] 个查询的答案。"},{"iden":"input","content":"第一行包含两个整数 #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]。"},{"iden":"output","content":"请输出 #cf_span[m] 个整数。第 #cf_span[i] 个整数必须等于第 #cf_span[i] 个查询的答案。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \\{1, 2, \\dots, n\\} $, and root $ r \\in V $.  \nLet $ a_i \\in \\mathbb{Z}^+ $ denote the value written on vertex $ i $, for $ i \\in V $.  \nLet $ d(i, j) $ denote the shortest-path distance (number of edges) between vertices $ i $ and $ j $ in $ T $.  \n\nFor a vertex $ x \\in V $ and integer $ k \\geq 0 $, the **$ k $-blocked subtree** of $ x $ is the set:  \n$$\nS(x, k) = \\{ y \\in V \\mid y \\text{ is in the subtree of } x \\text{ and } d(x, y) \\leq k \\}\n$$\n\n**Constraints**  \n1. $ 1 \\leq r \\leq n \\leq 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in V $  \n3. $ 1 \\leq m \\leq 10^6 $  \n4. Queries are given as $ (p_i, q_i) $, and the actual query parameters are:  \n   $$\n   x_i = ((p_i + \\text{last}) \\bmod n) + 1, \\quad k_i = (q_i + \\text{last}) \\bmod n\n   $$  \n   where $ \\text{last} $ is the answer to the previous query (0 for the first query).  \n\n**Objective**  \nFor each query $ i \\in \\{1, \\dots, m\\} $, compute:  \n$$\n\\min \\{ a_j \\mid j \\in S(x_i, k_i) \\}\n$$  \nand output the result.","simple_statement":null,"has_page_source":false}