CF725G.Messages on a Tree

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.

爱丽丝和鲍勃以互相发送消息而闻名。这一次，你有一棵有根树，鲍勃站在根节点上，其余每个顶点上都站着一个爱丽丝的副本。根节点编号为 0，其余节点编号为 1 到 $ n $。

在某些时刻，某些爱丽丝的副本希望向鲍勃发送一条消息并接收回复。我们将该副本称为发起者（initiator）。消息发送过程包含以下几个步骤：

• 发起者将消息发送给其父节点上的人，并开始等待回复。
• 当某个爱丽丝副本从她的某个子节点收到消息时，她将该消息转发给其父节点上的人，并开始等待回复。
• 当鲍勃从他的某个子节点收到消息时，他立即向该消息来源的子节点发送回复。
• 当某个爱丽丝副本（发起者除外）收到她正在等待的回复时，她立即将该回复发送至该消息最初来源的子节点。
• 当发起者收到她正在等待的回复时，她不再将该回复转发给任何人。
• 存在一个特殊情况：一个爱丽丝副本无法同时等待两个回复；因此，若某个爱丽丝副本在已处于等待某个回复状态时，又从她的某个子节点收到了新消息，则她拒绝该新消息，并向该子节点发送一条表示“拒绝”的消息。此时，位于该子节点上的爱丽丝副本将该“拒绝”消息视为来自鲍勃的回复进行处理。
• 向父节点或子节点发送消息的过程是瞬时的，但接收方（父节点或子节点）会在 1 秒后才实际收到该消息。

如果某个爱丽丝副本在未等待任何回复的状态下，于同一时刻从多个子节点收到了多条消息，则她仅处理其中发起者编号最小的那条消息，其余消息全部拒绝。如果某个爱丽丝副本在同一时刻既收到了来自子节点的若干消息，又收到了她正在等待的回复，则她优先处理该回复，然后立即按常规流程继续处理那些新到达的消息。

你将获得若干时刻，对应某些爱丽丝副本成为发起者并向鲍勃发送消息的时间点。对每条消息，请计算该发起者收到回复（该回复可能来自鲍勃，也可能来自某位爱丽丝副本）的时刻。

你可以假设：若某位爱丽丝副本在正等待某个回复期间又想发送新消息（即成为新的发起者），则她会立即拒绝该新消息，并在零时间内收到一条来自她自己的回复。

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 _p_1, _p_2, ..., p__n (0 ≤ p__i < i). The integer p__i 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 x__i and t__i (1 ≤ x__i ≤ n, 1 ≤ t__i ≤ 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. t__i + 1 ≥ t__i holds for 1 ≤ i < m). The pairs (x__i, t__i) are distinct.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 200\,000$）—— 分别表示拥有 Alice 的节点数量和消息数量。

第二行包含 $n$ 个整数 $p_1,\,p_2,\,\dots,\,p_n$（$0 \leq p_i < i$）。整数 $p_i$ 表示节点 $i$ 的父节点编号。

接下来的 $m$ 行描述各条消息。其中第 $i$ 行包含两个整数 $x_i$ 和 $t_i$（$1 \leq x_i \leq n$，$1 \leq t_i \leq 10^9$）—— 分别表示第 $i$ 条消息发起者的顶点编号及发起时间（单位：秒）。消息按发起时间递增顺序给出（即对所有 $1 \leq i < m$，满足 $t_{i+1} \geq t_i$）。所有二元组 $(x_i,\,t_i)$ 互不相同。

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.

输出 m 个整数——其中第 i 个整数表示第 i 条消息的答案被发起者接收到的时刻。

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.

在第一个例子中，第一条消息于时刻 6 发起，在时刻 10 到达 Bob，其回复于时刻 14 到达发起者。第二条消息于时刻 11 到达顶点 2；此时该顶点处的 Alice 副本仍在等待第一条消息的回复，因此她拒绝了第二条消息；该消息的回复于时刻 13 到达发起者。第三条消息根本未被发送，因为在时刻 11，顶点 5 处的 Alice 正在等待第二条消息的回复。

在第二个例子中，第一条消息到达 Bob，第二条消息被顶点 1 处的 Alice 拒绝。这是因为编号更小的发起者具有更高优先级。

在第三个例子中，第一条和第三条消息均到达 Bob，而第二条消息被顶点 3 处的 Alice 拒绝。