C. Phoenix and Towers-Codeforces Global Round 14

Problem - 1515C - Codeforces

C. Phoenix and Towers

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Phoenix has nn blocks of height h1,h2,…,hnh1,h2,…,hn, and all hihi don't exceed some value xx. He plans to stack all nn blocks into mm separate towers. The height of a tower is simply the sum of the heights of its blocks. For the towers to look beautiful, no two towers may have a height difference of strictly more than xx.

Please help Phoenix build mm towers that look beautiful. Each tower must have at least one block and all blocks must be used.

Input

The input consists of multiple test cases. The first line contains an integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains three integers nn, mm, and xx (1≤m≤n≤1051≤m≤n≤105; 1≤x≤1041≤x≤104) — the number of blocks, the number of towers to build, and the maximum acceptable height difference of any two towers, respectively.

The second line of each test case contains nn space-separated integers (1≤hi≤x1≤hi≤x) — the heights of the blocks.

It is guaranteed that the sum of nn over all the test cases will not exceed 105105.

Output

For each test case, if Phoenix cannot build mm towers that look beautiful, print NO. Otherwise, print YES, followed by nn integers y1,y2,…,yny1,y2,…,yn, where yiyi (1≤yi≤m1≤yi≤m) is the index of the tower that the ii-th block is placed in.

If there are multiple solutions, print any of them.

Example

input

Copy

2
5 2 3
1 2 3 1 2
4 3 3
1 1 2 3

output

Copy

YES
1 1 1 2 2
YES
1 2 2 3

Note

In the first test case, the first tower has height 1+2+3=61+2+3=6 and the second tower has height 1+2=31+2=3. Their difference is 6−3=36−3=3 which doesn't exceed x=3x=3, so the towers are beautiful.

In the second test case, the first tower has height 11, the second tower has height 1+2=31+2=3, and the third tower has height 33. The maximum height difference of any two towers is 3−1=23−1=2 which doesn't exceed x=3x=3, so the towers are

=========================================================================

就是说给出一组在x之内的整数，要求分成m个组，每组之间的差距不能超过x。我们考虑先对m个位置放置一个积木，这样有大有小，我们把公共部分全部消去，这样我们就会出现新的0，和一些小于x的数，这样我们继续填补0，填完之后我们再进行消去，消完之后又变成了这种情况，故一定是yes的，这一过程利用小根堆模拟即可

# include<iostream>
# include<algorithm>
# include<math.h>
# include<queue>

using namespace std;
typedef long long int ll;
struct node
{

    int id;

    ll sum;

    friend bool operator<(node a,node b)
    {

        return a.sum>b.sum;

    }
};

priority_queue<node>q;

int ans[100000+10];

ll a[100000+10];

int main()
{


   // n块积木，要分成m个塔，要求每个塔不能之间的差距不能超过x

   //我们把m个塔编号，记录当前高度，放入小根堆

   //每次我们取出来最小的，因为本身积木不会大于x

   //那么我们刚开始一定是把全部塔都变成了若干<=x的状态

   // 这样我们就可以消去共同部分 ，又剩下一部分零

   //继续填补，由于每次添加还是小于x,我们仍然可以在填完零

   //之后继续造0


   int t;

   cin>>t;

   while(t--)
   {

       int n,m,x;

       cin>>n>>m>>x;

       for(int i=1;i<=n;i++)
       {
           cin>>a[i];

           ans[i]=0;

       }

       while(!q.empty())
        q.pop();

       for(int i=1;i<=m;i++)
       {
           struct node now;

           now.id=i;

           now.sum=0;

           q.push(now);

       }

       int left=1;

       while(left<=n&&!q.empty())
       {
           struct node now=q.top();

           q.pop();

           ans[left]=now.id;

           now.sum+=a[left];

           left++;

           q.push(now);

       }


       cout<<"YES"<<endl;


       for(int i=1;i<=n;i++)
       {
           cout<<ans[i]<<" ";

       }

       cout<<endl;

   }



    return 0;

}