J - Cafe Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

カフェに、客 1 、客 2 、\ldots 、客 N と番号づけられた N 人の客が来店しました。
i = 1, 2, \ldots, N について、客 i は時刻 A_i から時刻 B_i まで（時刻 A_i と時刻 B_i も含む）カフェに滞在しました。
また、これら N 人の他には、カフェに来店した客はいませんでした。

Q 個の時刻 t_1, t_2, \ldots, t_Q について、 その時刻にカフェにいた客の人数を出力してください。

制約

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

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
Q
t_1
t_2
\vdots
t_Q

出力

Q 行出力せよ。 i = 1, 2, \ldots, Q について、i 行目には時刻 t_i にカフェにいた客の人数を出力せよ。

入力例 1

4
2 4
4 5
3 6
4 5
7
1
2
3
4
5
6
7

出力例 1

0
1
2
4
3
1
0
  • 時刻 1 には、カフェには客は誰もいません。
  • 時刻 2 には、カフェに 客 1 の 1 人の客のみがいます。
  • 時刻 3 には、カフェに 客 1, 3 の 2 人の客がいます。
  • 時刻 4 には、カフェに 客 1, 2, 3, 4 の 4 人の客がいます。
  • 時刻 5 には、カフェに 客 2, 3, 4 の 3 人の客がいます。
  • 時刻 6 には、カフェに 客 3 の 1 人の客のみがいます。
  • 時刻 7 には、カフェには客は誰もいません。

入力例 2

1
1 1000000000
2
1000000000
1

出力例 2

1
1

Problem Statement

N customers visited a cafe: customer 1, customer 2, \ldots, and customer N.
For i = 1, 2, \ldots, N, customer i stayed in the cafe from time A_i to time B_i (including time A_i and time B_i).
No customers other than these N visited the cafe.

For each of Q times t_1, t_2, \ldots, t_Q, find the number of customers who were staying in the cafe at that time.

Constraints

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq 10^9
  • 1 \leq t_i \leq 10^9
  • All input values are integers.

Input

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
Q
t_1
t_2
\vdots
t_Q

Output

Print Q lines. For i = 1, 2, \ldots, Q, the i-th line should contain the number of customers who were staying in the cafe at time t_i.

Sample Input 1

4
2 4
4 5
3 6
4 5
7
1
2
3
4
5
6
7

Sample Output 1

0
1
2
4
3
1
0
  • At time 1, no one was in the cafe.
  • At time 2, one customer was in the cafe: customer 1.
  • At time 3, two customers were in the cafe: customers 1 and 3.
  • At time 4, four customers were in the cafe: customers 1, 2, 3, and 4.
  • At time 5, three customers were in the cafe: customers 2, 3, and 4.
  • At time 6, one customer was in the cafe: customer 3.
  • At time 7, no one was in the cafe.

Sample Input 2

1
1 1000000000
2
1000000000
1

Sample Output 2

1
1