← 返回题目列表

Codeforces · 2008/D

D. 樱子的爱好

中文机器翻译题面 查看原题

对于某个排列 $$$p$$$$$$^{\text{∗}}$$$ 如果可以通过分配 $$$i=p_i$$$ 一定次数来使 $$$i$$$ 等于 $$$j$$$ ,那么 Sakurako 调用从整数 $$$i$$$ 可达的整数 $$$j$$$ 。

如果 $$$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$$$到达。

排列中的每个数字都是黑色或白色。

Sakurako 将函数 $$$F(i)$$$ 定义为从 $$$i$$$ 可到达的黑色整数的数量。

Sakurako 对每个 $$$1\le i\le n$$$ 的 $$$F(i)$$$ 感兴趣,但是计算所有值变得非常困难,所以她要求你,作为她的好朋友,来计算这个。

输入

第一行包含一个整数 $$$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$$$) — 排列的元素。

每个测试用例的第三行包含一个长度为$$$n$$$的字符串$$$s$$$,由'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)$$$。

示例

输入 #1

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

1 
0 1 1 1 1 
2 2 2 2 2 
4 1 4 4 1 4 
0 1 1 0 0 1