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\backslash text\{mex\}(\backslash \{\; \backslash \})\; =\; 0$
• $\text{mex}(\{1,2,3\})=0\backslash text\{mex\}(\backslash \{1,\; 2,\; 3\backslash \})\; =\; 0$
• $\text{mex}(\{5,0,1,1,4\})=2\backslash text\{mex\}(\backslash \{5,\; 0,\; 1,\; 1,\; 4\backslash \})\; =\; 2$
• $\text{mex}(\{0,5,2,1,5,0,1,2\})=3\backslash text\{mex\}(\backslash \{0,\; 5,\; 2,\; 1,\; 5,\; 0,\; 1,\; 2\backslash \})\; =\; 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]a\; =\; [a\_1,\; a\_2,\; \backslash cdots\; ,\; a\_n\; ]$ and $b=[b_1,b_2,\cdots ,b_n]b\; =\; [b\_1,\; b\_2,\; \backslash 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, $nn$ (1 ≤ n ≤ 250\,000), representing the length of the sequences. The second line contains $nn$ positive integers $a_1,a_2,\cdots ,a_{n}a\_1,\; a\_2,\; \backslash cdots\; ,\; a\_n$ (1 ≤ a_i ≤ 10^9) representing the sequence $aa$. The third line contains $nn$ positive integers $b_1,b_2,\cdots ,b_{n}b\_1,\; b\_2,\; \backslash cdots\; ,\; b\_n$ (1 ≤ b_i ≤ 10^9), representing the sequence $bb$.

출력

Your program is to write to standard output. Print exactly one line consisting of $nn$ space-separated integers, denoting $f_1,f_2,\cdots ,f_{n}f\_1,\; f\_2,\; \backslash cdots\; ,\; f\_n$.

3
3 1 5
2 2 4

0 1 1

8
1 2 9 4 6 9 7 10
9 3 7 1 1 7 1 1

0 1 1 2 1 2 2 3

15
1 1 5 1 2 3 8 8 6 5 9 1 1 4 3
2 5 7 4 6 4 1 3 4 8 3 4 2 10 1

0 1 0 2 3 4 1 2 5 6 3 5 6 7 8