Walking on a Tree

You are given an undirected tree with n nodes (a tree with no designated root). Every edge has weight 1. Initially you are located at node m. Then you will receive k instructions. Each instruction contains two integers d and t. For each instruction, you need to walk along the unique shortest path from your current position to node d with at most t steps (if t steps or fewer are enough to reach d, you will reach d, otherwise, you will stop at the node reached after taking exactly t steps). After each instruction, output your current position.

The distance between any two adjacent nodes is 1.

Note: If you cannot reach d within t steps, then you simply move along the path for t steps and remain at that node.

inputFormat

The first line contains three integers n, m and k (the number of nodes in the tree, the starting node, and the number of instructions).

The following n - 1 lines each contain two integers u and v, indicating an edge between nodes u and v.

The next k lines each contain two integers d and t representing an instruction.

It is guaranteed that the given edges form a tree.

outputFormat

For each instruction output one line containing the node at which you end up after following that instruction.

sample

5 1 3
1 2
2 3
3 4
3 5
4 2
5 3
2 1

3
5
3