被锤有一棵$n$个节点的有根树,根节点为$1$。

被锤给出了$2-n$的父亲。

因为被锤不会写树剖,他要$Q$次询问两个节点的LCA。

输入格式

第一行两个正整数$n,Q$，含义同题面。

接下来$n-1$行,第$i$行一个数字$fa[i]$,表示$i$的父亲$(1 \leq fa[i]\ < i)$。

接下来$Q$行,一行两个数字$x,y$,表示询问$x,y$的LCA。

输出格式

$Q$行，一行一个数字，表示答案。

样例一

input

3 1
1
1
2 3

output

1

数据范围

$test 1:\ n=10^5\ (10')$

$test 2:\ n=2*10^5\ (10')$

$test 3:\ n=3*10^5\ (10')$

$test 4:\ n=4.5*10^5\ (10')$

$test 5:\ n=6*10^5\ (10')$

$test 6:\ n=7.5*10^5\ (10')$

$test 7:\ n=9*10^5\ (10')$

$test 8:\ n=9*10^5\ (10')$

$test 9:\ n=9*10^5\ (10')$

$test 10:\ n=9*10^5\ (10')$

对于所有测试点,满足$Q=1*10^5$。

时间限制：$5s$

空间限制：$6MB$

小贴士:如果对于自己内存不放心的话可以使用自定义测试功能。

如果'c++'选手内存过大,可以放弃使用#include<iostream>达到减小内存消耗的效果。

在不使用#include<iostream>的情况下选手可用内存约为4.5MB