310770: CF1884B. Haunted House

B. Haunted Housetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a number in binary representation consisting of exactly $n$ bits, possibly, with leading zeroes. For example, for $n = 5$ the number $6$ will be given as $00110$, and for $n = 4$ the number $9$ will be given as $1001$.

Let's fix some integer $i$ such that $1 \le i \le n$. In one operation you can swap any two adjacent bits in the binary representation. Your goal is to find the smallest number of operations you are required to perform to make the number divisible by $2^i$, or say that it is impossible.

Please note that for each $1 \le i \le n$ you are solving the problem independently.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the binary representation of the number.

The second line of each test case contains a string of length $n$, consisting of $0$ and $1$, — the binary representation of the number.

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

Output

For each test case, for each $1 \le i \le n$ output the smallest number of operations required to make the number divisible by $2^i$, or output $-1$ if it is impossible.

ExampleInput

6
1
1
2
01
3
010
5
10101
7
0000111
12
001011000110

Output

-1 
1 -1 
0 1 -1 
1 3 -1 -1 -1 
3 6 9 12 -1 -1 -1 
0 2 4 6 10 15 20 -1 -1 -1 -1 -1 

Note

In the first test case, we cannot swap any elements, and the number $1$ is not divisible by $2$.

In the second test case, the initial number is $1$. It is not divisible by $2$, but if we perform the operation, then we obtain the number with binary representation $10$, which is equal to $2$ in decimal representation, thus, it is divisible by $2$. But this number is not divisible by $4$ and we cannot obtain any other number using the operations.

In the third test case, the initial number is $2$. For $i = 1$ we do not have to perform any operations since the initial number is divisible by $2$. For $i = 2$ we can perform one operation swapping the first two bits (we would obtain $100$ in binary representation, which corresponds to number $4$). There is no answer for $i = 3$.

题目大意：
这个题目是关于给定一个二进制表示的数，可能包含前导零，要求通过交换任意两个相邻的位，使得该数能够被2的i次幂整除，求出最小的交换次数。如果不可能，则输出-1。对于每一个1≤i≤n，你都需要独立解决。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
接下来每个测试用例有两行：
第一行包含一个整数n（1≤n≤10^5），表示二进制数的长度。
第二行包含一个长度为n的由0和1组成的字符串，表示二进制数。
所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，对于每个1≤i≤n，输出使得数能够被2的i次幂整除的最小交换次数，或者如果不可能则输出-1。

请注意，这个翻译是根据您提供的网页内容进行的，具体的编程题目可能需要您进一步理解和分析。题目大意： 这个题目是关于给定一个二进制表示的数，可能包含前导零，要求通过交换任意两个相邻的位，使得该数能够被2的i次幂整除，求出最小的交换次数。如果不可能，则输出-1。对于每一个1≤i≤n，你都需要独立解决。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 接下来每个测试用例有两行： 第一行包含一个整数n（1≤n≤10^5），表示二进制数的长度。 第二行包含一个长度为n的由0和1组成的字符串，表示二进制数。 所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，对于每个1≤i≤n，输出使得数能够被2的i次幂整除的最小交换次数，或者如果不可能则输出-1。 请注意，这个翻译是根据您提供的网页内容进行的，具体的编程题目可能需要您进一步理解和分析。