JRY is Fighting

Long long ago, there is a hero fighting against the emperor JRY. At the very beginning, the hero has $m$ HPs(health-points). There points represent his health - if ever they fall below or equal to zero, the hero will die. In the following $n$ seconds, he will be hurt by XXY. At the $i$ seconds, his HP will reduce by $h_i$. If $h_i<0$, it means his HP will increase by $|h_i|$.

The hero has a magic bottle which can store HPs. At first, the bottle is empty. Each time after the hero got hurt, the bottle can get $k$ more HPs, and the hero can decide whether he will release the HPs in the bottle. If he does, he will gain the HPs in the bottle and the bottle will be empty.

We define the hero's operating sequence as $s$, representing that he used the magic bottle at the $s_i$-th seconds. $|s|$ represent the times he used, as well as the length of the sequence.

Now, you should maximize the mininum time interval between two adjacent operation. In other words, let $T = \max \left \{ \min \left \{ s_{i}-s_{i-1} \right \}(1<i\leq |s|) \right \}$, you should find the value of $T$. We can easily find that if $|s|\leq 1$, $T=+ \infty$.

You should give him a plan as an operating sequence $s$ which is right for the hero to survive successfully. The hero is so strict that you should find the lexicographically smallest one.

Sequence $u_1,u_2,\cdots,u_n$ is lexicographically smaller than sequence $v_1,v_2,\cdots,v_m$, if

$n<m$ and $u_1=v_1,u_2=v_2,\cdots,u_n=v_n$, or

there exists an integer $k(1\leq k\leq \text{min}(n,m))$ where $u_1=v_1,u_2=v_2,\cdots,u_{k-1}=v_{k-1}$ and $u_k<v_k$ all hold.

There are multiple testcases, the sum of $n$ is less then $10^6$.
The first line contains three space-separated integers each, $n(1\leq n\leq 500000)$, $m(1\leq m \leq 10^6)$, $k(1\leq k \leq 100)$.
The second line contains $n$ space-separated integers, $a_i(0\leq |a_i| \leq 100)$.

If the hero can't survive, print "Poor Hero!".
If $T=+\infty$, print "Poor JRY!".
Otherwise, print three lines:
The first line, an integer, representing the value of $T$.
The second line, an integer, $|s|$.
The third line, $|s|$ space-separated intergers, $s_i$.

5 7 3
1 -2 10 2 2
2 33 33
-33 -33
1 1 1
1

2
2
1 3
Poor JRY!
Poor Hero!

Case 1 :
At second 1, hero's HP are $7-1=6$, bottle has 3 HP, hero used the bottle, hero's HP are $6+3=9$, bottle has 0 HP.
At second 2, hero's HP are $9+2=11$, bottle has 3 HP.
At second 3, hero's HP are $11-10=1$, bottle has $3+3=6$HP, hero used the bottle, hero's HP are $1+6=7$, bottle has 0 HP.
At second 4, hero's HP are $7-2=5$, bottle has 3 HP.
At second 5, hero's HP are $5-2=3$.
Hero escaped successfully with $T=2, s_1=1,s_2=3$.

Case 2 :
Anyhow, hero can survive without using the bottle. So $T=+\infty$.

Case 3 :
Anyhow, hero's HP will be zero in chamber 1. So he can't survive.

XJZX

2015 Multi-University Training Contest 2