Playing on Trees

You are playing a game on a tree.

Given a tree with (n) nodes and (Q) queries, each query provides three integers (x, y, z). For each query, find three nodes (u, v, w) such that

[ \operatorname{dis}(u,v) = x, \quad \operatorname{dis}(u,w) = y, \quad \operatorname{dis}(v,w) = z, ]

where (\operatorname{dis}(u,v)) denotes the number of edges in the unique simple path between nodes (u) and (v) (with (\operatorname{dis}(u,u)=0)). It is guaranteed that a solution exists for every query.

inputFormat

The first line contains two integers (n) and (Q).

The next (n-1) lines each contain two integers (u) and (v), indicating an edge between nodes (u) and (v).

Each of the next (Q) lines contains three integers (x, y, z), representing one query.

outputFormat

For each query, output three integers (u, v, w) separated by spaces on a new line, representing a valid triple of nodes that satisfy the conditions.

sample

3 1
1 2
2 3
1 2 1

1 2 3