AT_arc187_d.[ARC187D] Many Easy Optimizations

定义序列 $X$ 的价值为 $X$ 的最大值减去 $X$ 的最小值的值。

给定两个长度为 $N$ 序列 $A=(A_1,\dots,A_N)$ 和 $B=(B_1,\dots,B_N)$。对于每一个 $k=1,2,\dots,N$，解决以下问题：

• 求出序列 $C=(C_1,\dots,C_k)$ 的最小价值且序列 $C$ 满足 $C_i$ 为 $A_i$ 或 $B_i$。

第一行一个整数 $N$。

第二行 $N$ 个整数 $A_1,\dots,A_N$。

第三行 $N$ 个整数 $B_1,\dots,B_N$。

输出 $N$ 行。

第 $i$ 行为，当 $k=i$ 时序列 $C$ 的最小可能价值。

样例 1 解释

当 $k=1$ 时，序列 $C=(8)$，有最小价值 $0$。

当 $k=2$ 时，序列 $C=(7,6)$，有最小价值 $1$。

当 $k=3$ 时，序列 $C=(8,11,10)$，有最小价值 $3$。

• 所有输入均为整数。
• $1\le N\le 5\times 10^5$。
• $1\le A_i,B_i\le 10^9$。