English · Original
Chinese · Translation
Formal · Original
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.
<center></center>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.
## Input
The first line contains three integers _n_, _l_, _r_ (1 ≤ _n_ ≤ 105, 1 ≤ _l_ ≤ _r_ ≤ 109) — 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_.
## Output
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_.
[samples]
## Note
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\].
Dasha 登录系统后开始解题。其中一个题目如下：
给定两个长度均为 #cf_span[n] 的序列 #cf_span[a] 和 #cf_span[b]，你需要构造一个长度为 #cf_span[n] 的序列 #cf_span[c]，其中第 #cf_span[i] 个元素计算为：#cf_span[ci = bi - ai]。
已知序列 #cf_span[a] 和 #cf_span[b] 的元素均在范围 #cf_span[l] 到 #cf_span[r] 之间。更正式地，元素满足以下条件：#cf_span[l ≤ ai ≤ r] 和 #cf_span[l ≤ bi ≤ r]。对于序列 #cf_span[c]，我们知道它的所有元素互不相同。
Dasha 快速写出了该问题的解法，但在使用标准测试用例验证时遇到了困难。由于测试系统出现错误，仅知道该测试用例中的序列 #cf_span[a] 和序列 #cf_span[c] 的 _压缩序列_。
定义 _压缩序列_：长度为 #cf_span[n] 的序列 #cf_span[c] 的 _压缩序列_ 是一个长度为 #cf_span[n] 的序列 #cf_span[p]，其中 #cf_span[pi] 等于序列 #cf_span[c] 中小于等于 #cf_span[ci] 的整数个数。例如，对于序列 #cf_span[c = [250, 200, 300, 100, 50]]，其压缩序列为 #cf_span[p = [4, 3, 5, 2, 1]]。注意，#cf_span[c] 中所有整数互不相同，因此 _压缩序列_ 包含从 #cf_span[1] 到 #cf_span[n] 的所有整数。
请帮助 Dasha 找到任意一个序列 #cf_span[b]，使得计算出的序列 #cf_span[c] 的 _压缩序列_ 与给定值一致。
第一行包含三个整数 #cf_span[n], #cf_span[l], #cf_span[r] #cf_span[(1 ≤ n ≤ 105, 1 ≤ l ≤ r ≤ 109)] —— 序列长度及序列 #cf_span[a] 和 #cf_span[b] 元素的取值范围边界。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] #cf_span[(l ≤ ai ≤ r)] —— 序列 #cf_span[a] 的元素。
第三行包含 #cf_span[n] 个互不相同的整数 #cf_span[p1, p2, ..., pn] #cf_span[(1 ≤ pi ≤ n)] —— 序列 #cf_span[c] 的 _压缩序列_。
如果不存在合适的序列 #cf_span[b]，则在唯一一行输出 "_-1_"。
否则，在唯一一行输出 #cf_span[n] 个整数 —— 任意一个合适的序列 #cf_span[b] 的元素。
第二个样例中找到的序列 #cf_span[b] 是合适的，因为计算得到的序列 #cf_span[c = [2 - 3, 2 - 4, 2 - 8, 9 - 9] = [ - 1, - 2, - 6, 0]]（注意 #cf_span[ci = bi - ai]）的压缩序列为 #cf_span[p = [3, 2, 1, 4]]。
## Input
第一行包含三个整数 #cf_span[n], #cf_span[l], #cf_span[r] #cf_span[(1 ≤ n ≤ 105, 1 ≤ l ≤ r ≤ 109)] —— 序列长度及序列 #cf_span[a] 和 #cf_span[b] 元素的取值范围边界。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] #cf_span[(l ≤ ai ≤ r)] —— 序列 #cf_span[a] 的元素。第三行包含 #cf_span[n] 个互不相同的整数 #cf_span[p1, p2, ..., pn] #cf_span[(1 ≤ pi ≤ n)] —— 序列 #cf_span[c] 的 _压缩序列_。
## Output
如果不存在合适的序列 #cf_span[b]，则在唯一一行输出 "_-1_"。否则，在唯一一行输出 #cf_span[n] 个整数 —— 任意一个合适的序列 #cf_span[b] 的元素。
[samples]
## Note
第二个样例中找到的序列 #cf_span[b] 是合适的，因为计算得到的序列 #cf_span[c = [2 - 3, 2 - 4, 2 - 8, 9 - 9] = [ - 1, - 2, - 6, 0]]（注意 #cf_span[ci = bi - ai]）的压缩序列为 #cf_span[p = [3, 2, 1, 4]]。
**Definitions**
Let $ n, l, r \in \mathbb{Z} $ with $ 1 \leq n \leq 10^5 $, $ 1 \leq l \leq r \leq 10^9 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence with $ a_i \in [l, r] $.
Let $ P = (p_1, p_2, \dots, p_n) $ be a permutation of $ \{1, 2, \dots, n\} $, representing the compressed sequence of $ C = (c_1, \dots, c_n) $, where $ c_i = b_i - a_i $.
**Constraints**
1. $ c_i = b_i - a_i $ for all $ i \in \{1, \dots, n\} $.
2. $ b_i \in [l, r] $ for all $ i \in \{1, \dots, n\} $.
3. All $ c_i $ are distinct.
4. For all $ i \in \{1, \dots, n\} $, $ p_i = |\{ j \in \{1, \dots, n\} \mid c_j \leq c_i \}| $.
**Objective**
Find a sequence $ B = (b_1, \dots, b_n) $ such that $ b_i = c_i + a_i $, and the values $ c_i $ induced by $ P $ satisfy:
- $ c_i $ are distinct,
- $ b_i \in [l, r] $,
- The rank of $ c_i $ (i.e., its position in sorted order) is exactly $ p_i $.
Equivalently, assign distinct values $ c_{(1)} < c_{(2)} < \dots < c_{(n)} $ such that for each $ i $, $ c_i $ has rank $ p_i $, i.e., $ c_i = c_{(p_i)} $.
Then set $ b_i = c_{(p_i)} + a_i $, and check $ b_i \in [l, r] $.
If such $ c_{(1)}, \dots, c_{(n)} $ exist, output any valid $ B $. Otherwise, output $-1$.
API Response (JSON)
{
"problem": {
"name": "D. Dasha and Very Difficult Problem",
"description": {
"content": "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 ele",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF761D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Dasha logged into the system and began to solve problems. One of them is as follows:\n\nGiven two sequences _a_ and _b_ of length _n_ each you need to write a sequence _c_ of length _n_, the _i_\\-th ele...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Dasha 登录系统后开始解题。其中一个题目如下：\n\n给定两个长度均为 #cf_span[n] 的序列 #cf_span[a] 和 #cf_span[b]，你需要构造一个长度为 #cf_span[n] 的序列 #cf_span[c]，其中第 #cf_span[i] 个元素计算为：#cf_span[ci = bi - ai]。\n\n已知序列 #cf_span[a] 和 #cf_span[b] 的元素均...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, l, r \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^5 $, $ 1 \\leq l \\leq r \\leq 10^9 $. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence with $ a_i \\in [l, r] $. \nLet $ P = (p_...",
"is_translate": false,
"language": "Formal"
}
]
}