Background

As is well known, the divine J (Joker) goes to Chengdu French School pretending to attend classes every few days, but in reality, he plays with pointers. J can sneakily pull out a pointer to teleport himself to any location (a living specimen cabinet turning into a magic show?), or swap the pointers of two people (a Chengdu French School version of "Your Name"?), or chant system commands to make the OJ randomly slow down (mcfx: Why does the CPU slow down after turbo boost?).

The Divine Tree Master is very dissatisfied because trees must stand still, and the Divine Tree Master doesn't know how to use pointers. However, being divine, he plans to delete the database of this universe and run away, so the idle divine J can only play cards with the Divine Tree Master.

Problem Description

Given a string \( S \) of length \( T \) and \( n \) smaller strings \( a_i \).

You are provided with an array \( R \) of length \( m \), with indices starting from 1. Initially, there is an empty string \( X \). The Divine Tree Master plans to perform \( Q \) operations, where the \( i \)-th operation appends the smaller string \( a_{R_{(i-1) \bmod m + 1}} \) to the end of \( X \).

After each operation, the Divine Tree Master checks if there is a suffix of \( X \) that can be permuted to form \( S \).

Determine how many times there exists a suffix of \( X \) that can be permuted to form \( S \) (i.e., all characters appear the same number of times).

Unfortunately, the size of the characters in the string can be as high as \( 10^5 \), so you must read an integer array.

Input Format

Input consists of \( n \), \( T \), and \( Q \).

Next, input \( T \) numbers representing the string \( S \).

Then, input \( n \) lines, each starting with a number \( len \) indicating the length, followed by \( len \) numbers representing the smaller string, with each number in the range \([0, 10^5]\).

Next, input \( m \).

Input a line with \( m \) numbers representing \( R \).

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

6

Sample Input #2

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 

Sample Output #2

3001

Notes

Sample 1 Explanation

Data Range

For all data, \( n, T, m \leq 10^5 \), \( 1 \leq R_i \leq n \), \( Q \leq 10^9 \), the total length of all smaller strings does not exceed \( 10^5 \), and all characters are in the range \([0, 10^5]\).

见题面 Input 部分

见题面 Output 部分