{"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 element of which is calculated as follows: _c__i_ = _b__i_ - _a__i_.\n\nAbout 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.\n\n<center>![image](https://espresso.codeforces.com/041839fe8b08bee3b1ca88484750522e42d0e3cf.png)</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.\n\nLet'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.\n\nHelp Dasha to find any sequence _b_ for which the calculated _compressed sequence_ of sequence _c_ is correct.\n\n## Input\n\nThe 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.\n\nThe next line contains _n_ integers _a_1,  _a_2,  ...,  _a__n_ (_l_ ≤ _a__i_ ≤ _r_) — the elements of the sequence _a_.\n\nThe next line contains _n_ distinct integers _p_1,  _p_2,  ...,  _p__n_ (1 ≤ _p__i_ ≤ _n_) — the _compressed sequence_ of the sequence _c_.\n\n## Output\n\nIf there is no the suitable sequence _b_, then in the only line print \"_\\-1_\".\n\nOtherwise, in the only line print _n_ integers — the elements of any suitable sequence _b_.\n\n[samples]\n\n## Note\n\nSequence _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\\].","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] 的元素均在范围 #cf_span[l] 到 #cf_span[r] 之间。更正式地，元素满足以下条件：#cf_span[l ≤ ai ≤ r] 和 #cf_span[l ≤ bi ≤ r]。对于序列 #cf_span[c]，我们知道它的所有元素互不相同。\n\nDasha 快速写出了该问题的解法，但在使用标准测试用例验证时遇到了困难。由于测试系统出现错误，仅知道该测试用例中的序列 #cf_span[a] 和序列 #cf_span[c] 的 _压缩序列_。\n\n定义 _压缩序列_：长度为 #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] 的所有整数。\n\n请帮助 Dasha 找到任意一个序列 #cf_span[b]，使得计算出的序列 #cf_span[c] 的 _压缩序列_ 与给定值一致。\n\n第一行包含三个整数 #cf_span[n], #cf_span[l], #cf_span[r] #cf_span[(1 ≤ n ≤ 105, 1 ≤ l ≤ r ≤ 109)] —— 序列长度及序列 #cf_span[a] 和 #cf_span[b] 元素的取值范围边界。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1,  a2,  ...,  an] #cf_span[(l ≤ ai ≤ r)] —— 序列 #cf_span[a] 的元素。\n\n第三行包含 #cf_span[n] 个互不相同的整数 #cf_span[p1,  p2,  ...,  pn] #cf_span[(1 ≤ pi ≤ n)] —— 序列 #cf_span[c] 的 _压缩序列_。\n\n如果不存在合适的序列 #cf_span[b]，则在唯一一行输出 \"_-1_\"。\n\n否则，在唯一一行输出 #cf_span[n] 个整数 —— 任意一个合适的序列 #cf_span[b] 的元素。\n\n第二个样例中找到的序列 #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]]。\n\n## Input\n\n第一行包含三个整数 #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] 的 _压缩序列_。\n\n## Output\n\n如果不存在合适的序列 #cf_span[b]，则在唯一一行输出 \"_-1_\"。否则，在唯一一行输出 #cf_span[n] 个整数 —— 任意一个合适的序列 #cf_span[b] 的元素。\n\n[samples]\n\n## Note\n\n第二个样例中找到的序列 #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]]。","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_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 $.  \n\n**Constraints**  \n1. $ c_i = b_i - a_i $ for all $ i \\in \\{1, \\dots, n\\} $.  \n2. $ b_i \\in [l, r] $ for all $ i \\in \\{1, \\dots, n\\} $.  \n3. All $ c_i $ are distinct.  \n4. For all $ i \\in \\{1, \\dots, n\\} $, $ p_i = |\\{ j \\in \\{1, \\dots, n\\} \\mid c_j \\leq c_i \\}| $.  \n\n**Objective**  \nFind 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:  \n- $ c_i $ are distinct,  \n- $ b_i \\in [l, r] $,  \n- The rank of $ c_i $ (i.e., its position in sorted order) is exactly $ p_i $.  \n\nEquivalently, 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)} $.  \nThen set $ b_i = c_{(p_i)} + a_i $, and check $ b_i \\in [l, r] $.  \n\nIf such $ c_{(1)}, \\dots, c_{(n)} $ exist, output any valid $ B $. Otherwise, output $-1$.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF761D","tags":["binary search","brute force","constructive algorithms","greedy","sortings"],"sample_group":[["5 1 5\n1 1 1 1 1\n3 1 5 4 2","3 1 5 4 2"],["4 2 9\n3 4 8 9\n3 2 1 4","2 2 2 9"],["6 1 5\n1 1 1 1 1 1\n2 3 5 4 1 6","\\-1"]],"created_at":"2026-03-03 11:00:39"}}