404686: GYM101608 J Efficiency Test

You built a robot that only jumps. To test its efficiency you have created a circular path that contains empty cells and walls. Your robot may stand only on empty cells and allowed to jump above at most one wall at a time.

Initially the length of the jump is k. Each time the robot fails to jump because it will not land on an empty cell, or this jump will be above more than one wall, the robot decreases the current length of the jump by one and tries again. The robot is only allowed to decrease the current length when it fails to jump, and it is not allowed to increase it again. If the length of jump reaches zero, the robot stops.

To complete the test, you will place the robot at every position on the circular path, and record the number of jumps it needs to complete a path. A path is completed if the robot jumped over each wall at least once.

You will place the robot facing to the right and it will jump in clockwise direction without changing its direction.

The first line of input contains a single integer T (1 ≤ T ≤ 128), the number of test cases.

The first line of each test case contains two space-separated integers n and k (3 ≤ n ≤ 10⁵) (2 ≤ k ≤ min{n - 1, 50}), the length of the path, and the initial length of the jump.

The second line contains a string of n characters. Each character is either '.' (an empty cell) or '#' (a wall). The given path contains at least one wall.

Cells are numbered from 1 to n in the given order. Cell number 1 is to the right of cell number n.

The sum of n overall test cases doesn't exceed 2 × 10⁶.

For each test case, print n numbers on a single line, a₁, a₂, ..., a_n, where a_i is one of the following:

• 0, if cell i is a wall.
•  - 1, if it is impossible to complete a path starting from cell i.
• Otherwise, it is equal to the minimum number of jumps needed to complete a path if the robot started from cell number i.

4
3 2
###
4 2
.#..
6 5
.#...#
10 3
.#..#...#.

0 0 0
1 0 2 -1
2 0 2 2 2 0
3 0 -1 3 0 -1 3 3 0 4