Professor Ibrahim has prepared the final homework for his algorithm’s class. He asked his students to implement the Posterization Image Filter.

Their algorithm will be tested on an array of integers, where the $i$-th integer represents the color of the $i$-th pixel in the image. The image is in black and white, therefore the color of each pixel will be an integer between 0 and 255 (inclusive).

To implement the filter, students are required to divide the black and white color range [0, 255] into groups of consecutive colors, and select one color in each group to be the group’s key. In order to preserve image details, the size of a group must not be greater than $k$, and each color should belong to exactly one group.

Finally, the students will replace the color of each pixel in the array with that color’s assigned group key.

To better understand the effect, here is an image of a basking turtle where the Posterization Filter was applied with increasing $k$ to the right. 

 [Image] 

To make the process of checking the final answer easier, Professor Ibrahim wants students to divide the groups and assign the keys in a way that produces the lexicographically smallest possible array.


-----Input-----

The first line of input contains two integers $n$ and $k$ ($1 \leq n \leq 10^5$, $1 \leq k \leq 256$), the number of pixels in the image, and the maximum size of a group, respectively.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($0 \leq p_i \leq 255$), where $p_i$ is the color of the $i$-th pixel.


-----Output-----

Print $n$ space-separated integers; the lexicographically smallest possible array that represents the image after applying the Posterization filter.


-----Examples-----
Input
4 3
2 14 3 4

Output
0 12 3 3

Input
5 2
0 2 1 255 254

Output
0 1 1 254 254



-----Note-----

One possible way to group colors and assign keys for the first sample:

Color $2$ belongs to the group $[0,2]$, with group key $0$.

Color $14$ belongs to the group $[12,14]$, with group key $12$.

Colors $3$ and $4$ belong to group $[3, 5]$, with group key $3$.

Other groups won't affect the result so they are not listed here.

Difficulty: interview

Starter code:

Solutions:
def getIntList():
    return list(map(int, input().split()));
n, k = getIntList();
p=getIntList();
choosed=[False]*256;
left=[i for i in range(256)];
for i, x in enumerate(p):
    if not choosed[x]:
        best=x;
        #print(x-1, max(-1, x-k));
        for j in range(x-1, max(-1, x-k), -1):
            #print('try ',j)
            if not choosed[j]:
                best=j;
            else:
                if x-left[j]<k:
                    best=left[j];
                break;
        #print('best=',best)
        for j in range(best, x+1):
            choosed[j]=True;
            left[j]=best;
    p[i]=left[x];
print(' '.join(map(str, p)));

n, k = [int(x) for x in input().split()]

ps = [int(x) for x in input().split()]

mapping = [-1 for _ in range(256)]

res = []
for p in ps:
    if mapping[p] == -1:
        j = p - k + 1
        while j < 0 or (mapping[j] != -1 and mapping[j] + k <= p):
            j += 1
        for i in range(j, p+1):
            mapping[i] = j
    
    res.append(mapping[p])
print(" ".join(map(str, res)))


n, k = list(map(int, input().split()))
P = list(map(int, input().split()))

parent = list(range(256))
sz = [1] * 256
def rt(x):
    if x != parent[x]:
        parent[x] = rt(parent[x])
    return parent[x]

def u(rx, ry):
    parent[ry] = rx
    sz[rx] += sz[ry]

ans = [0] * n
for i, p in enumerate(P):
    rx = rt(p)
    while rx > 0 and sz[rx] + sz[rt(rx - 1)] <= k:        
        u(rt(rx - 1), rx)
        rx = rt(p)
    ans[i] = rt(p)
print(' '.join(map(str, ans)))



def solve():
    num_pixels, max_group_size = (int(x) for x in input().split())
    pixels = [int(x) for x in input().split()]
    groups = [None for _ in range(256)]

    for pixel in pixels:
        if groups[pixel] is None:
            smallest_of_group = pixel
            while smallest_of_group >= 0 and smallest_of_group > pixel - max_group_size and groups[smallest_of_group] is None:
                smallest_of_group -= 1

            if smallest_of_group >= 0 and groups[smallest_of_group] is not None and pixel - groups[smallest_of_group] + 1 <= max_group_size:
                group_color = groups[smallest_of_group]
            else:
                group_color = smallest_of_group + 1
            smallest_of_group += 1
            for color in range(smallest_of_group, pixel + 1):
                groups[color] = group_color

    print(*(groups[pixel] for pixel in pixels))

solve()


#!/usr/bin/env python3

[n, k] = list(map(int, input().strip().split()))
pis = list(map(int, input().strip().split()))

import sys
if k == 1:
	print(' '.join(map(str, pis)))
	return


N = 256
gamma = [-1 for _ in range(N)]
done = [False for _ in range(N)]
revdone = [False for _ in range(N)]
notset = 256
pends = {}

def get_bounds(i):
	try:
		l = N - 1 - revdone.index(True, N - 1 - i) + 1
	except ValueError:
		l = 0
	try:
		r = done.index(True, i) - 1
	except ValueError:
		r = N - 1
	return l, r

def set_gamma(l, r, v):
	for i in range(l, r + 1):
		gamma[i] = v
		done[i] = True
		revdone[N - 1 - i] = True



for p in pis:
	if not done[p]:
		lb, rb = get_bounds(p)
		if (lb > 0) and ((lb - 1) in pends) and (lb - 1 + pends[lb - 1] >= p):
			l = lb
			r = p
			set_gamma(l, r, gamma[lb - 1])
			if r - l + 1 < pends[lb - 1]:
				pends[r] = pends[lb - 1] - (r - l + 1)
			del pends[lb - 1]
		else:
			l = max(p - k + 1, lb)
			r = p
			set_gamma(l, r, l)
			if r - l + 1 < k:
				pends[p] = k - (r - l + 1)
		notset -= r - l + 1
		if notset == 0:
			break

if notset > 0:
	for i in range(N):
		if gamma[i] < 0:
			l, r = get_bounds(i)
			set_gamma(l, min(l + k - 1, r), l)

print(' '.join(str(gamma[p]) for p in pis))


def main():
    n, k = list(map(int, input().split()))
    p = list(map(int, input().split()))
    solve(n, k, p)

def solve(n, k, p):
    group = 256 * [None]
    r = p[:]
    for i, pi in enumerate(p):
#        print([(i, gi) for i, gi in enumerate(group)if gi is not None])
        if group[pi] is not None:
            r[i] = group[pi][0]
        else:
            lo = pi
            while lo >= 0 and pi - lo < k and group[lo] is None:
                lo -= 1
            if lo < 0 or pi - lo == k:
                lo += 1
                hi = pi + 1
            else: # group[lo] is not None
                if pi - group[lo][0] < k:
                    lo = group[lo][0]
                    hi = pi + 1
                else:
                    lo += 1
                    hi = pi + 1
            lohi = (lo, hi)
            for j in range(lo, hi):
                group[j] = lohi
            r[i] = group[pi][0]
    print(" ".join(map(str, r)))

main()


n,k=list(map(int,input().split()))
p=list(map(int,input().split()))

arr=[[] for i in range(256)]
ans=[]
for i in p:
    j=i
    if len(arr[i])==0:
        c=0
        while c<k and j>=0:
            if len(arr[j])+c>k:
                break
            #temp=len(arr[j])
            if len(arr[j])!=0:
                arr[i].extend(arr[j])
                break
            arr[j]=arr[i]
            arr[j].append(j)
            j-=1
            c+=1
        arr[i].sort()
    ans.append(arr[i][0])
print(*ans)
#print(arr)


n,k = [int(s) for s in input().split()]
p = [int(s) for s in input().split()]

map = {}
res = []

for pi in p:
    if map.get(pi) is None:
        key = pi
        for j in range(pi, pi-k, -1):
            if j < 0: break
            if map.get(j) is None:
                key = j
            else:
                if map[j] >= pi-k+1: key = map[j]
                break
        for j in range(pi, key-1, -1):
            if map.get(j):
                break
            map[j] = key
    res.append(map[pi])

print(*res, sep=" ")


N, K = input().split()
N, K = int(N), int(K)
P = [int(x) for x in input().split()]
A = [None]*256
A[0] = 0
for i in range(N):
    pn = P[i]
    if A[pn] is None:
        for j in range(K-1, -1, -1):
            if pn < j: continue
            if A[pn-j] is None:
                A[pn-j] = pn-j
                break
            else:
                if A[pn-j] + K - 1 >= pn:
                    break
        for jj in range(j, -1, -1):
            A[pn-jj] = A[pn-j]
print(*[A[P[i]] for i in range(N)])


n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
ans = [-1] * (max(p) + 1)
ans[0] = 0
for i in range(n):
	if ans[p[i]] < 0:
		position = p[i] - k + 1
		for j in range(max(0,p[i] - k + 1), p[i] + 1):
			if ans[j] < 0:
				position = j
				break
		j = max(0, position - 1)
		key = ans[j]
		count = 0
		while j >= 0:
			if ans[j] != key:
				position1 = j + 1
				break
			j -= 1
			count += 1
		if count + p[i] + 1 - position > k:
			key = position
		for j in range(position, p[i] + 1):
			ans[j] = key

for i in range(n):
	if i != len(p) - 1:
		wk1 = " "
	else:
		wk1 = "\n"
	print(ans[p[i]], end = wk1)


n,k = list(map(int,input().split()))
l = [int(x) for x in input().split()]
maps = []
for _ in range(256):
	maps.append(['empty',0])
output = []
for innum in l:
	if maps[innum][0] == 'chosen':
		outnum = maps[innum][1]
	elif maps[innum][0] == 'potential':
		outnum = maps[innum][1]
		i = innum
		while i >= 0 and maps[i][0] == 'potential':
			maps[i] = ['chosen',outnum]
			i -= 1
	else:
		i = innum
		while i >= 0 and i >= innum - (k-1) and maps[i][0] != 'chosen':
			i -= 1
		i += 1
		outnum = i
		for j in range(outnum,innum+1):
			maps[j] = ['chosen',outnum]
		if innum < 255:
			for j in range(innum+1,min(256,outnum+k)):
				if maps[j][0] != 'chosen':
					maps[j] = ['potential',outnum]
	output.append(str(outnum))
print(' '.join(output))


n, k = map(int, input().split())
ps = list(map(int, input().split()))
if k == 1:
    print(' '.join([str(i) for i in ps]))
    return

g = [None for i in range(256)]
f = [None for i in range(256)]
ans = []
for i in range(n):
    p = ps[i]
    if g[p] is not None:
        ans.append(g[p])
        f[p] = 1
    else:
        gb= 0
        for j in range(1, k):
            ind = p - j
            if f[ind] is not None:
                gb = ind +1
                break
            if ind <= 0:
                break
            if j == k-1:
                gb = ind
        ans.append(gb)
        for j in range(k):
            if gb+j >= 256:
                break
            if f[gb + j] is None:
                g[gb+j] = gb
            else:
                break
        f[gb] = 1
        f[p] = 1
print(' '.join([str(i) for i in ans]))

n, k = map(int, input().split())
ps = list(map(int, input().split()))


g = [None for i in range(256)]
f = [None for i in range(256)]
ans = []
for i in range(n):
    p = ps[i]
    if g[p] is not None:
        ans.append(g[p])
        f[p] = 1
    else:
        gb= 0
        for j in range(k):
            ind = p - j
            if f[ind] is not None:
                gb = ind +1
                break
            if ind <= 0:
                break
            if j == k-1:
                gb = ind
        ans.append(gb)
        for j in range(k):
            if gb+j >= 256:
                break
            if f[gb + j] is None:
                g[gb+j] = gb
            else:
                break
        f[gb] = 1
        f[p] = 1
print(' '.join([str(i) for i in ans]))

n, k = map(int, input().strip().split())
data = map(int, input().strip().split())
sol = []
mapping = [(-1,1000)]*256
for x in data:
    if mapping[x][0] == -1:
        for i in range(max(x-k+1,0), x+1):
            if mapping[i][0] == -1:
                if i > 0 and mapping[i-1][1]+(x-i+1) <= k:
                    p = mapping[i-1][1]+1
                    for j in range(i, x+1):
                        mapping[j] = (mapping[i-1][0], p)
                        p += 1
                else:                    
                    p = 1
                    for j in range(i, x+1):
                        mapping[j] = (i, p)
                        p += 1
                break
    sol.append(mapping[x][0])
print(' '.join(map(str, sol)))

import sys

n, k = list(map(int, next(sys.stdin).rstrip().split()))

xs = list(map(int, next(sys.stdin).rstrip().split()))

mapka = {}
lengths = {}

result = []

for x in xs:
    
    if x in mapka:
        result.append(mapka[x])
    else:
        left = max(0, x - k + 1)
        range_potential = x - left
        for i in range(range_potential, -1, -1):
            potential_left = x - i
            if potential_left not in mapka:
                result.append(potential_left)
                for y in range(potential_left, x + 1):
                    mapka[y] = potential_left

                lengths[potential_left] = x - potential_left + 1

                break
            else:

                if lengths[mapka[potential_left]] + (x - potential_left) <= k:
                    result.append(mapka[potential_left])
                    for y in range(mapka[potential_left] + lengths[mapka[potential_left]], x + 1):
                        mapka[y] = mapka[potential_left]
                        lengths[mapka[potential_left]] += 1

                    break
            
print(' '.join(map(str, result)))


a = [0 for i in range(0, 256)]
n,k = input().split(' ')
k = int(k)
for c in input().split(' '):
        c = int(c)
        if a[c] != 0:
            print(a[c]-1, end=' ')
        else:
            for x in range(c, c-k, -1):
                if a[x] == 0:
                    i = x
                else:
                    if c-a[x]+1<k:
                        i = a[x]-1
                    break
                if x == 0:
                    break
            for x in range(int(i), c+1):
                a[x] = i + 1
            print(i, end=' ')


#!/usr/bin/env python3

[n, k] = map(int, input().strip().split())
pis = list(map(int, input().strip().split()))

import sys
if k == 1:
	print (' '.join(map(str, pis)))
	return


N = 256
gamma = [-1 for _ in range(N)]
done = [False for _ in range(N)]
revdone = [False for _ in range(N)]
notset = 256
pends = {}

def get_bounds(i):
	try:
		l = N - 1 - revdone.index(True, N - 1 - i) + 1
	except ValueError:
		l = 0
	try:
		r = done.index(True, i) - 1
	except ValueError:
		r = N - 1
	return l, r

def set_gamma(l, r, v):
	for i in range(l, r + 1):
		gamma[i] = v
		done[i] = True
		revdone[N - 1 - i] = True



for p in pis:
	if not done[p]:
		lb, rb = get_bounds(p)
		if (lb > 0) and ((lb - 1) in pends) and (lb - 1 + pends[lb - 1] >= p):
			l = lb
			r = p
			set_gamma(l, r, gamma[lb - 1])
			if r - l + 1 < pends[lb - 1]:
				pends[r] = pends[lb - 1] - (r - l + 1)
			del pends[lb - 1]
		else:
			l = max(p - k + 1, lb)
			r = p
			set_gamma(l, r, l)
			if r - l + 1 < k:
				pends[p] = k - (r - l + 1)
		notset -= r - l + 1
		if notset == 0:
			break

if notset > 0:
	for i in range(N):
		if gamma[i] < 0:
			l, r = get_bounds(i)
			set_gamma(l, min(l + k - 1, r), l)

print (' '.join(str(gamma[p]) for p in pis))

n, k = [int(x) for x in input().split()]
ps = [int(x) for x in input().split()]
mapping = [-1 for _ in range(256)]

res = []
for p in ps:
    if mapping[p] == -1:
        j = p - k + 1
        while j < 0 or (mapping[j] != -1 and mapping[j] + k <= p):
            j += 1
        for i in range(j, p+1):
            mapping[i] = j
    res.append(mapping[p])
print(" ".join(map(str, res)))

def main():
	n, k = [int(_) for _ in input().split()]
	a = [int(_) for _ in input().split()]

	p = [-1] * 256
	p[0] = 0

	for x in a:
		if p[x] < 0:
			for y in range(x - 1, max(-1, x - k), -1):
				if p[y] >= 0:
					if p[y] + k > x:
						p[x] = p[y]
					else:
						p[x] = p[y + 1] = y + 1

					break
			if p[x] < 0:
				p[x] = p[x - k + 1] = x - k + 1

	b = [p[x] for x in a]

	print(' '.join(map(str, b)))

def __starting_point():
	main()
__starting_point()

n,k=[int(x)for x in input().split()]
ns=[int(x) for x in input().split()]
done=[None]*256
ans=[None]*n
for i in range(n):
    c=ns[i]
    if done[c]==None:
        j=c
        while True:
            if j<0 or c-j>=k or (done[j]!=None and done[j]!=-1):
                break
            j-=1
        j+=1
        for kk in range(k):
            if kk+j>=256 or (done[kk+j]!=None and done[kk+j]!=-1):
                break
            if kk+j<=c:
                done[kk+j]=j
            else:
                done[kk+j]=-1
    elif done[c]==-1:
        j=c
        while True:
            if done[j]!=None and done[j]!=-1:
                break
            j-=1
        a=done[j]
        for kk in range(j,c+1):
            done[kk]=a
    else:
        pass
    ans[i]=done[c]
    # print(ans[i])
    # print(done)
    # if ans[i]==146:
    #     print(ans[i])
    #     print(done)
    #     input()
ans=[str(x)for x in ans]
print(' '.join(ans))





n,k=map(int,input().split())

ar=[-1 for i in range(256)]
ls=list(map(int,input().split()))

for e in ls:
    if ar[e]==-1:
        tmp=max(0,e-k+1)
        for i in range(tmp,e+1):
            if ar[i]!=-1 and ar[i]!=i:
                tmp+=1
                continue
            else:
                while i<=e:
                    ar[i]=tmp
                    i+=1
    print(ar[e],end=" ")


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
c = [-1]*256

ans = [0]*n
for i in range(n):
    if c[a[i]] == -1:
        for j in range(a[i], max(-1, a[i]-k), -1):
            if c[j] != -1:
                if (c[j] +k) > a[i]:
                    c[a[i]] = c[j]
                else:
                    c[a[i]] = j+1
                break
        if c[a[i]] == -1:
            c[a[i]] = max(0, a[i]-k+1)
        for xx in range(c[a[i]], a[i]):
            c[xx] = c[a[i]]
    ans[i] = str(c[a[i]])

print(' '.join(ans))


n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
processed = set()
color = {}
length = {}
ans = []

def exists(p, elt, d):
    for e in p:
        if e > elt:
            if e <= elt + d:
                return True
            elif e - d <= elt + d:
                return False
    return False

def exists2(p, elt, d):
    for e in p:
        if e > elt:
            if e <= elt + d:
                return False
            elif e - d <= elt + d:
                return [True, e - d]
    return False
        

for i in range(n):
    elt = p[i]
    if elt in processed:
        ans.append(color[elt])
    else:
        processed.add(elt)
        new = 1
        run = True
        for j in range(1, k):
            if elt - j < 0:
                break
            elif (elt - j) not in processed:
                processed.add(elt - j)
                new += 1
            elif length[elt - j] + new <= k:
                for i2 in range(length[elt - j] + new):
                    color[elt - i2] = color[elt - j]
                length[elt] = length[elt - j] + new
                run = False
                break
            else:
                break
        if run:
            for j in range(new):
                color[elt - j] = elt - new + 1
            length[elt] = new
s = str(color[p[0]])
for elt in p[1:]:
    s += ' ' + str(color[elt])
print(s)



n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
processed = set()
color = {}
length = {}
ans = []

for i in range(n):
    elt = p[i]
    if elt in processed:
        ans.append(color[elt])
    else:
        processed.add(elt)
        new = 1
        run = True
        for j in range(1, k):
            if elt - j < 0:
                break
            elif (elt - j) not in processed:
                processed.add(elt - j)
                new += 1
            elif length[elt - j] + new <= k:
                for i2 in range(length[elt - j] + new):
                    color[elt - i2] = color[elt - j]
                length[elt] = length[elt - j] + new
                run = False
                break
            else:
                break
        if run:
            for j in range(new):
                color[elt - j] = elt - new + 1
            length[elt] = new
s = str(color[p[0]])
for elt in p[1:]:
    s += ' ' + str(color[elt])
print(s)