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 自动生成