#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Data{
	Data(int arg_left_index,int arg_right_index){
		left_index = arg_left_index;
		right_index = arg_right_index;
	}
	int left_index,right_index;
};

struct Info{
	int length;
	vector<Data> children;
};


int N,M,P,Q,R;

void func(){

	scanf("%d",&M);

	scanf("%d %d %d",&P,&Q,&R);

	Info info[3],work[3];

	int a,b;

	scanf("%d %d",&a,&b);

	info[0].children.push_back(Data(b+1,N));
	info[1].children.push_back(Data(a+1,b));
	info[2].children.push_back(Data(1,a));

	for(int i = 0; i < 3; i++){
		info[i].length = info[i].children[0].right_index-info[i].children[0].left_index+1;
	}

	int tmp,a_last_info,a_last_child;

	for(int loop = 1; loop <= M; loop++){
		if(loop < M){
			scanf("%d %d",&a,&b);
		}else{
			a = P-1;
			b = Q;
		}

		if(a <= info[0].length){

			tmp = 0;
			for(int i = 0; i < info[0].children.size(); i++){
				if(tmp + info[0].children[i].right_index-info[0].children[i].left_index+1 < a){
					tmp += info[0].children[i].right_index-info[0].children[i].left_index+1;
					work[0].children.push_back(info[0].children[i]);

				}else{
					if(tmp + info[0].children[i].right_index-info[0].children[i].left_index+1 == a){
						work[0].children.push_back(info[0].children[i]);
						a_last_child = i;
					}else{
						work[0].children.push_back(Data(info[0].children[i].left_index,info[0].children[i].left_index+(a-tmp)-1));
						info[0].children[i].left_index += (a-tmp);
						a_last_child = i-1;
					}
					break;
				}
			}

			a_last_info = 0;

		}else if(a <= info[0].length+info[1].length){

			for(int i = 0; i < info[0].children.size(); i++){
				work[0].children.push_back(info[0].children[i]);
			}
			tmp = info[0].length;

			for(int i = 0; i < info[1].children.size(); i++){
				if(tmp + info[1].children[i].right_index-info[1].children[i].left_index+1 < a){
					tmp += info[1].children[i].right_index-info[1].children[i].left_index+1;
					work[0].children.push_back(info[1].children[i]);

				}else{

					if(tmp + info[1].children[i].right_index-info[1].children[i].left_index+1 == a){
						work[0].children.push_back(info[1].children[i]);
						a_last_child = i;
					}else{
						work[0].children.push_back(Data(info[1].children[i].left_index,info[1].children[i].left_index+(a-tmp)-1));
						info[1].children[i].left_index += (a-tmp);
						a_last_child = i-1;
					}
					break;
				}
			}

			a_last_info = 1;

		}else{
			for(int i = 0; i < info[0].children.size(); i++){
				work[0].children.push_back(info[0].children[i]);
			}

			for(int i = 0; i < info[1].children.size(); i++){
				work[0].children.push_back(info[1].children[i]);
			}
			tmp = info[0].length + info[1].length;

			for(int i = 0; i < info[2].children.size(); i++){
				if(tmp + info[2].children[i].right_index-info[2].children[i].left_index+1 < a){
					tmp += info[2].children[i].right_index-info[2].children[i].left_index+1;
					work[0].children.push_back(info[2].children[i]);

				}else{
					if(tmp + info[2].children[i].right_index-info[2].children[i].left_index+1 == a){
						work[0].children.push_back(info[2].children[i]);
						a_last_child = i;
					}else{
						work[0].children.push_back(Data(info[2].children[i].left_index,info[2].children[i].left_index+(a-tmp)-1));
						info[2].children[i].left_index += (a-tmp);
						a_last_child = i-1;
					}
					break;
				}
			}
			a_last_info = 2;
		}



		if(b <= info[0].length){

			tmp = 0;
			for(int i = 0; i <  work[0].children.size(); i++){
				tmp += work[0].children[i].right_index-work[0].children[i].left_index+1;
			}

			for(int i = a_last_child+1; i < info[0].children.size(); i++){
				if(tmp + info[0].children[i].right_index-info[0].children[i].left_index+1 < b){
					tmp += info[0].children[i].right_index-info[0].children[i].left_index+1;
				}else{

					if(tmp + info[0].children[i].right_index-info[0].children[i].left_index+1 == b){
						for(int k = a_last_child+1; k <= i; k++){
							work[1].children.push_back(info[0].children[k]);
						}
						for(int k = i+1; k < info[0].children.size(); k++){
							work[2].children.push_back(info[0].children[k]);
						}

					}else{
						for(int k = a_last_child+1; k <= i-1; k++){
							work[1].children.push_back(info[0].children[k]);
						}
						work[1].children.push_back(Data(info[0].children[i].left_index,info[0].children[i].left_index+(b-tmp)-1));
						work[2].children.push_back(Data(info[0].children[i].left_index+(b-tmp),info[0].children[i].right_index));
						for(int k = i+1; k < info[0].children.size(); k++){
							work[2].children.push_back(info[0].children[k]);
						}
					}

					for(int k = 0; k < info[1].children.size(); k++){
						work[2].children.push_back(info[1].children[k]);
					}
					for(int k = 0; k < info[2].children.size(); k++){
						work[2].children.push_back(info[2].children[k]);
					}
					break;
				}
			}

		}else if(b <= info[0].length+info[1].length){

			if(a_last_info == 0){

				for(int i = a_last_child+1;i < info[0].children.size(); i++){
					work[1].children.push_back(info[0].children[i]);
				}
				a_last_child = -1;
				tmp = info[0].length;
			}else{
				tmp = 0;
				for(int i = 0; i < work[0].children.size(); i++){
					tmp += work[0].children[i].right_index-work[0].children[i].left_index+1;
				}
			}

			for(int i = a_last_child+1; i < info[1].children.size(); i++){
				if(tmp + info[1].children[i].right_index-info[1].children[i].left_index + 1 < b){
					tmp += info[1].children[i].right_index-info[1].children[i].left_index+1;
				}else{
					if(tmp + info[1].children[i].right_index-info[1].children[i].left_index + 1 == b){
						for(int k = a_last_child+1; k <= i; k++){
							work[1].children.push_back(info[1].children[k]);
							}
							for(int k = i+1; k < info[1].children.size(); k++){
								work[2].children.push_back(info[1].children[k]);
							}

					}else{
						for(int k = a_last_child+1; k <= i-1; k++){
							work[1].children.push_back(info[1].children[k]);
						}
						work[1].children.push_back(Data(info[1].children[i].left_index,info[1].children[i].left_index+(b-tmp)-1));
						work[2].children.push_back(Data(info[1].children[i].left_index+(b-tmp),info[1].children[i].right_index));
						for(int k = i+1; k < info[1].children.size(); k++){
							work[2].children.push_back(info[1].children[k]);
						}
					}
					for(int k = 0; k < info[2].children.size(); k++){
						work[2].children.push_back(info[2].children[k]);
					}
					break;
				}
			}

		}else{

			if(a_last_info == 0){

				for(int i = a_last_child+1; i < info[0].children.size(); i++){
					work[1].children.push_back(info[0].children[i]);
				}
				for(int i = 0; i < info[1].children.size(); i++){
					work[1].children.push_back(info[1].children[i]);
				}
				a_last_child = -1;
				tmp = info[0].length+info[1].length;
			}else if(a_last_info == 1){

				for(int i = a_last_child+1; i < info[1].children.size(); i++){
					work[1].children.push_back(info[1].children[i]);
				}
				a_last_child = -1;
				tmp = info[0].length+info[1].length;
			}else{
				tmp = 0;
				for(int i = 0; i < work[0].children.size(); i++){
					tmp += work[0].children[i].right_index-work[0].children[i].left_index+1;
				}
			}

			for(int i = a_last_child+1; i < info[2].children.size(); i++){
				if(tmp + info[2].children[i].right_index-info[2].children[i].left_index + 1 < b){
					tmp += info[2].children[i].right_index-info[2].children[i].left_index+1;
				}else{

					if(tmp + info[2].children[i].right_index-info[2].children[i].left_index + 1 == b){
						for(int k = a_last_child+1; k <= i; k++){
							work[1].children.push_back(info[2].children[k]);
						}
						for(int k = i+1; k < info[2].children.size(); k++){
							work[2].children.push_back(info[2].children[k]);
						}

					}else{
						for(int k = a_last_child+1; k <= i-1; k++){
							work[1].children.push_back(info[2].children[k]);
						}
						work[1].children.push_back(Data(info[2].children[i].left_index,info[2].children[i].left_index+(b-tmp)-1));
						work[2].children.push_back(Data(info[2].children[i].left_index+(b-tmp),info[2].children[i].right_index));
						for(int k = i+1; k < info[2].children.size(); k++){
							work[2].children.push_back(info[2].children[k]);
						}
					}
					break;
				}
			}
		}

		for(int i = 0; i < 3; i++){
			info[i].children.clear();
		}

		for(int i = 0; i < work[2].children.size(); i++){
			info[0].children.push_back(work[2].children[i]);
		}

		for(int i = 0; i < work[1].children.size(); i++){
			info[1].children.push_back(work[1].children[i]);
		}

		for(int i = 0; i < work[0].children.size(); i++){
			info[2].children.push_back(work[0].children[i]);
		}

		for(int i = 0; i < 3; i++){
			tmp = 0;
			for(int k = 0; k < info[i].children.size(); k++){
				tmp += info[i].children[k].right_index-info[i].children[k].left_index+1;
			}
			info[i].length = tmp;
		}

		for(int i = 0; i < 3; i++){
			work[i].children.clear();
		}

	}

	int ans = 0;

	for(int i = 0; i < info[1].children.size(); i++){
		if(info[1].children[i].left_index > R)continue;

		if(info[1].children[i].right_index <= R){
			ans += info[1].children[i].right_index-info[1].children[i].left_index+1;
		}else{
			ans += R-info[1].children[i].left_index+1;
		}
	}

	printf("%d\n",ans);

}


int main(){

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func();
	}

	return 0;
}
### Prompt

Your challenge is to write a Cpp solution to the following 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

### Response

```cpp
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Data{
	Data(int arg_left_index,int arg_right_index){
		left_index = arg_left_index;
		right_index = arg_right_index;
	}
	int left_index,right_index;
};

struct Info{
	int length;
	vector<Data> children;
};


int N,M,P,Q,R;

void func(){

	scanf("%d",&M);

	scanf("%d %d %d",&P,&Q,&R);

	Info info[3],work[3];

	int a,b;

	scanf("%d %d",&a,&b);

	info[0].children.push_back(Data(b+1,N));
	info[1].children.push_back(Data(a+1,b));
	info[2].children.push_back(Data(1,a));

	for(int i = 0; i < 3; i++){
		info[i].length = info[i].children[0].right_index-info[i].children[0].left_index+1;
	}

	int tmp,a_last_info,a_last_child;

	for(int loop = 1; loop <= M; loop++){
		if(loop < M){
			scanf("%d %d",&a,&b);
		}else{
			a = P-1;
			b = Q;
		}

		if(a <= info[0].length){

			tmp = 0;
			for(int i = 0; i < info[0].children.size(); i++){
				if(tmp + info[0].children[i].right_index-info[0].children[i].left_index+1 < a){
					tmp += info[0].children[i].right_index-info[0].children[i].left_index+1;
					work[0].children.push_back(info[0].children[i]);

				}else{
					if(tmp + info[0].children[i].right_index-info[0].children[i].left_index+1 == a){
						work[0].children.push_back(info[0].children[i]);
						a_last_child = i;
					}else{
						work[0].children.push_back(Data(info[0].children[i].left_index,info[0].children[i].left_index+(a-tmp)-1));
						info[0].children[i].left_index += (a-tmp);
						a_last_child = i-1;
					}
					break;
				}
			}

			a_last_info = 0;

		}else if(a <= info[0].length+info[1].length){

			for(int i = 0; i < info[0].children.size(); i++){
				work[0].children.push_back(info[0].children[i]);
			}
			tmp = info[0].length;

			for(int i = 0; i < info[1].children.size(); i++){
				if(tmp + info[1].children[i].right_index-info[1].children[i].left_index+1 < a){
					tmp += info[1].children[i].right_index-info[1].children[i].left_index+1;
					work[0].children.push_back(info[1].children[i]);

				}else{

					if(tmp + info[1].children[i].right_index-info[1].children[i].left_index+1 == a){
						work[0].children.push_back(info[1].children[i]);
						a_last_child = i;
					}else{
						work[0].children.push_back(Data(info[1].children[i].left_index,info[1].children[i].left_index+(a-tmp)-1));
						info[1].children[i].left_index += (a-tmp);
						a_last_child = i-1;
					}
					break;
				}
			}

			a_last_info = 1;

		}else{
			for(int i = 0; i < info[0].children.size(); i++){
				work[0].children.push_back(info[0].children[i]);
			}

			for(int i = 0; i < info[1].children.size(); i++){
				work[0].children.push_back(info[1].children[i]);
			}
			tmp = info[0].length + info[1].length;

			for(int i = 0; i < info[2].children.size(); i++){
				if(tmp + info[2].children[i].right_index-info[2].children[i].left_index+1 < a){
					tmp += info[2].children[i].right_index-info[2].children[i].left_index+1;
					work[0].children.push_back(info[2].children[i]);

				}else{
					if(tmp + info[2].children[i].right_index-info[2].children[i].left_index+1 == a){
						work[0].children.push_back(info[2].children[i]);
						a_last_child = i;
					}else{
						work[0].children.push_back(Data(info[2].children[i].left_index,info[2].children[i].left_index+(a-tmp)-1));
						info[2].children[i].left_index += (a-tmp);
						a_last_child = i-1;
					}
					break;
				}
			}
			a_last_info = 2;
		}



		if(b <= info[0].length){

			tmp = 0;
			for(int i = 0; i <  work[0].children.size(); i++){
				tmp += work[0].children[i].right_index-work[0].children[i].left_index+1;
			}

			for(int i = a_last_child+1; i < info[0].children.size(); i++){
				if(tmp + info[0].children[i].right_index-info[0].children[i].left_index+1 < b){
					tmp += info[0].children[i].right_index-info[0].children[i].left_index+1;
				}else{

					if(tmp + info[0].children[i].right_index-info[0].children[i].left_index+1 == b){
						for(int k = a_last_child+1; k <= i; k++){
							work[1].children.push_back(info[0].children[k]);
						}
						for(int k = i+1; k < info[0].children.size(); k++){
							work[2].children.push_back(info[0].children[k]);
						}

					}else{
						for(int k = a_last_child+1; k <= i-1; k++){
							work[1].children.push_back(info[0].children[k]);
						}
						work[1].children.push_back(Data(info[0].children[i].left_index,info[0].children[i].left_index+(b-tmp)-1));
						work[2].children.push_back(Data(info[0].children[i].left_index+(b-tmp),info[0].children[i].right_index));
						for(int k = i+1; k < info[0].children.size(); k++){
							work[2].children.push_back(info[0].children[k]);
						}
					}

					for(int k = 0; k < info[1].children.size(); k++){
						work[2].children.push_back(info[1].children[k]);
					}
					for(int k = 0; k < info[2].children.size(); k++){
						work[2].children.push_back(info[2].children[k]);
					}
					break;
				}
			}

		}else if(b <= info[0].length+info[1].length){

			if(a_last_info == 0){

				for(int i = a_last_child+1;i < info[0].children.size(); i++){
					work[1].children.push_back(info[0].children[i]);
				}
				a_last_child = -1;
				tmp = info[0].length;
			}else{
				tmp = 0;
				for(int i = 0; i < work[0].children.size(); i++){
					tmp += work[0].children[i].right_index-work[0].children[i].left_index+1;
				}
			}

			for(int i = a_last_child+1; i < info[1].children.size(); i++){
				if(tmp + info[1].children[i].right_index-info[1].children[i].left_index + 1 < b){
					tmp += info[1].children[i].right_index-info[1].children[i].left_index+1;
				}else{
					if(tmp + info[1].children[i].right_index-info[1].children[i].left_index + 1 == b){
						for(int k = a_last_child+1; k <= i; k++){
							work[1].children.push_back(info[1].children[k]);
							}
							for(int k = i+1; k < info[1].children.size(); k++){
								work[2].children.push_back(info[1].children[k]);
							}

					}else{
						for(int k = a_last_child+1; k <= i-1; k++){
							work[1].children.push_back(info[1].children[k]);
						}
						work[1].children.push_back(Data(info[1].children[i].left_index,info[1].children[i].left_index+(b-tmp)-1));
						work[2].children.push_back(Data(info[1].children[i].left_index+(b-tmp),info[1].children[i].right_index));
						for(int k = i+1; k < info[1].children.size(); k++){
							work[2].children.push_back(info[1].children[k]);
						}
					}
					for(int k = 0; k < info[2].children.size(); k++){
						work[2].children.push_back(info[2].children[k]);
					}
					break;
				}
			}

		}else{

			if(a_last_info == 0){

				for(int i = a_last_child+1; i < info[0].children.size(); i++){
					work[1].children.push_back(info[0].children[i]);
				}
				for(int i = 0; i < info[1].children.size(); i++){
					work[1].children.push_back(info[1].children[i]);
				}
				a_last_child = -1;
				tmp = info[0].length+info[1].length;
			}else if(a_last_info == 1){

				for(int i = a_last_child+1; i < info[1].children.size(); i++){
					work[1].children.push_back(info[1].children[i]);
				}
				a_last_child = -1;
				tmp = info[0].length+info[1].length;
			}else{
				tmp = 0;
				for(int i = 0; i < work[0].children.size(); i++){
					tmp += work[0].children[i].right_index-work[0].children[i].left_index+1;
				}
			}

			for(int i = a_last_child+1; i < info[2].children.size(); i++){
				if(tmp + info[2].children[i].right_index-info[2].children[i].left_index + 1 < b){
					tmp += info[2].children[i].right_index-info[2].children[i].left_index+1;
				}else{

					if(tmp + info[2].children[i].right_index-info[2].children[i].left_index + 1 == b){
						for(int k = a_last_child+1; k <= i; k++){
							work[1].children.push_back(info[2].children[k]);
						}
						for(int k = i+1; k < info[2].children.size(); k++){
							work[2].children.push_back(info[2].children[k]);
						}

					}else{
						for(int k = a_last_child+1; k <= i-1; k++){
							work[1].children.push_back(info[2].children[k]);
						}
						work[1].children.push_back(Data(info[2].children[i].left_index,info[2].children[i].left_index+(b-tmp)-1));
						work[2].children.push_back(Data(info[2].children[i].left_index+(b-tmp),info[2].children[i].right_index));
						for(int k = i+1; k < info[2].children.size(); k++){
							work[2].children.push_back(info[2].children[k]);
						}
					}
					break;
				}
			}
		}

		for(int i = 0; i < 3; i++){
			info[i].children.clear();
		}

		for(int i = 0; i < work[2].children.size(); i++){
			info[0].children.push_back(work[2].children[i]);
		}

		for(int i = 0; i < work[1].children.size(); i++){
			info[1].children.push_back(work[1].children[i]);
		}

		for(int i = 0; i < work[0].children.size(); i++){
			info[2].children.push_back(work[0].children[i]);
		}

		for(int i = 0; i < 3; i++){
			tmp = 0;
			for(int k = 0; k < info[i].children.size(); k++){
				tmp += info[i].children[k].right_index-info[i].children[k].left_index+1;
			}
			info[i].length = tmp;
		}

		for(int i = 0; i < 3; i++){
			work[i].children.clear();
		}

	}

	int ans = 0;

	for(int i = 0; i < info[1].children.size(); i++){
		if(info[1].children[i].left_index > R)continue;

		if(info[1].children[i].right_index <= R){
			ans += info[1].children[i].right_index-info[1].children[i].left_index+1;
		}else{
			ans += R-info[1].children[i].left_index+1;
		}
	}

	printf("%d\n",ans);

}


int main(){

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func();
	}

	return 0;
}
```