Informacja genetyczna bajtockich istot, w odróżnieniu od ziemskich, kodowana jest nie przez cztery, ale przez $10^{9}$ różnych związków chemicznych, tzw. bajtokwasów. Połączona sekwencja bajtokwasów zwana jest BNA.

BNA jest szczególnie podatne na mutacje inwersyjne, polegające na tym, że dwa sąsiednie bajtokwasy zamieniają się miejscami. Wielki biotechnolog Bajtazar, stosując model teoretyczny, odkrył, że na drodze samych mutacji inwersyjnych można przekształcić bajtockiego ogórka w pomidora. Co więcej, obliczył, że potrzeba i wystarcza na to dokładnie $k$ inwersji BNA ogórka.

Bajtoccy naukowcy ustalili pewną liczbę naturalną $l$, $0 \le l \le k$, i starają się stworzyć organizm, który byłby w $l/k$-tej części pomidorem, a w pozostałej ogórkiem. Ściślej rzecz ujmując, zamierzają wywołać $l$ mutacji inwersyjnych w ogórku, tak aby otrzymać organizm, który po dalszych $k - l$ mutacjach mógłby stać się pomidorem.

Ze względów dietetycznych im mniejsze jest BNA organizmu w porządku leksykograficznym, tym lepiej. Zatem spośród wszystkich BNA spełniających powyższy wymóg, naukowcy chcą uzyskać to, którego pierwszy bajtokwas ma najniższy możliwy numer, w przypadku remisu drugi bajtokwas ma najniższy możliwy numer itd.

Input Format

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite $n$, $k$ i $l$ ($1 \le n \le 300\,000$, $1 \le k \le 10^{12}$, $0 \le l \le k$), oznaczające długość BNA ogórka (i zarazem pomidora), liczbę inwersji potrzebnych do przekształcenia ogórka w pomidora i część, w jakiej wynikowy organizm ma być pomidorem. W kolejnych dwóch wierszach znajdują się ciągi $n$ liczb całkowitych z przedziału $[1, 10^{9}]$, które oznaczają numery przypisane kolejnym bajtokwasom genomu odpowiednio ogórka i pomidora.

Możesz założyć, że istnieje ciąg $k$ operacji przekształcających pierwsze BNA w drugie oraz że jest to najkrótszy taki ciąg operacji.

Output Format

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać ciąg $n$ liczb całkowitych, będących numerami kolejnych bajtokwasów BNA poszukiwanego organizmu.

Examples

Input

6 3 2
2 1 3 6 4 5
3 2 1 6 5 4

Output

2 3 1 6 5 4

Input 2

4 3 2
2 2 2 1
1 2 2 2

Output 2

2 1 2 2