F. Top Cluster
time limit per test
4 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Top Cluster is a useful data structure for maintaining data on a tree. Using Top Cluster, we can do range queries efficiently.

Lovely EMmm likes data structure technologies very much. She is learning Top Cluster now, and she is trying to solve a data structure problem. Can you write a program to solve the problem together with EMmm?

In the problem, you will be given a tree with $$$n$$$ vertices, labeled by $$$1, 2, \ldots, n$$$. The value of the $$$i$$$-th vertex is a non-negative integer $$$w_i$$$. All the values are pairwise distinct.

You will then be given $$$q$$$ queries. In the $$$i$$$-th query, you will be given two integers $$$x_i$$$ and $$$k_i$$$ ($$$1 \leq x_i \leq n$$$, $$$0 \leq k_i \leq 10^{15}$$$), and you need to find the value of $$$\mathrm{mex}\left(\left\{w_u \mid \mathrm{dist}(u, x_i) \leq k_i \land 1 \leq u \leq n\right\}\right)$$$.

Here, $$$\mathrm{dist}(u, v)$$$ denotes the length of the shortest path from vertex $$$u$$$ to vertex $$$v$$$. In mathematics, the mex ("minimum excluded value") of a set is the smallest non-negative integer that does not belong to the set.

EMmm is good at solving mex problems. She found that when all the values are pairwise distinct, the problem above is equivalent to finding the smallest non-negative integer that either occurred outside the given range, which means $$$\mathrm{dist}(x_i, u) \gt k_i$$$, or never occurred in the whole tree. However, she can't go any further. Can you help her solve the problem?

Input

The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 5 \cdot 10^5$$$) denoting the number of vertices and the number of queries.

The second line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \leq w_i \leq 10^9$$$) denoting the values of the vertices. It is guaranteed that all the values are pairwise distinct.

Each of the next $$$n - 1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$ and $$$\ell_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$1 \leq \ell_i \leq 10^9$$$) denoting a two-way edge between vertices $$$u_i$$$ and $$$v_i$$$ with length $$$\ell_i$$$. It is guaranteed that the input forms a tree.

Each of the next $$$q$$$ lines contains two integers $$$x_i$$$ and $$$k_i$$$ ($$$1 \leq x_i \leq n$$$, $$$0 \leq k_i \leq 10^{15}$$$) denoting the $$$i$$$-th query.

Output

For each query, print a single line containing an integer: the $$$\mathrm{mex}$$$ value that you found.

Example
Input
5 4
3 9 0 1 2
1 2 10
3 1 4
3 4 3
3 5 2
3 0
1 0
4 6
4 7
Output
1
0
3
4