Do the Times Overlap?

Interview

Time limit1sMemory limit512 MB

Summary

Given N closed time intervals [S, E] of seat use, count how many intervals contain each queried time t.

Level: Easy3 of 10
Topics: Prefix sum, Sorting, Binary search
Solved: No attempts yet

Problem

Not long ago, a question appeared on the Pusan National University community board asking which time slots have the most empty seats in the library reading room.

The poster asked students to reply with when they used the reading room last Sunday.

Many students replied with the times they were there.

Pusan National University students do not leave their assigned seats during study hours.

A seat cannot be selected at the moment its use ends.

For convenience, times are given from $0$ to $1\,000\,000$ in integer units. Find the number of seats that cannot be selected at each given time.

Input

The first line contains $N$ , the number of students who replied. $(1\leq N\leq 100\,000)$

Each of the next $N$ lines contains $S$ , the start time of a student's seat use, and $E$ , the end time. $(1\leq S\leq E\leq 1\,000\,000)$

The next line contains $Q$ , the number of times to check. $(1\leq Q\leq 100\,000)$

The next line contains the $Q$ times to check.

Output

For each given time, print the number of seats that cannot be selected at that time, in the given order, one per line.

Examples2

Example 1
Input
```
1
1 3
2
2 4
```
Expected output
```
1
0
```
Example 2
Input
```
2
1 5
3 6
3
2 3 7
```
Expected output
```
1
2
0
```