E. Anuj's Longest Subarray
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ which is a permutation of length $$$n$$$ and a positive integer $$$k$$$ $$$(k \le 10)$$$.

For each index $$$i$$$ of the array, find the length of the longest continuous subarray (length of the subarray should be atleast $$$k$$$) containing that index, such that $$$a_i$$$ is greater than or equal to $$$k^{th}$$$ maximum element in the subarray. In other words, $$$a_i$$$ should come at $$$x^{th}$$$ position $$$(x\le k)$$$ when that subarray is sorted in descending order.

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ - the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains two integers $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ and $$$k$$$ $$$(1 \le k \le \min(n,10) )$$$ - the size of the array and the value of $$$k$$$.

The second line contains $$$n$$$ space-separated positive integers $$$a_1, a_2, a_3, ..., a_n$$$ $$$(1 \le a_i \le n)$$$ - the elements of $$$a$$$.

The sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

Output

For every test case, print $$$n$$$ space-separated positive integers where $$$i^{th}$$$ number represents the length of the longest subarray for the $$$i^{th}$$$ index of the array as described in the statement.

Example
Input
5
2 2
1 2
4 4
2 1 4 3
4 4
1 2 4 3
3 2
3 1 2
7 4
1 5 3 4 7 6 2
Output
2 2 
4 4 4 4 
4 4 4 4 
3 2 3 
4 7 5 7 7 7 4
Note

Permutation of length $$$n$$$ means permutation of first $$$n$$$ natural numbers $$$(1, 2, 3, .... , n-1, n)$$$.