Problem: problem

There are n cards with numbers from 1 to n. First, make a pile of cards by stacking them in order so that the top is the number 1 card, the second from the top is the number 2 card, ..., and the bottom is the number n card.

<image>



Sort the cards by performing the following operation called "shuffle (x, y)" on the pile of cards (x, y is an integer that satisfies 1 ≤ x <y <n).

Shuffle (x, y)
n cards, pile A consisting of the xth cards from the top, pile B consisting of the x + 1th to yth cards, y + 1 consisting of the nth cards Divide into three mountains of mountain C. Then, mountain B is placed on top of mountain A, and mountain C is placed on top of it.

For example, if you perform "shuffle (3,5)" on 9 cards in order, the numbers written on the 9 cards will be 6, 7, 8, 9, 4 in order from the top. , 5, 1, 2, 3.

<image>



Shuffle m times from the state of the first pile "Shuffle (x1, y1)" "Shuffle (x2, y2)" ... Count from the top in the pile of cards after performing "shuffle (xm, ym)" in order Create a program to find out how many cards with numbers r or less are included in the pth to qth cards.



input

The input consists of multiple datasets. Each dataset is given in the following format.

The input consists of m + 3 lines. The number of cards n is written on the first line (3 ≤ n ≤ 1000000000 = 109). The second line contains the integer m, which represents the number of shuffles (1 ≤ m ≤ 5000). The integers p, q, r are written on the third line (1 ≤ p ≤ q ≤ n, 1 ≤ r ≤ n). On the third line of i + (1 ≤ i ≤ m), two integers xi and yi (1 ≤ xi <yi <n) are written separated by a blank.

When n is 0, it indicates the end of input. The number of data sets does not exceed 5.

output

For each data set, in the pile of cards after m shuffling, output the number of cards whose number is r or less in the pth to qth cards counted from the top in one line. ..

Examples

Input

9
1
3 7 4
3 5
12
3
3 8 5
3 8
2 5
6 10
0


Output

2
3


Input

None


Output

None

Solution (in CPP):

Solution:
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef pair<int,int> pii;

int N;
int M;
int P,Q,R;

void decidePlace(int &sumX,vector<pii>&deck,int &xPos,int x){
    for(int j=0;j<deck.size();j++){
        if(sumX+deck[j].second-deck[j].first+1>=x){
            xPos=j;
            break;
        }
        sumX+=deck[j].second-deck[j].first+1;
    }
}
void divideBlock(vector<pii> &deck,int &xPos,int &sumX,int x,bool isX){
    int minu=1;
    if(isX)minu++;
    pii p1=pii(deck[xPos].first,deck[xPos].first+(x-sumX-minu));
    pii p2=pii(p1.second+1,deck[xPos].second);
    deck.erase(deck.begin()+xPos);
    if(p2.first<=p2.second)deck.insert(deck.begin()+xPos,p2);
    if(p1.first<=p1.second)deck.insert(deck.begin()+xPos,p1);
}

int main(){
    while(cin>>N&&N){
        int res=0;
        cin>>M>>P>>Q>>R;
        vector<pii> deck;
        deck.push_back(pii(1,N));
        int x,y;
        for(int i=0;i<M;i++){
            cin>>x>>y;
            // xÌÓÆyÌÓðÁèµAVbt
            int sumX=0;
            int sumY=0;
            int xPos,yPos;
            // x+1ÚðÁè
            x++;
            decidePlace(sumX,deck,xPos,x);
            //for(int j=0;j<deck.size();j++){
            //    if(sumX+deck[j].second-deck[j].first+1>=x){
            //        xPos=j;
            //        break;
            //    }
            //    sumX+=deck[j].second-deck[j].first+1;
            //}
            // yÚðÁè
            decidePlace(sumY,deck,yPos,y);
            //for(int j=0;j<deck.size();j++){
            //    if(sumY+deck[j].second-deck[j].first+1>=y){
            //        yPos=j;
            //        break;
            //    }
            //    sumY+=deck[j].second-deck[j].first+1;
            //}
            // x+1Ú©çy+1ÚÜÅÌÓðØèæèAVbt
            // ¯¶æÔÉ¶Ý
            if(xPos==yPos){
                // »ÝÌæÔðRª
                pii p1=pii(deck[xPos].first,deck[xPos].first+(x-sumX-2));
                pii p2=pii(p1.second+1,deck[yPos].first+(y-sumY-1));
                pii p3=pii(p2.second+1,deck[xPos].second);
                deck.erase(deck.begin()+xPos);
                if(p3.first<=p3.second)deck.insert(deck.begin()+xPos,p3);
                if(p2.first<=p2.second)deck.insert(deck.begin()+xPos,p2);
                if(p1.first<=p1.second)deck.insert(deck.begin()+xPos,p1);
            }
            // ÊÌæÔÉ¶Ý·éêÍA»ê¼êÌæÔ²ÆÉªðs¤
            else{
                // y
                //{
                //    pii p1=pii(deck[yPos].first,deck[yPos].first+(y-sumY-1));
                //    pii p2=pii(p1.second+1,deck[yPos].second);
                //    deck.erase(deck.begin()+yPos);
                //    if(p2.first<=p2.second)deck.insert(deck.begin()+yPos,p2);
                //    if(p1.first<=p1.second)deck.insert(deck.begin()+yPos,p1);
                //}
                divideBlock(deck,yPos,sumY,y,false);
                divideBlock(deck,xPos,sumX,x,true);
                // x
                //{
                //    pii p1=pii(deck[xPos].first,deck[xPos].first+(x-sumX-2));
                //    pii p2=pii(p1.second+1,deck[xPos].second);
                //    deck.erase(deck.begin()+xPos);
                //    if(p2.first<=p2.second)deck.insert(deck.begin()+xPos,p2);
                //    if(p1.first<=p1.second)deck.insert(deck.begin()+xPos,p1);
                //}
            }
            // à¤êxxÆyÌêðTõµA©Â¯½çVbt
            sumX=sumY=0;
            decidePlace(sumX,deck,xPos,x);
            decidePlace(sumY,deck,yPos,y);
            //for(int j=0;j<deck.size();j++){
            //    if(sumX+deck[j].second-deck[j].first+1>=x){
            //        xPos=j;
            //        break;
            //    }
            //    sumX+=deck[j].second-deck[j].first+1;
            //}
            //for(int j=0;j<deck.size();j++){
            //    if(sumY+deck[j].second-deck[j].first+1>=y){
            //        yPos=j;
            //        break;
            //    }
            //    sumY+=deck[j].second-deck[j].first+1;
            //}
            // xpos©çyposÜÅÌÓð²«oµÄAVbt
            vector<pii> cutPlace;
            vector<pii> prv;
            vector<pii> nxt;
            for(int i=xPos;i<=yPos;i++)cutPlace.push_back(deck[i]);
            for(int i=0;i<xPos;i++)prv.push_back(deck[i]);
            for(int i=yPos+1;i<deck.size();i++)nxt.push_back(deck[i]);
            deck.clear();
            for(int i=0;i<nxt.size();i++)deck.push_back(nxt[i]);
            for(int i=0;i<cutPlace.size();i++)deck.push_back(cutPlace[i]);
            for(int i=0;i<prv.size();i++)deck.push_back(prv[i]);
        }
        // VbtI¹ãApÆqÌl©çAðð½·àÌðTõ
        int sum=0;
        bool isApP=false;
        for(int i=0;i<deck.size();i++){
            int cnt=deck[i].second-deck[i].first+1;
            sum+=cnt;
            if(sum<P)continue;
            // ¡ñÌæÔÉñÂÆàÜÜêéê
            if(sum-cnt<P&&sum-cnt<Q&&sum>=P&&sum>=Q){
                int pPos=P-(sum-cnt)-1;
                int pNum=pPos+deck[i].first;
                int qPos=Q-(sum-cnt)-1;
                int qNum=qPos+deck[i].first;
                // pÌl©çrÈºÌàÌð¦ã°
                if(pNum<=R)
                    res+=max(0,min(-qNum+R+1,qNum-pNum+1));
                break;
            }
            // ¡ñÌæÔÅßÄpª»ê½ê
            else if(!isApP&&sum>=P){
                isApP=true;
                int pPos=P-(sum-cnt)-1;
                int pNum=pPos+deck[i].first;
                // pÌl©çrÈºÌàÌð¦ã°
                if(pNum<=R)
                    res+=max(0,min(-deck[i].first+R+1,deck[i].second-pNum+1));
            }
            // pªo»ÏÝÌê
            else if(isApP){
                // ¡ñQª»ê½çðµÄbreak
                if(sum>=Q){
                    int qPos=Q-(sum-cnt)-1;
                    int qNum=qPos+deck[i].first;
                    if(deck[i].first<=R)res+=min(qNum-deck[i].first+1,(R-deck[i].first+1));
                    break;
                }
                // æÔÌl·×ÄÉÎµÄvZ
                else{
                    if(deck[i].first<=R){
                        res+=max(0,min(-deck[i].first+R+1,deck[i].second-deck[i].first+1));
                    }
                }
            }
        }
        cout<<res<<endl;
    }
    return 0;
}