题目描述

松鼠大作战这个游戏的完整地图，可以看做是一棵$\red{n}$个节点的树，树根为$\red{1，}$节点编号$\red{1}$到$\red{n}$。

每次任务可以抽象为从一个关卡$\red{u}$开始，不断向上打怪升级（只能向上走），一直到关卡$\red{v}$为止。（保 证$\red{v}$是$\red{u}$的祖先）。

在一次任务开始的时候，你会得到一个武器，攻击力为$\red{c，}$然后每一关都有一个武器宝箱，宝箱中的武 器有一个攻击力$\red{a[i]}$。如果箱子中武器的攻击力高于你手中的，你就会选择用这个武器替换手中的武 器。

这样的任务总共有$\red{q}$个。给出每一个关卡中武器的攻击力，以及$\red{q}$次任务的起点与终点，以及任务初始 时的武器攻击力。

现在想知道，对于每个任务，你会更换多少次武器。

输入格式

第一行，两个正整数 $\red{n,q}$。（$\red{2≤}$$\red{n≤}$$\red{100000,1≤}$$\red{q≤}$$\red{100000）}$

第二行，$\red{n }$个正整数 $\red{a[i] }$描述每个关卡上武器的攻击力。

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

接下来 $\red{q }$行，每行描述一次行程 $\red{u,v,c(1<=u,v<=n)}$。

输出格式

输出共$\red{q}$行，对于每次任务输出一行表示更换武器的次数。

样例

输入样例

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

提示

对于 $\red{10\% }$的数据，$\red{2<=n<=100,1<=q<=100}$；

对于 $\red{22.5\% }$的数据，$\red{2<=n<=5000,1<=q<=2000 }$；

对于 $\red{100\% }$的数据，$\red{2<=n<=10^5 }$。