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 ≤ 105) (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 × 106.
For each test case, print n numbers on a single line, a1, a2, ..., an, where ai is one of the following:
## Input
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 ≤ 105) (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 × 106.
## Output
For each test case, print n numbers on a single line, a1, a2, ..., an, where ai 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.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $ be the length of the circular path.
- Let $ k \in \mathbb{Z} $ be the initial jump length.
- Let $ s \in \{., \#\}^n $ be the string representing the path, where $ s_i = \# $ denotes a wall at position $ i $, and $ s_i = . $ denotes an empty cell.
- The path is circular: position $ i+1 $ follows position $ i $, and position $ 1 $ follows position $ n $.
- The robot starts at position $ i \in \{1, \dots, n\} $ facing right (clockwise), with initial jump length $ k $.
- The robot jumps in clockwise direction; a jump of length $ \ell $ moves from position $ p $ to position $ (p + \ell - 1) \bmod n + 1 $.
- A jump of length $ \ell $ is valid only if:
- The landing cell is empty ($ s_{(p + \ell - 1) \bmod n + 1} = . $),
- The jump crosses at most one wall (i.e., among the $ \ell $ consecutive cells starting at $ p $, at most one is $ \# $, excluding the starting cell).
- On failure, the robot decrements $ \ell $ by 1; it cannot increase $ \ell $.
- The robot stops when $ \ell = 0 $.
- A test is completed if the robot has jumped over *at least one* wall during its sequence of jumps.
- For each starting position $ i $, let $ a_i \in \mathbb{Z}_{\ge 0} $ be the number of successful jumps before stopping, or $ 0 $ if the robot never completes the test (i.e., never jumps over any wall).
**Constraints**
1. $ 1 \le T \le 128 $
2. $ 3 \le n \le 10^5 $, $ 2 \le k \le \min\{n-1, 50\} $
3. $ s $ contains at least one $ \# $
4. $ \sum_{\text{test cases}} n \le 2 \times 10^6 $
**Objective**
For each test case, output $ a_1, a_2, \dots, a_n $, where $ a_i $ is the number of successful jumps made by the robot starting at position $ i $, before it either stops (jump length reaches 0) or completes the test (has jumped over at least one wall).