You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

有一个树状的城市网络（即 $n$ 个城市由 $n-1$ 条道路连接的连通图），首都为 $1$ 号城市，每个城市售卖价值为 $a_i$ 的珠宝。

你是一个珠宝商，现在安排有 $q$ 次行程，每次行程为从 $u$ 号城市前往 $v$ 号城市（走最短路径），保证 $v$ 在 $u$ 前往首都的最短路径上。

在每次行程开始时，你手上有价值为 $c$ 的珠宝（每次行程可能不同），并且每经过一个城市时（包括 $u$ 和 $v$），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。

现在你想要对每一次行程，求出会进行多少次购买事件。

Format

Input

第一行，两个正整数 $n , q$。

第二行，$n$ 个正整数 $a_i$ 描述每个城市售卖的珠宝的价值。

接下来 $n-1$ 行，每行描述一条道路 $x , y$ ($1 \leq x , y \leq n$)，表示有一条连接 $x$ 和 $y$ 的道路。

接下来 $q$ 行，每行描述一次行程 $u , v , c$ ($1 \leq u , v \leq n$)。

Output

对于每次行程输出一行，为所购买次数。

Samples

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

2
1
1
0

Limitation

对于 $100 \%$ 的数据，保证 $2 \leq n \leq 10^5 , 1 \leq q \leq 10^5$ , $1 \leq a_i \leq 10^5$ , $1 \leq c \leq 10^5$。