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

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

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

现在想知道，对于每个任务，你会更换多少次武器。这样的任务总共有q个。给出每一个关卡中武器的攻击力，以及q次任务的起点与终点，以及任务初始时的武器攻击力。

1. 第一行，两个正整数n，q。(2 ≤ n ≤ 100000, 1 ≤ q ≤ 100000)

2. 第二行，n个正整数a[i]描述每个关卡上武器的攻击力。

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

4. 接下来q行，每行描述一次行程u, v, c(1 ≤ u, v ≤ n)。

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

- 对于10%的数据，2 ≤ n ≤ 100，1 ≤ q ≤ 100；

- 对于22.5%的数据，2 ≤ n ≤ 5000，1 ≤ q ≤ 2000；

- 对于100%的数据，2 ≤ n ≤ 10^5，1 ≤ q ≤ 10^5，1 ≤ a[i] ≤ 10^5，1 ≤ c ≤ 10^5。