34783번 - Bus Seating 다국어

문제

A bus has $n$ rows numbered 1ドル$ through $n$ with $k$ seats in each row, and there will be $m$ people entering the bus. Each person has a favorite row, and they will derive utility $C$ from being able to sit in that row. People prefer to sit closer to their favorite row, so if a person's favorite row is $r_x,ドル and they sit in row $r_y,ドル then that person will normally derive utility $C - |r_x - r_y|$ for sitting in it.

However, people are also introverts. For each person already sitting in a given row, the utility the person would derive gets halved. Formally, if $p$ people are already sitting in row $r_y$ and the person's favorite row is $r_x,ドル then the person would derive $\dfrac{C - |r_x - r_y|}{2^p}$ utility for sitting in row $r_y$. Each seat can accommodate exactly one person, so if all $k$ seats in a row are occupied, then the person cannot sit in that row.

Can you determine where everyone will sit, if every person is trying to maximize their personal utility at the time they decide where to sit? If the row that maximizes the personal utility is not uniquely determined, the person will pick, among all such rows, the row with the smallest number. People do not change rows after sitting down.

입력

The first line of input contains four integers $n, k, m,ドル and $C$ (1ドル\le n,k,m\le 2\cdot 10^5,ドル $n\le C\le 10^9,ドル and $m\le n\cdot k$) --- the number of rows in the bus, the number of seats in each row, the number of people entering the bus, and each person's utility of sitting in their favorite row, respectively.

The next line contains $m$ integers $a_1,a_2,\ldots,a_m$ (1ドル\le a_i\le n$) --- $a_i$ is person $i$'s favorite row. People sit down in the order specified in the input.

출력

Output one line containing $m$ integers $b_1,b_2,\ldots,b_m$ (1ドル\le b_i\le n$) --- $b_i$ being the row in which person $i$ will sit.

제한

노트

In the first sample, here is what the utilities look like for every person:

1. The utilities for a person with preference 3ドル$ are $[(4-2), (4-1), (4-0)] = [2, 3, 4]$ so they choose row 3ドル$.
2. The utilities for a person with preference 2ドル$ now are $[(4-1), (4-0), (4-1)/2] = [3, 4, 1.5]$ so they choose row 2ドル$.
3. The utilities for a person with preference 3ドル$ now are $[(4-2), (4-1)/2, (4-0)/2] = [2, 1.5, 2]$ so they choose row 1ドル$.
4. The utilities for a person with preference 2ドル$ now are $[(4-1)/2, (4-0)/2, (4-1)/2] = [1.5, 2, 1.5]$ so they choose row 2ドル$.
5. The utilities for a person with preference 2ドル$ now are $[(4-1)/2, (4-0)/4, (4-1)/2] = [1.5, 1, 1.5]$ so they choose row 1ドル$.
6. The utilities for a person with preference 1ドル$ now are $[(4-0)/4, (4-1)/4, (4-2)/2] = [1, 0.75, 1]$. Since row 1ドル$ is full, they choose row 3ドル$.