Rotate and Rewrite#6107
Two sequences of integers : A_1 A_2 ... A_n and : B_1 B_2 ... B_m and a set of rewriting rules of the form "x_1 x_2 ... x_k → " are given. The following transformations on each of the sequences are allowed an arbitrary number of times in an arbitrary order independently.
Rotate: Moving the first element of a sequence to the last. That is, transforming a sequence c_1 c_2 ... c_p to c_2 ... c_p c_1.
Rewrite: With a rewriting rule "x_1 x_2 ... x_k → ", transforming a sequence c_1 c_2 ... c_i x_1 x_2 ... x_k d_1 d_2 ... d_j to c_1 c_2 ... c_i d_1 d_2 ... d_j.
Your task is to determine whether it is possible to transform the two sequences and into the same sequence. If possible, compute the length of the longest of the sequences after such a transformation.
The input consists of multiple datasets. Each dataset has the following form.
A_1 A_2 ... A_n
B_1 B_2 ... B_m
R_1
...
R_r
The first line of a dataset consists of three positive integers , , and , where (n \le 25) is the length of the sequence , (m \le 25) is the length of the sequence , and (r \le 60) is the number of rewriting rules. The second line contains integers representing the elements of . The third line contains integers representing the elements of . Each of the last lines describes a rewriting rule in the following form.
x_1 x_2 ... x_k
The first is an integer (2 \le k \le 10), which is the length of the left-hand side of the rule. It is followed by integers x_1 x_2 ... x_k, representing the left-hand side of the rule. Finally comes an integer , representing the right-hand side.
All of A_1, .., A_n, B_1, ..., B_m, x_1, ..., x_k, and are in the range between and , inclusive.
A line " " denotes the end of the input.
For each dataset, if it is possible to transform and to the same sequence, print the length of the longest of the sequences after such a transformation. Print if it is impossible.
Example 1