Description

The pizzeria offers $m$ different pizzas. Toppings are labeled with positive integers. The $i$-th pizza has $k_i$ toppings, with labels $b_{i,1},b_{i,2},\cdots,b_{i,k_i}$.

Mirko is very picky about food. He does not like $n$ kinds of toppings, with labels $a_1,a_2,\cdots,a_n$, so he wants to order a pizza that does not contain any of the toppings above. Find the number of pizzas Mirko can order.

Input Format

The first line contains an integer $n$, the number of toppings Mirko does not like. Then follow $n$ distinct integers $a_i$, the labels of the toppings Mirko does not like.

The second line contains an integer $m$, the number of pizzas.

In the next $m$ lines, the $i$-th line contains an integer $k_i$, the number of toppings on the $i$-th pizza. Then follow $k_i$ distinct integers $b_{i,j}$, the labels of the toppings on that pizza.

There will not be two pizzas with exactly the same set of toppings.

Output Format

Output the number of pizzas Mirko can order.

1 2
3
1 1
1 2
1 3

2

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

2

1 4
3
1 1
1 2
1 3

3

Hint

Constraints

For $40\%$ of the testdata, $n=k_1=k_2=\cdots=k_m=1$.

For $100\%$ of the testdata, $1 \le n,m,a_i,k_i,b_{i,j} \le 100$.

Notes

The scoring of this problem follows the original COCI problem, with a full score of $50$.

Translated from COCI2020-2021 CONTEST #4 T1 Pizza.

Translated by ChatGPT 5