You're given a permutation aaa of length nnn (1≤n≤1051 \le n \le 10^51≤n≤105).

For each i∈[1,n]i \in [1,n]i∈[1,n], construct a sequence sis_isi​ by the following rules:

  1. si[1]=is_i[1]=isi​[1]=i;
  2. The length of sis_isi​ is nnn, and for each j∈[2,n]j \in [2, n]j∈[2,n], si[j]≤si[j−1]s_i[j] \le s_i[j-1]si​[j]≤si​[j−1];
  3. First, we must choose all the possible elements of sis_isi​ from permutation aaa. If the index of si[j]s_i[j]si​[j] in permutation aaa is pos[j]pos[j]pos[j], for each j≥2j \ge 2j≥2, ∣pos[j]−pos[j−1]∣≤k|pos[j]-pos[j-1]|\le k∣pos[j]−pos[j−1]∣≤k (1≤k≤1051 \le k \le 10^51≤k≤105). And for each sis_isi​, every element of sis_isi​ must occur in aaa at most once.
  4. After we choose all possible elements for sis_isi​, if the length of sis_isi​ is smaller than nnn, the value of every undetermined element of sis_isi​ is 000;
  5. For each sis_isi​, we must make its weight high enough.

Consider two sequences C=[c1,c2,...cn]C = [c_1, c_2, ... c_n]C=[c1​,c2​,...cn​] and D=[d1,d2,...,dn]D=[d_1, d_2, ..., d_n]D=[d1​,d2​,...,dn​], we say the weight of CCC is higher than that of DDD if and only if there exists an integer kkk such that 1≤k≤n1 \le k \le n1≤k≤n, ci=dic_i=d_ici​=di​ for all 1≤i<k1 \le i < k1≤i<k, and ck>dkc_k > d_kck​>dk​.

If for each i∈[1,n]i \in [1,n]i∈[1,n], ci=dic_i=d_ici​=di​, the weight of CCC is equal to the weight of DDD.

For each i∈[1,n]i \in [1,n]i∈[1,n], print the number of non-zero elements of sis_isi​ separated by a space.

It's guaranteed that there is only one possible answer.

Input

There are multiple test cases.

The first line contains one integer T(1≤T≤20)T(1 \le T \le 20)T(1≤T≤20), denoting the number of test cases.

Each test case contains two lines, the first line contains two integers nnn and kkk (1≤n,k≤1051 \le n,k \le 10^51≤n,k≤105), the second line contains nnn distinct integers a1,a2,...,ana_1, a_2, ..., a_na1​,a2​,...,an​ (1≤ai≤n1 \le a_i \le n1≤ai​≤n) separated by a space, which is the permutation aaa.

Output

For each test case, print one line consists of nnn integers ∣s1∣,∣s2∣,...,∣sn∣|s_1|, |s_2|, ..., |s_n|∣s1​∣,∣s2​∣,...,∣sn​∣ separated by a space.

∣si∣|s_i|∣si​∣ is the number of non-zero elements of sequence sis_isi​.

There is no space at the end of the line.

样例输入复制

2
3 1
3 2 1
7 2
3 1 4 6 2 5 7

样例输出复制

1 2 3
1 1 2 3 2 3 3

题意：

给定一个1到n的排列，求n个子序列，每个里有多少非零元素，第i个子序列满足：

1.长度为n

2.第一个元素为i

3.子序列中每个元素在原序列中至少出现一次

4.从第2个元素开始，每个元素从原序列中找

5.子序列递减（因为原排列中不会有重复的元素）

6.子序列字典序尽量大

7.子序列中每两个相邻的元素在原序列中的下标差值<=k

8.当无法再在原序列中找到满足题意的元素后，不足n个元素用0补齐

 

暴力给过QwQ

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+30;
int a[N];
int pre[N];
int mp[N];
int main()
{
    int t,n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            mp[a[i]]=i;
        }
        pre[0]=0;
        for(int i=1;i<=n;i++)
        {
            int id=mp[i];
            pre[i]=1;
            int maxx=0;
            for(int j=i-1;j>=1;j--)
            {
                if(abs(mp[j]-id)<=k)
                {
                    maxx=j;
                    break;
                }
            }
            pre[i]+=pre[maxx];
            cout<<pre[i];
            if(i<n)
                cout<<' ';
        }
        cout<<'\n';
    }
    return 0;
}