RCPC Simulare 2023 day 2 | M. Dragons

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

stdin

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

stdout

YES
NO
YES