Messages on a Tree
Contest: Canada Cup 2016
Difficulty rating: 3300

Alice and Bob are well-known for sending messages to each other. This time you have a rooted tree with Bob standing in the root node and copies of Alice standing in each of the other vertices. The root node has number 0, the rest are numbered 1 through n.

At some moments of time some copies of Alice want to send a message to Bob and receive an answer. We will call this copy the initiator. The process of sending a message contains several steps:

- The initiator sends the message to the person standing in the parent node and begins waiting for the answer.
- When some copy of Alice receives a message from some of her children nodes, she sends the message to the person standing in the parent node and begins waiting for the answer.
- When Bob receives a message from some of his child nodes, he immediately sends the answer to the child node where the message came from.
- When some copy of Alice (except for initiator) receives an answer she is waiting for, she immediately sends it to the child vertex where the message came from.
- When the initiator receives the answer she is waiting for, she doesn't send it to anybody.
- There is a special case: a copy of Alice can't wait for two answers at the same time, so if some copy of Alice receives a message from her child node while she already waits for some answer, she rejects the message and sends a message saying this back to the child node where the message came from. Then the copy of Alice in the child vertex processes this answer as if it was from Bob.
- The process of sending a message to a parent node or to a child node is instant but a receiver (a parent or a child) gets a message after 1 second.

If some copy of Alice receives several messages from child nodes at the same moment while she isn't waiting for an answer, she processes the message from the initiator with the smallest number and rejects all the rest. If some copy of Alice receives messages from children nodes and also receives the answer she is waiting for at the same instant, then Alice first processes the answer, then immediately continue as normal with the incoming messages.

You are given the moments of time when some copy of Alice becomes the initiator and sends a message to Bob. For each message, find the moment of time when the answer (either from Bob or some copy of Alice) will be received by the initiator.

You can assume that if Alice wants to send a message (i.e. become the initiator) while waiting for some answer, she immediately rejects the message and receives an answer from herself in no time.

Input format:
The first line of input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of nodes with Alices and the number of messages.

Second line contains n integers p1, p2, ..., pn (0 ≤ pi < i). The integer pi is the number of the parent node of node i.

The next m lines describe the messages. The i-th of them contains two integers xi and ti (1 ≤ xi ≤ n, 1 ≤ ti ≤ 109) — the number of the vertex of the initiator of the i-th message and the time of the initiation (in seconds). The messages are given in order of increasing initiation time (i.e. ti + 1 ≥ ti holds for 1 ≤ i < m). The pairs (xi, ti) are distinct.

Output format:
Print m integers — the i-th of them is the moment of time when the answer for the i-th message will be received by the initiator.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example the first message is initiated at the moment 6, reaches Bob at the moment 10, and the answer reaches the initiator at the moment 14. The second message reaches vertex 2 at the moment 11. At this moment the copy of Alice in this vertex is still waiting for the answer for the first message, so she rejects the second message. The answer reaches the initiator at the moment 13. The third message is not sent at all, because at the moment 11 Alice in vertex 5 is waiting for the answer for the second message.

In the second example the first message reaches Bob, the second is rejected by Alice in vertex 1. This is because the message with smaller initiator number has the priority.

In the third example the first and the third messages reach Bob, while the second message is rejected by Alice in vertex 3.

Example input:
6 3
0 1 2 3 2 5
4 6
6 9
5 11

Example output:
14 13 11

Example input:
3 2
0 1 1
2 1
3 1

Example output:
5 3

Editorial:
Hint: Sort the queries somehow so that the answer on every query will depend only on previous queries. After that, use heavy-light decomposition to answer the queries quickly.
Solution: First, sort the queries by d[xi] + ti, where d[a] is the depth of the vertex a. It can be easily shown that the answer for every query depends only on the previous ones, so we can proceed them one by one.
Also, after the sort we can assume that any query blocks the path from the initiator to the node that rejects the query in one instant, so we can only care about unblocking times. Suppose some node v unblocks at the moment Tv. Which queries will be rejected by v if they reach it? Obviously, the queries which have v on the path from the initiator to the root and for which ti + d[xi] - d[v] < Tv holds. Let's rewrite this as follows: Tv + d[v] > ti + d[xi]. Now the left part depends only on the blocking node, and the right part depends only on the query. Let's define Bv = Tv + d[v].
Now we have an O(nm) solution: we proceed queries one by one, for each query we find such a node v on the path from xi to the root so that the Bv > ti + d[xi] holds for the node, and it has the maximum depth, and then reassign values of Bv on the path from xi to v.
To make the solution faster, we have to construct the heavy-light decomposition on the tree. Now let's store the values Bv in segment trees on the decomposed paths. To assign on the path we should note that the values Bv form arithmetical progression. To query the deepest node we should store the maximum value of Bv in every node of the segment trees. This solution works in $${\mathcal {O}}(m\log ^{2}(n))$$.