{"raw_statement":[{"iden":"statement","content":"Professor Ibrahim has prepared the final homework for his algorithm’s class. He asked his students to implement the Posterization Image Filter.\n\nTheir 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).\n\nTo 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.\n\nFinally, the students will replace the color of each pixel in the array with that color’s assigned group key.\n\nTo better understand the effect, here is an image of a basking turtle where the Posterization Filter was applied with increasing $k$ to the right.\n\n<center>![image](https://espresso.codeforces.com/0e1be1716cabc713374d2a7de753e569a9f2fa7e.png)</center>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."},{"iden":"input","content":"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.\n\nThe 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."},{"iden":"output","content":"Print $n$ space-separated integers; the lexicographically smallest possible array that represents the image after applying the Posterization filter."},{"iden":"examples","content":"Input\n\n4 3\n2 14 3 4\n\nOutput\n\n0 12 3 3\n\nInput\n\n5 2\n0 2 1 255 254\n\nOutput\n\n0 1 1 254 254"},{"iden":"note","content":"One possible way to group colors and assign keys for the first sample:\n\nColor $2$ belongs to the group $[0,2]$, with group key $0$.\n\nColor $14$ belongs to the group $[12,14]$, with group key $12$.\n\nColors $3$ and $4$ belong to group $[3, 5]$, with group key $3$.\n\nOther groups won't affect the result so they are not listed here."}],"translated_statement":[{"iden":"statement","content":"教授 Ibrahim 为他的算法课程准备了最终作业。他要求学生们实现海报化图像滤镜。\n\n他们的算法将在一个整数数组上进行测试，其中第 $i$ 个整数表示图像中第 $i$ 个像素的颜色。图像是黑白的，因此每个像素的颜色是一个介于 0 到 255（含）之间的整数。\n\n为了实现该滤镜，学生需要将黑白颜色范围 [0, 255] 划分为若干连续颜色的组，并在每组中选择一个颜色作为该组的主键。为了保留图像细节，每组的大小不得超过 $k$，且每个颜色必须恰好属于一个组。\n\n最后，学生需将数组中每个像素的颜色替换为其所属组的主键。\n\n为了更好地理解效果，右侧图像展示了对一只晒太阳的龟应用海报化滤镜时，随着 $k$ 增大产生的变化。\n\n为了便于检查最终答案，教授 Ibrahim 希望学生们以一种能产生字典序最小数组的方式划分组并分配主键。\n\n输入的第一行包含两个整数 $n$ 和 $k$（$1 lt.eq n lt.eq 10^5$，$1 lt.eq k lt.eq 256$），分别表示图像中的像素数量和每组的最大大小。\n\n第二行包含 $n$ 个整数 $p_1, p_2, dots.h, p_n$（$0 lt.eq p_i lt.eq 255$），其中 $p_i$ 表示第 $i$ 个像素的颜色。\n\n请输出 $n$ 个用空格分隔的整数：表示应用海报化滤镜后可能得到的字典序最小的数组。\n\n对于第一个样例，一种可能的分组和主键分配方式如下：\n\n颜色 $2$ 属于组 $[ 0, 2 ]$，主键为 $0$。\n\n颜色 $14$ 属于组 $[ 12, 14 ]$，主键为 $12$。\n\n颜色 $3$ 和 $4$ 属于组 $[ 3, 5 ]$，主键为 $3$。\n\n其他组不影响结果，因此未列出。"},{"iden":"input","content":"输入的第一行包含两个整数 $n$ 和 $k$（$1 lt.eq n lt.eq 10^5$，$1 lt.eq k lt.eq 256$），分别表示图像中的像素数量和每组的最大大小。第二行包含 $n$ 个整数 $p_1, p_2, dots.h, p_n$（$0 lt.eq p_i lt.eq 255$），其中 $p_i$ 表示第 $i$ 个像素的颜色。"},{"iden":"output","content":"请输出 $n$ 个用空格分隔的整数：表示应用海报化滤镜后可能得到的字典序最小的数组。"},{"iden":"examples","content":"输入\n4 3\n2 14 3 4\n输出\n0 12 3 3\n\n输入\n5 2\n0 2 1 255 254\n输出\n0 1 1 254 254"},{"iden":"note","content":"对于第一个样例，一种可能的分组和主键分配方式如下：\n颜色 $2$ 属于组 $[ 0, 2 ]$，主键为 $0$。\n颜色 $14$ 属于组 $[ 12, 14 ]$，主键为 $12$。\n颜色 $3$ 和 $4$ 属于组 $[ 3, 5 ]$，主键为 $3$。\n其他组不影响结果，因此未列出。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\le n \\le 10^5 $, $ 1 \\le k \\le 256 $.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be the input pixel color array, where $ p_i \\in \\{0, 1, \\dots, 255\\} $.  \n\nLet $ G = \\{ [L_j, R_j] \\}_{j=1}^m $ be a partition of the color range $[0, 255]$ into contiguous intervals (groups), such that:  \n- $ 0 = L_1 \\le R_1 < L_2 \\le R_2 < \\dots < L_m \\le R_m = 255 $,  \n- $ R_j - L_j + 1 \\le k $ for all $ j \\in \\{1, \\dots, m\\} $.  \n\nFor each group $ [L_j, R_j] $, a key $ c_j \\in [L_j, R_j] $ is selected.  \n\nDefine the mapping $ f: \\{0, 1, \\dots, 255\\} \\to \\{0, 1, \\dots, 255\\} $ such that $ f(x) = c_j $ if $ x \\in [L_j, R_j] $.  \n\n**Constraints**  \n1. Each group has size at most $ k $: $ \\forall j, \\; R_j - L_j + 1 \\le k $.  \n2. Groups are contiguous and partition $[0, 255]$.  \n3. Each color maps to exactly one group key.  \n\n**Objective**  \nChoose the partition $ G $ and keys $ \\{c_j\\} $ such that the output array $ Q = (f(p_1), f(p_2), \\dots, f(p_n)) $ is lexicographically smallest among all valid assignments.  \n\n**Output**  \nThe array $ Q $ of length $ n $, where each $ f(p_i) $ is the key assigned to color $ p_i $ under the optimal grouping and key selection.","simple_statement":null,"has_page_source":false}