H. Date
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ruby and Aqua are going to the amusement park!

The amusement park can be represented as a tree with $$$n$$$ nodes. Each node represents a ride with an enjoyment value of $$$a_i$$$ and an opening time of $$$b_i$$$. Ruby and Aqua can visit the rides by moving through the edges of the tree, and the first time they visit ride $$$i$$$, they will gain an enjoyment of $$$a_i$$$. However, the $$$i$$$-th ride is only open once every $$$b_i$$$ days. For example, if a ride has an opening time of $$$3$$$, then it will be open on days $$$3$$$, $$$6$$$, $$$9$$$, $$$\ldots$$$. If a ride is not open, all edges connected to the ride will be closed and no enjoyment can be gained from that ride.

However, Kana wants to interfere with Ruby and Aqua's plans, and she can choose to force any single ride to close. Ruby and Aqua want to figure out the maximum total enjoyment they can gain from visiting the amusement park even if Kana interferes, so they ask you $$$q$$$ queries of two types.

The $$$i$$$-th query contains three integers $$$x_i$$$, $$$y_i$$$, and $$$z_i$$$, asking if they visit the amusement park starting at node $$$x_i$$$ on day $$$y_i$$$ and Kana forcibly closes ride $$$z_i$$$, what is the maximum total enjoyment they can gain from exploring the park?

Input

The first line contains two integers $$$n$$$ ($$$2 \le n \le 10^5$$$) and $$$q$$$ ($$$1 \le q \le 10^5$$$), denoting the size of the amusement park and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), denoting the enjoyment value of each ride.

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^5$$$), denoting the opening time of each ride.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), denoting an edge between ride $$$u$$$ and ride $$$v$$$. It is guaranteed that the given edges form a tree.

Each of the next $$$q$$$ lines contains three integers $$$x$$$ ($$$1 \le x \le n$$$), $$$y$$$ ($$$1 \le y \le 10^6$$$), and $$$z$$$ ($$$1 \le z \le n$$$), asking if Ruby and Aqua start at node $$$x$$$ on day $$$y$$$ and Kana forcibly closes ride $$$z$$$, what is the maximum total enjoyment they can gain from exploring the park.

Output

Output $$$q$$$ lines each containing one integer. The $$$i$$$-th line should contain the answer to the $$$i$$$-th query.

Example
Input
7 6
1 2 3 4 5 6 7
3 1 4 6 3 7 5
1 2
2 3
2 4
2 5
1 6
6 7
1 123 2
2 124 1
7 7 1
7 5 7
4 1998 5
4 6 2
Output
1
5
0
0
7
4
Note

In the first query, rides $$$1$$$ and $$$2$$$ are open and reachable from node $$$1$$$. However, node $$$2$$$ is blocked, so the maximum total enjoyment the two can get is $$$a_1$$$ which is $$$1$$$.

In the second query, rides $$$1$$$, $$$2$$$, and $$$3$$$ are open and reachable from node $$$2$$$. However, node $$$1$$$ is blocked, so the maximum total enjoyment the two can get is $$$a_2 + a_3 $$$ which is $$$5$$$.

Problem Credits: Thomas Liu