I couldn't solve this. Please do tell me any simple approach which can pass the time constraint.

Problem:

You are given n intervals which are termed as special intervals. Each interval is of a different type.

Again, you are given a set of q non-special intervals. For each non-special interval in the given q intervals, you have to find the number of different types of special intervals in that non-special interval.

Note: A special interval is inside a non-special interval if there exists a point x which belongs to both special interval and non-special interval.

Input format

First line: n denoting the number of special intervals

Next n lines: Two integers denoting lspecial[i] and rspecial[i] denoting the range [l,r] for the ith special interval.

Next line: q denoting the number of non-special intervals

Next q lines: Two integers denoting lnonspecial[i] and rnonspecial[i] denoting the range [l,r] for the ith non-special interval.

Output format

print q space-seperated integers denoting the answer for each of the q non-special integers.

Constraints

1<=n<=10^5

-10^9<=lspecial[i]<=10^9

-10^9<=rspecial[i]<=10^9

1<=q<= 5 * 10^4

-10^9<=lnonspecial[i]<=10^9

-10^9<=rnonspecial[i]<=10^9

Sample Input 3 1 2 1 5 1 7 3 1 3 3 3 6 7

Sample Output

3 2 1

Time Limit 1 second