Döndür və Yenidən Yaz#6107
İki tam ədəd ardıcıllığı A: A_1 A_2 ... A_n və B: B_1 B_2 ... B_m verilmişdir. Həmçinin, "x_1 x_2 ... x_k → y" formasında yenidən yazma qaydaları mövcuddur. Hər iki ardıcıllıq üzərində aşağıdakı çevrilmələr istənilən sayda və istənilən qaydada müstəqil olaraq icazə verilir:
Fırlatma: Ardıcıllığın ilk elementini sonuncuya keçirmək. Yəni, c_1 c_2 ... c_p ardıcıllığını c_2 ... c_p c_1 ardıcıllığına çevirmək.
Yenidən yazma: "x_1 x_2 ... x_k → y" qaydası ilə, c_1 c_2 ... c_i x_1 x_2 ... x_k d_1 d_2 ... d_j ardıcıllığını c_1 c_2 ... c_i y d_1 d_2 ... d_j ardıcıllığına çevirmək.
Sizin vəzifəniz, ardıcıllıqları A və B eyni ardıcıllığa çevirmək mümkün olub-olmadığını müəyyən etməkdir. Əgər mümkündürsə, belə çevrilmədən sonra ən uzun ardıcıllığın uzunluğunu hesablayın.
Giriş bir neçə datasetdən ibarətdir. Hər dataset aşağıdakı formadadır:
n m r
A_1 A_2 ... A_n
B_1 B_2 ... B_m
R_1
...
R_r
Datasetin ilk sətri üç müsbət tam ədəd n, m və r ibarətdir, burada n (n ≤ 25) ardıcıllıq A-nın uzunluğudur, m (m ≤ 25) ardıcıllıq B-nin uzunluğudur və r (r ≤ 60) yenidən yazma qaydalarının sayıdır. İkinci sətir A-nın n elementini təmsil edən n tam ədəd ehtiva edir. Üçüncü sətir B-nin m elementini təmsil edən m tam ədəd ehtiva edir. Son r sətirin hər biri aşağıdakı formada yenidən yazma qaydasını təsvir edir:
k x_1 x_2 ... x_k y
Birinci k qaydanın sol tərəfinin uzunluğu olan tam ədəddir (2 ≤ k ≤ 10). Ardınca qaydanın sol tərəfini təmsil edən k tam ədəd x_1 x_2 ... x_k gəlir. Nəhayət, sağ tərəfi təmsil edən bir tam ədəd y gəlir.
Bütün A_1, .., A_n, B_1, ..., B_m, x_1, ..., x_k və y ədədləri 1 ilə 30 arasında, daxil olmaqla, yerləşir.
"Sıfır 0 0 0" sətri girişin sonunu göstərir.
Hər dataset üçün, əgər A və B ardıcıllıqlarını eyni ardıcıllığa çevirmək mümkündürsə, belə çevrilmədən sonra ən uzun ardıcıllığın uzunluğunu çap edin. Əgər mümkün deyilsə, -1 çap edin.
Nümunə 1