与地球生物不同，字节生物的遗传信息不是由四种，而是由$10^{9}$种不同的化学物质，即所谓的字节酸，进行编码。连接起来的字节酸序列被称为BNA。

BNA特别容易发生逆序突变，即两个相邻的字节酸交换位置。伟大的生物技术专家Bajtazar，运用理论模型发现，仅通过逆序突变就可以将字节黄瓜转化为番茄。此外，他计算出，这需要且仅需要对黄瓜的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长度、将黄瓜转化为番茄所需的逆序次数，以及最终生物体应成为番茄的部分。接下来的两行是分别是$n$个整数的序列，范围在$[1, 10^{9}]$之间，分别代表黄瓜和番茄基因组中连续字节酸的编号。

你可以假设存在一个由$k$次操作组成的序列，能将第一个BNA转化为第二个BNA，并且这是最短的操作序列。

输出格式

标准输出的第一行且仅一行应包含一个由$n$个整数组成的序列，表示所求生物体BNA中连续字节酸的编号。

样例

输入

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

输出

2 3 1 6 5 4

输入 2

4 3 2
2 2 2 1
1 2 2 2

输出 2

2 1 2 2