Educational Codeforces Round 66 (Rated for Div. 2) E. Minimal Segment Cover 倍增

E. Minimal Segment Cover

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given nn intervals in form [l;r][l;r] on a number line.

You are also given mm queries in form [x;y][x;y] . What is the minimal number of intervals you have to take so that every point (not necessarily integer) from xx to yy is covered by at least one of them?

If you can't choose intervals so that every point from xx to yy is covered, then print -1 for that query.

Input

The first line contains two integers nn and mm (1≤n,m≤2⋅1051≤n,m≤2⋅105 ) — the number of intervals and the number of queries, respectively.

Each of the next nn lines contains two integer numbers lili and riri (0≤li<ri≤5⋅1050≤li<ri≤5⋅105 ) — the given intervals.

Each of the next mm lines contains two integer numbers xixi and yiyi (0≤xi<yi≤5⋅1050≤xi<yi≤5⋅105 ) — the queries.

Output

Print mm integer numbers. The ii -th number should be the answer to the ii -th query: either the minimal number of intervals you have to take so that every point (not necessarily integer) from xixi to yiyi is covered by at least one of them or -1 if you can't choose intervals so that every point from xixi to yiyi is covered.

Examples

Input

Copy

2 3
1 3
2 4
1 3
1 4
3 4

Output

Copy

1
2
1

Input

Copy

3 4
1 3
1 3
4 5
1 2
1 3
1 4
1 5

Output

Copy

1
1
-1
-1

Note

In the first example there are three queries:

1. query [1;3][1;3] can be covered by interval [1;3][1;3] ;
2. query [1;4][1;4] can be covered by intervals [1;3][1;3] and [2;4][2;4] . There is no way to cover [1;4][1;4] by a single interval;
3. query [3;4][3;4] can be covered by interval [2;4][2;4] . It doesn't matter that the other points are covered besides the given query.

In the second example there are four queries:

1. query [1;2][1;2] can be covered by interval [1;3][1;3] . Note that you can choose any of the two given intervals [1;3][1;3] ;
2. query [1;3][1;3] can be covered by interval [1;3][1;3] ;
3. query [1;4][1;4] can't be covered by any set of intervals;
4. query [1;5][1;5] can't be covered by any set of intervals. Note that intervals [1;3][1;3] and [4;5][4;5] together don't cover [1;5][1;5] because even non-integer points should be covered. Here 3.53.5 , for example, isn't covered.

 

给出n个区间,m个询问

对于每个询问 最少用多少个区间覆盖这个询问的区间

很经典的题  倍增

参考

Cometoj算法讨论群  青蛙老师%

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const int max_p=20;
int max_reach[maxn];
int dp[maxn][max_p];
const int inf=0x3f3f3f3f;
int main()
{

    int n,m,x,y,mx=0,mi=inf;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
       scanf("%d%d",&x,&y);
       max_reach[x]=max(max_reach[x],y);
    }
    for(int i=1;i<maxn;i++)
    {
       max_reach[i]=max(max_reach[i-1],max_reach[i]);
    }
    for(int j=0;j<maxn;j++)
    {
       dp[j][0]=max_reach[j];
    }
    for(int i=1;i<max_p;i++)
    {
        for(int j=0;j<maxn;j++)
        {
            dp[j][i]=dp[dp[j][i-1]][i-1];
        }
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        int ans=0;
        if(dp[x][max_p-1]<y)
        {
            ans=-1;
            printf("%d\n",ans);
            continue;
        }
        for(int j=max_p-1;j>=0;j--)
        {
            if(dp[x][j]<y)
            {
                ans+=(1<<j);
                x=dp[x][j];
            }
        }
        ans++;
        printf("%d\n",ans);
    }
}
/*
6 20
9 10
0 1
7 9
3 7
8 10
5 8
4 10
*/