A10862. Dasha and Very Difficult Problem
编程题
普及/提高-
知识点
题目描述
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.
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$ .
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$ .
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]$ .