{"raw_statement":[{"iden":"statement","content":"Lech got into a tree consisting of _n_ vertices with a root in vertex number 1. At each vertex _i_ written integer _a__i_. He will not get out until he answers _q_ queries of the form _u_ _v_. Answer for the query is maximal value among all vertices _i_ on path from _u_ to _v_ including _u_ and _v_, where _dist_(_i_, _v_) is number of edges on path from _i_ to _v_. Also guaranteed that vertex _u_ is ancestor of vertex _v_. Leha's tastes are very singular: he believes that vertex is ancestor of itself.\n\nHelp Leha to get out.\n\nThe expression means the bitwise exclusive _OR_ to the numbers _x_ and _y_.\n\nNote that vertex _u_ is ancestor of vertex _v_ if vertex _u_ lies on the path from root to the vertex _v_."},{"iden":"input","content":"First line of input data contains two integers _n_ and _q_ (1 ≤ _n_ ≤ 5·104, 1 ≤ _q_ ≤ 150 000) — number of vertices in the tree and number of queries respectively.\n\nNext line contains _n_ integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ _n_) — numbers on vertices.\n\nEach of next _n_ - 1 lines contains two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_) — description of the edges in tree.\n\nGuaranteed that given graph is a tree.\n\nEach of next _q_ lines contains two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_) — description of queries. Guaranteed that vertex _u_ is ancestor of vertex _v_."},{"iden":"output","content":"Output _q_ lines — answers for a queries."},{"iden":"examples","content":"Input\n\n5 3\n0 3 2 1 4\n1 2\n2 3\n3 4\n3 5\n1 4\n1 5\n2 4\n\nOutput\n\n3\n4\n3\n\nInput\n\n5 4\n1 2 3 4 5\n1 2\n2 3\n3 4\n4 5\n1 5\n2 5\n1 4\n3 3\n\nOutput\n\n5\n5\n4\n3"}],"translated_statement":[{"iden":"statement","content":"Lech 进入了一棵包含 #cf_span[n] 个顶点的树，根节点为第 #cf_span[1] 号顶点。每个顶点 #cf_span[i] 上写有一个整数 #cf_span[ai]。他必须回答 #cf_span[q] 个形如 #cf_span[u] #cf_span[v] 的查询后才能离开。每个查询的答案是路径从 #cf_span[u] 到 #cf_span[v]（包含 #cf_span[u] 和 #cf_span[v]）上所有顶点 #cf_span[i] 中，表达式 #cf_span[ai ⊕ dist(i, v)] 的最大值，其中 #cf_span[dist(i, v)] 表示从 #cf_span[i] 到 #cf_span[v] 的路径上的边数。题目保证顶点 #cf_span[u] 是顶点 #cf_span[v] 的祖先。Leha 的品味非常独特：他认为一个顶点是它自身的祖先。\n\n表达式 #cf_span[x ⊕ y] 表示数字 #cf_span[x] 和 #cf_span[y] 的按位异或。\n\n注意，顶点 #cf_span[u] 是顶点 #cf_span[v] 的祖先，当且仅当 #cf_span[u] 位于从根到 #cf_span[v] 的路径上。\n\n输入数据的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 5·104]，#cf_span[1 ≤ q ≤ 150 000]），分别表示树中顶点数和查询数。\n\n下一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ n]），表示每个顶点上的数值。\n\n接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]），描述树中的一条边。\n\n保证给定图是一棵树。\n\n接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]），描述一个查询。保证顶点 #cf_span[u] 是顶点 #cf_span[v] 的祖先。\n\n请输出 #cf_span[q] 行，每行为对应查询的答案。\n\n"},{"iden":"input","content":"输入数据的第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 5·104]，#cf_span[1 ≤ q ≤ 150 000]），分别表示树中顶点数和查询数。下一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ n]），表示每个顶点上的数值。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]），描述树中的一条边。保证给定图是一棵树。接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]），描述一个查询。保证顶点 #cf_span[u] 是顶点 #cf_span[v] 的祖先。"},{"iden":"output","content":"请输出 #cf_span[q] 行，每行为对应查询的答案。"},{"iden":"examples","content":"输入\n5 3\n0 3 2 1 4\n1 2\n2 3\n3 4\n3 5\n1 4\n1 5\n2 4\n输出\n3\n4\n3\n\n输入\n5 4\n1 2 3 4 5\n1 2\n2 3\n3 4\n4 5\n1 5\n2 5\n1 4\n3 3\n输出\n5\n5\n4\n3"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the number of vertices and queries, respectively.  \nLet $ T = (V, E) $ be a rooted tree with vertex set $ V = \\{1, 2, \\dots, n\\} $ and root at vertex $ 1 $.  \nLet $ a: V \\to \\mathbb{Z} $ be a function assigning to each vertex $ i $ a value $ a_i \\in [0, n] $.  \nFor any two vertices $ u, v \\in V $, let $ P(u, v) $ denote the unique simple path from $ u $ to $ v $ in $ T $.  \nGiven that $ u $ is an ancestor of $ v $, $ P(u, v) $ is the path from $ u $ down to $ v $ along the tree.\n\n**Constraints**  \n1. $ 1 \\le n \\le 5 \\cdot 10^4 $  \n2. $ 1 \\le q \\le 150\\,000 $  \n3. $ 0 \\le a_i \\le n $ for all $ i \\in V $  \n4. The input graph is a tree with root at vertex $ 1 $.  \n5. For each query $ (u, v) $, $ u $ is an ancestor of $ v $ (including $ u = v $).\n\n**Objective**  \nFor each query $ (u, v) $, compute:  \n$$\n\\max_{i \\in P(u, v)} a_i\n$$  \nThat is, the maximum value among all vertex weights on the path from $ u $ to $ v $, inclusive.","simple_statement":null,"has_page_source":false}