I. Binary Reverser
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers, and a binary string $$$b$$$ of length $$$n$$$.

For each $$$i$$$ from $$$1$$$ to $$$n$$$ (in order), you will perform one of the following actions:

  • if $$$b_i$$$ is '0', do nothing
  • if $$$b_i$$$ is '1', reverse the prefix of length $$$i$$$, that is for each integer $$$j$$$ $$$(1 \le j \le i)$$$ , set $$$a_j = a_{i - j + 1}$$$.
Your task is to print the final array after performing all the operations.
Input

The first line of the input contains a single integer $$$tc$$$ $$$(1 \le tc \le 10^5)$$$ — the number of testcases.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$ — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ $$$(1 \le a_i \le n)$$$ — the array $$$a$$$.

The third line of each test case contains a binary string $$$b$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print the final array after performing all the operations.

Example
Input
2
3
1 2 3
111
5
4 5 1 1 2
01101
Output
3 1 2 
2 1 5 4 1