#4763. 雪辉

内存限制:512 MiB 时间限制:39 Sec

题目描述

上次立下的NOIP退役Flag没有成功
这次就立一个WC狗牌的Flag
三周目的由乃被钦定成为了卡密,她立刻赶去二周目的世界寻找雪辉
但是按照设定,两个平行世界是没法互相影响的,也就是原则上由乃是没法去二周目世界的
这时候Deus又跳出来说,其实设定是作者骗你的,只要爱的力量足够强大什么都可以做到(好狗血)
Deus:由乃你为了雪辉是不是什么都可以做呀
yuno:当然啦这还用想
Deus:那你帮我做个题吧
yuno:只要不是数据结构,什么题我都做
Deus:出题人是那个nzhtl1477呀,他出(抄)的题除了傻逼数据结构还有啥。。。
yuno:你说的很有道理。。。
Deus:上次那个题你不是两分钟就秒了吗,这个题比那个还简单
yuno:(小声)其实那个是bzoj上面的大佬帮我做的
Deus:好吧就这么愉快的钦定了
给一个n个点的树,点有点权,有m次询问,每次询问多条链的并有多少种不同的点权以及它的mex
mex就是一个集合中最小的没有出现的非负整数,注意0要算
比如说集合是1,9,2,6,0,8,1,7,则出现了0,1,2,6,7,8,9这7种不同的点权,因为没有3所以mex是3

输入格式

第一行三个数n,m,意义如题所述,和一个数f
如果f是0,代表Deus没有使用膜法,如果f是1,代表Deus使用了膜法
之后一行n个数,表示点权
之后n-1行,每行两个数x,y,表示x和y节点之间有一条边,保证是一个树
之后m行,每行先是一个数a,表示这次输入a条链,紧接着2a个数(x1,y1)(x2,y2)...表示每条树链
如果数据被Deus施了膜法,这2a个数都要异或上上一个询问的答案lastans,如果是第一次询问则这个lastans = 0,因为每次询问有两个答案,lastans为这两个答案的和
如果没有膜法,则-1s并且不异或
数据范围:
设a的和为q
对于20%的数据,n,q<=1000,f=0
对于另外30%的数据,n,q<=100000,树是一条链,f=0
对于所有数据n,q<=100000,且点权<=30000

输出格式

m行,每行两个数表示点权种类数以及mex

样例

样例输入


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

样例输出


			
3 3

数据范围与提示

可爱(口径)即正义~