#P4971. 断罪者

断罪者

题目背景

重阳节的地狱……

四季映姬·亚玛萨那度(以下简称四季大人)是地狱的最高裁判长,她平时负责给死者定罪,判断让死者去地狱还是天界,或者别的什么地方。

四季大人当然可以轻松地给死者断罪,但是死者太多了,四季大人需要你帮她断罪,以便腾出时间让她对别人进行说教。

题目描述

人们的罪恶值EE由人们生前所做过的事和他的死亡方式来决定。他们做过的坏事都会有一个罪恶值,这些坏事有可能会并入同一个集合,一个集合的罪恶值为该集合中罪恶值最大的坏事的罪恶值,而他们一生做过的事会互相影响,我们将他们生前做过的事分为4种,而最后的罪恶值EE由其中所有集合的罪恶值的和决定。

  1. 做坏事——有罪恶值,单独为一集合。
  2. 做好事——将一件坏事的罪恶值清零。
  3. 忏悔——将指定集合中,最大罪恶值的事罪恶值减少。
  4. 认清自己——将两个坏事集合合并。

而死亡方式可分为 自然死亡事故死亡自杀

  1. 自然死亡,没什么影响。
  2. 事故死亡,可以免除最大罪恶的坏事集合。
  3. 自杀,最大的坏事集合罪恶值翻倍。

输入格式

第一行三个输入 T,W,KT,W,K,代表有 TT 个人等待断罪,WW 为死亡方式,与描述序号对应,KK 含义见输出格式。

接下来的 TT 组数据,每组数据第一行两个输入 n,mn,m,代表他做过的坏事数量和其他事的数量。

第二行 nn 个输入,代表每件坏事的罪恶值。

33 到第 m+2m+2 行,每行有三种输入可能。(请联系题目描述进行理解)

  • 2 A\verb!2 A!:表示做好事,将坏事 AA 罪恶值清零
  • 3 A B\verb!3 A B!:表示忏悔,指定集合为 AA 所在的集合,最大罪恶值的事减少 BB,若最大罪恶值比 BB 小,则最大罪恶值的事罪恶值清零对于罪恶值相等的坏事,认为编号更小的更坏
  • 4 A B\verb!4 A B!: 表示认清自己,将 BB 所在集合与 AA 所在的集合合并。

输出格式

对于每一个人,一行输出一个字符串和一个整数。

若他的罪恶值为 00 则输出 Gensokyo,若他的罪恶值大于 KK 则输出 Hell,否则输出 Heaven。再输出它的罪恶值。

1 1 10
5 2
1 2 3 4 5
2 3
4 2 4
Heaven 10
2 2 8
5 4
4 8 7 5 6
4 2 4
2 2
4 2 3
3 3 2
3 2
5 1 2
2 2
3 3 2
Hell 9
Gensokyo 0
2 1 15
5 4
1 2 3 4 5
4 2 3
3 2 100
4 1 4
4 4 1
5 4
1 2 3 4 5
3 2 15
4 2 3
4 1 4
4 3 4
Heaven 11
Heaven 9

提示

样例 1 解释

一开始有五件坏事,罪恶值分别为 1.2.3.4.51.2.3.4.5,做好事之后,罪恶值分别为 1.2.0.4.51.2.0.4.5,认清自我后,只剩下四个集合,罪恶值分别是 1.4.0.51.4.0.5,由于是自然死亡,所以最后的罪恶值 E=1+4+5=10K&&E!=0E=1+4+5=10 \le K \&\& E!=0,因此输出 HeavenHeaven

样例 2 解释

对于样例2的第一组输入如下图,黑色椭圆代表一个集合,红色为罪恶值,下面为点的编号,由于是事故死亡,可以免去标号5的最大值,故罪恶值为E=4+5E=4+5

说明

所有数据均在长整型范围内,对于所有数据,均有mnm\le n,1K1\le K,保证输入不存在负数。
由于读入数据可能会很大,建议使用较快的读入。

约定 ① 对于合并两个集合的操作,至少有一个集合只有一件坏事; 约定 ② 这群人不会做好事。

测试点编号 T n 时限 约定
1 10\le10 100\le100 1s1s ①②
2 300\le300
3 500\le500
4 20\le20 1000\le1000 ①②
5 3000\le3000
6 7000\le7000
7 30\le30 10000\le10000 ①②
8 30000\le30000
9 50000\le50000
10 70000\le70000 ①②
11 10\le10 100000\le100000
12 150000\le150000
13 200000\le200000 ①②
14 500000\le500000
15 1000000\le1000000 2s2s
16 ①②
17
18 2000000\le2000000
19
20
21 11 路径压缩