L. Regnaissance
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

redemption

nothingness

rebirth

Why are you crying?

Luvia gives you a tree with $$$n$$$ nodes numbered $$$1 \sim n$$$, and $$$q$$$ queries $$$l,r,x$$$,

you should answer the LCA of nodes numbered $$$l \sim r$$$ when the root of the tree is $$$x$$$.

LCA means the lowerest common ancestor.

Input

The first line, two integers $$$n,q$$$ ($$$1 \le n,q \le 3 \times 10^5$$$).

Each of the next $$$n-1$$$ lines contains two integers $$$x,y$$$ ($$$1 \le x,y \le n$$$), indicating an edge from node $$$x$$$ to node $$$y$$$.

It is guaranteed that the given edges form a tree.

The next $$$q$$$ lines, each contains a query with three integers $$$l,r,x$$$ ($$$1 \le l \le r \le n,1 \le x \le n$$$).

Output

Output $$$q$$$ lines, line $$$i$$$ contains one integer ——the answer of the $$$i$$$-query.

Example
Input
8 6
1 2
1 3
1 7
2 4
3 5
3 6
5 8
5 6 1
1 4 7
6 8 4
1 8 4
4 7 2
5 5 3
Output
3
1
1
4
2
5