Find Idle Skills Query

Each log entry has a skill ID and a request time. For each query q, count the skills that have no request in the closed interval [q−window,q], and output the answers in the original query order.

输入格式

The first line contains numSkills m q window; each of the next m lines contains a 1-based skill ID and a time, and the last line contains q query times. The four size/window parameters are in 1..100000, times and queries are in 1..100000, and IDs are valid.

输出格式

Output q idle skill counts in the original query order.

样例 1

输入：

3 3 2 5
1 3
2 6
1 5
10 11

输出：

1 2

样例 2

输入：

6 4 3 2
3 2
4 3
2 6
6 3
3 2 6

输出：

3 5 5

样例 3

输入：

1 1 2 1
1 5
6 7

输出：

0 1

样例说明

Example 1: in the window 5..10 the active skills are 1 and 2, so 1 is idle; in 6..11 only skill 2 is active, so 2 are idle. Example 2: in the original query order the active counts are 3, 1, 1, so the idle counts are 3, 5, 5. Example 3: query 6 includes the request at the left end 5, so 0 are idle; query 7 does not, so 1 is idle.