F. Binary Bubble Sort Inversions
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Define performing a bubble on an array $$$b_1, b_2, \ldots, b_m$$$ to be performing the following action:

  • For each integer $$$i$$$ ($$$1 \leq i \lt m$$$) in order, if $$$b_i \gt b_{i+1}$$$, swap $$$b_i$$$ and $$$b_{i+1}$$$.
Define performing a reverse bubble on an array $$$b_1, b_2, \ldots, b_m$$$ to be performing the following action:
  • For each integer $$$i$$$ ($$$1 \leq i \lt m$$$) in reverse order, if $$$b_i \gt b_{i+1}$$$, swap $$$b_i$$$ and $$$b_{i+1}$$$.

For example, if we perform a bubble on $$$[1, 1, 0]$$$, we would transform it as follows: $$$[\color{red}{1, 1}, 0] \to [1, \color{red}{1, 0}] \to [1, 0, 1]$$$. If we perform a reverse bubble on $$$[1, 1, 0]$$$, we would transform it as follows: $$$[1, \color{red}{1, 0}] \to[\color{red}{1, 0}, 1] \to [0, 1, 1]$$$.

You are given an array $$$a_1, a_2, \ldots, a_n$$$ consisting of only 0s and 1s and a binary string$$$^{\text{∗}}$$$ $$$s$$$ of length $$$n$$$. You perform $$$n$$$ operations in order, where the $$$i$$$-th operation performs a bubble on $$$a$$$ if $$$s_i = \texttt{1}$$$ and performs a reverse bubble on $$$a$$$ if $$$s_i = \texttt{0}$$$. For each of the $$$n + 1$$$ states of $$$a$$$ — before any operations have been performed and after each operation — count the number of inversions$$$^{\text{†}}$$$ in $$$a$$$.

$$$^{\text{∗}}$$$A binary string is a string that only contains 0s and 1s.

$$$^{\text{†}}$$$An inversion in an array $$$c$$$ of length $$$m$$$ is a pair of indices $$$i, j$$$ such that $$$1 \leq i \lt j \leq m$$$ and $$$c_i \gt c_j$$$.

Input

The first line of each input contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — the length of $$$a$$$ and $$$s$$$.

The second line of each test case contains $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$) — the array $$$a$$$.

The third line of each test case contains $$$s$$$ ($$$s_i \in \{0, 1\}$$$, $$$|s| = n$$$$$$^{\text{∗}}$$$) — the binary string $$$s$$$.

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

$$$^{\text{∗}}$$$$$$|c|$$$ denotes the length of a string $$$c$$$.

Output

For each test case, output $$$n + 1$$$ space separated integers, the $$$i$$$-th integer denoting the number of inversions in $$$a$$$ after the first $$$i - 1$$$ operations have been performed.

Example
Input
7
4
1 1 0 0
1010
7
0 1 0 1 1 0 0
0101001
4
0 0 1 1
1001
1
1
1
5
0 1 1 0 0
11101
3
1 0 0
000
6
1 0 1 1 0 0
011000
Output
4 2 1 0 0 
7 4 2 0 0 0 0 0 
0 0 0 0 0 
0 0 
4 2 0 0 0 0 
2 1 0 0 
7 4 2 1 0 0 0
Note

In the first test case:

  • Before any operations: $$$a = [1, 1, 0, 0]$$$, which has $$$4$$$ inversions.
  • After the first operation: $$$a = [1, 0, 0, 1]$$$, which has $$$2$$$ inversions.
  • After the second operation: $$$a = [0, 1, 0, 1]$$$, which has $$$1$$$ inversion.
  • After the third operation: $$$a = [0, 0, 1, 1]$$$, which has $$$0$$$ inversions.
  • After the fourth operation: $$$a = [0, 0, 1, 1]$$$, which has $$$0$$$ inversions.