問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N) が与えられます。

区間 [l,r] \,(1 \le l \le r \le N) のスコアを以下で定義します。

• |\min(A_l,A_{l+1},\ldots,A_r)-\min(B_l,B_{l+1},\ldots,B_r)|

k=0,1,\ldots,N-1 について、r-l=k を満たす [l,r] を選んだときのスコアとしてあり得る最小値を求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i,B_i \leq 10^9
• 入力はすべて整数

入力例 1

3
1 3 4
8 5 7

出力例 1

2
2
4

k=0 のとき、l=2,r=2 とするとスコアが最小になります。

k=1 のとき、l=2,r=3 とするとスコアが最小になります。

k=2 のとき、l=1,r=3 とするとスコアが最小になります。

入力例 2

1
1
1

出力例 2

0

入力例 3

6
3 1 4 1 5 9
2 6 5 3 5 8

出力例 3

0
0
1
1
1
1