게놈

바이트기아 생물의 유전 정보는 지구 생물과 달리 네 가지가 아니라 $10^9$ 가지의 서로 다른 화합물로 부호화되며, 이 화합물을 바이트산이라고 부른다. 바이트산을 이어 붙인 하나의 사슬을 BNA라고 한다.

BNA는 역위 돌연변이에 특히 취약하다. 역위 돌연변이 한 번은 인접한 두 바이트산의 자리를 서로 바꾼다. 위대한 생명공학자 바이트자르는 이론 모형을 통해, 역위 돌연변이만으로 바이트기아 오이를 토마토로 바꿀 수 있으며, 그렇게 하는 데 오이 BNA의 역위가 정확히 $k$번 필요하고 또 충분함을 밝혀냈다.

과학자들은 자연수 $l$ ($0 \le l \le k$)을 하나 정하고, 전체의 $l/k$ 만큼은 토마토이고 나머지는 오이인 생물을 만들려고 한다. 더 정확히 말하면, 오이에 역위 돌연변이를 정확히 $l$번 적용하여, 이후 정확히 $k - l$번의 역위로 토마토가 될 수 있는 생물을 얻으려 한다.

식이 요법상 결과 BNA가 사전순으로 작을수록 좋다. 따라서 위 조건을 만족하는 모든 BNA 중에서, 첫 번째 바이트산의 번호가 가능한 한 작고, 그 값이 같다면 두 번째 바이트산의 번호가 가능한 한 작으며, 이런 식으로 계속되는 BNA를 구하려고 한다.

첫 번째 줄에 세 정수 $n$, $k$, $l$ ($1 \le n \le 300\,000$, $1 \le k \le 10^{12}$, $0 \le l \le k$)이 주어진다. 각각 오이 BNA의 길이(토마토 BNA의 길이와 같다), 오이를 토마토로 바꾸는 데 필요한 역위의 수, 그리고 결과 생물이 토마토여야 하는 비율을 뜻한다.

다음 두 줄에는 각각 $[1, 10^9]$ 범위의 정수 $n$개가 주어지며, 이는 각각 오이 게놈과 토마토 게놈의 연속한 바이트산 번호들이다.

첫 번째 BNA를 두 번째 BNA로 바꾸는 역위 $k$번의 수열이 존재하며, 그것이 가장 짧은 수열임을 가정해도 된다.

한 줄에 정수 $n$개를 출력한다. 이는 구하려는 생물의 BNA를 이루는 연속한 바이트산들의 번호이다.