题目背景

上次立下的 NOIP 退役 Flag 没有成功。

这次就立一个 WC 狗牌的 Flag。

三周目的由乃被钦定成为了卡密，她立刻赶去二周目的世界寻找雪辉。

但是按照设定，两个平行世界是没法互相影响的，也就是原则上由乃是没法去二周目世界的、

这时候 Deus 又跳出来说，其实设定是作者骗你的，只要爱的力量足够强大什么都可以做到（好狗血）。

• Deus：由乃你为了雪辉是不是什么都可以做呀。
• yuno：当然啦这还用想。
• Deus：那你帮我做个题吧。
• yuno：只要不是数据结构，什么题我都做。
• Deus：出题人是那个 nzhtl1477 呀，他出（抄）的题除了傻逼数据结构还有啥。。。
• yuno：你说的很有道理。。。
• Deus：上次那个题你不是两分钟就秒了吗，这个题比那个还简单。
• yuno：（小声）其实那个是 bzoj 上面的大佬帮我做的。
• Deus：好吧就这么愉快的钦定了。

题目描述

给一个 $n$ 个点的树，点有点权，有 $m$ 次询问，每次询问多条链的并有多少种不同的点权以及它的 $\text{mex}$。

$\text{mex}$ 就是一个集合中最小的没有出现的非负整数，注意 $0$ 要算。

比如说集合是 $1,9,2,6,0,8,1,7$，则出现了 $0,1,2,6,7,8,9$ 这 $7$ 种不同的点权，因为没有 $3$ 所以 $\text{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)\ldots$ 表示每条树链。

如果数据被 Deus 施了膜法，这 $2a$ 个数都要异或上上一个询问的答案 $lastans$，如果是第一次询问则这个 $lastans = 0$，因为每次询问有两个答案，$lastans$ 为这两个答案的和。

如果没有膜法，则 $-1s$ 并且不异或。

输出格式

$m$ 行，每行两个数表示点权种类数以及 $\text{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

数据范围

设 $\sum a$ 为 $q$。

• 对于 $20\%$ 的数据，$n,q\le 10^3$，$f=0$。
• 对于另外 $30\%$ 的数据，$n,q\le 10^5$，树是一条链，$f=0$。
• 对于所有数据 $n,q\le 10^5$,且点权 $\le 3\times 10^4$。