P17380 [PacNW 2025] Bus Seating

一辆公交车有 $n$ 排座位，编号为 $1$ 到 $n$，每排有 $k$ 个座位。共有 $m$ 个人依次上车。每个人都有自己最喜欢的一排；如果能坐在那里，就会获得效用 $C$。人们更喜欢坐在靠近自己最喜欢位置的排：若某人最喜欢第 $r_x$ 排，而实际坐在第 $r_y$ 排，通常能获得 $C-|r_x-r_y|$ 的效用。 不过，这些人也都很内向。目标排中每多坐着一个人，这名乘客能获得的效用就会减半。形式化地说，若第 $r_y$ 排已经坐着 $p$ 个人，而该乘客最喜欢第 $r_x$ 排，那么坐在第 $r_y$ 排得到的效用为 $$ \frac{C-|r_x-r_y|}{2^p}. $$ 每个座位恰好能坐一人，因此如果一排的 $k$ 个座位全部被占用，就不能再选择这一排。 每个人都会在决定座位的当时最大化自己的效用。若达到最大效用的排不唯一，就在其中选择编号最小的一排。坐下后，任何人都不会再换排。请确定每个人最终坐在哪一排。

第一行包含四个整数 $n,k,m,C$，满足 $1\le n,k,m\le2\cdot10^5$、$n\le C\le10^9$ 且 $m\le n\cdot k$，分别表示公交车的排数、每排座位数、上车人数，以及坐在最喜欢的一排时的效用。 第二行包含 $m$ 个整数 $a_1,a_2,\ldots,a_m$（$1\le a_i\le n$），其中 $a_i$ 是第 $i$ 个人最喜欢的一排。乘客按输入顺序依次就座。

输出一行 $m$ 个整数 $b_1,b_2,\ldots,b_m$（$1\le b_i\le n$），其中 $b_i$ 表示第 $i$ 个人所坐的排。

在样例 1 中，每个人选择座位时各排的效用如下： 1. 最喜欢第 $3$ 排的乘客面对的效用为 $[4-2,4-1,4-0]=[2,3,4]$，因此选择第 $3$ 排。 2. 最喜欢第 $2$ 排的乘客面对的效用为 $[4-1,4-0,(4-1)/2]=[3,4,1.5]$，因此选择第 $2$ 排。 3. 最喜欢第 $3$ 排的乘客面对的效用为 $[4-2,(4-1)/2,(4-0)/2]=[2,1.5,2]$，因此选择第 $1$ 排。 4. 最喜欢第 $2$ 排的乘客面对的效用为 $[(4-1)/2,(4-0)/2,(4-1)/2]=[1.5,2,1.5]$，因此选择第 $2$ 排。 5. 最喜欢第 $2$ 排的乘客面对的效用为 $[(4-1)/2,(4-0)/4,(4-1)/2]=[1.5,1,1.5]$，因此选择第 $1$ 排。 6. 最喜欢第 $1$ 排的乘客面对的效用为 $[(4-0)/4,(4-1)/4,(4-2)/2]=[1,0.75,1]$。由于第 $1$ 排已经坐满，因此选择第 $3$ 排。