AT_joi2009yo_e シャッフル

[problemUrl]: https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_e $ 1 $ から $ n $ までの番号が書かれた $ n $ 枚のカードがある．まず，一番上が番号 $ 1 $ のカード，上から $ 2 $ 枚目が番号 $ 2 $ のカード，$ \ldots $，一番下が番号 $ n $ のカードとなるように順番に重ねて，カードの山を作る．  カードの山に対して，「シャッフル $ (x,\ y) $ 」と呼ばれる次のような操作を行うことで，カードを並び替える（$ x,\ y $ は $ 1\ \leqq\ x\

入力は $ 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\

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

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