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

---

hide comments

	ort: 2019-01-05 20:32:42 UPDATEIT code, copy, replace few lines, because input order is different, paste, AC
	dipankar12: 2018-05-05 16:56:56 Can be solved with seg+lazy in JAVA as well.
	julkas: 2017-10-21 11:29:11 Can be solved with simple approach. O(1) for point query. PyPy ~ 0.7 s. Last edit: 2017-11-19 21:03:28
	bhagirathi08: 2017-08-25 07:13:18 I tried segment tree in JAVA and C++ it timed out. BIT works well
	kira28: 2017-07-09 14:52:21 JAVA:- BIT with O(N+M)logW complexity - AC in 1.45 sec Prefix sum with O(N+M) complexity - AC in 1.48 sec Strange ^ ^ Oo
	morass: 2017-03-28 21:32:08 @anonymous: Thanks - updated Yes, seem you are right
	anonymous: 2017-03-28 18:01:05 Description contains unfortunate name collision between furrow size L and low index of range L. BTW, problem is very similar to UPDATEIT.