K - 奇妙な等式 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

問題文

長さ N の整数列 A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N),C=(C_1,C_2,\dots,C_N),D=(D_1,D_2,\dots,D_N),E=(E_1,E_2,\dots,E_N) が与えられます。

任意の i\ (1\leq i\leq N) について、f(i) を \max(A_i, B_j-C_i)=D_j+E_i を満たす j\ (1\leq j\leq N) の個数と定めます。

f(1),f(2),\dots,f(N) を求めてください。

制約

  • 1\leq N \leq 2\times 10^5
  • -10^9\leq A_i,B_i,C_i,D_i,E_i \leq 10^9
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
C_1 C_2 \dots C_N
D_1 D_2 \dots D_N
E_1 E_2 \dots E_N

出力

f(1),f(2),\dots,f(N) をこの順に空白区切りで出力せよ。

入力例 1

3
4 3 10
3 1 9
2 6 6
1 3 4
3 5 6

出力例 1

2 0 1
  • i=1 のとき、\max(A_i, B_j-C_i)=D_j+E_i を満たす j は j=1,3 です。 実際、j=3 のとき \max(4, 9-2)=4+3 が成り立ちます。
  • i=2 のとき、\max(A_i, B_j-C_i)=D_j+E_i を満たす j はありません。
  • i=3 のとき、\max(A_i, B_j-C_i)=D_j+E_i を満たす j は j=3 です。

よって、f(1)=2,f(2)=0,f(3)=1 です。

入力例 2

3
4 6 -10
9 2 6
-5 -5 3
7 0 4
7 7 -1

出力例 2

3 3 3

すべての 1\leq i,j\leq 3 について \max(A_i, B_j-C_i)=D_j+E_i が成り立ちます。

入力例 3

8
68 108 176 112 146 156 80 82
-158 -59 72 108 -9 -158 51 95
-69 -192 -177 -61 -38 -157 -112 -83
-60 39 14 97 37 -60 97 97
-29 94 79 15 49 59 66 -15

出力例 3

0 1 0 1 3 0 2 0

Problem Statement

You are given length-N integer sequences A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N),C=(C_1,C_2,\dots,C_N),D=(D_1,D_2,\dots,D_N), and E=(E_1,E_2,\dots,E_N).

For an integer i\ (1\leq i\leq N), let f(i) be the number of indices j\ (1\leq j\leq N) such that \max(A_i, B_j-C_i)=D_j+E_i.

Find f(1),f(2),\dots,f(N).

Constraints

  • 1\leq N \leq 2\times 10^5
  • -10^9\leq A_i,B_i,C_i,D_i,E_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
C_1 C_2 \dots C_N
D_1 D_2 \dots D_N
E_1 E_2 \dots E_N

Output

Print f(1),f(2),\dots,f(N) in this order, with spaces in between.

Sample Input 1

3
4 3 10
3 1 9
2 6 6
1 3 4
3 5 6

Sample Output 1

2 0 1
  • For i=1, the indices j that satisfy \max(A_i, B_j-C_i)=D_j+E_i are j=1,3. Indeed, for j=3 we have \max(4, 9-2)=4+3.
  • For i=2, no indices j satisfy \max(A_i, B_j-C_i)=D_j+E_i.
  • For i=3, the indices j that satisfy \max(A_i, B_j-C_i)=D_j+E_i are j=3.

Therefore, f(1)=2,f(2)=0, and f(3)=1.

Sample Input 2

3
4 6 -10
9 2 6
-5 -5 3
7 0 4
7 7 -1

Sample Output 2

3 3 3

\max(A_i, B_j-C_i)=D_j+E_i holds for all 1\leq i,j\leq 3.

Sample Input 3

8
68 108 176 112 146 156 80 82
-158 -59 72 108 -9 -158 51 95
-69 -192 -177 -61 -38 -157 -112 -83
-60 39 14 97 37 -60 97 97
-29 94 79 15 49 59 66 -15

Sample Output 3

0 1 0 1 3 0 2 0