You are given a weighted tree of $n$ vertices rooted at $1$.
There are $q$ queries, each of the form $(u, v)$, find weight of the heaviest edge on the simple path between $u$ and $v$.
### Input
- The first line contain 2 integers $n, q$.
- The next $n - 1$ lines, each line contains 3 integers $u, v, w$, there is an edge of weight $w$ between $u$ and $v$.
- The next $q$ lines, each line contains 2 integers $u, v$, an query.
### Output
- Print $q$ integers, the answers to $q$ queries.
### Constraints
- $1 \le n, q\le 10^5$.
- $1 \le u, v \le n$.
- $1 \le w \le 10^9$.
### Example
Input:
```
7 3
1 2 1
1 3 2
2 4 3
2 5 2
3 6 1
3 7 3
4 5
2 6
2 1
```
Output:
```
3
2
1
```
