C. Star Farming
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

Each galaxy contains some stars, and the number of stars in the $$$i$$$-th galaxy is $$$s_i$$$.

Pheonix will make $$$q$$$ wormhole trips between galaxies. During a single trip, Pheonix will not visit any galaxy more than once.

Pheonix has limited knowledge of astronomy, but his mathematical observation skills are keen. For each trip, he wants to ask Little T the following questions:

  • Put the numbers of stars of the galaxies visited (including the starting and ending ones) during the wormhole trip from galaxy $$$x$$$ to galaxy $$$y$$$ into a multiset $$$S$$$, i.e., $$$S = \{s_i : i\ \text{is on the path from}\ x \ \text{to}\ y\}$$$.
  • Are there any elements in $$$S$$$ whose frequency of occurrence is strictly greater than $$$\frac{|S|}{k}$$$? Here, $$$k$$$ is an integer specified by Pheonix in each query. If there are, find out what they are.

Please help Little T answer these questions.

Input

The first line contains a single integer $$$T$$$ ($$$ 1 \le T \le 10^5$$$), representing the number of test cases.

The first line of each test case 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 trips Pheonix makes.

The next line contains $$$n$$$ integers $$$s_1$$$, $$$s_2$$$, $$$\ldots$$$, $$$s_n$$$ ($$$1 \le s_i \le n$$$), representing the number of stars each galaxy has respectively.

Each of the following $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$), representing a wormhole channel connecting $$$u$$$ and $$$v$$$.

Each of the next $$$q$$$ lines contains $$$3$$$ integers $$$x$$$, $$$y$$$, and $$$k$$$ ($$$1 \le x, y \le n, 2 \le k \le n, x \ne y$$$), representing the starting and ending galaxies of a trip, and the query parameter.

It is guaranteed that $$$\sum n, \sum q, \sum k \le 3 \times 10^5$$$ over all test cases. It is also guaranteed that the wormhole channels in each test case allow reaching any galaxy from any other galaxy.

Output

For each test case, output $$$q$$$ lines. The $$$i$$$-th line should contain the answer to the $$$i$$$-th query:

  • If there are elements in $$$S$$$ whose frequency is strictly greater than $$$\frac{|S|}{k}$$$, output these star numbers in strictly increasing order of their values (not by their frequencies).
  • Otherwise, output a single integer $$$-1$$$.
Example
Input
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
Output
2
1
-1
1 2
2
-1
1 2
1
-1
Note

The figure above shows the wormhole connections and the number of stars for the 1st test case.

The 1st query asks about the path from galaxy $$$3$$$ to galaxy $$$6$$$, with the parameter $$$2$$$. The visited galaxies are $$$3 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6$$$, and the numbers of stars are $$$S = \{2, 2, 1, 2, 3\}$$$. The star number that satisfies having a frequency strictly greater than the threshold $$$\frac{|S|}{k} = 2.5$$$ is $$$2$$$.