背景

SBW和LYH被SML送进了一棵树，并且被丢在不同的节点上
SBW希望找到LYH
通过XY宏，SBW可以确定一些节点是LYH可能出现的位置
SBW希望求出这些点的最近公共祖先，以便找到LYH

描述

给出一棵N个点以1为根的树和一个1至N的排列
M个询问，每次询问排列中l至r那些点的最近公共祖先

输入

第一行两个整数N,M
第二行N个整数，为1至N的一个排列
接下来N-1行，每行两个整数x,y表示树上x与y之间有边
接下来M行，每行两个整数l,r

输出

M行，每行一个整数，为对应询问的答案

样例

输入

7 5
1 3 2 4 6 7 5
2 1
3 1
4 2
5 3
6 3
7 5
6 7
5 7
2 4
3 4
4 5

输出

5
3
1
2
1

范围

40% N,M<=10
70% N<=3000 M<=700
100% 1<=N<=300000 1<=M<=500000 1<=x,y<=N 1<=l<=r<=N

限制

2000ms
256M