Rotate and Rewrite

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

回転と書換

整数の列 A: A1 A2 ... An と B: B1 B2 ... Bm および "x1 x2 ... xky" という形式の書き換えルールがいくつか与えられる. 二つの列に対して独立に以下の変換を,任意の順序で任意回繰り返すことができる.

  • 回転: 先頭要素を末尾に動かす.つまり,列 c1 c2 ... cpc2 ... cp c1 にする.
  • 書換: 与えられた書き換えルールに "x1 x2 ... xky" があるときに, 列 c1 c2 ... ci x1 x2 ... xk d1 d2 ... djc1 c2 ... ci y d1 d2 ... dj にする.

これらの操作を繰り返すことで,A と B を全く同じ列に変形することができるかどうか判定せよ. できる場合は,そのような変形を施した後の列のうちで最長の列の長さを答えよ.

Input

入力は複数のデータセットからなり,各データセットは以下の形をしている.

n m r
A1 A2 ... An
B1 B2 ... Bm
R1
...
Rr

データセットの最初の行は三つの正整数 n, m, r からなり, n (n ≤ 25) は列 A の長さ, m (m ≤ 25) は列 B の長さ, r (r ≤ 60) は書き換えルールの個数を表す. 次の行には n 個の整数があり,これが列 A の n 個の要素を表す. その次の行には m 個の整数があり,これが列 B の m 個の要素を表す. その次には r 行が以下の形式で続く.各行が一つの書き換えルールに対応する.

k x1 x2 ... xk y

最初の整数 k (2 ≤ k ≤ 10) はルールの左辺の長さである. 次に来る k 個の整数 x1 x2 ... xk はルールの左辺を表す. 最後に来る整数 y はルールの右辺を表す.

A1, .., An, B1, ..., Bm, x1, ..., xk, y はすべて 1 以上 30 以下である.

"0 0 0" と書かれた行が入力の終わりを示す.

Output

各データセットについて, 同じ列に変形できる場合は, そのような変換を施した後の列のうちで最長のものの長さを出力せよ. 同じ列に変形できない場合は,-1 を出力すること.

Sample Input

3 3 3
1 2 3
4 5 6
2 1 2 5
2 6 4 3
2 5 3 1
3 3 2
1 1 1
2 2 1
2 1 1 2
2 2 2 1
7 1 2
1 1 2 1 4 1 2
4
3 1 4 1 4
3 2 4 2 4
16 14 5
2 1 2 2 1 3 2 1 3 2 2 1 1 3 1 2
2 1 3 1 1 2 3 1 2 2 2 2 1 3
2 3 1 3
3 2 2 2 1
3 2 2 1 2
3 1 2 2 2
4 2 1 2 2 2
0 0 0

Output for the Sample Input

2
-1
1
9

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Aizu, Japan, 2013-07-12
http://sparth.u-aizu.ac.jp/icpc2013/