You are given n intervals in form [l;r] on a number line.
You are also given m queries in form [x;y]. What is the minimal number of intervals you have to take so that every point (not necessarily integer) from x to y is covered by at least one of them?
If you can't choose intervals so that every point from x to y is covered, then print -1 for that query.
The first line contains two integers n and m (1≤n,m≤2⋅105) — the number of intervals and the number of queries, respectively.
Each of the next n lines contains two integer numbers li and ri (0≤li<ri≤5⋅105) — the given intervals.
Each of the next m lines contains two integer numbers xi and yi (0≤xi<yi≤5⋅105) — the queries.
Print m integer numbers. The i-th number should be the answer to the i-th query: either the minimal number of intervals you have to take so that every point (not necessarily integer) from xi to yi is covered by at least one of them or -1 if you can't choose intervals so that every point from xi to yi is covered.
2 3 1 3 2 4 1 3 1 4 3 4
1 2 1
3 4 1 3 1 3 4 5 1 2 1 3 1 4 1 5
1 1 -1 -1
In the first example there are three queries:
In the second example there are four queries:
Name |
---|