変更履歴

2023/8/14: 制約の$x,y$を$10^{9}$から$10^{18}$に変更しました。

はじめに

Pythonのdict(defaultdict)やC++のunordered_mapの各アクセスの計算量の平均時間計算量は$O(1)$です。 しかし、これらの内部のデータ構造の内部を意識した意図的な入力に対して$O(N)$となることがあります。

問題文

2次元平面上に$N$個の点があり、各点は$(x,y)$の形式で与えられます。

$Q$行の$a$が与えられます。$x=a$である点が何個あるかを答えてください。

制約

• $1 \leq n, q \leq 2 \times 10^{5}$
• $0 \leq x_i, y_i \leq 10^{18}$
• 入力は整数
• 同じ座標や同じクエリが複数回与えられることがあります。

入力

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

N
x_1 y_1
x_2 y_2
...
x_N y_N
Q
a_1 a_2 ... a_Q

出力

出力は1行で$Q$個の整数を改行区切りで回答してください。

入力例1

4
0 0
2 2
2 2
2 10
3
0 2 3

出力例1

1 3 0

平面上には$(x,y) = (0,0), (2,2), (2,2), (2, 10)$の4つの点があります。同じ座標に複数の点が与えられることがあります。

$x=0$の点は1つ、$x=2$の点は3つ、$x=3$の点は0です。

入力例2

3
1000000000000000000 1000000000000000000
1 1000000000000000000
1000000000000000000 1
3
1 1000000000000000000 1000000000000000000

出力例2

1 2 2

クエリも同じ数が与えられることもあるので気をつけてください。

入力例3

5
409625736937271963 750740243247026844
135717226958827691 871048951565803286
135717226958827691 715892133706525003
626644811401629911 478812307546956573
995364342760369820 212527392052600681
7
891598449773446849 409625736937271963 135717226958827691 754906740922233097 626644811401629911 995364342760369820 515759173885864023

出力例2

0 1 2 0 1 1 0