题目描述

一个国家生产各种各样的珠宝，这个国家有 $n$ 个城市，每个城市会售卖价格为 $a_i$ 的珠宝，$n$ 个城市的道路组成了一个树状的结构，国家中最大的交易所在 $1$ 号城市。

你是一个旅行商，计划安排 $q$ 次旅行，每次选择一个城市 $u$ ，走最短的路径前往城市 $v$ ，因为交易所在 $1$ 号城市，所以你每次计划的终点城市 $v$ 一定是城市 $u$ 到 $1$ 号城市的最短路径上的某个城市。

在每次旅行之前，你手上有价值为 $c$ 的珠宝，如果你当前所在的城市售卖的珠宝价格高于你目前持有的珠宝价格，那么你就会把所有的珠宝更换成当前城市的珠宝。现在你想知道，在一次旅行中，会进行多少次更换。

输入格式

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

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

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

接下来 $q$ 行，每行描述一次行程 $u , v , c$ 。

输出格式

对于每次行程输出一行，表示本次行程的更换次数。

样例 #1

样例输入 #1

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

样例输出 #1

2
1
1
0

数据范围

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