D. Sakurako's Hobby
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For a certain permutation $$$p$$$$$$^{\text{∗}}$$$ Sakurako calls an integer $$$j$$$ reachable from an integer $$$i$$$ if it is possible to make $$$i$$$ equal to $$$j$$$ by assigning $$$i=p_i$$$ a certain number of times.

If $$$p=[3,5,6,1,2,4]$$$, then, for example, $$$4$$$ is reachable from $$$1$$$, because: $$$i=1$$$ $$$\rightarrow$$$ $$$i=p_1=3$$$ $$$\rightarrow$$$ $$$i=p_3=6$$$ $$$\rightarrow$$$ $$$i=p_6=4$$$. Now $$$i=4$$$, so $$$4$$$ is reachable from $$$1$$$.

Each number in the permutation is colored either black or white.

Sakurako defines the function $$$F(i)$$$ as the number of black integers that are reachable from $$$i$$$.

Sakurako is interested in $$$F(i)$$$ for each $$$1\le i\le n$$$, but calculating all values becomes very difficult, so she asks you, as her good friend, to compute this.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation (the number $$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but the array contains $$$4$$$).

Input

The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$)  — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$)  — the number of elements in the array.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1\le p_i\le n$$$)  — the elements of the permutation.

The third line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of '0' and '1'. If $$$s_i=0$$$, then the number $$$p_i$$$ is colored black; if $$$s_i=1$$$, then the number $$$p_i$$$ is colored white.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers $$$F(1), F(2), \dots, F(n)$$$.

Example
Input
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
Output
1 
0 1 1 1 1 
2 2 2 2 2 
4 1 4 4 1 4 
0 1 1 0 0 1