题目背景

Due to variations in the performance of the evaluation system, an additional 2 seconds of time limit is provided for this problem.

题目描述

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 \le i \le n$,

$$f_i = \text{mex}(\{f_j \mid 1 \le j \le i-1; a_i \le a_j + b_j; a_j \le a_i + b_i\})$$

输入格式

Your program is to read from standard input. The first line contains a single integer, $n$ ($1 \le n \le 250,000$), representing the length of the sequences. The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$) representing the sequence $a$. The third line contains $n$ positive integers $b_1, b_2, \cdots, b_n$ ($1 \le b_i \le 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$.

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