← 返回题目列表

Codeforces · 761/D

D. 大傻和非常困难的问题

中文机器翻译题面 查看原题

大傻登录系统,开始解决问题。其中之一如下:

给定两个长度为 n 的序列 a 和 b,您需要编写一个长度为 n 的序列 c,其第 i 个元素计算如下:ci = bi - ai。

关于序列a和b,我们知道它们的元素在l到r的范围内。更正式地说,元素满足以下条件:l ≤ ai ≤ r 且 l ≤ bi ≤ r。关于序列 c,我们知道它的所有元素都是不同的。

Dasha 很快就写出了该问题的解决方案,但在标准测试中检查她的工作并不那么容易。由于测试系统中的错误,从该测试中仅获知序列a和序列c的压缩序列。

让我们给出压缩序列的定义。长度为n的序列c的压缩序列是长度为n的序列p,因此pi等于序列c中小于或等于ci的整数的数量。例如,对于序列 c = [250, 200, 300, 100, 50],压缩序列将为 p = [4, 3, 5, 2, 1]。请注意,在 c 中,所有整数都是不同的。因此,压缩序列包含从 1 到 n 的所有整数(包括 1 和 n)。

帮助Dasha找到序列c的计算压缩序列正确的任意序列b。

输入

第一行包含三个整数 n、l、r (1 ≤ n ≤ 105, 1 ≤ l ≤ r ≤ 109) — 序列的长度以及序列 a 和 b 的元素所在段的边界。

下一行包含 n 个整数 a1, a2, ..., an (l ≤ ai ≤ r) — 序列 a 的元素。

下一行包含 n 个不同的整数 p1, p2, ..., pn (1 ≤ pi ≤ n) — 序列 c 的压缩序列。

输出

如果没有合适的序列b,则在唯一的行中打印“-1”。

否则,在唯一的行中打印 n 个整数 - 任何合适序列 b 的元素。

示例

输入 #1

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

输出 #1

3 1 5 4 2

输入 #2

4 2 9
3 4 8 9
3 2 1 4

输出 #2

2 2 2 9

输入 #3

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

输出 #3

-1

注意

在第二个样本中找到的序列b是合适的,因为计算出的序列c = [2 - 3, 2 - 4, 2 - 8, 9 - 9] = [ - 1, - 2, - 6, 0](注意ci = bi - ai)压缩序列等于p = [3, 2, 1, 4]。