Problem Background

Time Limit: 3s, Memory Limit: 512MB

In the third iteration, Yuno is designated as the deity and immediately rushes to the second iteration's world to find Yukii.

However, according to the setting, two parallel worlds cannot influence each other, meaning Yuno should not be able to go to the second iteration's world.

At this moment, Deus jumps out and says that the setting was a lie by the author, and that with enough love, anything can be achieved (how cliché).

Deus: Yuno, are you willing to do anything for Yukii?

Yuno: Of course, what else would I think?

Deus: Then help me solve a problem.

Yuno: As long as it's not a data structure problem, I'll solve any problem.

Deus: The problem setter is n????????, his problems (copied) are nothing but stupid data structures...

Yuno: You make a good point...

Deus: Last time, you solved that problem in two minutes, this one is even simpler.

Yuno: (whispers) Actually, a BZOJ expert helped me with that.

Deus: Well, let's just happily designate it then.

Problem Description

Given a tree with n nodes, each node has a weight. There are m queries, each asking for the union of multiple chains and the number of different node weights and their mex.

The mex of a set is the smallest non-negative integer that does not appear in the set, note that 0 should be considered.

For example, if the set is {1, 9, 2, 6, 0, 8, 1, 7}, then the different node weights are {0, 1, 2, 6, 7, 8, 9}, and since 3 is not present, the mex is 3.

Input Format

The first line contains three numbers n, m, as described in the problem, and a number f.

If f is 0, it means Deus did not use magic; if f is 1, it means Deus used magic.

The next line contains n numbers, representing the node weights.

The next n-1 lines, each containing two numbers x and y, indicate that there is an edge between nodes x and y, ensuring it is a tree.

The next m lines, each starting with a number a, indicating the number of chains in this input, followed by 2a numbers (x1, y1)(x2, y2)... representing each tree chain.

If the data is enchanted by Deus, these 2a numbers should be XORed with the last answer lastans. If it is the first query, lastans is 0, as each query has two answers, lastans is the sum of these two answers.

If there is no magic, it is -1s and no XOR operation is performed.

Output Format

m lines, each containing two numbers representing the number of different node weights and the mex.

Sample Input and Output

Input Sample #1

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

Output Sample #1

2 1

Input Sample #2

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

Output Sample #2

3 3

Notes/Hints

Let the sum of a be q.

For 20% of the data, n, q <= 1000, f = 0.

For another 30% of the data, n, q <= 100000, the tree is a single chain, f = 0.

For all data, n, q <= 100000, and node weights <= 30000.

Lastly, Yuno wishes everyone a Happy New Year.

见题面 Input 部分

见题面 Output 部分