火焰冲击

题目描述

在游戏中，玩家扮演一位使用技能攻击怪兽的英雄。

游戏世界可以看作一个由二维坐标系构成的平面，大小为 $P \times Q$，左下角为坐标原点 $(0,0)$。

游戏开始时，场上共有 $N$ 只怪兽。第 $i$ 只怪兽位于坐标 $(x_i,y_i)$，初始血量为 $H_i$，击杀后可以获得分数 $V_i$。同一位置可能存在多只怪兽。

当玩家用技能击中怪兽时，怪兽的血量减少 $1$。当某只怪兽的血量 $H_i \le 0$ 时，它会立即死亡，玩家获得该怪兽的击杀分数 $V_i$，死亡的怪兽会永久退出游戏。

玩家可以使用英雄的专属技能 「火焰冲击」，生成一道平行或垂直于坐标轴的燃烧之墙，攻击连续若干行或若干列：

• 生成一道垂直于 $x$ 轴的墙，从最上方无限远处向下攻击，对所有 $x_i \in [l,r]$ 的怪兽造成 $1$ 点伤害；
• 生成一道平行于 $x$ 轴的墙，从最左侧无限远处向右攻击，对所有 $y_i \in [l,r]$ 的怪兽造成 $1$ 点伤害。

整个游戏过程可以抽象为 $M$ 个事件，事件分为三种类型：前两类事件是玩家使用技能攻击，第三类事件是新的怪兽在坐标平面上出现。

现在你需要编写一个即时游戏插件，在每个事件发生后输出玩家当前的分数。

为保证插件的"即时性"，部分输入数据会被加密，需要在读入时即时解密，解密方法见「输入格式」。

输入格式

第一行四个正整数 $N,M,P,Q$（$1\le N,M,P,Q\le 10^5$），分别表示初始怪兽数量、游戏过程的事件总数、地图的长和宽。

接下来 $N$ 行，每行四个非负整数 $x_i,y_i,H_i,V_i$（$0\le x_i<P$，$0\le y_i<Q$，$1\le H_i\le 10^5$，$1\le V_i\le 10^4$），分别表示怪兽的横坐标、纵坐标、初始血量、击杀分数。

接下来 $M$ 行，每行表示一个事件，以参数 $Type_i$ 开头：

• 当 $Type_i=1$：表示玩家释放垂直于 $x$ 轴的墙，向下攻击。此时还需读入两个参数 $l_i',r_i'$（$0\le l_i',r_i'<P$），表示加密后的攻击范围。解密公式为：

$$l=\min\big((l_i'+score)\bmod P,\ (r_i'+score)\bmod P\big)$$$$r=\max\big((l_i'+score)\bmod P,\ (r_i'+score)\bmod P\big)$$

其中 $score$ 表示本次攻击前的玩家分数。随后所有满足 $x_i\in[l,r]$ 的怪兽受到 $1$ 点伤害，血量 $\le 0$ 的怪兽死亡并获得击杀分数。

• 当 $Type_i=2$：表示玩家释放平行于 $x$ 轴的墙，向右攻击。此时还需读入两个参数 $l_i',r_i'$（$0\le l_i',r_i'<Q$），表示加密后的攻击范围。解密公式为：

$$l=\min\big((l_i'+score)\bmod Q,\ (r_i'+score)\bmod Q\big)$$$$r=\max\big((l_i'+score)\bmod Q,\ (r_i'+score)\bmod Q\big)$$

随后所有满足 $y_i\in[l,r]$ 的怪兽受到 $1$ 点伤害，血量 $\le 0$ 的怪兽死亡并获得击杀分数。

• 当 $Type_i=3$：表示出现一只新的怪兽。此时还需读入四个非负整数 $x_i,y_i,H_i,V_i$，含义同初始怪兽。

玩家的初始分数为 $0$。

输出格式

输出 $M$ 行，每行一个整数，表示对应事件发生后玩家的分数 $score$。

样例 #1

样例输入 #1

3 4 15 8
5 4 2 1
5 5 2 1
4 5 2 1
1 5 8
2 1 4
3 4 5 1 1
2 4 1

样例输出 #1

0
1
1
3

样例 #1 解释

玩家初始分数为 $0$。

• 第一个事件释放垂直于 $x$ 轴的墙。解密后的 $l,r$ 分别为 $5,8$，攻击了前两只怪兽，此时分数为 $0$。
• 第二个事件释放平行于 $x$ 轴的墙。解密后的 $l,r$ 分别为 $1,4$，攻击了第一只怪兽，此时分数为 $1$。
• 第三个事件新增一只怪兽（可位于已有怪兽相同坐标），分数不变，仍为 $1$。
• 第四个事件释放平行于 $x$ 轴的墙。解密后的 $l,r$ 分别为 $2,5$，攻击了除已死亡第一只怪兽外的所有怪兽，此时分数为 $3$。

样例 #2

样例输入 #2

12 20 10 15
3 14 2 9
9 12 1 5
8 7 1 10
7 6 4 9
0 6 4 10
1 13 5 9
5 13 3 1
0 9 2 1
5 11 3 10
1 8 2 8
3 13 3 9
9 4 1 3
1 6 3
3 0 8 2 1
1 0 4
2 5 0
1 0 9
3 0 7 3 5
1 9 7
1 1 6
1 5 6
1 1 5
2 13 1
3 0 0 2 2
2 14 11
3 0 14 1 5
2 12 6
2 9 1
1 6 6
2 7 5
1 9 0
1 0 9

样例输出 #2

0
0
9
24
24
24
32
53
56
56
56
56
57
57
57
80
80
80
95
95

数据范围与子任务

测试点	数据范围	A	B	C
1~5	$N,M,P,Q\le 5000$	×	×	×
6	$N,M,P,Q\le 50000$	√		√
7				×
8		×	√	√
9				×
10			×	√
11-12				×
13	$N,M,P,Q\le 100000$	√		√
14				×
15		×	√	√
16				×
17			×	√
18-20				×

特殊性质：

• 性质 A：怪兽血量 $H_i=1$；
• 性质 B：怪兽血量 $H_i\le 30$；
• 性质 C：每次技能的攻击范围恰为一行或一列（即解密后 $l=r$）。

对于所有数据：$1\le N,M,P,Q\le 10^5$，$0\le x_i<P$，$0\le y_i<Q$，$1\le H_i\le 10^5$，$1\le V_i\le 10^4$。