Description

Xiao Z recently learned about binary numbers. He thinks very small binary numbers are boring, so he wants to perform the following $4$ basic operations on a huge binary number:

Operation $1$: Add $1$ to the entire binary number.

Operation $2$: Subtract $1$ from the entire binary number.

Operation $3$: Multiply the entire binary number by $2$.

Operation $4$: Integer divide the entire binary number by $2$.

Xiao Z really wants to know the result after the operations, so he asks you for help.

(P.S.: To simplify the problem, the testdata guarantees that the + and - operations will not cause a carry-out or a borrow at the most significant bit.)

Input Format

The first line contains two positive integers $n, m$, representing the length of the original binary number and the number of operations.

The second line contains $n$ characters, each being 0 or 1, representing this binary number.

The third line contains $m$ characters, each being one of +, -, *, /, corresponding to operations $1, 2, 3, 4$.

Output Format

Output one line with some characters, representing the binary number after performing the operations.

4 10
1101
*/-*-*-/*/

10110

Hint

Constraints:

For $30\%$ of the testdata, $1 \leq n, m \leq 1000$.

For $60\%$ of the testdata, $1 \leq n, m \leq 10^5$.

For $100\%$ of the testdata, $1 \leq n, m \leq 5 \times 10^6$.

Translated by ChatGPT 5