Problem A
CRT

Implement Chinese remainder theorem.

Input

Each line of the input consists of a space-separated list of: one integer $k$ determining the number of moduli, $k$ pairwise coprime moduli $q_1,\ldots ,q_ k$, and $k$ integers $a_1,\ldots ,a_ k$. All integers are positive and given in decimal.

Output

For each input line output a line containing the unique integer $a\in \{ 0,\ldots ,\prod _{i=1}^ kq_ i-1\} $ such that $a=a_ i\bmod q_ i$ for $i=1,\ldots ,k$. The output integers should be given in decimal.

3 3 5 7 1 2 3
4 11 13 17 23 4 5 6 7

52
51550