一辆公交车有 $n$ 排，编号为 $1$ 到 $n$，每排有 $k$ 个座位。将有 $m$ 个人依次上车。
每个人都有一个最喜欢的排，如果能坐在那一排，他们将获得 $C$ 的效用。人们更喜欢坐在离自己最喜欢的排更近的地方，因此如果一个人最喜欢的排是 $r_x$，而他坐在第 $r_y$ 排，那么他通常会获得 $C - |r_x - r_y|$ 的效用。
然而，人们也是内向的。对于已经坐在某一排的每一个人，该人能从该排获得的效用都会减半。正式地，如果已经有 $p$ 个人坐在第 $r_y$ 排，而该人最喜欢的排是 $r_x$，那么他坐在第 $r_y$ 排将获得 $\frac{C - |r_x - r_y|}{2^p}$ 的效用。每个座位只能容纳一个人，因此如果第 $r_y$ 排的所有 $k$ 个座位都已被占用，那么该人就不能坐在那一排。
如果每个人在决定坐哪里时都试图最大化自己的个人效用，你能确定每个人会坐在哪里吗？如果使个人效用最大化的排不唯一，该人将选择这些排中编号最小的一排。人们坐下后不会更换排。
输入格式
输入的第一行包含四个整数 $n, k, m$ 和 $C$ ($1 \le n, k, m \le 2 \cdot 10^5$，$n \le C \le 10^9$，且 $m \le n \cdot k$) —— 分别表示公交车的排数、每排的座位数、上车的人数，以及每个人坐在自己最喜欢的排时获得的效用。
第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$ ($1 \le a_i \le n$) —— $a_i$ 是第 $i$ 个人的最爱排。人们按照输入中指定的顺序依次就坐。
输出格式
输出一行，包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($1 \le b_i \le n$) —— $b_i$ 表示第 $i$ 个人将要坐的排。
样例
输入样例 1
3 2 6 4 3 2 3 2 2 1
输出样例 1
3 2 1 2 1 3
输入样例 2
2 5 8 1000000000 2 2 2 2 2 2 2 2
输出样例 2
2 1 2 1 2 1 2 1
说明
在第一个样例中，每个人的效用情况如下：
- 最爱排为 3 的人的效用为 $[(4 - 2), (4 - 1), (4 - 0)] = [2, 3, 4]$，因此他们选择第 3 排。
- 最爱排为 2 的人的效用现在为 $[(4 - 1), (4 - 0), (4 - 1)/2] = [3, 4, 1.5]$，因此他们选择第 2 排。
- 最爱排为 3 的人的效用现在为 $[(4 - 2), (4 - 1)/2, (4 - 0)/2] = [2, 1.5, 2]$，因此他们选择第 1 排。
- 最爱排为 2 的人的效用现在为 $[(4 - 1)/2, (4 - 0)/2, (4 - 1)/2] = [1.5, 2, 1.5]$，因此他们选择第 2 排。
- 最爱排为 2 的人的效用现在为 $[(4 - 1)/2, (4 - 0)/4, (4 - 1)/2] = [1.5, 1, 1.5]$，因此他们选择第 1 排。
- 最爱排为 1 的人的效用现在为 $[(4 - 0)/4, (4 - 1)/4, (4 - 2)/2] = [1, 0.75, 1]$。由于第 1 排已满，他们选择第 3 排。