Alice 和 Bob 因互相发送消息而闻名。这次你有一个有根树,鲍勃站在根节点,爱丽丝的副本站在其他每个顶点。根节点编号为 0,其余节点编号为 1 到 n。
在某些时刻,Alice 的某些副本想要向 Bob 发送消息并接收答复。我们将此副本称为发起者。发送消息的过程包含几个步骤:
- 发起者将消息发送给站在父节点中的人并开始等待答复。
- 当 Alice 的某个副本从她的一些子节点接收到消息时,她将该消息发送给站在父节点中的人并开始等待答案。
- 当 Bob 从他的一些子节点收到消息时,他立即将答案发送到消息来源的子节点。
- 当 Alice 的某个副本(发起者除外)收到她正在等待的答案时,她立即将其发送到消息来源的子顶点。
- 当发起者收到她正在等待的答案时,她不会将其发送给任何人。
- 有一种特殊情况:Alice 的副本不能同时等待两个答案,因此,如果 Alice 的某个副本在她已经等待某个答案时收到来自她的子节点的消息,她会拒绝该消息并将一条消息发送回消息来源的子节点。然后,子顶点中的 Alice 副本会处理这个答案,就像它来自 Bob 一样。
- 向父节点或子节点发送消息的过程是即时的,但接收者(父节点或子节点)会在 1 秒后收到消息。
如果 Alice 的某个副本在没有等待答案的情况下同时收到来自子节点的多条消息,她会处理来自编号最小的发起者的消息,并拒绝其余所有消息。如果 Alice 的某个副本从子节点接收到消息,同时也收到了她正在等待的答案,那么 Alice 首先处理答案,然后立即像平常一样继续处理传入消息。
当 Alice 的某个副本成为发起者并向 Bob 发送消息时,您会遇到这样的时刻。对于每条消息,找到发起者收到答案(来自 Bob 或 Alice 的某个副本)的时刻。
您可以假设,如果 Alice 在等待答复时想要发送消息(即成为发起者),她会立即拒绝该消息并立即收到自己的答复。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 200 000) — 具有 Alice 的节点数量和消息数量。
第二行包含 n 个整数 p1, p2, ..., pn (0 ≤ pi < i)。整数pi是节点i的父节点的编号。
接下来的 m 行描述消息。其中第 i 个包含两个整数 xi 和 ti (1 ≤ xi ≤ n, 1 ≤ ti ≤ 109) - 第 i 条消息的发起者的顶点编号和发起时间(以秒为单位)。消息按照启动时间递增的顺序给出(即 ti + 1 ≥ ti 满足 1 ≤ i < m)。 (xi, ti) 对是不同的。
输出
打印 m 个整数 — 其中第 i 个是发起者收到第 i 条消息的答案的时刻。
示例
输入 #1
6 3 0 1 2 3 2 5 4 6 6 9 5 11
输出 #1
14 13 11
输入 #2
3 2 0 1 1 2 1 3 1
输出 #2
5 3
输入 #3
8 3 0 1 1 2 3 3 4 5 6 1 8 2 4 5
输出 #3
7 6 11
注意
在第一个示例中,第一条消息在时刻 6 发起,在时刻 10 到达 Bob,答案在时刻 14 到达发起者。第二条消息在时刻 11 到达顶点 2。此时,该顶点中的 Alice 副本仍在等待第一条消息的答案,因此她拒绝第二条消息。答案在时刻 13 到达发起者。第三条消息根本没有发送,因为此时顶点 5 中的 11 Alice 正在等待第二条消息的答案。
在第二个示例中,第一条消息到达 Bob,第二条消息在顶点 1 中被 Alice 拒绝。这是因为发起者编号较小的消息具有优先级。
在第三个示例中,第一条和第三条消息到达 Bob,而第二条消息在顶点 3 中被 Alice 拒绝。