Recently Monocarp got a job. His working day lasts exactly $m$ minutes. During work, Monocarp wants to drink coffee at certain moments: there are $n$ minutes $a_1, a_2, \dots, a_n$, when he is able and willing to take a coffee break (for the sake of simplicity let's consider that each coffee break lasts exactly one minute). 

However, Monocarp's boss doesn't like when Monocarp takes his coffee breaks too often. So for the given coffee break that is going to be on minute $a_i$, Monocarp must choose the day in which he will drink coffee during the said minute, so that every day at least $d$ minutes pass between any two coffee breaks. Monocarp also wants to take these $n$ coffee breaks in a minimum possible number of working days (he doesn't count days when he is not at work, and he doesn't take coffee breaks on such days). Take into account that more than $d$ minutes pass between the end of any working day and the start of the following working day.

For each of the $n$ given minutes determine the day, during which Monocarp should take a coffee break in this minute. You have to minimize the number of days spent. 


-----Input-----

The first line contains three integers $n$, $m$, $d$ $(1 \le n \le 2\cdot10^{5}, n \le m \le 10^{9}, 1 \le d \le m)$ — the number of coffee breaks Monocarp wants to have, the length of each working day, and the minimum number of minutes between any two consecutive coffee breaks.

The second line contains $n$ distinct integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le m)$, where $a_i$ is some minute when Monocarp wants to have a coffee break.


-----Output-----

In the first line, write the minimum number of days required to make a coffee break in each of the $n$ given minutes. 

In the second line, print $n$ space separated integers. The $i$-th of integers should be the index of the day during which Monocarp should have a coffee break at minute $a_i$. Days are numbered from $1$. If there are multiple optimal solutions, you may print any of them.


-----Examples-----
Input
4 5 3
3 5 1 2

Output
3
3 1 1 2 

Input
10 10 1
10 5 7 4 6 3 2 1 9 8

Output
2
2 1 1 2 2 1 2 1 1 2 



-----Note-----

In the first example, Monocarp can take two coffee breaks during the first day (during minutes $1$ and $5$, $3$ minutes will pass between these breaks). One break during the second day (at minute $2$), and one break during the third day (at minute $3$).

In the second example, Monocarp can determine the day of the break as follows: if the minute when he wants to take a break is odd, then this break is on the first day, if it is even, then this break is on the second day.

Difficulty: interview

Starter code:

Solutions:
from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque
from collections import Counter


def read():
    return int(input())


def readmap():
    return map(int, input().split())


def readlist():
    return list(map(int, input().split()))


n, m, d = readmap()
A = readlist()
Aind = dict([(A[i], i) for i in range(n)])
A.sort()

q = deque()
a = A[0]
ans = [0] * n
ans[Aind[a]] = 1
maxday = 1

q.append((a, 1))
for i in range(1, n):
    if A[i] > q[0][0] + d:
        ans[Aind[A[i]]] = q[0][1]
        q.append((A[i], q[0][1]))
        q.popleft()
    else:
        maxday += 1
        ans[Aind[A[i]]] = maxday
        q.append((A[i], maxday))

print(maxday)
print(" ".join(list(map(str, ans))))

n, m, d = list(map(int, input().split()))
breaks = list(map(int, input().split()))

breaks_S = sorted(breaks)
index_s = [i[0] for i in sorted(enumerate(breaks), key=lambda x:x[1])]

d += 1

answer = [-1] * n

x = 1


for i in range(n):
	while True:
		if i >= x and breaks_S[i] - breaks_S[i - x] < d:
			x += 1
		elif n - i > x and breaks_S[i + x] - breaks_S[i] < d:
			x += 1
		else:
			break


for i in range(n):
	answer[index_s[i]] = i % x + 1


print(x)
print(*answer)






n,m,d=list(map(int,input().split()))
arr=list(map(int,input().split()))
arrx=[]
for i in range(n):
    arrx.append((arr[i],i))
arrx.sort()
arr1=[0]*n
arr1[arrx[0][1]]=1
count=1
index=0
for i in range(1,n):
    if(arrx[i][0]>=arrx[index][0]+d+1):
        arr1[arrx[i][1]]=arr1[arrx[index][1]]
        index+=1
    else:
        count+=1
        arr1[arrx[i][1]]=count
print(count)
print(*arr1)




from collections import deque


def follow(idx, this_or_first_free):
    if idx == -2:
        return -2

    if this_or_first_free[idx] == -1:
        return idx
    if this_or_first_free[idx] == -2:
        return -2

    root = follow(this_or_first_free[idx], this_or_first_free)
    this_or_first_free[idx] = root
    return root


def take(idx, this_or_first_free, initial_next):
    this_or_first_free[idx] = initial_next[idx]  # this can be -2 or an index to follow


def legit(idx):
    return idx != -1 and idx != -2


(n, m, d) = list(map(int, input().split()))
break_list = list([(int(idx_val[1]), idx_val[0]) for idx_val in enumerate(input().split())])

break_list.sort()

assignment = [-1] * n
breaks_initial_next = [-2] * n

TFO = [False] * n

deq = deque()
for i in range(n):
    val = break_list[i][0]  # pos of this break
    deq.append((val, i))  # append the pos and its index in the array

    while len(deq) > 0 and val - deq[0][0] - 1 >= d:
        breaks_initial_next[deq[0][1]] = i
        deq.popleft()

head_initial_next = [i + 1 for i in range(n)]
head_initial_next[-1] = -2
head_first_free = [-1] * n

first_not_taken = 0
days_count = 0
while legit(first_not_taken):
    current = first_not_taken
    days_count += 1

    while legit(current):
        take(current, head_first_free, head_initial_next)  # invalidate head
        assignment[break_list[current][1]] = days_count

        if not TFO[current]:
            TFO[current] = True
            current = breaks_initial_next[current]

        current = follow(current, head_first_free)

    first_not_taken = follow(first_not_taken, head_first_free)  # find next head

print(days_count)
print(str(assignment)[1:-1].replace(",", ""))


def check(p):
    for i in range(n - p):
        if a[i + p] - a[i] - 1 < d:
            return False
    
    return True


def binSearch(a, b):
    left, right = a - 1, b + 1

    while right - left > 1:
        mid = (left + right) // 2

        if check(mid):
            right = mid

        else:
            left = mid

    return right


n, m, d = map(int, input().split())
a = list(map(int, input().split()))

a_ind = {i: a[i] for i in range(n)}
a.sort()

b = binSearch(1, n)
ans = {el: 0 for el in a}

for i, el in enumerate(a, 1):
    ans[el] = (i - 1) % b + 1

print(b)
print(' '.join(map(str, [ans[a_ind[i]] for i in range(n)])))

n , m , d = map(int,input().split())
a = list(map(int,input().split()))
id = {a[i] : i for i in range(n)}

a.sort()

#for i in range(0,n) :
#    print(i , a[i] , id[i])

def Solve(x) :
    for i in range(x,n) :
        if (a[i] - a[i-x]) <= d :
            return False
    return True

l = 1
r = n
while l < r :
    mid = int((l+r)/2)
    if Solve(mid) :
        r = mid
    else :
        l = mid + 1
ans = [0 for i in range(n)]
for i in range(n) :
    ans[id[a[i]]] = (i % l) + 1
print(l)
print(' '.join(map(str, ans)))

from collections import deque


def main():
    n, m, d = list(map(int, input().split()))
    aa = list(map(int, input().split()))
    q, cnt = deque(((-d, 1),)), 1
    for i in sorted(list(range(n)), key=aa.__getitem__):
        a = aa[i]
        b, j = q.popleft()
        if a <= b + d:
            q.appendleft((b, j))
            j = cnt = cnt + 1
        aa[i] = j
        q.append((a, j))
    print(cnt)
    print(' '.join(list(map(str, aa))))


def __starting_point():
    main()

__starting_point()

import heapq
n, m, d = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = []
a = [(x,i) for i,x in enumerate(a)]
a.sort()
heap = []
day = 0
for b, i in a:
	found = False
	if len(heap) > 0:
		if heap[0][0] + d < b:
			heapq.heappush(heap, (b,i,heap[0][2]))
			ans.append(heapq.heappop(heap))
			found = True
	if not found:
		heapq.heappush(heap, (b,i,day+1))
		day += 1
for t in heap:
	ans.append(t)
idx = [0]*n
print(day)
for i in range(len(ans)):
	idx[ans[i][1]] = ans[i][2]
for i in idx:
	print(i, end=' ')

from operator import itemgetter
n,m,d = map(int,input().split())
ai = list(map(int,input().split()))
ai2 = [[ai[i],i] for i in range(n)]
d += 1
ai2.sort(key = itemgetter(0))
ai4 = [0] * n
ai5 = [0] * n
ai4[0] = ai2[0][0]
ai5[0] = 1
ai[ai2[0][1]] = 1
j = 1
i = 1
z = 0
while i < n:
    if ai2[i][0] < ai4[z] + d:
        ai4[j + z] = ai2[i][0]
        ai5[j + z] = j + 1
        j += 1
        ai[ai2[i][1]] = j
    else:
        ai4[j + z] = ai2[i][0]
        ai5[j + z] = ai5[z]
        ai[ai2[i][1]] = ai5[z]
        z += 1
    i += 1
print(j)
for i in range(n):
    print(ai[i],end=" ")


from collections import Counter, defaultdict, deque
read = lambda: list(map(int,input().split()))

def solve(a,d,df):
    cnt = 1
    res = [0] * n
    Q = deque([(a[0], cnt)])
    res[df[a[0]]] = 1
    for i in range(1,n):
        if a[i] > Q[0][0] + d:
            val, day = Q.popleft()
            res[df[a[i]]] = day
            Q.append((a[i], day))
        else:
            cnt += 1
            res[df[a[i]]] = cnt
            Q.append((a[i], cnt))
    print(cnt)
    print(' '.join(map(str, res)))

n,m,d = read()
a = read()
df = {v:i for i,v in enumerate(a)}
a.sort()
solve(a,d,df)

import math
import sys
from bisect import bisect_right, bisect_left, insort_right
from collections import Counter, defaultdict
from heapq import heappop, heappush
from itertools import accumulate
from sys import stdout

R = lambda: map(int, input().split())
n, m, d = R()
a = sorted((x, i) for i, x in enumerate(R()))
res = [-1] * len(a)
res[0] = 0
cnt = 0
q = [(a[0][0], 0)]
for r in range(1, n):
    h = heappop(q)
    if a[r][0] - h[0] > d:
        res[r] = h[1]
    else:
        cnt += 1
        res[r] = cnt
        heappush(q, h)
    heappush(q, (a[r][0], res[r]))
print(max(res) + 1)
for t in sorted(zip(a, res), key=lambda x: x[0][1]):
    print(t[1] + 1, end=' ')


R = lambda: map(int, input().split())
n, m, d = R()
a = sorted((x, i) for i, x in enumerate(R()))
res = [-1] * len(a)
res[0] = 0
cnt = 0
l = 0
for r in range(1, n):
    if a[r][0] - d <= a[l][0]:
        cnt += 1
        res[r] = cnt
    else:
        res[r] = res[l]
        l += 1
print(max(res) + 1)
for t in sorted(zip(a, res), key=lambda x: x[0][1]):
    print(t[1] + 1, end=' ')

n,m,d=map(int,input().split())
a=list(map(int,input().split()))
o=[0]*n
x=[(a[i],i) for i in range(n)]
x.sort()
u=0
i=j=0
while i<n:
    if x[i][0]-d<=x[j][0]:u+=1;o[x[i][1]]=u
    else:o[x[i][1]]=o[x[j][1]];j+=1
    i+=1
print(u)
print(' '.join(list(map(str,o))))

a,b,c=list(map(int,input().split()))
l=list(map(int,input().split()))
l1=[(l[i],i) for i in range(a)]
otv=[0]*a
l1=sorted(l1,key=lambda x:x[0])
i=j=0
k=0
for i in range(a) :
    if l1[i][0]-c<=l1[j][0] :
        k+=1
        otv[l1[i][1]]=k
    else :
        otv[l1[i][1]]=otv[l1[j][1]]
        j+=1
print(k)
print(" ".join(map(str,otv)))
        


n, m, k = list(map(int, input().split()))
l = list(map(int, input().split()))
for i in range(n):
    l[i] = [l[i], i]
l.sort()

uk1 = 1
uk2 = n

def pos(n):
    cnt = [-10000000001] * len(l)
    nonlocal k
    for i in range(len(l)):
        if l[i][0] - cnt[i % n] <= k:
            return False
        else:
            cnt[i % n] = l[i][0]

    return True
while uk2 - uk1 > 1:
    if pos((uk2 + uk1) // 2):
        uk2 = (uk1 + uk2) // 2
    else:
        uk1 = (uk1 + uk2) // 2

ans = [0] * n
if not pos(uk1):
    for i in range(n):
        ans[l[i][1]] = i % uk2 + 1
    print(uk2)
    for i in range(n):
        print(ans[i], end =' ')
else:
    for i in range(n):
        ans[l[i][1]] = i % uk1 + 1
    print(uk1)
    for i in range(n):
        print(ans[i], end =' ')

n, work, gap = list(map(int, input().split()))
a = list(map(int, input().split()))
a = sorted([(a[i], i) for i in range(n)])
ret = [0] * n
day = 0
left = right = 0
while right < n:
    if a[right][0] - a[left][0] <= gap:
        day += 1
        ret[a[right][1]] = day
    else:
        ret[a[right][1]] = ret[a[left][1]]
        left += 1
    right += 1
print(day)
print(*ret)


a,b,c=map(int,input().split())
l=list(map(int,input().split()))
l1=[(l[i],i) for i in range(a)]
otv=[0]*a
l1=sorted(l1,key=lambda x:x[0])
i=j=0
k=0
for i in range(a) :
    if l1[i][0]-c<=l1[j][0] :
        k+=1
        otv[l1[i][1]]=k
    else :
        otv[l1[i][1]]=otv[l1[j][1]]
        j+=1
    # print(j,i)
print(k)
print(" ".join(map(str,otv)))

n,m,D=map(int,input().split())
lst=[*map(int,input().split())]
d={}
for i,x in enumerate(lst):d[x]=i
lst.sort()
res,j,result=[0]*n,0,0
for i,x in enumerate(lst):
    if x-lst[j]>D:
        res[d[x]]=res[d[lst[j]]]
        j+=1
    else:
        result+=1
        res[d[x]]=result
print(result)
print(*res)

n,m,D=map(int,input().split())
lst=[*map(int,input().split())]
d={x:i for i,x in enumerate(lst)}
lst.sort()
res,j,result=[0]*n,0,0
for i,x in enumerate(lst):
    if x-lst[j]>D:
        res[d[x]]=res[d[lst[j]]]
        j+=1
    else:
        result+=1
        res[d[x]]=result
print(result)
print(*res)

n , m , d = map(int , input().split())
a = list(map(int , input().split()))
a = sorted([(a[i] , i) for i in range(n)])

right = 0
left = 0
day = 0
ret = [0] * n
while right < n :
    if a[right][0] - a[left][0] <= d :
        day += 1
        ret[a[right][1]] = day
    else :
        ret[a[right][1]] = ret[a[left][1]]
        left += 1
    right += 1
print(day)
print(*ret)

n,m,d = list(map(int,input().split()))
lis = list(map(int,input().split()))
l1=[[lis[i],i] for i in range(n)]
l1.sort()
ans=[0]*n
#print(l1)
j=k=0
for i in range(n):
    if l1[i][0]-l1[j][0]<=d:
        k+=1
        ans[l1[i][1]]=k
    else:
        ans[l1[i][1]]=ans[l1[j][1]]
        j+=1
print(k)
print(*ans)        


            
    


n, m, d = map(int, input().split())
a = list(map(int, input().split()))
a = sorted([(a[i],i) for i in range(n)])
coffeeTable = [0] * n
minimumDays = 0
i = j = 0
while i<n:
	if a[i][0] - d <= a[j][0] :
		minimumDays += 1
		coffeeTable[a[i][1]] = minimumDays
	else:
		coffeeTable[a[i][1]] = coffeeTable[a[j][1]]
		j += 1
	i += 1
print(minimumDays)
print(' '.join(list(map(str, coffeeTable))))


n,m,d=list(map(int,input().split()))
a=list(map(int,input().split()))
l=[]
for i in range(n):
	l.append((a[i],i))
l.sort()
j=0
ans=[0]*n
c=0
for i in range(n):
	if l[i][0]-d<=l[j][0]:
		c+=1
		ans[l[i][1]]=c
	else:
		ans[l[i][1]]=ans[l[j][1]]
		j+=1
print(c)
print(*ans)



n,m,d=list(map(int,input().split()))
a=list(map(int,input().split()))
l=[]
for i in range(n):
	l.append((a[i],i))
l.sort()
j=0
ans=[0]*n
c=0
for i in range(n):
	if l[i][0]-d<=l[j][0]:
		c+=1
		ans[l[i][1]]=c
	else:
		ans[l[i][1]]=ans[l[j][1]]
		j+=1
print(c)
print(*ans)


# -*- coding: utf-8 -*-

# Baqir Khan
# Software Engineer (Backend)

from sys import stdin

inp = stdin.readline

n, m, d = list(map(int, inp().split()))
a = [(int(minute), index) for index, minute in enumerate(inp().split())]
ans = [0] * n

a.sort()
ans[a[0][1]] = 1
max_cur_day = 1
j = 0
count = 1

for i in range(1, n):
    if a[i][0] - a[j][0] > d:
        ans[a[i][1]] = ans[a[j][1]]
        j += 1
    else:
        count += 1
        ans[a[i][1]] = count

print(count)
print(*ans)