Interval query

This is a very simple question. There are N intervals in number axis, and M queries just like “QUERY(a,b)” indicate asking the maximum number of the disjoint intervals between (a,b) .

There are several test cases. For each test case, the first line contains two integers N, M (0<N, M<=100000) as described above. In each following N lines, there are two integers indicate two endpoints of the i-th interval. Then come M lines and each line contains two integers indicating the endpoints of the i-th query.
You can assume the left-endpoint is strictly less than the right-endpoint in each given interval and query and all these endpoints are between 0 and 1,000,000,000.

For each query, you need to output the maximum number of the disjoint intervals in the asked interval in one line.

3 2
1 2
2 3
1 3
1 2
1 3

1
2

HIT

2012 Multi-University Training Contest 5