Description

Communicating with machines via voice and having them understand what you are saying is a long-held human dream. Speech recognition technology is a high-tech process that allows machines to recognize and understand speech signals, converting them into corresponding text or commands.

Now, we need you to solve a simplified version of a speech recognition problem: The information recorded by a microphone can be considered as a series of independent signals. Each signal is represented as a non-negative integer based on its voltage level, and the ordered sequence formed by these signals is the signal sequence input by the microphone.

A signal sequence can be described as a sequence of non-negative integers, such as $A = \{a_1, a_2, \dots, a_n\}$. A subsequence $A'$ of a signal sequence $A$ is a contiguous segment of signals in $A$, i.e., $A' = \{a_i, a_{i+1}, \dots, a_{j-1}, a_j\}$.

In practical situations, the signal sequence recorded by a microphone is often mixed with a small amount of noise. To handle the problems caused by noise in speech recognition, we need to introduce the concept of approximate matching:

Let $A$ and $B$ be two signal sequences. $A$ approximately matches $B$ if, after deleting a certain number of signals from $A$, the resulting signal sequence is exactly equal to $B$. We call the number of signals deleted from $A$ the degree of difference of the approximate match of $A$ with respect to $B$. It is worth noting that for recognition to be meaningful, only approximate matches with a small degree of difference are significant. For example, deleting one signal $2$ from the signal sequence $\{1, 2, 0\}$ results in the signal sequence $\{1, 0\}$. Therefore, $\{1, 2, 0\}$ approximately matches $\{1, 0\}$ with a degree of difference of $1$. Similarly, $\{1, 2, 0\}$ also approximately matches $\{0\}$ with a degree of difference of $2$. However, if the degree of difference for an approximate match is limited to no more than $1$, then the approximate match of $\{1, 2, 0\}$ with $\{0\}$ would be ignored. Specifically, if two signal sequences are identical, their match can be considered an approximate match with a degree of difference of $0$.

Researchers have pre-processed many commonly used characters to obtain the signal sequence corresponding to each character. The set of signal sequences for these characters is called a dictionary. Let $A'$ be a subsequence of signal sequence $A$. If $A'$ approximately matches signal sequence $B$, then $A'$ is an approximate occurrence of $B$ in $A$.

For a signal sequence $A = \{a_1, a_2, a_3, a_4, a_5, a_6\} = \{3, 3, 3, 1, 2, 0\}$, then $A_1 = \{a_1, a_2, a_3\}$, $A_2 = \{a_4, a_5\}$, $A_3 = \{a_6\}$, $A_4 = \{a_1, a_2\}$ are all subsequences of $A$. Consider the dictionary $\Sigma = \{a = \{1\}, b = \{1, 2\}, c = \{0\}, d = \{3, 3\}\}$, and the upper limit for the degree of difference of an approximate match is $1$. Then $A_1$ and $A_4$ are both approximate occurrences of $d$ in $A$, $A_2$ is an approximate occurrence of $a$ or $b$, and $A_3$ is an approximate occurrence of $c$.

To achieve the best possible recognition for the signal sequence input by the microphone, the most intuitive idea is to recognize as many characters as possible from the input signal sequence. Specifically, if we can find a set of subsequences $D_1, D_2, \dots, D_s$ from the input signal sequence $A = \{a_1, a_2, \dots, a_n\}$ that satisfy the following for the dictionary $\Sigma$:

1. For any $i, j$, $D_i$ and $D_j$ have no overlapping parts; that is, if $D_i = \{a_p, a_{p+1}, \dots, a_q\}$ and $D_j = \{a_u, a_{u+1}, \dots, a_v\}$, then the intervals $[p, q]$ and $[u, v]$ must not intersect, i.e., $p > v$ or $q < u$.
2. For any $D_i$, there exists a character in the dictionary (let it be $word_i$) such that $D_i$ approximately matches the signal sequence of $word_i$.

Then $D_1 \to word_1, D_2 \to word_2, \dots, D_s \to word_s$ is called an identification scheme for $A$. Arranging these approximate matches in the order of their appearance gives the identification result, and $s$ is the length of this identification scheme. The goal is to find a set that forms the longest identification scheme.

Input

The first line contains three integers $N, M, K$, representing the length of the signal sequence to be tested, the size of the dictionary, and the upper limit of the degree of difference for approximate matching, respectively. The second line contains $N$ non-negative integers separated by spaces, describing the signal sequence $A$. The next $M$ lines each describe a different character in the dictionary. For each line: First, input a non-negative integer $L$, representing the length of the signal sequence corresponding to this character, followed by $L$ integers giving the signal sequence corresponding to this character. Adjacent integers are separated by spaces. Note: Different characters may correspond to the same or similar signal sequences.

Output

The output file contains two lines: The first line contains two integers, representing the number of characters in the dictionary that can be detected in $A$, and the total number of approximate occurrences. The second line contains two integers, representing the length of the longest identification scheme, and the number of essentially different longest identification schemes (the number of schemes should be output modulo $1\,000\,003$). Note: Each line must contain exactly two integers separated by a single space. No extra spaces or line breaks are allowed, and the output must be complete.

Examples

Input 1

6 4 1 
3 3 3 1 2 0 
1 1 
2 1 2 
1 0 
2 3 3

Output 1

4 12 
3 2

Note

The example is the one given in the problem background.

Constraints

There are 10 test cases in total, each worth 10 points. Each test case is scored independently.

Where $L$ represents the total length of the signal sequences of all characters in the dictionary.