N. BitShift
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string $$$s$$$ of length $$$n$$$. This binary string represents an integer (without trailing zeroes) $$$x$$$.

$$$m$$$ operations are then performed on this integer. In each operation, an integer $$$k$$$ is given, and the value of $$$x$$$ is updated to $$$\lfloor x \cdot 2^{k} \rfloor$$$. Equivalently, this operation can be understood as:

  • If $$$k \ge 0$$$, then $$$x$$$ is replaced by $$$x \lt \lt |k|$$$ (binary left shift by $$$k$$$ bits).
  • If $$$k \lt 0$$$, then $$$x$$$ is replaced by $$$x \gt \gt |k|$$$ (binary right shift by $$$-k$$$ bits).

Output (without leading zeroes) the binary string corresponding to the final value of $$$x$$$ after all $$$m$$$ operations.

Input

The first line of each test contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of the binary string and the number of operations.

The second line of each test case contains a binary string $$$s$$$ (consisting only of the characters 0 and 1). It is guaranteed that $$$|s| = n$$$ and that the first character of $$$s$$$ is 1.

The third line of each test case contains $$$m$$$ space-separated integers $$$k_i$$$ ($$$-2 \cdot 10^5 \le k_i \le 2 \cdot 10^5$$$) — the value of $$$k$$$ for the $$$i^{\text{th}}$$$ operation. It is guaranteed that the sum of $$$k$$$ over all operations lies between $$$-2 \cdot 10^5$$$ and $$$2 \cdot 10^5$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases and the sum of $$$m$$$ over all test cases are both at most $$$2 \cdot 10^5$$$.

Output

For each test case, output a single line containing a binary string corresponding to the final value of $$$x$$$. The binary string should not contain any leading zeroes — it should either be "0" or start with a 1.

Example
Input
2
1 2
1
-1 18
10 5
1111101010
2 -4 6 -8 10
Output
0
1111100000000000
Note

For the first test case, the binary string $$$s$$$ is "1" which corresponds to the integer $$$x = 1$$$.

  • In the first operation, $$$x$$$ is updated to $$$1 \gt \gt 1 = 0$$$.
  • In the second operation, $$$x$$$ is updated to $$$0 \lt \lt 18 = 0$$$.
The final value is $$$x = 0$$$, so the output is "0".

For the second test case, the binary string $$$s$$$ is "1111101010" which corresponds to the integer $$$x = 2026$$$.

  • In the first operation, $$$x$$$ is updated to $$$2026 \lt \lt 2 = 8104$$$.
  • In the second operation, $$$x$$$ is updated to $$$8104 \gt \gt 4 = 506$$$.
  • In the third operation, $$$x$$$ is updated to $$$506 \lt \lt 6 = 32384$$$.
  • In the fourth operation, $$$x$$$ is updated to $$$32384 \gt \gt 8 = 126$$$.
  • In the fifth operation, $$$x$$$ is updated to $$$126 \lt \lt 10 = 129024$$$.
The final value is $$$x = 129024$$$, so the output is "11111100000000000".