codeforces509B

Painting Pebbles

There are n piles of pebbles on the table, the i-th pile contains a_i pebbles. Your task is to paint each pebble using one of the k given colors so that for each color c and any two piles i and j the difference between the number of pebbles of color cin pile i and number of pebbles of color c in pile j is at most one.

In other words, let's say that b_i, c is the number of pebbles of color c in the i-th pile. Then for any 1 ≤ c ≤ k, 1 ≤ i, j ≤ n the following condition must be satisfied |b_i, c - b_j, c| ≤ 1. It isn't necessary to use all k colors: if color c hasn't been used in pile i, then b_i, c is considered to be zero.

Input

The first line of the input contains positive integers n and k (1 ≤ n, k ≤ 100), separated by a space — the number of piles and the number of colors respectively.

The second line contains n positive integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 100) denoting number of pebbles in each of the piles.

Output

If there is no way to paint the pebbles satisfying the given condition, output "NO" (without quotes) .

Otherwise in the first line output "YES" (without quotes). Then n lines should follow, the i-th of them should contain a_i space-separated integers. j-th (1 ≤ j ≤ a_i) of these integers should be equal to the color of the j-th pebble in the i-th pile. If there are several possible answers, you may output any of them.

Examples

Input

4 4
1 2 3 4

Output

Input

5 2
3 2 4 1 3

Output

NO

Input

5 4
3 2 4 3 5

Output

YES
1 2 3
1 3
1 2 3 4
1 3 4
1 1 2 3 4

sol：构造题真好van♂
容易发现，当一个ai和aj的差大于K时，就无法构造出一个方案使得ai和aj满足条件；
证明：容易发现（XJB乱玩）每个堆中染得尽量平均一定是最优的，所以就有上面的东西了
这样就可以判断无解了，同理构造的时候也只要平均分配一轮轮K循环直到涂满就可以了

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=105;
int n,K;
struct Record
{
    int Size,Id;
    int Ans[N];
}a[N];
inline bool cmp_Size(Record p,Record q)
{
    return p.Size<q.Size;
}
inline bool cmp_Id(Record p,Record q)
{
    return p.Id<q.Id;
}
int main()
{
    int i,j,Now=0;
    R(n); R(K);
    for(i=1;i<=n;i++) R(a[a[i].Id=i].Size);
    sort(a+1,a+n+1,cmp_Size);
    if(a[n].Size-a[1].Size>K) return 0*puts("NO");
    puts("YES");
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=a[i].Size;j++) a[i].Ans[j]=j%K+1;
    }
    sort(a+1,a+n+1,cmp_Id);
    for(i=1;i<=n;i++)
    {
        sort(a[i].Ans+1,a[i].Ans+a[i].Size+1);
        for(j=1;j<=a[i].Size;j++) W(a[i].Ans[j]);
        puts("");
    }
    return 0;
}
/*
input
4 4
1 2 3 4
output
YES

input
5 2
3 2 4 1 3
output
NO

input
5 4
3 2 4 3 5
output
YES

input
4 3
5 6 7 8
output
YES
*/

View Code