CF2187E.Doors and Keys

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.

有 $n+1$ 个房间排成一行，从左到右编号为 $1$ 到 $n+1$。另有 $n$ 扇门，编号为 $1$ 到 $n$，其中第 $i$ 扇门连接房间 $i$ 和 $i+1$。每扇门 $i$ 关联一个非负整数 $a_i$。

给定一个长度为 $n$ 的二进制字符串$^{\text{∗}}$ $s$。对每个 $1 \le i \le n$：

• 若 $s_i=\texttt{1}$，则房间 $i$ 初始时包含一把钥匙；
• 否则，房间 $i$ 不含钥匙。

在第 $0$ 秒初，你位于房间 $1$，且所有门均处于关闭状态。对每个 $k \ge 0$，在第 $k$ 秒内将按如下顺序发生以下事件：

• 在第 $k$ 秒初，所有满足 $a_j=k$ 的门 $j$ 将自动开启；
• 假设你当前位于房间 $i$：
  • 若你未携带任何钥匙，且房间 $i$ 中至少有一把钥匙，则你可以拾取其中一把并随身携带；
  • 若你正携带一把钥匙，则你可以将其丢弃在房间 $i$ 中；
• 在第 $k$ 秒末：
  • 你可以移动至房间 $i+1$；若门 $i$ 仍处于关闭状态，则你必须携带一把钥匙才能通过，且该钥匙将在使用后被消耗，同时门 $i$ 将开启；
  • 若 $i > 1$，你可以移动至房间 $i-1$；
  • 你可以停留在房间 $i$ 中。

对于任意一扇门，无论其是自动开启还是通过使用钥匙开启，一旦开启，将永远保持开启状态。

在任意时刻，你最多只能携带一把钥匙。此外，尽管初始时每个房间至多含有一把钥匙，但在整个过程中，同一房间中可能放置多把钥匙。

对每个 $1 \le i \le n$，求到达房间 $i+1$ 所需的最少秒数。注意：各 $i$ 对应的答案相互独立。

$^{\text{∗}}$二进制字符串是指仅由字符 0 或 1 组成的字符串。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 门的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \le 2 \cdot 10^5$）—— 与每扇门关联的整数。

每个测试用例的第三行包含一个长度为 $n$ 的二进制字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出 $n$ 个整数，其中第 $i$ 个整数表示到达房间 $i+1$ 所需的最少秒数。

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.

在第一个测试用例中，门 $1$ 在第 $0$ 秒初开启。你可在第 $0$ 秒末移动至房间 $2$，从而于第 $1$ 秒到达房间 $2$。

在第二个测试用例中，门 $1$ 在第 $2$ 秒初开启。你必须先在房间 $1$ 中等待，再于第 $2$ 秒末移至房间 $2$，从而于第 $3$ 秒到达房间 $2$。

在第三个测试用例中，你可在第 $0$ 秒于房间 $1$ 拾取钥匙，并立即用其开启门 $i$，从而于第 $1$ 秒到达房间 $2$。