D. Хобби Сакурако
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для некоторой перестановки $$$p$$$$$$^{\text{∗}}$$$ Сакурако называет целое число $$$j$$$ достижимым из целого числа $$$i$$$, если можно сделать так, чтобы $$$i$$$ стало равным $$$j$$$, присваивая $$$i=p_i$$$ некоторое количество раз.

Если $$$p=[3,5,6,1,2,4]$$$, то, например, $$$4$$$ достижимо из $$$1$$$, потому что: $$$i=1$$$ $$$\rightarrow$$$ $$$i=p_1=3$$$ $$$\rightarrow$$$ $$$i=p_3=6$$$ $$$\rightarrow$$$ $$$i=p_6=4$$$. Теперь $$$i=4$$$, так что $$$4$$$ достижимо из $$$1$$$.

Каждое число перестановки окрашено либо в чёрный, либо в белый цвет.

Сакурако определяет функцию $$$F(i)$$$ как количество целых чисел чёрного цвета, которые достижимы из $$$i$$$.

Сакурако интересует $$$F(i)$$$ для каждого $$$1\le i\le n$$$, но вычислить все значения становится очень сложно, поэтому она просит вас, как своего хорошего друга, вычислить это.

$$$^{\text{∗}}$$$Перестановка длины $$$n$$$ — это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой (число $$$2$$$ встречается дважды в массиве), а $$$[1,3,4]$$$ также не является перестановкой ( $$$n=3$$$, но в массиве есть $$$4$$$).

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

В первой строке содержится одно целое число $$$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'. Если $$$s_i=0$$$, то число $$$p_i$$$ окрашено в чёрный цвет, если $$$s_i=1$$$, то число $$$p_i$$$ окрашено в белый цвет.

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

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$F(1), F(2), \dots, F(n)$$$.

Пример
Входные данные
5
1
1
0
5
1 2 4 5 3
10101
5
5 4 1 3 2
10011
6
3 5 6 1 2 4
010000
6
1 2 3 4 5 6
100110
Выходные данные
1 
0 1 1 1 1 
2 2 2 2 2 
4 1 4 4 1 4 
0 1 1 0 0 1