Description

Keke’s happy journey on Joy Island continues. He wants to buy some souvenirs for his classmates, so he goes to the gift shop and finds an interesting calculator.

This calculator is a special one that supports addition and subtraction of mixed-radix integers (mixed-radix means each digit can have a different base. For example, if the least significant digit uses base $3$ and the next digit uses base $5$, then $42$ in this system converts to decimal as $4\times 3+2=14$).

The shopkeeper notices Keke’s interest and asks: “Kid, if I tell you this calculator supports mixed-radix integers of up to $N$ digits, and the bases for each digit are $x_1,x_2,\ldots,x_n$, do you know the maximum integer $M$ it can represent?” Keke thinks for a while and answers: “The maximum integer $M$ it can represent is $(x_1\times x_2\times \cdots\times x_n)-1$.”

The shopkeeper is very happy and says: “You are a smart kid. If I give you two mixed-radix integers $A$ and $B$ of length $N$, compute $(A + B)\bmod(M+1)$ or $(A - B)\bmod(M+1)$ as required, and give the answer in the same mixed-radix system. If you get it right, I will give you this calculator.”

This stumps Keke, but he really wants the calculator. Can you help him?

Input Format

• The first line contains an integer $N$, the length of the mixed-radix numbers supported by the calculator.
• The second line contains $N$ integers $x_1,x_2,\ldots,x_N$, the bases of digits $1\sim N$ (from the most significant digit to the least significant digit).
• The third line contains $N$ integers $A_1,A_2,\ldots,A_N$, representing the first operand.
• The fourth line contains a character $op$, representing the operation type.
• The fifth line contains $N$ integers $B_1,B_2,\ldots,B_N$, representing the second operand.

Output Format

If $op$ is '+', output $(A+B)\bmod(M+1)$. Otherwise, output $(A-B)\bmod(M+1)$. Separate digits with a single space, pad with leading zeros to $N$ digits, and do not print extra spaces before the most significant digit or after the least significant digit.

3
3 2 5
1 1 2
+
0 0 3

2 0 0

Hint

Constraints:

• For $100\%$ of the testdata, $1\le N \le 10^5$, $1 < x_1,x_2,\ldots,x_N<100$.
• For $30\%$ of the testdata, $N \le 9$, and $x_1 = x_2 = \ldots = x_N = 10$.

Translated by ChatGPT 5