Get Stale Skill Count

Each log entry is a skillId and a timestamp. For each query q, count the skills that have no request in the closed interval [q−timeWindow,q]; output the answers in the input order of the queries.

输入格式

The first line contains numSkills m q timeWindow, all four in 1..100000; then m lines of skill timestamp, then one line of q queryTime values. skill is in 1..numSkills, and all times are in 1..100000.

输出格式

One line of q inactive counts, separated by spaces.

样例 1

输入：

3 2 2 2
1 1
2 3
3 4

输出：

1 2

样例 2

输入：

2 1 2 1
1 5
5 1

输出：

1 2

样例 3

输入：

1 2 1 1
1 1
1 2
2

输出：

0

样例说明

Example 1: for q=3 the window [1,3] contains skills 1 and 2, so 1 skill is inactive; for q=4 the window [2,4] contains only skill 2, so 2 are inactive. Example 2: query 5 has skill 1, so 1 is inactive; query 1 has no logs, so 2 are inactive, and the original order is kept. Example 3: both log entries belong to skill 1, which counts as only one active skill, so 0 are inactive.