Tavas lives in Tavaspolis. Tavaspolis has $*n*$ cities numbered from $1$ to $*n*$ connected by $*n* - 1$ bidirectional roads. There exists a path between any two cities. Also each road has a length.

Tavas' favorite strings are binary strings (they contain only 0 and 1). For any binary string like $*s* = *s*_{1}*s*_{2}... *s*_{*k*}$, $*T*(*s*)$ is its $*Goodness*$. $*T*(*s*)$ can be calculated as follows:

Consider there are exactly $*m*$ blocks of $1$s in this string (a block of $1$s in $*s*$ is a maximal consecutive substring of $*s*$ that only contains $1$) with lengths $*x*_{1}, *x*_{2}, ..., *x*_{*m*}$.

Define where $*f*$ is a given sequence (if $*m* = 0$, then $*T*(*s*) = 0$).

Tavas loves queries. He asks you to answer $*q*$ queries. In each query he gives you numbers $*v*, *u*, *l*$ and you should print following number:

Consider the roads on the path from city $*v*$ to city $*u*$: $*e*_{1}, *e*_{2}, ..., *e*_{*x*}$.

Build the binary string $*b*$ of length $*x*$ such that: $*b*_{*i*} = 1$ if and only if $*l* ≤ *w*(*e*_{*i*})$ where $*w*(*e*)$ is the length of road $*e*$.

You should print $*T*(*b*)$ for this query.

Input

The first line of input contains integers $*n*$ and $*q*$ ($2 ≤ *n* ≤ 10^{5}$ and $1 ≤ *q* ≤ 10^{5}$).

The next line contains $*n* - 1$ space separated integers $*f*_{1}, *f*_{2}, ..., *f*_{*n* - 1}$ ($|*f*_{*i*}| ≤ 1000$).

The next $*n* - 1$ lines contain the details of the roads. Each line contains integers $*v*, *u*$ and $*w*$ and it means that there's a road between cities $*v*$ and $*u*$ of length $*w*$ ($1 ≤ *v*, *u* ≤ *n*$ and $1 ≤ *w* ≤ 10^{9}$).

The next $*q*$ lines contain the details of the queries. Each line contains integers $*v*, *u*, *l*$ ($1 ≤ *v*, *u* ≤ *n*$, $*v* ≠ *u*$ and $1 ≤ *l* ≤ 10^{9}$).

Output

Print the answer of each query in a single line.