Polynomial Base Equation

Given three sequences of non‐negative integers a, b, and c with lengths \(|a|\), \(|b|\), and \(|c|\) respectively, where the coefficients are provided in little‐endian order (i.e. the element at index i represents the coefficient of \(B^i\)), define

\[ l = \max\{a_i, b_i, c_i\} \]

Your task is to find any positive integer \(B\) in the range \([l+1, 10^{19})\) such that

[ \Bigl(\sum_{i=0}^{|a|-1}a_iB^i\Bigr)\cdot\Bigl(\sum_{j=0}^{|b|-1}b_jB^j\Bigr)=\sum_{k=0}^{|c|-1}c_kB^k. ]

The input is guaranteed to satisfy the following: if there exists any positive integer \(B\ge l+1\) making the above equality hold, then there exists one in the range \([l+1,10^{19})\).

inputFormat

The first line contains three integers n m k representing the number of digits in sequences a, b, and c respectively. The second line contains n non-negative integers representing sequence a. The third line contains m non-negative integers representing sequence b. The fourth line contains k non-negative integers representing sequence c.

Note that each sequence is given in little‐endian order (i.e. the ith digit is the coefficient of \(B^i\)). Also, for any valid base \(B\) we must have every digit strictly less than \(B\); hence, the minimum allowed base is \(l+1\) where \(l=\max\{a_i,b_i,c_i\}\).

outputFormat

Output any valid integer base \(B\) in the range \([l+1,10^{19})\) such that

[ \Bigl(\sum_{i=0}^{n-1} a_iB^i\Bigr)\cdot\Bigl(\sum_{j=0}^{m-1} b_jB^j\Bigr)=\sum_{k=0}^{k-1} c_kB^k. ] If no such base exists, output -1.

sample

2 2 3
1 1
1 1
1 2 1

2