#4763. 雪辉

题目描述

上次立下的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

数据范围与提示

可爱（口径）即正义~