Description

由乃不太会打扑克

所以她出了一个数据结构题

给一个N个点树，第i个点的点权为Ai，M次操作， 每次求一些树链的并的贡献，强制在线

贡献定义：

定义权值集合为这些树链的并里面出现过的所有点权的集合

权值集合中每一段连续出现的数的贡献为这一段长度的k次方

例如出现了1,9,2,6,0,8,1,7这些数，k=3的时候贡献为3^3+4^3，因为0,1,2是连续一段，6,7,8,9为连续一段

每次询问给出x条树链，以及一个k，贡献对2^32取模

Format

Input

一行两个整数N,M

接下来一行N个整数， 第i个整数表示Ai

接下来N-1行每行两个数u,v， 用来描述树上的一条边, 1≤u,v≤N

接下来M行， 每行首先给出一个数x， 接下来2x个数， 读入的这2x个数需要异或上一次询问的答案解密得到，初

始答案为0， 得到的第2i+1以及2i+2个数表示第i条链的起点以及终点， 最后一个数k

0≤N,M≤10^5, 0≤∑x≤10^5, 0≤k≤30, 0≤Ai≤30000

Output

对于每个询问输出一个数表示答案

Samples

8 2
1 9 2 6 0 8 1 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
2 1 4 5 8 3
1 90 90 2

91
1