题目描述

给定一棵 $n$ 个点树，点有点权且互不相同。

有 $q$ 个询问，每个询问为查询一条链上，任意两个数的差的绝对值的最小值。

输入格式

第一行两个整数 $n, q$，分别表示节点数和询问数。

之后一行 $n$ 个整数，第 $i$ 个数记为 $a_i$ 。

之后 $n-1$ 行，每行两个整数 $x,y$，表示点 $x$ 和点 $y$ 之间有一条边。

之后 $q$ 行，每行两个整数 $u, v$，在对 $u,v$ 进行如下变换

$$u = (u + \text{lastans}) \bmod n + 1$$

$$v = (v + \text{lastans}) \bmod n + 1$$

（其中 $\text{lastans}$ 表示上次询问的答案, 初始为 $0$）后，查询节点 $u$ 到节点 $v$ 表示的这条树链。

输出格式

一共 $q$ 行，每行一个数，表示这条链上任意两数的差的绝对值的最小值。如果该链上只有一种权值，则输出 $-1$ 。

样例

input

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

output

2
1
1
-1
-1
1

数据范围与提示

$1000 \leq n, q \leq 40000$

$1 \leq x,y,u,v \leq n$

$1 \leq a_i \leq 10^9$