E. Doors and Keys
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$n+1$$$ rooms arranged in a line, numbered from $$$1$$$ to $$$n+1$$$ from left to right. There are also $$$n$$$ doors numbered from $$$1$$$ to $$$n$$$, where the $$$i$$$-th door connects rooms $$$i$$$ and $$$i+1$$$. Each door $$$i$$$ has an associated non-negative integer $$$a_i$$$.

You are given a binary string$$$^{\text{∗}}$$$ $$$s$$$ of length $$$n$$$. For each $$$1 \le i \le n$$$:

  • If $$$s_i=\texttt{1}$$$, then room $$$i$$$ initially contains one key.
  • Otherwise, room $$$i$$$ contains no key.

At the beginning of the $$$0$$$-th second, you are in room $$$1$$$, and all doors are closed. For each $$$k \ge 0$$$, the following events will happen in order in the $$$k$$$-th second:

  • At the beginning of the $$$k$$$-th second, all doors $$$j$$$ with $$$a_j=k$$$ will open.
  • Suppose you are in room $$$i$$$:
    • If you are not carrying any keys and there is at least one key in room $$$i$$$, you may pick it up and carry it with you.
    • If you are carrying a key, you may drop it in room $$$i$$$.
  • At the end of the $$$k$$$-th second:
    • You may move to room $$$i+1$$$. If door $$$i$$$ is still closed, you have to be carrying a key to move to room $$$i+1$$$. The key will be consumed after use, and door $$$i$$$ will open.
    • You may move to room $$$i-1$$$ if $$$i \gt 1$$$.
    • You may stay in room $$$i$$$.

For any door, no matter how it was opened (automatically or with a key), it will remain open forever.

At any moment, you may carry with you at most one key. Also, even though initially each room contains at most one key, during the process, multiple keys may be placed in the same room.

For each $$$1 \le i \le n$$$, find the minimum number of seconds required to reach room $$$i+1$$$. Note that the answers to each $$$i$$$ are independent.

$$$^{\text{∗}}$$$A binary string is a string consisting of only 0 or 1.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of doors.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$) — the integers associated with each door.

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers, where the $$$i$$$-th integer represents the minimum number of seconds to reach room $$$i+1$$$.

Example
Input
5
1
0
0
1
2
0
1
114514
1
4
0 9 10 9
1101
10
0 1 4 2 3 14 10 18 7 25
1110000001
Output
1 
3 
1 
1 2 5 6 
1 2 3 4 5 8 11 17 18 19
Note

In the first test case, door $$$1$$$ opens at the beginning of the $$$0$$$-th second. You can move to room $$$2$$$ at the end of the $$$0$$$-th second, thus reaching room $$$2$$$ at the $$$1$$$-st second.

In the second test case, door $$$1$$$ opens at the beginning of the $$$2$$$-nd second. You have to wait in room $$$1$$$ before moving to room $$$2$$$ at the end of the $$$2$$$-nd second, thus reaching room $$$2$$$ at the $$$3$$$-rd second.

In the third test case, you may pick up the key in room $$$1$$$ and use it to open door $$$i$$$ in the $$$0$$$-th second, thus reaching room $$$2$$$ at the $$$1$$$-st second.