One day, you intercept a top secret message--a paper which records all the pairwise relationship between troops. You can learn from the paper that whether troop  and troop  belongs to the same legion for each . However, each piece of data has a independent probability of  being reversed.
Formally, the troop is numbered from  to , and the region is numbered from  to  . You are given  boolean numbers, indicating whether   and  belong to the same region (1 for yes and 0 for no). However, every number will be reversed(i.e., 0 to 1 and 1 to 0) in a probablity of . You can assume that the data is generated like this:



be[i] means the region that troop  belongs to. rand() can be considered as a uniform random function. i.e., select a integer from interval  with equal probability.

Note that you have already known  and , but you don't know the exact value of $m$. Please help country B construct the original data.

The input contains multiple cases. The first line of the input contains a single integer , the number of cases.

For each case, the first line of the input contains two integers  (), denoting the number of troops and the integer parameter to generate data. There is a binary string (i.e. the string only contains '0' and '1') with length  in the next line, decribing the pairwise relationship. It is arrayed like this: .

 is not given but it is guaranteed that . And the sum of  over  cases doesn't exceed .

For each case, output  integers seperated by space, the $i$-th integer describes be[i]. The value of be[i] is meaningless, so please output the solution with the smallest lexicographical order. For example, if there are 4 troops and 2 regions , you should output .

1
10 20
101110101010101010100010010101010100101010010

0 0 1 0 1 0 1 0 1 0

The sample input does not follow the input format, and it won't appear in the final test. The parameter is .