题目描述

小 A 有一棵 $n$ 个点的无根树，树上的每个点有一个权值，点 $i$ 的权值是 $a_i$。树上还有一些边是关键边。定义一条关键边的不平衡度为：将其删去后，得到的两棵子树的点权和之差的绝对值。定义整棵树的不平衡度为所有关键边的不平衡度的最大值。

给定 $k,L,R$，以及 $k$ 条关键边。小 A 每次可以将一个点的权值增加 $1$，他至少要进行 $L$ 次操作，至多进行 $R$ 次操作。小 A 想知道，进行若干次操作后，这棵树的不平衡度最小能是多少？

小 A 有 $Q$ 次询问，每次都会给定 $k,L,R$ 以及 $k$ 条这次询问中的关键边，你需要对每次询问输出答案。

输入格式

第一行 2 个整数 $n, Q$。

第二行 $n$ 个以空格分隔的整数 $a_1,\dots,a_n$ 表示点的权值。

接下来 $n-1$ 行每行两个以空格分隔的整数 $u_i,v_i$ 表示编号为 $i$ 的边。

接下来有 $Q$ 次询问，每个询问的第一行是 $3$ 个整数 $k,L,R$，第二行是 $k$ 个空格分开的整数表示关键边的编号（从小到大给出且不重复）。

输出格式

输出 $Q$ 行，第 $i$ 行一个整数表示第 $i$ 次询问中树的最小不平衡度。

输入样例1

5 2
1 4 2 6 10
1 4
2 3
2 4
4 5
3 0 5
2 3 4
2 10 20
1 3

输出样例1

14
16

数据范围

对于所有测试点，$2\le n\le 3\times 10^5$，$1\le Q\le n$，$0\le a_i\le 10^6$，$0\le L\le R\le 10^9$，$1\le k\le n-1$，$\sum k\le n$。