G. Gifting Problems
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You live in a tree-shaped country with $$$n$$$ cities, and you conveniently live in city $$$1$$$. It's almost Christmas, so you want to send a gift to your friends. Luckily, you can use the famous post service called IMEmail. It's so quick that it only takes one day to move packages between two neighboring cities (wow! What a relief!). As always, there are some caveats when it comes to this: once a package travels through a city, it can't take a route that passes through that city again. In other words, there can't be a cycle in the path a package takes.

This year, you decided to gift all your friends headphones! You just finished buying the headphones, but now realized that they didn't come with a charging cable. Your friends will only be happy if they receive both the headphones and the charging cable exactly on Christmas day. Now, you decide to call many manufacturers to see how soon they can start distributing the cables across the country.

On the $$$i^{th}$$$ query, you'll send the headphones $$$x$$$ days before Christmas. You also find out that there's a manufacturer located in city $$$u$$$ that will send out the chargers $$$y$$$ days before Christmas. Given these various parameters, for each query, you want to know how many friends will be happy on Christmas Day.

Input

The first line contains two integers $$$n$$$, $$$q$$$, $$$(2 \leq n \leq 2 \times 10^5)$$$, $$$(1 \leq q \leq 2 \times 10^5)$$$ — the total number of cities and the number of queries, respectively.

The next line contains $$$n$$$ integers $$$f_1, f_2, \cdots, f_n\,(0 \leq f_i \leq 10^9)$$$ — the number of friends located in city $$$i$$$.

The following $$$n - 1$$$ lines each contain a pair of integers $$$u$$$, $$$v$$$, $$$(1\leq u, v\leq n,\, u \neq v)$$$ — indicating that cities $$$u$$$ and $$$v$$$ are connected. Of course, all the cities are somehow connected.

The next $$$q$$$ lines each contain three integers $$$u, x, y\, (2\leq u \leq n,\, 0 \leq x, y \leq n - 1)$$$ — indicating that there's a manufacturer located in city $$$u$$$ that will send the packages $$$y$$$ days before Christmas, while you send out the packages $$$x$$$ days before Christmas.

Output

For each query, print out the number of friends that will be happy on Christmas Day.

Example
Input
7 3
3 8 1 9 2 0 3
1 2
2 3
1 4
4 5
2 6
1 7
6 1 1
5 2 0
3 1 3
Output
8
2
12