P4971 Judge of Sin

Hell on the Double Ninth Festival…… Shikieiki Yamaxanadu (hereinafter referred to as Lady Shiki) is the Chief Judge of Hell. She is usually responsible for judging the dead, deciding whether they go to Hell, Heaven, or somewhere else. Of course, Lady Shiki can easily judge the dead, but there are too many dead people. She needs your help to judge them, so that she can spare time to preach to others.

A person’s sin value $E$ is determined by **what they did while alive** and their **cause of death**. Every **bad deed** has a sin value. Bad deeds may be merged into the same set. The sin value of a set is the maximum sin value among the bad deeds in that set. The things a person did in their life **affect each other**. We classify what they did while alive into 4 types, and the final sin value $E$ is determined by the **sum of the sin values of all sets**. 1. Do a bad deed: has a sin value, and forms its own set. 2. Do a good deed: sets the sin value of one bad deed to zero. 3. Repent: for a specified set, decrease the bad deed with the maximum sin value by some amount. 4. Know yourself: merge two sets of bad deeds. The cause of death can be *natural death*, *accidental death*, or *suicide*. 1. Natural death: no effect. 2. Accidental death: the set with the maximum sin value can be forgiven (removed). 3. Suicide: the maximum set’s sin value is doubled.

The first line contains three integers $T, W, K$, where there are $T$ people to be judged, $W$ is the cause of death (corresponding to the numbering in the description), and $K$ is defined in the output format. The next $T$ groups of data describe each person. In each group, the first line contains two integers $n, m$, representing the number of bad deeds and the number of other actions. The second line contains $n$ integers, representing the sin value of each bad deed. Lines $3$ to $m + 2$ each contain one of the following three types of inputs. (Please refer to the description to understand them.) - $\verb!2 A!$: do a good deed, setting the sin value of bad deed $A$ to **zero**. - $\verb!3 A B!$: repent. The specified set is the set containing $A$. Decrease the bad deed with the maximum sin value in that set by $B$. If the maximum sin value is smaller than $B$, then set that bad deed’s sin value to **zero**. **If multiple bad deeds have the same sin value, the one with the smaller index is considered worse**. - $\verb!4 A B!$: know yourself, merging the set containing $B$ into the set containing $A$.

For each person, output one string and one integer on one line. If their sin value is $0$, output `Gensokyo`. If their sin value is greater than $K$, output `Hell`. Otherwise, output `Heaven`. Then output their sin value.

### Sample 1 Explanation At the beginning there are five bad deeds, with sin values $1.2.3.4.5$. After doing a good deed, the sin values become $1.2.0.4.5$. After knowing oneself, only four sets remain, with sin values $1.4.0.5$. Since it is natural death, the final sin value is $E=1+4+5=10 \le K \&\& E!=0$, so output $Heaven$. ### Sample 2 Explanation For the first test case of Sample 2, it is shown in the figure below. Black ovals represent sets, red numbers are sin values, and the numbers below are node indices. Since it is accidental death, the maximum set with index $5$ can be forgiven, so the sin value is $E=4+5$.  ### Notes All data fit in 64-bit signed integers. For all testdata, $m\le n$, $1\le K$, and the input contains no negative numbers. Since the input may be very large, faster input methods are recommended. > Convention ①: For the operation of merging two sets, at least one set contains only one bad deed. > Convention ②: These people will not do good deeds. | Test Point ID | T | n | Time Limit | Conventions | |:-:|:-:|:-:|:-:|:-:| | 1 | $\le10$ | $\le100$ | $1s$ | ①② | | 2 | $\le10$ | $\le300$ | $1s$ | ① | | 3 | $\le10$ | $\le500$ | $1s$ | | | 4 | $\le20$ | $\le1000$ | $1s$ | ①② | | 5 | $\le20$ | $\le3000$ | $1s$ | ① | | 6 | $\le20$ | $\le7000$ | $1s$ | | | 7 | $\le30$ | $\le10000$ | $1s$ | ①② | | 8 | $\le30$ | $\le30000$ | $1s$ | ① | | 9 | $\le30$ | $\le50000$ | $1s$ | | | 10 | $\le30$ | $\le70000$ | $1s$ | ①② | | 11 | $\le10$ | $\le100000$ | $1s$ | ① | | 12 | $\le10$ | $\le150000$ | $1s$ | | | 13 | $\le10$ | $\le200000$ | $1s$ | ①② | | 14 | $\le10$ | $\le500000$ | $1s$ | ① | | 15 | $\le10$ | $\le1000000$ | $2s$ | | | 16 | $\le10$ | $\le1000000$ | $2s$ | ①② | | 17 | $\le10$ | $\le1000000$ | $2s$ | ① | | 18 | $\le10$ | $\le2000000$ | $2s$ | | | 19 | $\le10$ | $\le2000000$ | $2s$ | | | 20 | $\le10$ | $\le2000000$ | $2s$ | | | 21 | $1$ | $\le2000000$ | $2s$ | Path Compression | Translated by ChatGPT 5