P2104 Binary

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.)

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 one line with some characters, representing the binary number after performing the operations.

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