You are given a tree of n vertices.
You have a robot. You can place it at a vertex u on the tree and order it to move to v using the simple path between 2 vertices.
Moving from one vertex to another costs 1 energy. When the robot runs out of energy, it stops.
There are q queries, each of the form (u,v,w), the robot starts at u and moves to v with w energy initially. Where will it stop?
### Input
- The first line contain 2 integers n,q.
- The next n−1 lines, each line contains 2 integers u,v, there is an edge between u and v.
- The next q lines, each line contains 3 integers u,v,w, an query.
### Output
- Print q integers, the answers to q queries.
### Constraints
- 1≤n,q≤105.
- 1≤u,v,w≤n.
### Example
Input:
73121324253637141562653
Output:
212
