The genetic information of Bytelandian organisms, unlike that of Earthlings, is encoded not by four, but by $10^{9}$ different chemical compounds, known as Bytacids. A combined sequence of Bytacids is called BNA.
BNA is particularly susceptible to inversion mutations, where two adjacent Bytacids swap places. The great biotechnologist Bytazar, using a theoretical model, discovered that through inversion mutations alone, one can transform a Bytelandian cucumber into a tomato. Moreover, he calculated that exactly $k$ BNA inversions are necessary and sufficient to achieve this.
Bytelandian scientists have determined a natural number $l$, $0 \le l \le k$, and are trying to create an organism that is $l/k$ tomato and the rest cucumber. More precisely, they intend to perform $l$ inversion mutations on the cucumber to obtain an organism that could become a tomato after $k - l$ further mutations.
For dietary reasons, the lexicographically smaller the BNA of the organism, the better. Therefore, among all BNA sequences satisfying the above requirement, the scientists want to obtain the one whose first Bytacid has the lowest possible number, and in case of a tie, the second Bytacid has the lowest possible number, and so on.
Input
The first line of input contains three integers $n$, $k$, and $l$ ($1 \le n \le 300\,000$, $1 \le k \le 10^{12}$, $0 \le l \le k$), representing the length of the BNA of the cucumber (and the tomato), the number of inversions needed to transform the cucumber into the tomato, and the fraction of the transformation to be performed. The next two lines contain sequences of $n$ integers in the range $[1, 10^{9}]$, representing the numbers assigned to the successive Bytacids of the cucumber and tomato genomes, respectively.
You may assume that there exists a sequence of $k$ operations transforming the first BNA into the second, and that this is the shortest such sequence of operations.
Output
The first and only line of standard output should contain a sequence of $n$ integers, representing the numbers of the successive Bytacids of the BNA of the desired organism.
Examples
Input 1
6 3 2 2 1 3 6 4 5 3 2 1 6 5 4
Output 1
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