题目描述
给定一棵 $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$