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
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.
## Output
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.
[samples]
## 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.
Alice 和 Bob 以互相发送消息而闻名。这次你有一棵有根树，Bob 位于根节点，其余每个顶点上都有一个 Alice 的副本。根节点编号为 #cf_span[0]，其余节点编号为 #cf_span[1] 到 #cf_span[n]。
在某些时刻，某些 Alice 的副本希望向 Bob 发送消息并接收回复。我们将这个副本称为 _initiator_。发送消息的过程包含若干步骤：
如果某个 Alice 的副本在同一时刻从多个子节点收到多条消息，而她此时并未等待回复，则她仅处理来自 _initiator_ 编号最小的消息，拒绝其余所有消息。如果某个 Alice 的副本在同一时刻从子节点收到消息，同时又收到她正在等待的回复，则她先处理回复，然后立即继续处理新到达的消息。
你将获得某些 Alice 的副本成为发起者并发送消息给 Bob 的时刻。对于每条消息，求出其发起者收到回复（来自 Bob 或某个 Alice 副本）的时刻。
你可以假设：如果 Alice 在等待某条回复时试图发送消息（即成为发起者），她会立即拒绝该消息，并在瞬时从自己那里收到回复。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 200 000]) —— 拥有 Alice 副本的节点数和消息数。
第二行包含 #cf_span[n] 个整数 #cf_span[p1, p2, ..., pn] (#cf_span[0 ≤ pi < i])。整数 #cf_span[pi] 表示节点 #cf_span[i] 的父节点编号。
接下来的 #cf_span[m] 行描述消息。第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[ti] (#cf_span[1 ≤ xi ≤ n], #cf_span[1 ≤ ti ≤ 109]) —— 第 #cf_span[i] 条消息的发起者所在顶点编号和发起时刻（秒）。消息按发起时间递增顺序给出（即对 #cf_span[1 ≤ i < m]，有 #cf_span[ti + 1 ≥ ti]）。所有 #cf_span[(xi, ti)] 对互不相同。
请输出 #cf_span[m] 个整数 —— 第 #cf_span[i] 个整数表示第 #cf_span[i] 条消息的发起者收到回复的时刻。
在第一个例子中，第一条消息在时刻 #cf_span[6] 发起，于时刻 #cf_span[10] 到达 Bob，回复在时刻 #cf_span[14] 到达发起者。第二条消息在时刻 #cf_span[11] 到达顶点 #cf_span[2]。此时该顶点的 Alice 副本仍在等待第一条消息的回复，因此她拒绝了第二条消息。回复在时刻 #cf_span[13] 到达发起者。第三条消息根本没有发送，因为在时刻 #cf_span[11]，顶点 #cf_span[5] 的 Alice 正在等待第二条消息的回复。
在第二个例子中，第一条消息到达 Bob，第二条消息被顶点 #cf_span[1] 的 Alice 拒绝。这是因为发起者编号较小的消息具有优先级。
在第三个例子中，第一条和第三条消息到达 Bob，而第二条消息被顶点 #cf_span[3] 的 Alice 拒绝。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 200 000]) —— 拥有 Alice 副本的节点数和消息数。第二行包含 #cf_span[n] 个整数 #cf_span[p1, p2, ..., pn] (#cf_span[0 ≤ pi < i])。整数 #cf_span[pi] 表示节点 #cf_span[i] 的父节点编号。接下来的 #cf_span[m] 行描述消息。第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[ti] (#cf_span[1 ≤ xi ≤ n], #cf_span[1 ≤ ti ≤ 109]) —— 第 #cf_span[i] 条消息的发起者所在顶点编号和发起时刻（秒）。消息按发起时间递增顺序给出（即对 #cf_span[1 ≤ i < m]，有 #cf_span[ti + 1 ≥ ti]）。所有 #cf_span[(xi, ti)] 对互不相同。
## Output
请输出 #cf_span[m] 个整数 —— 第 #cf_span[i] 个整数表示第 #cf_span[i] 条消息的发起者收到回复的时刻。
[samples]
## Note
在第一个例子中，第一条消息在时刻 #cf_span[6] 发起，于时刻 #cf_span[10] 到达 Bob，回复在时刻 #cf_span[14] 到达发起者。第二条消息在时刻 #cf_span[11] 到达顶点 #cf_span[2]。此时该顶点的 Alice 副本仍在等待第一条消息的回复，因此她拒绝了第二条消息。回复在时刻 #cf_span[13] 到达发起者。第三条消息根本没有发送，因为在时刻 #cf_span[11]，顶点 #cf_span[5] 的 Alice 正在等待第二条消息的回复。在第二个例子中，第一条消息到达 Bob，第二条消息被顶点 #cf_span[1] 的 Alice 拒绝。这是因为发起者编号较小的消息具有优先级。在第三个例子中，第一条和第三条消息到达 Bob，而第二条消息被顶点 #cf_span[3] 的 Alice 拒绝。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ be the number of nodes and messages, respectively.
Let $ T = \{(x_i, t_i) \mid i \in \{1, \dots, m\}\} $ be the sequence of messages, where $ x_i \in \{1, \dots, n\} $ is the initiator node and $ t_i \in \mathbb{Z}^+ $ is the initiation time, with $ t_{i+1} \geq t_i $.
Let $ P = (p_1, \dots, p_n) $ be the parent array, where $ p_i \in \{0, \dots, i-1\} $ is the parent of node $ i $, and node $ 0 $ is the root (Bob).
For each node $ v \in \{0, 1, \dots, n\} $, let $ \text{path}(v) = (v = v_0, v_1, \dots, v_k = 0) $ be the unique path from $ v $ to the root, where $ v_{j+1} = p_{v_j} $.
Let $ d(v) = |\text{path}(v)| - 1 $ be the depth of node $ v $ (number of edges to root).
**Constraints**
1. $ 1 \leq n, m \leq 200{,}000 $
2. $ 1 \leq t_i \leq 10^9 $, $ t_{i+1} \geq t_i $
3. $ p_i < i $ for all $ i \in \{1, \dots, n\} $
4. All pairs $ (x_i, t_i) $ are distinct.
**Objective**
For each message $ i $, compute $ a_i \in \mathbb{Z}^+ $, the time when the answer is received by initiator $ x_i $, under the following rules:
- A message initiated at $ (x_i, t_i) $ propagates upward along $ \text{path}(x_i) $, taking 1 second per edge: it arrives at node $ v_j \in \text{path}(x_i) $ at time $ t_i + j $.
- At each non-root node $ v $, if multiple messages arrive simultaneously, only the one from the initiator with smallest node number is processed; others are rejected.
- If a node $ v $ is already processing a message (waiting for an answer) when another arrives, the new message is rejected.
- When a message reaches Bob (node 0), he immediately replies; the reply propagates downward along the same path, taking 1 second per edge.
- If an initiator attempts to send a message while waiting for an answer, it is immediately rejected and answered in 0 time (i.e., $ a_i = t_i $).
- The answer to message $ i $ is received at time $ a_i = t_i + 2 \cdot d(x_i) $, **if** it is not rejected en route.
- A message $ i $ is **rejected** at node $ v $ if at time $ t_i + j $ (where $ j $ is the distance from $ x_i $ to $ v $), node $ v $ is already processing another message $ k $ with $ k < i $, or if a message $ k $ with $ k < i $ is being processed along the same path and has not yet completed.
**Output**
For each $ i \in \{1, \dots, m\} $, output $ a_i $, the time the answer is received by initiator $ x_i $, or $ t_i $ if rejected immediately.