Mixed Radix Modular Calculator

On Happy Island, little Keke finds a special calculator in the Gifts Department. This calculator supports arithmetic operations on integers in a mixed radix system, where each digit may have a different base. For example, if the least significant digit uses base $3$ and the next uses base $5$, then the mixed radix number 42 represents the decimal value $4\times3+2=14$.

The maximum number that can be represented with $N$ digits (with digits bases $x_1,x_2,\ldots,x_N$) is \[ M=(x_1\times x_2\times \cdots \times x_N)-1 \] For instance, in the example above with bases $3$ and $5$, the maximum representable value is $(3\times5)-1=14$.

You are given two mixed radix integers $A$ and $B$ (each with exactly $N$ digits) and an operator which is either addition or subtraction. Your task is to compute \[ (A \oplus B) \bmod (M+1) \] where \(\oplus\) stands for either $+$ or $-$, and then output the result in the same mixed radix representation with exactly $N$ digits. Note that the digits are given in normal order (most significant digit first), but the least significant digit corresponds to the first base provided.

Input Format (see below for details):

• The first line contains an integer $N$ indicating the number of digits.
• The second line contains $N$ positive integers $x_1,x_2,\ldots,x_N$, where $x_1$ is the base for the least significant digit, $x_2$ for the next, and so on.
• The third line contains a character which is either '+' or '-' indicating the operation.
• The fourth and fifth lines each contain a string of exactly $N$ digits representing the mixed radix integers $A$ and $B$ respectively. The string is given in normal order (most significant digit first). It is guaranteed that each digit is in the range $0$ to $x_i-1$ for its corresponding radix position.

Output Format: Output a single line containing the resulting mixed radix number (with exactly $N$ digits, including any leading zeros) in normal order.

inputFormat

The input consists of multiple lines:

1. The first line contains an integer $N$, the number of digits.
2. The second line contains $N$ space-separated positive integers $x_1,x_2,\ldots,x_N$, which represent the bases for the digits (from least significant to most significant).
3. The third line contains a single character ('+' or '-') representing the operation.
4. The fourth line contains a string of $N$ digits representing the first mixed radix integer $A$ (with the most significant digit first).
5. The fifth line contains a string of $N$ digits representing the second mixed radix integer $B$.

outputFormat

Output a single line with the resulting mixed radix number in normal order (most significant digit first) with exactly $N$ digits.

sample

2
3 5
+
42
21

20