개구리

길고 곧게 뻗은 시내에 물 위로 솟은 바위가 $n$개 있습니다. 시내의 발원지에서 잰 각 바위의 위치는 $p_1 < p_2 < \dots < p_n$으로 엄격히 증가합니다. 한 마리 개구리가 바위 하나에 앉아 도약 훈련을 합니다. 현재 위치가 $p_i$인 바위에 있을 때, 개구리는 언제나 자신에게서 $k$번째로 가까운 바위로 뛰어오릅니다(거리는 $|p_j - p_i|$로 재며, 자신이 앉은 바위는 세지 않습니다). 정확히는 다음을 만족하는 바위 $p_j$로 이동합니다.

$\left|\{\,p_a : |p_a - p_i| < |p_j - p_i|\,\}\right| \le k \quad\text{그리고}\quad \left|\{\,p_a : |p_a - p_i| \le |p_j - p_i|\,\}\right| > k.$

$k$번째로 가까운 바위가 (양쪽에 같은 거리로) 둘이어서 유일하지 않다면, 개구리는 발원지에 더 가까운 바위, 즉 위치 값이 더 작은 바위를 고릅니다. 각 시작 바위에 대해, 개구리가 정확히 $m$번 도약한 뒤 앉아 있는 바위를 구하세요.

첫 줄에 세 정수 $n$, $k$, $m$이 주어집니다($1 \le k < n \le 1{,}000{,}000$, $1 \le m \le 10^{18}$). 각각 바위의 수, 도약 매개변수, 도약 횟수입니다. 둘째 줄에 바위의 위치 $p_1, p_2, \dots, p_n$이 증가하는 순서로 주어집니다($1 \le p_1 < p_2 < \dots < p_n \le 10^{18}$).

한 줄에 $n$개의 정수 $r_1, r_2, \dots, r_n$을 공백 하나로 구분해 출력하세요. 각 값은 $[1, n]$ 범위입니다. $r_i$는 $i$번째 바위에서 출발한 개구리가 $m$번 도약한 뒤 도착하는 바위의 번호(입력 순서)입니다.

그림은 각 바위에서 개구리가 한 번 도약해 도달하는 바위를 보여줍니다.