AT_joi2009yo_e シャッフル

手上有编号从 $1$ 到 $n$ 的 $n$ 张卡片。我们将这些卡片按编号顺序从上到下叠成一堆，顶部是编号为 $1$ 的卡片，最底层是编号为 $n$ 的卡片。 现在，我们要对卡片堆进行一种称为“洗牌 $(x, y)$”的操作，用来改变卡片的顺序，其中 $1 \le x < y < n$。 ### 洗牌 $(x, y)$ 操作 首先，把 $n$ 张卡片分成三部分：从顶部开始的前 $x$ 张构成第一部分 A，第 $x+1$ 张到第 $y$ 张构成第二部分 B，第 $y+1$ 张到最底成为第三部分 C。然后按顺序将 B 移到 A 之上，再将 C 放到最上面。 例如，有 $9$ 张按顺序排列的卡片，执行“洗牌 $(3, 5)$”后，卡片从上到下的编号变为：$6, 7, 8, 9, 4, 5, 1, 2, 3$。 在最初的卡片堆上依次进行 $m$ 次洗牌操作，最终我们需要找到从顶部起第 $p$ 张到第 $q$ 张卡片中，编号不超过 $r$ 的卡片数量。

第一行包含一个整数 $n$，表示卡片总数（$3 \le n \le 10^9$）。 第二行包含一个整数 $m$，表示洗牌的次数（$1 \le m \le 5000$）。 第三行包含三个整数 $p, q, r$，分别指明所需关注的卡片范围以及编号的上限（$1 \le p \le q \le n$，$1 \le r \le n$）。 接下来的 $m$ 行每行包含两个整数 $x_i, y_i$，表示第 $i$ 次洗牌的参数（$1 \le x_i < y_i < n$）。

经过 $m$ 次洗牌后，输出指定范围内编号不超过 $r$ 的卡片数量。 ### 样例解析 1 对于输入例 1，执行“洗牌 $(3, 5)$”后，将得到卡片顺序为 $6, 7, 8, 9, 4, 5, 1, 2, 3$。从上数第 $3$ 张到第 $7$ 张卡片中，编号不超过 $4$ 的卡片有两张，即编号 $4$ 和编号 $1$。 ### 样例解析 2 对于输入例 2，依次执行“洗牌 $(3, 8)$”、“洗牌 $(2, 5)$”、“洗牌 $(6, 10)$”后，卡片顺序为 $9, 10, 3, 11, 12, 4, 5, 6, 7, 8, 1, 2$。从上数第 $3$ 张到第 $8$ 张卡片中，编号不超过 $5$ 的卡片数量为 $3$。 **本翻译由 AI 自动生成**

### 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 $ 枚である．