В своей старой тетради Ксюша нашла три числа $$$A$$$, $$$B$$$, $$$C$$$ и равенство $$$A + B = C$$$, которое ей показалось довольно подозрительным.
Ксюша поняла, что числа, вероятно, записаны в какой-то альтернативной системе счисления и решила найти все возможные целые основания систем счисления $$$b \ge 2$$$, при которых все три записи чисел корректны и равенство верно. Так как таких систем счисления может быть много, она решила вычислить сумму их оснований.
Помогите Ксюше вычислить искомую сумму. Если таких оснований бесконечно много, сообщите об этом.
Напомним, что запись числа в системе счисления с основанием $$$b$$$ задаётся массивом цифр $$$d_1, d_2, \ldots, d_n$$$, от старшего разряда к младшему. Она корректна, если $$$0 \le d_i \lt b$$$ для всех $$$1 \le i \le n$$$. Значение числа, заданного цифрами $$$d_1, d_2, \ldots, d_n$$$ в системе счисления с основанием $$$b$$$ равно $$$$$$\sum_{i=1}^{n} d_i b^{n-i}.$$$$$$ Традиционно для систем счисления с основанием больше $$$10$$$ для записи цифр используются буквы и другие значки, но в этой задаче мы просто зададим значения каждой цифры в записи чисел, не вводя специальных обозначений.
Первая строка содержит целое число $$$n_A$$$ — длину записи числа $$$A$$$ ($$$1 \le n_A \le 10^5$$$). Вторая строка содержит $$$n_A$$$ целых чисел $$$a_1, a_2, \ldots, a_{n_A}$$$ — значения её цифр ($$$0 \le a_i \le 10^9$$$).
Третья строка содержит целое число $$$n_B$$$ — длину записи числа $$$B$$$ ($$$1 \le n_B \le 10^5$$$). Четвёртая строка содержит $$$n_B$$$ целых чисел $$$b_1, b_2, \ldots, b_{n_B}$$$ — значения её цифр ($$$0 \le b_i \le 10^9$$$).
Пятая строка содержит целое число $$$n_C$$$ — длину записи числа $$$C$$$ ($$$1 \le n_C \le 10^5$$$). Шестая строка содержит $$$n_C$$$ целых чисел $$$c_1, c_2, \ldots, c_{n_C}$$$ — значения её цифр ($$$0 \le c_i \le 10^9$$$).
Цифры каждой записи перечислены от старшего разряда к младшему.
Гарантируется, что записи чисел не содержат ведущих нулей.
В единственной строке выведите сумму всех целых оснований $$$b \ge 2$$$, при которых записи чисел $$$A$$$, $$$B$$$ и $$$C$$$ корректны и выполняется равенство $$$A + B = C$$$.
Если таких оснований нет, выведите $$$0$$$. Если их бесконечно много, выведите строку «inf».
2 1 2 1 3 2 2 0
5
2 1 2 2 3 4 2 4 6
inf
2 1 2 1 0 2 2 0
0
| Название |
|---|


