序列的 mex（minimum excluded value，最小排斥值）是指序列中未出现的最小非负整数。例如：

• $\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, \dots, a_n]$ 和 $b = [b_1, b_2, \dots, 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\})$$

输入格式

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

输出格式

程序向标准输出写入数据。输出一行，包含 $n$ 个由空格分隔的整数，表示 $f_1, f_2, \dots, f_n$。

样例

输入 1

3
3 1 5
2 2 4

输出 1

0 1 1

输入 2

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

输出 2

0 1 1 2 1 2 2 3

输入 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

输出 3

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