CF761D.Dasha and Very Difficult Problem

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Dasha logged into the system and began to solve problems. One of them is as follows:

Given two sequences aa and bb of length nn each you need to write a sequence cc of length nn , the ii -th element of which is calculated as follows: ci=biaic_{i}=b_{i}-a_{i} .

About sequences aa and bb we know that their elements are in the range from ll to rr . More formally, elements satisfy the following conditions: l<=ai<=rl<=a_{i}<=r and l<=bi<=rl<=b_{i}<=r . About sequence cc 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 aa and the compressed sequence of the sequence cc were known from that test.

Let's give the definition to a compressed sequence. A compressed sequence of sequence cc of length nn is a sequence pp of length nn , so that pip_{i} equals to the number of integers which are less than or equal to cic_{i} in the sequence cc . For example, for the sequence c=[250,200,300,100,50]c=[250,200,300,100,50] the compressed sequence will be p=[4,3,5,2,1]p=[4,3,5,2,1] . Pay attention that in cc all integers are distinct. Consequently, the compressed sequence contains all integers from 11 to nn inclusively.

Help Dasha to find any sequence bb for which the calculated compressed sequence of sequence cc is correct.

输入格式

The first line contains three integers nn , ll , rr (1<=n<=105,1<=l<=r<=109)(1<=n<=10^{5},1<=l<=r<=10^{9}) — the length of the sequence and boundaries of the segment where the elements of sequences aa and bb are.

The next line contains nn integers a1,a2,...,ana_{1},a_{2},...,a_{n} (l<=ai<=r)(l<=a_{i}<=r) — the elements of the sequence aa .

The next line contains nn distinct integers p1,p2,...,pnp_{1},p_{2},...,p_{n} (1<=pi<=n)(1<=p_{i}<=n) — the compressed sequence of the sequence cc .

输出格式

If there is no the suitable sequence bb , then in the only line print "-1".

Otherwise, in the only line print nn integers — the elements of any suitable sequence bb .

输入输出样例

  • 输入#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 bb which was found in the second sample is suitable, because calculated sequence c=[23,24,28,99]=[1,2,6,0]c=[2-3,2-4,2-8,9-9]=[-1,-2,-6,0] (note that ci=biaic_{i}=b_{i}-a_{i} ) has compressed sequence equals to p=[3,2,1,4]p=[3,2,1,4] .

首页