Description

序列的 mex（最小未出现值 的缩写）是指不在序列中的最小非负整数。例如：

• $\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$

虽然 mex 函数在组合博弈论中有应用，但它仍然是一种相当小众的将序列映射为整数的方法。在没有更“有机”问题的情况下，我们借用这个概念构造了一个略显人为的任务。抱歉！

请编写一个程序，在给定两个正整数序列 $a = [a_1, a_2, \cdots, a_n]$ 和 $b = [b_1, b_2, \cdots, b_n]$ 后，计算以下递推式：对于 $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\})$$

Input Format

你的程序需要从标准输入读取数据。第一行包含一个整数 $n$ ($1 \le n \le 250,000$)，表示序列的长度。第二行包含 $n$ 个正整数 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$)，表示序列 $a$。第三行包含 $n$ 个正整数 $b_1, b_2, \cdots, b_n$ ($1 \le b_i \le 10^9$)，表示序列 $b$。

Output Format

你的程序需要向标准输出写入数据。输出恰好一行，包含 $n$ 个用空格分隔的整数，分别表示 $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