当前没有测试数据。

题目描述

Shan is a kind of fish and looks very beautiful in dress.

There is a tree whose root is 1. Every node i in this tree owns a weight , satisfying that if is an ancestor of then $W[x] \le W[y]$.

Shan have several questions, each question can be represented as a pair(x,k), Shan wants to find the biggest node y such that $y - k \le W[lca(x,y)]$

Shan is not happy today, can you help her to answer these questions?

输入格式

First line two integers: $n(\le 10^5)n(≤105) and m(≤105)m(\le 10^5)$ Second line n integers, the ithi_{th}ith​ integer represents $W[i](0 \le W[i]\le 10^6)W[i]$ Next n-1 lines, two integers each line u and v meaning that there an edge between u and v. Next m lines, two integers each line $(1 \le x \le n)x$and $k( -10^6 \le k \le 10^6)k$ representing a question.

输出格式

m lines. One integer each line, ithi_{th}ith​ integer represents the answer to ithi_{th}ith​ question, and output 0 if there is no such node.

样例

样例输入 1

5 5
1 3 4 3 5
1 2
2 3
2 4
1 5
1 1
2 3
3 -3
4 1
5 2

样例输出 1

2
4
0
4
5