34869번 - Mex Culpa 다국어

문제

The mex (shorthand for minimum excluded value) of a sequence is the smallest non-negative integer that is not in the sequence. For example:

• $\text{mex}(\{ \}) = 0$
• $\text{mex}(\{1, 2, 3\}) = 0$
• $\text{mex}(\{5, 0, 1, 1, 4\}) = 2$
• $\text{mex}(\{0, 5, 2, 1, 5, 0, 1, 2\}) = 3$

While the mex function has applications in combinatorial game theory, it is still a rather niche method for mapping a sequence to an integer. In the absence of a more organic problem, we have repurposed this concept to construct a task of a somewhat artificial nature. Sorry!

Write a program that, given two sequences of positive integers $a = [a_1, a_2, \cdots , a_n ]$ and $b = [b_1, b_2, \cdots , b_n ],ドル evaluates the following recurrence: for 1ドル ≤ i ≤ n,ドル

$$f_i = \text{mex}(\{f_j | 1 ≤ j ≤ i − 1; a_i ≤ a_j + b_j ; a_j ≤ a_i + b_i \})$$

입력

Your program is to read from standard input. The first line contains a single integer, $n$ (1ドル ≤ n ≤ 250,000円$), representing the length of the sequences. The second line contains $n$ positive integers $a_1, a_2, \cdots , a_n$ (1ドル ≤ a_i ≤ 10^9$) representing the sequence $a$. The third line contains $n$ positive integers $b_1, b_2, \cdots , b_n$ (1ドル ≤ b_i ≤ 10^9$), representing the sequence $b$.

출력

Your program is to write to standard output. Print exactly one line consisting of $n$ space-separated integers, denoting $f_1, f_2, \cdots , f_n$.

제한

노트