Background

:::epigraph Star farming is a great invention of ancient China. :::

Problem Description

Pheonix has arrived in outer space. There are $n$ galaxies, numbered $1, 2, ..., n$. These galaxies are connected by $n-1$ bidirectional wormholes, and every galaxy can be reached from any other through these wormholes.

Each galaxy contains some stars. The number of stars in galaxy $i$ is $s_i$.

Pheonix will make $q$ trips through wormholes between galaxies. During one trip, Pheonix will not visit the same galaxy more than once.

Pheonix knows little about astronomy, but he has sharp mathematical insight. For each trip, he wants to ask Little T the following question:

• Put the star counts of the galaxies passed on the wormhole trip from galaxy $x$ to galaxy $y$ (including the start and end) into a multiset $S$, that is, $S = \{s_i : i \text{ is on the path from } x \text{ to } y\}$.
• Do there exist elements in $S$ whose frequency is strictly greater than $\frac{|S|}{k}$? Here $k$ is an integer specified by Pheonix in each query. If yes, output all such elements.

Please help Little T answer these queries.

Input Format

The first line contains an integer $T \ (1 \le T \le 10^5)$, the number of testdata.

For each testdata, the first line contains two integers $n$ and $q \ (2 \le n \le 10^5, 1 \le q \le 10^5)$, representing the number of galaxies and the number of Pheonix's trips.

The next line contains $n$ integers $s_1, s_2, \dots, s_n \ (1 \le s_i \le n)$, where $s_i$ is the number of stars in galaxy $i$.

The next $n-1$ lines each contain two integers $u$ and $v \ (1 \le u, v \le n, u \ne v)$, indicating a wormhole connecting $u$ and $v$.

The next $q$ lines each contain three integers $x, y, k \ (1 \le x, y \le n, 2 \le k \le n, x \ne y)$, representing the start and end of a trip, and the query parameter.

It is guaranteed that $\sum n, \sum q, \sum k \le 3 \times 10^5$ over all testdata. It is also guaranteed that in each testdata, the wormholes make all galaxies mutually reachable.

Output Format

For each testdata, output $q$ lines. The $i$-th line is the answer to the $i$-th query:

• If there exist elements in $S$ whose frequency is strictly greater than $\frac{|S|}{k}$, output those star counts in increasing order of the star count (not by frequency).
• Otherwise, output a single integer $-1$.

2
6 4
1 2 2 1 2 3
1 2
2 3
2 4
4 5
5 6
3 6 2
1 4 3
1 6 2
1 5 3
7 5
1 2 1 3 2 2 4
1 2
1 3
2 4
2 5
3 6
6 7
4 5 2
4 7 3
5 6 4
3 1 2
7 5 2

2
1
-1
1 2
2
-1
1 2
1
-1

Hint

Explanation for Sample 1

:::align{center} :::

The figure above shows the wormhole connections and star counts for the first testdata.

In the first query, the trip is from galaxy $3$ to galaxy $6$ with parameter $2$. The galaxies on the path are $3 \to 2 \to 4 \to 5 \to 6$, with star counts $S = \{2, 2, 1, 2, 3\}$. The star count that appears strictly more than the threshold $\frac{|S|}{k} = 2.5$ times is $2$.

Translated by ChatGPT 5