Genome

The genetic information of Byteotian organisms, unlike that of Earth organisms, is encoded not by four but by $10^9$ different chemical compounds called byteacids. A single joined chain of byteacids is called a BNA.

A BNA is especially prone to inversion mutations: one such mutation swaps two adjacent byteacids. Using a theoretical model, the great biotechnologist Byteazar discovered that inversion mutations alone can turn a Byteotian cucumber into a tomato, and that exactly $k$ inversions of the cucumber's BNA are both necessary and sufficient to do so.

The scientists fix a natural number $l$ with $0 \le l \le k$ and want to build an organism that is a tomato in an $l/k$ fraction and a cucumber in the rest. More precisely, they want to apply exactly $l$ inversion mutations to the cucumber so that the resulting organism could still be turned into the tomato by exactly $k - l$ further inversions.

For dietary reasons, the smaller the resulting BNA is in lexicographic order, the better. So among all BNAs that meet the requirement above, the scientists want the one whose first byteacid has the smallest possible number; in case of a tie, whose second byteacid has the smallest possible number, and so on.

The first line contains three integers $n$, $k$, and $l$ ($1 \le n \le 300\,000$, $1 \le k \le 10^{12}$, $0 \le l \le k$): the length of the cucumber's BNA (equal to the tomato's), the number of inversions needed to turn the cucumber into the tomato, and the fraction to which the resulting organism should be a tomato.

The next two lines each contain $n$ integers in the range $[1, 10^9]$: the numbers of the successive byteacids of the cucumber's genome and of the tomato's genome, respectively.

You may assume that a sequence of $k$ inversions transforming the first BNA into the second exists, and that it is a shortest such sequence.

Output one line with $n$ integers: the numbers of the successive byteacids of the BNA of the desired organism.