Problem Description

There are $n$ cards numbered from $1$ to $n$. First, the cards are stacked in order, with the card numbered $1$ on top, the card numbered $2$ as the second from the top, ..., and the card numbered $n$ at the bottom.

By performing a "shuffle $(x, y)$" operation on the stack of cards, the cards are rearranged. Here, $x$ and $y$ are integers satisfying $1 \leq x < y < n$.

Shuffle $(x, y)$

The $n$ cards are divided into three stacks: stack A consisting of the top $x$ cards, stack B consisting of the cards from the $(x + 1)$-th to the $y$-th, and stack C consisting of the cards from the $(y + 1)$-th to the $n$-th. Then, stack B is placed on top of stack A, and stack C is placed on top of stack B.

For example, performing "shuffle $(3, 5)$" on a stack of 9 cards arranged in order results in the cards numbered from top to bottom as $6, 7, 8, 9, 4, 5, 1, 2, 3$.

From the initial stack, after performing $m$ shuffles "shuffle $(x_1, y_1)$", "shuffle $(x_2, y_2)$", ..., "shuffle $(x_m, y_m)$" in order, create a program to determine how many cards numbered $r$ or below are included in the $p$-th to $q$-th cards from the top in the final stack.

Input Format

The input consists of $m + 3$ lines. The first line contains the number of cards $n$ ($3 \leq n \leq 1,000,000,000 = 10^9$). The second line contains the number of shuffles $m$ ($1 \leq m \leq 5000$). The third line contains the integers $p, q, r$ ($1 \leq p \leq q \leq n$, $1 \leq r \leq n$). The $(i + 3)$-th line ($1 \leq i \leq m$) contains two integers $x_i, y_i$ ($1 \leq x_i < y_i < n$), separated by a space.

Output Format

Output the number of cards numbered $r$ or below that are included in the $p$-th to $q$-th cards from the top in the final stack after $m$ shuffles.

Sample Input and Output

Sample Input #1

9
1
3 7 4
3 5

Sample Output #1

2

Sample Input #2

12
3
3 8 5
3 8
2 5
6 10

Sample Output #2

3

Notes/Hints

Sample Explanation 1

For the stack in Sample Input #1, performing "shuffle $(3, 5)$" results in the cards numbered from top to bottom as $6, 7, 8, 9, 4, 5, 1, 2, 3$. The cards numbered $4$ or below included in the 3rd to 7th cards from the top are the cards numbered $4$ and $1$, totaling $2$ cards.

Sample Explanation 2

For the stack in Sample Input #2, performing "shuffle $(3, 8)$", "shuffle $(2, 5)$", and "shuffle $(6, 10)$" in order results in the cards numbered from top to bottom as $9, 10, 3, 11, 12, 4, 5, 6, 7, 8, 1, 2$. The cards numbered $5$ or below included in the 3rd to 8th cards from the top total $3$ cards.

见题面 Input 部分

见题面 Output 部分