問題

$1$ から $n$ までの番号が書かれた $n$ 枚のカードがある．まず，一番上が番号 $1$ のカード，上から $2$ 枚目が番号 $2$ のカード，$\\ldots$，一番下が番号 $n$ のカードとなるように順番に重ねて，カードの山を作る．

カードの山に対して，「シャッフル $(x, y)$ 」と呼ばれる次のような操作を行うことで，カードを並び替える（$x, y$ は $1 \\leqq x < y < n$ をみたす整数）．

シャッフル $(x, y)$

$n$ 枚のカードを，一番上から $x$ 枚目までのカードからなる山 A，$x + 1$ 枚目から $y$ 枚目のカードからなる山 B，$y + 1$ 枚目から $n$ 枚目のカードからなる山 C の $3$ つの山に分ける．そして，山 A の上に山 B を重ね，さらにその上に山 C を重ねる．

例えば，順番に並んでいる $9$ 枚のカードに対して「シャッフル $(3, 5)$」を行うと，$9$ 枚のカードに書かれた番号は，上から順番に $6, 7, 8, 9, 4, 5, 1, 2, 3$ となる．

最初の山の状態から $m$ 回のシャッフル「シャッフル $(x_1, y_1)$」「シャッフル $(x_2, y_2)$」$\\cdots$「シャッフル $(x_m, y_m)$」を順番に行った後のカードの山において，上から数えて $p$ 枚目から $q$ 枚目のカードの中に番号が $r$ 以下のカードが何枚含まれているかを求めるプログラムを作成せよ．

入力

入力は $m + 3$ 行からなる．$1$ 行目にはカードの枚数 $n$ が書かれている ($3 \\leqq n \\leqq 1\\,000\\,000\\,000 = 10^9$) ．$2$ 行目にはシャッフルの回数を表す整数 $m$ が書かれている ($1 \\leqq m \\leqq 5000$)．$3$ 行目には整数 $p, q, r$ が書かれている ($1 \\leqq p \\leqq q \\leqq n$，$1 \\leqq r \\leqq n$)．$i + 3$ 行目 ($1 \\leqq i \\leqq m$) には $2$ つの整数 $x_i, y_i$ ($1 \\leqq x_i < y_i < n$) が空白を区切りとして書かれている．

出力

$m$ 回のシャッフル後のカードの山において，上から数えて $p$ 枚目から $q$ 枚目のカードの中に含まれている番号が $r$ 以下のカードの枚数を出力せよ．

入力例 1

9
1
3 7 4
3 5

出力例 1

2

入力例 $1$ の山に対して, 「シャッフル $(3, 5)$」を行うと，カードは上から順番に $6, 7, 8, 9, 4, 5, 1, 2, 3$ となる．上から数えて $3$ 枚目から $7$ 枚目に含まれる番号が $4$ 以下のカードは，番号 $4$ と番号 $1$ の $2$ 枚である．

入力例 2

12
3
3 8 5
3 8
2 5
6 10

出力例 2

3

入力例 $2$ の山に対して, 「シャッフル $(3, 8)$」「シャッフル $(2, 5)$」「シャッフル $(6, 10)$」を順番に行うと，カードは上から順番に $9, 10, 3, 11, 12, 4, 5, 6, 7, 8, 1, 2$ となる．上から数えて $3$ 枚目から $8$ 枚目に含まれる番号が $5$ 以下のカードは $3$ 枚である．