Dasha and Very Difficult Problem

题意翻译

# 题目大意 现有a[i]，b[i]两个数组(l<=a[i]<=b[i]<=r),我们定义p,c两个数组,其中c[i]=b[i]-a[i],p数组是c数组的相对大小,现给你a和p数组,把任意满足的一组b数组求出来.如果没有满足的,则输出‘-1’(没有引号). # 输入格式 第一行包含3个整数n,l,r 其中(1<=n<=10^5)，(1<=l<=r<=10^9) 第二行为n个a[1],a[2],...,a[n], 第三行为n个p[1],p[2],...,p[n] a,p的意义已在题目大意中有讲述 # 输出格式 一行符合条件的b数组， 若没有符合的情况，则输出'-1'(没有引号)

题目描述

Dasha logged into the system and began to solve problems. One of them is as follows: Given two sequences $ a $ and $ b $ of length $ n $ each you need to write a sequence $ c $ of length $ n $ , the $ i $ -th element of which is calculated as follows: $ c_{i}=b_{i}-a_{i} $ . About sequences $ a $ and $ b $ we know that their elements are in the range from $ l $ to $ r $ . More formally, elements satisfy the following conditions: $ l<=a_{i}<=r $ and $ l<=b_{i}<=r $ . About sequence $ c $ we know that all its elements are distinct. Dasha wrote a solution to that problem quickly, but checking her work on the standard test was not so easy. Due to an error in the test system only the sequence $ a $ and the compressed sequence of the sequence $ c $ were known from that test. Let's give the definition to a compressed sequence. A compressed sequence of sequence $ c $ of length $ n $ is a sequence $ p $ of length $ n $ , so that $ p_{i} $ equals to the number of integers which are less than or equal to $ c_{i} $ in the sequence $ c $ . For example, for the sequence $ c=[250,200,300,100,50] $ the compressed sequence will be $ p=[4,3,5,2,1] $ . Pay attention that in $ c $ all integers are distinct. Consequently, the compressed sequence contains all integers from $ 1 $ to $ n $ inclusively. Help Dasha to find any sequence $ b $ for which the calculated compressed sequence of sequence $ c $ is correct.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ l $ , $ r $ $ (1<=n<=10^{5},1<=l<=r<=10^{9}) $ — the length of the sequence and boundaries of the segment where the elements of sequences $ a $ and $ b $ are. The next line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ $ (l<=a_{i}<=r) $ — the elements of the sequence $ a $ . The next line contains $ n $ distinct integers $ p_{1},p_{2},...,p_{n} $ $ (1<=p_{i}<=n) $ — the compressed sequence of the sequence $ c $ .

输出格式

If there is no the suitable sequence $ b $ , then in the only line print "-1". Otherwise, in the only line print $ n $ integers — the elements of any suitable sequence $ 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

说明

Sequence $ b $ which was found in the second sample is suitable, because calculated sequence $ c=[2-3,2-4,2-8,9-9]=[-1,-2,-6,0] $ (note that $ c_{i}=b_{i}-a_{i} $ ) has compressed sequence equals to $ p=[3,2,1,4] $ .