/ 
Time Limit: 5 sec / Memory Limit: 1024 MiB
配点 : 900 点
問題文
数列 X のコストを，(X の最大値 - X の最小値) で定義します．
長さ N の数列 A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_N) が与えられるので，k=1,2,\ldots,N に対して次の問題を解いてください．
- i 番目の要素 C_i が A_i または B_i であるような数列 C=(C_1,\ldots,C_k) のコストとしてあり得る最小値を求めてください．
制約
- 入力される数値は全て整数
- 1 \leq N \leq 5\times 10^5
- 1\leq A_i,B_i\leq 10^9
入力
入力は以下の形式で標準入力から与えられる．
N A_1 \ldots A_N B_1 \ldots B_N
出力
N 行出力せよ．
i\ (1\leq i\leq N) 行目には，k=i の場合の数列 C のコストとしてあり得る最小値を出力せよ．
入力例 1
3 8 11 10 7 6 1
出力例 1
0 1 3
k=1 の場合，C=(8) とすると C のコストは 0 となりこれが最小です．
k=2 の場合，C=(7,6) とすると C のコストは 1 となりこれが最小です．
k=3 の場合，C=(8,11,10) とすると C のコストは 3 となりこれが最小です．
入力例 2
10 43 35 36 58 25 7 61 4 96 3 55 29 88 15 99 49 67 57 92 49
出力例 2
0 8 8 23 28 33 36 36 64 64
Score : 900 points
Problem Statement
Define the cost of a sequence X as (the maximum value of X minus the minimum value of X).
You are given sequences A = (A_1, \ldots, A_N) and B = (B_1, \ldots, B_N) of length N. Solve the following problem for k = 1, 2, \ldots, N.
- Find the minimum possible cost of the sequence C = (C_1, \ldots, C_k) whose i-th element C_i is A_i or B_i.
Constraints
- All input numbers are integers.
- 1 \leq N \leq 5 \times 10^5
- 1 \leq A_i, B_i \leq 10^9
Input
The input is given from Standard Input in the following format:
N A_1 \ldots A_N B_1 \ldots B_N
Output
Print N lines.
The i-th line (1 \leq i \leq N) should contain the minimum possible cost of sequence C for k = i.
Sample Input 1
3 8 11 10 7 6 1
Sample Output 1
0 1 3
For k=1, if we choose C = (8), the cost of C is 0, which is the minimum.
For k=2, if we choose C = (7,6), the cost of C is 1, which is the minimum.
For k=3, if we choose C = (8,11,10), the cost of C is 3, which is the minimum.
Sample Input 2
10 43 35 36 58 25 7 61 4 96 3 55 29 88 15 99 49 67 57 92 49
Sample Output 2
0 8 8 23 28 33 36 36 64 64