对于某个排列 $$$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