K. Cake Hater
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Agent Wang is a very reserved person and prefers not to share his birthday. However, the MaratonUSP trio managed to find out when his birthday is!

To celebrate, the trio decided to bake a cake from scratch. The responsibility for the recipe fell to Antonio, the trio's cook — but there's a problem: Antonio does not like cakes.

After some investigation, Antonio discovered which cake ingredients he doesn't like and decided simply not to use them in the preparation, even if it compromises the result. The cake recipe is divided into several steps, and each step uses a list of ingredients. The cake will become bad if, in any step, more than one third of the ingredients of of the step are missing.

What is the first step in which the cake becomes bad, if any?

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^3$$$), the number of steps.

The second line contains two integers $$$A$$$ and $$$B$$$ ($$$1 \leq B \leq A \leq 3 \cdot 10^5$$$), the total number of ingredients and the number of ingredients Antonio does not like.

The third line contains $$$B$$$ distinct integers between $$$1$$$ and $$$A$$$, indicating the ingredients Antonio does not like.

Each of the next $$$N$$$ lines represents a step, containing an integer $$$M$$$ ($$$1 \leq M \leq A$$$), the number of ingredients in that step, followed by $$$M$$$ distinct integers between $$$1$$$ and $$$A$$$ representing the ingredients of the step.

The sum of the number of ingredients in all steps is at most $$$3 \cdot 10^5$$$.

Output

Print a single integer, the index of the first step in which the cake becomes bad, or $$$-1$$$ if no step makes the cake become bad.

Example
Input
3
6 3
1 3 5
4 1 2 4 6
3 2 3 4
6 6 5 4 3 2 1
Output
3
Note

In the first test case, there are $$$3$$$ steps and $$$6$$$ ingredients, and Antonio does not like ingredients $$$1$$$, $$$3$$$, and $$$5$$$.

In the first step, out of $$$4$$$ ingredients, Antonio does not like ingredient $$$1$$$. Thus, the cake does not become bad.

In the second step, out of $$$3$$$ ingredients, Antonio does not like ingredient $$$3$$$. Antonio removes exactly one third of the ingredients, so the cake does not become bad.

In the third and last step, out of $$$6$$$ ingredients, Antonio does not like half of them. Thus, the cake becomes bad.