For a tree with $n$ vertices, let $d(u, v)$ be the number of edges on the simple path from $u$ to $v$. Given $q$ queries of the form $(a, b, c)$, find a vertex $x$ such that $d(a, x) + d(b, x) + d(c, x)$ is minimized.
### Input
- The first line consists of two integers $n, q$.
- The next $n - 1$ lines, each line contains three integers $u, v$, indicating an edge between $u$ and $v$.
- The next $q$ lines, each line contains three integers $a, b, c$, a query.
### Output
- For each query, print the vertex that satisfies the condition.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le a, b, c \le n$.
### Sample test
Input
```
10 7
1 2
1 3
2 4
3 5
2 6
5 7
1 8
4 9
4 10
4 4 2
1 5 8
10 6 9
7 2 5
7 9 2
7 5 4
8 3 4
```
Output:
```
4
1
4
5
2
5
1
```
