Top Cluster

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(\{w_u \mid \mathrm{dist}(u, x_i) \leq k_i \land 1 \leq u \leq n\}\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) > k_i$, or never occurred in the whole tree. However, she can't go any further. Can you help her solve the problem?

The first line of the input contains two integers $n$ and $q$ ($1 \leq n, q \leq 5 \cdot 10^5$), 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$), the values of the vertices. 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$), describing a two-way edge between vertices $u_i$ and $v_i$ with length $\ell_i$. 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}$), describing the $i$-th query.

For each query, print a single line containing the mex value you found.