Shuffle

There are $n$ cards numbered $1$ through $n$. Initially they are stacked in order so that the top card is number $1$, the second from the top is number $2$, …, and the bottom card is number $n$.

The deck is rearranged by an operation called shuffle$(x, y)$, where $x$ and $y$ are integers with $1 \le x < y < n$.

• shuffle$(x, y)$
  • Split the $n$ cards into three piles: pile $A$ consisting of the top $x$ cards, pile $B$ consisting of the cards from position $x+1$ to $y$, and pile $C$ consisting of the cards from position $y+1$ to $n$. Then place pile $B$ on top of pile $A$, and place pile $C$ on top of that.

For example, applying shuffle$(3, 5)$ to $9$ ordered cards makes the numbers, from top to bottom, $6, 7, 8, 9, 4, 5, 1, 2, 3$.

Starting from the initial deck, perform $m$ shuffles shuffle$(x_1, y_1)$, shuffle$(x_2, y_2)$, …, shuffle$(x_m, y_m)$ in order. Write a program that, in the resulting deck, counts how many cards numbered $r$ or less lie among the cards from position $p$ to position $q$ counted from the top.

The input consists of $m+3$ lines.

• Line $1$: the number of cards $n$ ($3 \le n \le 10^9$).
• Line $2$: the number of shuffles $m$ ($1 \le m \le 5000$).
• Line $3$: three integers $p, q, r$ ($1 \le p \le q \le n$, $1 \le r \le n$).
• Line $i+3$ (for $1 \le i \le m$): two integers $x_i$ and $y_i$ ($1 \le x_i < y_i < n$) separated by a space.

Output the number of cards numbered $r$ or less among the cards from position $p$ to position $q$ (counted from the top) in the deck after the $m$ shuffles.

Applying shuffle$(3, 5)$ to a deck of $9$ cards makes the cards, from top to bottom, $6, 7, 8, 9, 4, 5, 1, 2, 3$. Among positions $3$ through $7$ from the top, the cards numbered $4$ or less are number $4$ and number $1$ — $2$ cards.

Applying shuffle$(3, 8)$, shuffle$(2, 5)$, shuffle$(6, 10)$ in order to a deck of $12$ cards makes the cards, from top to bottom, $9, 10, 3, 11, 12, 4, 5, 6, 7, 8, 1, 2$. Among positions $3$ through $8$ from the top, there are $3$ cards numbered $5$ or less.