M. Dragons
time limit per test
2.5 s
memory limit per test
256 MB
input
standard input
output
standard output

You are playing a game in which you must defend your village from a dragon.

The village can be represented as a tree (a connected acyclic graph) with $$$N$$$ nodes, indexed form $$$1$$$ to $$$N$$$, each node representing fortifications of varying heights. The height of fortification $$$i$$$ is denoted as $$$h_i$$$.

The dragon has a power level of $$$P$$$ and starts flying at the base of fortification $$$u$$$ (i. e. its initial height is $$$0$$$). Its goal is to attack fortification $$$v$$$. It flies along the path from $$$u$$$ to $$$v$$$ and when it encounters a fortification $$$x$$$ with a height $$$h_x$$$ greater than or equal to its current height, it loses $$$h_x$$$ points from its power and continues flying at a height of $$$h_x$$$.

Unfortunately, there's a bug in the game: if the dragon's current power $$$P_{crt}$$$ becomes less than $$$0$$$, it immediately becomes $$$-P_{crt}$$$. You have the ability to shuffle the fortifications along the path from $$$u$$$ to $$$v$$$. Your objective is to find an arrangement such that the dragon's power is reduced to $$$0$$$ when it reaches fortification $$$v$$$, preventing the dragon from attacking it.

Being given $$$Q$$$ scenarios $$$(u, v, P)$$$, you should find if it's possible to shuffle the fortifications along the path from $$$u$$$ from $$$v$$$ so the dragon won't attack the tower $$$v$$$.

Input

The first line contains one integer $$$N$$$ ($$$2 \leq N \leq 10^4)$$$, the number of nodes. The second line contains $$$N$$$ integers $$$h_1$$$, $$$h_2$$$, $$$\dots$$$, $$$h_N \ (1 \leq h_i \leq 10^3)$$$.

Each of the following $$$N - 1$$$ lines contains two integers $$$u$$$ and $$$v \ (1 \leq u, v \leq N)$$$, meaning that there is an edge between $$$u$$$ and $$$v$$$.

The next line contains one integer $$$Q$$$ ($$$1 \leq Q \leq 10^4)$$$, the number of scenarios. Each of the next $$$Q$$$ lines contains three integers $$$u$$$, $$$v \ (1 \leq u, v \leq N)$$$ and $$$P \ (1 \leq P \leq 10^3)$$$ describing a scenario.

Output

For each scenario, output $$$"$$$YES$$$"$$$ if it's possible to shuffle the fortifications so the dragon won't attack, or $$$"$$$NO$$$"$$$ otherwise.

Example
Input
9
1 2 3 4 5 6 7 8 9
1 2
1 3
1 4
2 5
3 6
3 7
4 8
6 9
3
5 7 13
5 7 1
9 8 12
Output
YES
NO
YES