CF311C Fetch the Treasure

Rainbow 在一排长度为 $h$ 的格子中建造了 $h$ 个格子，这些格子从左到右编号为 $1$ 到 $h$。其中有 $n$ 个格子藏有宝藏。我们称这 $n$ 个格子为“藏宝格”。第 $i$ 个“藏宝格”为第 $a_i$ 个格子，其宝藏价值为 $c_i$ 美元。 Freda 站在第一个格子。目前，她只能每次往前走 $k$ 个格子，或者返回到第一个格子。也就是说，Freda 能到达的格子为第 $1$、$(k+1)$、$(2k+1)$、$(3k+1)$ 等格子。 随后 Rainbow 给了 Freda $m$ 次操作。每次操作为以下三种类型之一： 1. 新增前进方式 $x$：Freda 可随时选择往前走 $x$ 个格子。例如，最开始她只有一种方式 $k$。如果此时她有 $a_1,a_2,\ldots,a_r$ 种方式，则她可以到达所有编号为形式 $$ 1 + v_1 a_1 + v_2 a_2 + \ldots + v_r a_r $$ 的格子，其中 $v_i$ 为非负整数。 2. 将第 $x$ 个“藏宝格”的宝藏价值减少 $y$ 美元，即令 $c_x = c_x - y$。 3. 查询 Freda 当前能到达的所有藏宝格中，宝藏价值最大的那一个，并输出其价值。如果当前没有可达的“藏宝格”，输出 $0$。否则，Freda 会取走这个宝藏。如果有多个“藏宝格”拥有同样的最大宝藏价值，则取编号最小的“藏宝格”（不一定是格子编号最小的格子）。之后，这个“藏宝格”不再计入后续的藏宝格总数。 你需要为 Freda 编写程序，回答每一次操作类型 3 的询问。

第一行包含四个整数：$h$（$1 \leq h \leq 10^{18}$）、$n$、$m$（$1 \leq n,m \leq 10^5$）以及 $k$（$1 \leq k \leq 10^4$）。 接下来 $n$ 行，每行包括两个整数 $a_i$（$1 \leq a_i \leq h$）、$c_i$（$1 \leq c_i \leq 10^9$），表示第 $i$ 个“藏宝格”在第 $a_i$ 个格子，宝藏价值为 $c_i$ 美元。所有 $a_i$ 互不相同。 接下来的 $m$ 行，每行是一种下列格式之一： - "1 $x$"——类型 1 操作，$1 \leq x \leq h$； - "2 $x$ $y$"——类型 2 操作，$1 \leq x \leq n, 0 \leq y < c_x$； - "3"——类型 3 操作。 类型 1 操作最多不超过 20 次。保证任何时刻每个藏宝格的宝藏价值均为正数。也保证所有操作合法（不会减少已经取走的宝藏的价值）。 **注意：请勿在 C++ 中使用 %lld 读取 64 位整数。建议使用 cin/cout 或 %I64d。**

对于每次类型 3 操作，输出一个整数，即 Freda 当前能到达的所有“藏宝格”中，宝藏价值最大的那一个（美元）。如果没有可达的藏宝格，输出 $0$。

在样例中，共有 10 个格子和 3 个藏宝格。第一个藏宝格在第 5 个格子，宝藏价值为 50 美元。第二个藏宝格在第 7 个格子，宝藏价值为 60 美元。第三个藏宝格在第 8 个格子，宝藏价值为 100 美元。 一开始，Freda 只能到达第 1、3、5、7、9 号格子。在第一次操作中，将第二个藏宝格的价值由 60 减少到 55。此时能到达的藏宝格价值最大为 max(50, 55) = 55。第三次操作后，Freda 新增了一种每次前进 3 格的方式，于是她能到达第 1、3、4、5、6、7、8、9、10 号格子，这时价值最大的藏宝格变为 100。 注意，Freda 每次取走最大价值的藏宝格后，该藏宝格不再算作藏宝格，因此后续答案变为 50。 由 ChatGPT 5 翻译