Ada the Ladybug is currently growing plants. She has a very long furrow, in which she does so. It is so long, that most of water falling from rains drops just onto a part (segment) of the furrow. Ada doesn't want the plants to wither, so she records all rains to know, how much water every particular plant got. Sadly, there are so many rains that she couldn't handle this alone!

At first, you will be given N queries with [L,R] segments telling you, where all of the N rains fallen. Afterward M queries follows, with number i - the i-th plant for which you want to know, the number of rains, which has fallen onto it.

Input

The first line will contain 0< N,M ≤ 10⁵,0< W ≤ 10⁶, number of rains, number of questions and size of furrow respectively.

Then N lines follow, each containing two integers 0 ≤ L ≤ R <W, symbolizing left and right plant in segment on which i-th rain has fallen.

Afterward M lines follow, each containing a number 0 ≤ a < W, asking for number of rains which has fallen on plant number a

Output

Print M lines (for each query of second type), with integer indicating number of rains, which has fallen on the plant in query.

Example Input

6 7 10
0 9
3 5
4 6
4 8
1 8
5 5
1
5
9
4
9
6
7

Example Output

2
6
1
5
1
4
3