F :: Farmers of Kasian

Time Limit: 5 Seconds    Memory Limit: 65536 KB

The land of Kasian is in the form of an infinite strip. It has a width of W. Farmers of Kasian have divided their land into subdivisions with n line segments that fully extend across the strip and are non-intersecting. Subdivisions are numbered from 0 through n (inclusive) from left to right.

http://sharecode.ir/assets/problem_images/1337_c7979238c64ba1864f3095a39281044f.jpg

An example of subdivions of Kasian

The governor of Kasian is collecting taxes from the farmers. He has sent an agent to calculate and collect the taxes. As there are quite a lot of subdivisions, the agent has decided to visit only m random locations and collect the tax from the owners of those subdivisions.

Unfortunately because of the complications in the territory of farmers, the agent cannot accurately decide on which subdivision he is standing. So he asked you as an experienced programmer to do this job for him.

Input

First line of input contains a single integer t (t ≤ 10), the number tests that follow. On the first line of each test there are two integers n, W (1 ≤ n ≤ 5 × 104,1 ≤ W ≤ 109), the number of subdivisions and the parameter W as defined in the problem statement. From now on we assume the land is the unbounded area in between lines y = 0 and y = W.

Next n lines will contain two integers x1 and x2 (−109≤ x1,x2 ≤ 109). It means that there is line segment from (x1,0) to (x2,W). It is guaranteed that these line segments are disjoint.

Next line consists of a single integer m (1 ≤ m ≤ 5 × 104), the number of locations the agent checks. After that there are m lines follow, each containing two integers xi, yi (−109≤ xi ≤ 109,0 ≤ yi≤ W), the i-th location that the agent checks. No query point lie on any line segment.

Output

For each test you should output m lines. i-th line for each test should be the number of subdivision for the i-th query point. The answer for each query should be a number from 0 to n.

There should be exactly one empty line after each test.

Sample Input

2
1 2
10 0
2
5 0
5 2
4 10
8 8
3 1
4 5
15 12
5
2 1
9 10
3 1
6 0
14 5

Sample Output

0
1

0
3
1
2
4
Submit

Source: 4th Kashan University's ACM Contest