You are given a weighted tree of $N$ nodes that is rooted at node $1$. The nodes represent the cities in your country. Also, the edges between the nodes $u$ and $v$ represent the fuel that will be utilized while traveling from node $u$ to $v$ or vice versa. Any cars consume the same fuel while moving from node $u$ to $v$ (that is equal to the edge weight between $u$ and $v$). Cars can only move towards the root.   

Your task is to answer $Q$ queries of the following type:

In each query, you are provided with two values $u$ and $f$, that denotes that you are currently at node $u$ and your car has $f$ amount of fuel in it initially. You will move from city $p$ to city $q$ only if $q$ is the parent of $p$ and the edge weight between $p$ and $q$ is not more than the fuel left in the car. While moving from node $p$ to node $q$, the fuel in the car decrease by the amount equal to the edge weight between $p$ and $q$. You'll stop whenever you either reach node $1$ or cannot move any further up due to the restriction described above. Also, you cannot pass through a node that has a car parked in it. After you reach your destination, your car will be parked at that node and will affect the subsequent queries. For each query, you are required to print the node where the car is parked. 

Note: Assume that no car is parked initially (before query 1).

Input format

• First line: Two space-separated integers $N$ and $Q$ denoting the number of nodes in the tree and the number of queries ($1 \le N, Q \le 10^5$)
• Next $N - 1$ lines: Three space-separated integers $u, v,$ and $w$ representing a road from city $u$ to city $v$ with a weight of $w$ ($1 \le u, v \le N,$ and $1 \le w \le 10^9$)
• Each of the next $Q$ lines: Two space-separated integers $u$ and $f$ denoting the node where you are standing currently and the amount of fuel that your car contain initially ($1 \le u \le N$ and $1 \le f \le 10^{15}$)

Output format

For each query, print the node where the car is parked on a new line.