题目描述

$\mathrm{Ethan}$ 有 $n$ 个数字集合，每个集合有如下属性：

编号：第 $i$ 个集合编号为 $i$。

大小：第 $i$ 个集合大小为 $num_i$。

魔力：第 $i$ 个集合魔力为 $t_i$。

数字：第 $i$ 个集合中含有数字 $c_{i,1},c_{i,2},\dots,c_{i,num_i}$。

在 $\mathrm{Ethan}$ 的世界中，一共只有 $m+1$ 个数：$0$ 到 $m$。

$\mathrm{Ethan}$ 对数字有奇特的感情，在这 $m+1$ 个数中，有 $d$ 个数是他喜欢的，分别是 $p_1,p_2,\dots,p_d$ ，剩下 $m-d+1$ 个是他不喜欢的。

现在 $\mathrm{Ethan}$ 要删除一些集合，准确来说，他要选择一段区间 $[L,R]$，删除所有编号在这个区间以外的集合。

• 他想要使得在剩余的集合中，包含所有他喜欢的数。

• 并且在剩余的集合中，他不喜欢的数的个数尽可能小（注：这里的个数是指出现的次数，即如果 $1$ 是 $\mathrm{Ethan}$ 不喜欢的数，并且剩余的集合中出现了 $3$ 个 $1$，那么算 $3$ 个不喜欢的数）。

• 如果有多个满足条件的区间，他想要使得剩余集合的魔力之和尽可能大。

求出满足要求的 $[L,R]$，如果无解输出 $-1$，如果有多解，输出任意一解。

输入格式

第一行三个整数 $n,m,d$。

第二行 $d$ 个整数 $p_1,p_2,\dots,p_d$。

第三行至第 $n+2$ 行：每行先是两个整数 $t_i,num_i$，随后 $num_i$ 个整数 $c_{i,1},c_{i,2},\dots,c_{i,num_i}$。

输出格式

一行，如果无解输出 $-1$，否则输出两个整数 $L,R$。

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

2 4

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

-1

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

2 3

提示

样例解释：

在样例 $1$ 中，$\mathrm{Ethan}$ 可以选择 $[2,4]$，这样在剩余的集合中包含了所有他喜欢的数，且只有 $2$ 个他不喜欢的数在这些集合中出现。

在样例 $2$ 中，不存在合法的解。

数据范围：

本题使用 subtask。

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\%$。