E. Двери и ключи
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n+1$$$ комнат, расположенных в ряд, пронумерованных от $$$1$$$ до $$$n+1$$$ слева направо. Также есть $$$n$$$ дверей, пронумерованных от $$$1$$$ до $$$n$$$, где $$$i$$$-я дверь соединяет комнаты $$$i$$$ и $$$i+1$$$. Каждая дверь $$$i$$$ имеет назначенное целое неотрицательное число $$$a_i$$$.

Вам дана бинарная строка$$$^{\text{∗}}$$$ $$$s$$$ длиной $$$n$$$. Для каждого $$$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-1$$$, если $$$i \gt 1$$$.
    • Вы можете остаться в комнате $$$i$$$.

Для любой двери, независимо от того, как она была открыта (автоматически или с помощью ключа), она останется открытой навсегда.

В любой момент вы можете носить с собой не более одного ключа. Также, хотя изначально каждая комната содержит не более одного ключа, в процессе может быть размещено несколько ключей в одной и той же комнате.

Для каждого $$$1 \le i \le n$$$ найдите минимальное количество секунд, необходимых для достижения комнаты $$$i+1$$$. Обратите внимание, что для каждого $$$i$$$ вам нужно ответить независимо.

$$$^{\text{∗}}$$$Бинарная строка — это строка, состоящая только из символов 0 и 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$$$) — целые числа, назначенные каждой двери.

Третья строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел, где $$$i$$$-е число обозначает минимальное количество секунд для достижения комнаты $$$i+1$$$.

Пример
Входные данные
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
Выходные данные
1 
3 
1 
1 2 5 6 
1 2 3 4 5 8 11 17 18 19
Примечание

В первом наборе входных данных дверь $$$1$$$ открывается в начале $$$0$$$-й секунды. Вы можете перейти в комнату $$$2$$$ в конце $$$0$$$-й секунды, таким образом, достигнув комнаты $$$2$$$ на $$$1$$$-й секунде.

Во втором наборе входных данных дверь $$$1$$$ открывается в начале $$$2$$$-й секунды. Вам нужно подождать в комнате $$$1$$$, прежде чем перейти в комнату $$$2$$$ в конце $$$2$$$-й секунды, таким образом, достигнув комнаты $$$2$$$ на $$$3$$$-й секунде.

В третьем наборе входных данных вы можете поднять ключ в комнате $$$1$$$ и использовать его, чтобы открыть дверь $$$i$$$ на $$$0$$$-й секунде, таким образом, достигнув комнаты $$$2$$$ на $$$1$$$-й секунде.