Problem Description

Ethan has $n$ sets of numbers, each with the following attributes:

• ID: The $i$-th set is numbered $i$.
• Size: The $i$-th set has a size of $num_i$.
• Magic: The $i$-th set has a magic value of $t_i$.
• Numbers: The $i$-th set contains the numbers $c_{i,1}, c_{i,2}, \dots, c_{i,num_i}$.

In Ethan's world, there are only $m+1$ numbers: $0$ to $m$.

Among these $m+1$ numbers, Ethan likes $d$ of them, which are $p_1, p_2, \dots, p_d$, and dislikes the remaining $m-d+1$ numbers.

Ethan wants to delete some sets. Specifically, he will choose an interval $[L, R]$ and delete all sets whose IDs are outside this interval.

• He wants the remaining sets to include all the numbers he likes.
• Among the remaining sets, he wants the count of the numbers he dislikes to be as small as possible (Note: The count refers to the number of occurrences. For example, if $1$ is a disliked number and appears $3$ times in the remaining sets, it counts as $3$ disliked numbers).
• If there are multiple intervals that satisfy the above conditions, he wants the sum of the magic values of the remaining sets to be as large as possible.

Find the interval $[L, R]$ that meets the requirements. If there is no solution, output $-1$. If there are multiple solutions, output any one.

Input Format

The first line contains three integers $n, m, d$.

The second line contains $d$ integers $p_1, p_2, \dots, p_d$.

From the third line to the $(n+2)$-th line: Each line starts with two integers $t_i, num_i$, followed by $num_i$ integers $c_{i,1}, c_{i,2}, \dots, c_{i,num_i}$.

Output Format

One line, if there is no solution, output $-1$. Otherwise, output two integers $L, R$.

Sample Input and Output

Sample Input #1

5 7 4
1 3 4 5
3 3 4 6 5
4 2 1 5
2 3 1 7 3
5 2 2 4
6 6 3 5 4 6 1 7

Sample Output #1

2 4

Sample Input #2

2 3 2
1 2
4 1 1
4 2 1 3

Sample Output #2

-1

Sample Input #3

4 3 2
1 2
1 1 3
1 2 1 2
1 1 2
1 3 1 2 3

Sample Output #3

2 3

Notes

Sample Explanation:

In Sample #1, Ethan can choose the interval $[2, 4]$. This way, the remaining sets contain all the numbers he likes, and only $2$ of the numbers he dislikes appear in these sets.

In Sample #2, there is no valid solution.

Data Range:

This problem uses subtasks.

• Subtask 1: $1 \leq n, m \leq 100$, $20\%$.
• Subtask 2: $1 \leq n, m \leq 500$, $30\%$.
• Subtask 3: $1 \leq n \leq 3000, 1 \leq m \leq 1000, 1 \leq t_i \leq 10^9$, $50\%$.

见题面 Input 部分

见题面 Output 部分