Jewel Magic — Eolymp

Input

There will be several test cases. The first line of each test case contains two integers $n$ and $m$ ( $1 \leq n, m \leq 200, 000$ 1 \leq n, m \leq 200{,}000), where $n$ is the number of pearls initially and $m$ is the number of operations. The next line contains a $01$ string of length $n$ . Each of the next $m$ lines contains an operation. The input is terminated by end-of-file ( $EOF$ ). The size of the input file does not exceed $5$ MB.

Output

For each type- $4$ operation, output the answer.

Examples

Example 1

Loading

Note

String after operation $101$ : $1000100001100$

String after operation $3710$ : $1000101000100$

String after operation $29$ : $100010100100$