Description

There is a string $S$ of length $T$ and $n$ small strings $a_i$.

You are given an array $R$ of length $m$, indexed starting from 1. Initially, there is an empty string $X$. Lord Divine Tree will perform $Q$ operations. In the $i$-th operation, he appends the small string $a_{R_{(i-1)\bmod m+1}}$ to the end of $X$.

After each operation, Lord Divine Tree checks whether the string $X$ has a suffix such that, after an arbitrary permutation, it can become $S$.

Ask how many times the string $X$ has a suffix that can become $S$ after an arbitrary permutation (that is, the counts of all characters are the same).

Unfortunately, the character set size of this string is as large as $10^5$, so you must read the strings as integer arrays.

Input Format

Input $n, T, Q$.

Then input $T$ numbers representing the string $S$.

Then input $n$ lines. In each line, the first number $len$ is the length, followed by $len$ numbers representing this small string. Each input number is in the range $[0,10^5]$.

Then input $m$.

Input one line with $m$ numbers representing $R$.

Output Format

Output the answer.

5 5 20
2 2 0 2 0
2 2 0
2 0 2
3 0 2 0
3 0 2 0
2 2 2
10
2 1 5 5 2 2 4 2 5 3

6

10 10 10000
0 1 1 1 0 1 1 0 0 0 
6 0 0 1 1 1 0 
6 0 0 0 0 0 0 
5 0 0 0 0 0 
4 1 0 0 0 
5 1 1 1 0 1 
2 1 1 
6 0 0 0 0 0 1 
1 0 
4 0 0 1 1 
1 1 
30
10 4 3 9 10 9 4 8 5 10 9 8 6 10 10 4 9 2 2 9 6 4 1 10 10 1 9 10 3 5 

3001

Hint

Explanation for Sample 1

Constraints

For all testdata, $n, T, m \leq 10^5$, $1 \leq R_i \leq n$, $Q \leq 10^9$. The total length of all small strings does not exceed $10^5$. All characters are in $[0,10^5]$.

Translated by ChatGPT 5