Optimal Admission and Ranking Improvement

In this problem, there are n contestants (numbered from 1 to n) and m mentors (numbered from 1 to m). Each contestant submits a piece of code and a description of their dream. After that, all mentors rank the contestants, and no ties occur. In addition, every contestant fills in an application form consisting of m rounds of preferences. In each round, a contestant may list at most C distinct mentors (and is allowed to leave the round blank).

Each mentor has a fixed team capacity. The admission process is done in the order of the contestants’ ranking (which exactly coincides with their numbering). The process is defined recursively:

• The 1^st contestant is admitted optimally if and only if they are admitted by one of the mentors listed in the earliest (i.e. highest) non‐empty round. (In particular, if the contestant did not fill in any preference, they are rejected.)
• For contestant i (for i > 1), assuming that the admission decisions for contestants 1 to i−1 are optimal, contestant i is admitted by the highest possible round among their choices that is theoretically possible (i.e. there is at least one mentor in that round whose team is not full). If the contestant did not fill in any preference or if all mentors in every round are full, then the contestant is rejected.

Every contestant i also has an ideal value s_i (1 ≤ s_i ≤ m), meaning they wish to be admitted by their s_i^th (or a higher) preference. If not, they become very depressed.

After all preferences and rankings are public (with the ranking equal to the contestants’ numbers), for each contestant, you are to answer the following two questions:

1. In the optimal admission scheme, by which round (i.e. which preference) is the contestant admitted? (If the contestant is rejected, report 0.)
2. Assuming the relative order of all the other contestants remains unchanged, what is the minimum number of positions the contestant must move up in the ranking so that they will not be depressed (i.e. be admitted by a round ≤ s_i)? If it is impossible even by becoming rank 1, output -1.

Note: When processing a contestant, for each round from 1 to m, if the contestant has listed any mentors in that round, then if at least one of those mentors has remaining capacity, the contestant is admitted in that round and one available seat from the first such mentor (in the order given) is taken. The process stops as soon as the contestant is admitted.

Theoretically, if a solution achieves an optimal admission for all n contestants (i.e. every contestant is admitted in the best round possible given the constraints), we call that scheme optimal.

inputFormat

The input begins with a line containing three integers n, m and C (1 ≤ n, m, C ≤ 1000), indicating the number of contestants, the number of mentors, and the maximum number of choices allowed per round respectively.

The next line contains m integers, where the j^th integer is the capacity of mentor j.

This is followed by n blocks, one for each contestant in the order of their ranking (i.e. contestant 1 first, then contestant 2, …, contestant n). Each contestant block is formatted as follows:

• A line containing an integer s_i (1 ≤ s_i ≤ m), which is the contestant's ideal round.
• Then m lines follow, one for each round from 1 to m. Each line starts with an integer k (number of mentors chosen in that round, with 0 ≤ k ≤ C). If k > 0, it is followed by k distinct integers representing the mentors selected (each between 1 and m). If k = 0, the contestant leaves the round blank.

It is guaranteed that each contestant does not repeat any mentor across rounds.

outputFormat

Output n lines. The i^th line should contain two integers separated by a space:

• The first integer is the round (i.e. preference number) by which contestant i is admitted in the optimal scheme (or 0 if the contestant is rejected).
• The second integer is the minimum number of positions contestant i must move up (keeping the order of all other contestants unchanged) so that they are admitted by a round ≤ s_i. If it is not possible, output -1.

sample

3 2 1
1 1
1
1 1
0
1
1 2
0
2
0
1 2

1 0
1 0
0 1

</p>