B. Berland Music
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Berland Music — это стриминговый сервис, созданный специально для поддержки локальных Берляндских исполнителей. Его разработчики в данный момент работают над модулем рекомендаций песен.

Представим, что Монокарпу порекомендовали $$$n$$$ песен, пронумерованных от $$$1$$$ до $$$n$$$. У $$$i$$$-й песни предсказанный рейтинг равен $$$p_i$$$, где $$$1 \le p_i \le n$$$ и каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз. Другими словами, $$$p$$$ — перестановка.

После прослушивания каждой песни Монокарп ее оценил — понравилась она ему или нет. Последовательность его оценок представлена строкой $$$s$$$ такой, что $$$s_i=0$$$ значит, что ему не понравилась $$$i$$$-я песня, а $$$s_i=1$$$ значит, что понравилась.

Теперь сервису надо пересчитать рейтинги песен так, чтобы:

  • новые рейтинги $$$q_1, q_2, \dots, q_n$$$ все еще были перестановкой ($$$1 \le q_i \le n$$$; каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз);
  • каждая песня, которая понравилась Монокарпу, имеет рейтинг больше каждой, которая ему не понравилась (формально, для всех $$$i, j$$$ таких, что $$$s_i=1$$$ и $$$s_j=0$$$, выполняется $$$q_i>q_j$$$).

Среди всех корректных перестановок $$$q$$$ найдите такую, у которой значение $$$\sum\limits_{i=1}^n |p_i-q_i|$$$ наименьшее, где $$$|x|$$$ — это абсолютное значение $$$x$$$.

Выведите перестановку $$$q_1, q_2, \dots, q_n$$$. Если существует несколько ответов, выведите любой из них.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество песен.

Во второй строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — перестановка предсказанных рейтингов.

Третья строка каждого набора входных данных содержит строку $$$s$$$, состоящую из $$$n$$$ символов. Каждый символ — либо $$$0$$$, либо $$$1$$$. $$$0$$$ значит, что Монокарпу не понравилась песня, а $$$1$$$ — что понравилась.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите перестановку $$$q$$$ — пересчитанные рейтинги песен. Если существует несколько ответов таких, что $$$\sum\limits_{i=1}^n |p_i-q_i|$$$ минимально, выведите любой из них.

Пример
Входные данные
3
2
1 2
10
3
3 1 2
111
8
2 3 1 8 5 4 7 6
01110001
Выходные данные
2 1
3 1 2
1 6 5 8 3 2 4 7
Примечание

В первом наборе входных данных существует только одна перестановка $$$q$$$ такая, что каждая понравившаяся песня имеет рейтинг выше, чем каждая не понравившаяся: песня $$$1$$$ получает рейтинг $$$2$$$, а песня $$$2$$$ — рейтинг $$$1$$$. $$$\sum\limits_{i=1}^n |p_i-q_i|=|1-2|+|2-1|=2$$$.

Во втором наборе входных данных Монокарпу понравились все песни, поэтому корректны все перестановки. Перестановка с минимальной суммой абсолютных разностей равна перестановке $$$p$$$. Ее стоимость равна $$$0$$$.