有$$$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$$$ 秒开始时,所有 $$$j$$$ 且 $$$a_j=k$$$ 的门都会打开。
- 假设您在 $$$i$$$ 房间:
- 如果您没有携带任何钥匙,并且 $$$i$$$ 房间中至少有一把钥匙,您可以拿起它并随身携带。
- 如果您携带钥匙,您可以将其放在房间 $$$i$$$ 中。
- 在第 $$$k$$$ 秒结束时:
- 您可以搬到$$$i+1$$$房间。如果$$$i$$$ 门仍然关闭,您必须携带钥匙才能进入$$$i+1$$$ 房间。使用后钥匙将被消耗,门$$$i$$$将打开。
- 如果$$$i \gt 1$$$,你可以移动到房间$$$i-1$$$。
- 您可以入住 $$$i$$$ 房间。
对于任何门,无论它是如何打开的(自动或用钥匙),它都会永远保持打开状态。
您可以随时随身携带 最多 1 个 键。此外,尽管最初每个房间最多包含一把钥匙,但在此过程中,同一个房间中可能会放置多把钥匙。
对于每个 $$$1 \le i \le n$$$,找到到达房间 $$$i+1$$$ 所需的最少秒数。请注意,每个 $$$i$$$ 的答案是 独立.
$$$^{\text{*}}$$$二进制字符串是仅由 0 or 1.
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出 $$$n$$$ 个整数,其中第 $$$i$$$ 个整数表示到达 $$$i+1$$$ 房间的最小秒数。
示例
输入复制
51001201114514140 9 10 91101100 1 4 2 3 14 10 18 7 251110000001
输出复制
1311 2 5 61 2 3 4 5 8 11 17 18 19
注意
在第一个测试用例中,门 $$$1$$$ 在第 $$$0$$$ 秒开始时打开。您可以在第 $$$0$$$ 秒结束时移动到 $$$2$$$ 房间,从而在第 $$$1$$$ 秒到达 $$$2$$$ 房间。
在第二个测试用例中,门 $$$1$$$ 在第 $$$2$$$-nd 秒开始时打开。您必须在 $$$1$$$ 房间等待,然后在 $$$2$$$-nd 秒结束时移动到 $$$2$$$ 房间,从而在 $$$3$$$-rd 第二秒到达 $$$2$$$ 房间。
在第三个测试用例中,您可以在$$$1$$$房间中拿起钥匙,并用它在第$$$0$$$秒打开门$$$i$$$,从而在第$$$1$$$秒到达$$$2$$$房间。