小睿睿的兄弟
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小睿睿给了你一颗大小为n的以1为根的树
每次给定x,k，求x的k代兄弟中第k小的权值
k代兄弟指与他拥有相同的第k代祖先的点（包括自己）


输入描述:

第1行2个整数n,m
第2行n个整数val_i，表示各节点的权值
第3至n+1行，每行2个整数i,j，表示节点i,j间有一条边
接下来m行
每行两个整数a,k ( x = ( a xor lastans ) mod n + 1 )
其中lastans为上一个询问的答案，其初始值为0，如上个询问的答案为"?"，则为前一个有效答案

输出描述:

共m行，每行1个整数，表示答案，如果该节点没有k个兄弟或第k代祖先，输出"?"（不包含引号）
示例1

输入

复制 
5 4
1 5 2 5 4 
1 2
2 5
3 5
4 5
1 4
4 2
2 2
1 1

输出

复制 
?
?
5
4

说明

第一个询问：解码后x=2，没有k=4的祖先，答案为？

第二个询问：解码后x=5，只有1个k=2兄弟（自己），答案为?

第三个询问：解码后x=3，有2个k=2兄弟3,4，权值分别为2,5，第k=2小权值为5，答案为5

第四个询问：解码后x=5，有1个k=1兄弟5，权值为4，答案为4
示例2

输入

复制 
5 4
1 2 2 2 2 
1 2
2 5
3 5
4 5
1 4
4 2
2 2
1 1

输出

复制 
?
?
2
2

备注:

对于100%的数据