Поверніть і Перепишіть
Дано дві послідовності цілих чисел A: A_1 A_2 ... A_n та B: B_1 B_2 ... B_m, а також набір правил переписування у вигляді "x_1 x_2 ... x_k → y". Ви можете виконувати наступні перетворення над кожною з послідовностей необмежену кількість разів у будь-якому порядку незалежно.
Обертання: Переміщення першого елемента послідовності в кінець. Тобто, перетворення послідовності c_1 c_2 ... c_p на c_2 ... c_p c_1.
Переписування: За правилом переписування "x_1 x_2 ... x_k → y", перетворення послідовності c_1 c_2 ... c_i x_1 x_2 ... x_k d_1 d_2 ... d_j на c_1 c_2 ... c_i y d_1 d_2 ... d_j.
Ваше завдання - визначити, чи можливо перетворити дві послідовності A та B в одну й ту ж послідовність. Якщо це можливо, обчисліть довжину найдовшої з послідовностей після такого перетворення.
Вхідні дані
Вхід складається з кількох наборів даних. Кожен набір даних має наступну структуру.
n m r
A_1 A_2 ... A_n
B_1 B_2 ... B_m
R_1
...
R_r
Перша строка набору даних складається з трьох додатних цілих чисел n, m та r, де n (n ≤ 25) - це довжина послідовності A, m (m ≤ 25) - це довжина послідовності B, і r (r ≤ 60) - це кількість правил переписування. Друга строка містить n цілих чисел, що представляють n елементів A. Третя строка містить m цілих чисел, що представляють m елементів B. Кожна з останніх r строк описує правило переписування у наступній формі.
k x_1 x_2 ... x_k y
Перше k - це ціле число (2 ≤ k ≤ 10), яке є довжиною лівої частини правила. За ним слідують k цілих чисел x_1 x_2 ... x_k, що представляють ліву частину правила. Нарешті йде ціле число y, що представляє праву частину.
Всі з A_1, .., A_n, B_1, ..., B_m, x_1, ..., x_k, та y знаходяться в діапазоні від 1 до 30 включно.
Строка "0 0 0" позначає кінець вводу.
Вихідні дані
Для кожного набору даних, якщо можливо перетворити A та B в одну й ту ж послідовність, виведіть довжину найдовшої з послідовностей після такого перетворення. Виведіть -1, якщо це неможливо.