Problem Background

bj12z_jiasiyuan enjoys flipping and reversing.

Problem Description

bj12z_jiasiyuan has a binary string \( s \) of length \( n \), where the \( i \)-th character is denoted as \( s_i \). He will perform \( q \) operations, each with the following details:

• 1, flip the binary string \( s \), which means reversing the order of characters in the string. For example, if the original string \( s \) was 10010, after flipping, it becomes 01001.

• 2, reverse the binary string \( s \), which means inverting each bit. For each \( i \) (where \( 1 \leq i \leq n \)), if \( s_i = 0 \), change it to \( 1 \); otherwise, change it to \( 0 \).

Please tell bj12z_jiasiyuan the binary string \( s \) after performing \( q \) operations.

Input Format

The input consists of three lines.

• The first line contains two integers \( n \) and \( q \).
• The second line contains a binary string \( s \) of length \( n \).
• The third line contains a string \( w \) of length \( q \), where \( w_i \) indicates the type of the \( i \)-th operation. If \( w_i = 1 \), it means a flip operation; if \( w_i = 2 \), it means a reverse operation.

Output Format

Output the binary string \( s \) after performing \( q \) operations.

Sample Input and Output

Sample Input #1

7 10
1001100
1222121222

Sample Output #1

1100110

Sample Input #2

20 18
01100001111110010100
122121212112211221

Sample Output #2

11010110000001111001

Sample Input #3

18 18
101111010011101101
122222221112211211

Sample Output #3

101111010011101101

Notes

Data Size and Constraints

• For 50% of the test cases, \( 1 \leq n \leq 10^3 \) and \( 1 \leq q \leq 10^3 \).
• For 100% of the test cases, \( 1 \leq n \leq 10^5 \) and \( 1 \leq q \leq 10^5 \).

见题面 Input 部分

见题面 Output 部分