To Kill the Dragon#5610
A small group of brave magicians gathered together to kill the evil dragon. Since they do this every week (sometimes in several attempts), they know the dragon's behavior by heart and can predict all his moves with one-second precision.
There are two kinds of magicians: attackers and healers. Attackers damage the dragon, while healers heal injured magicians. Each attacker can create an anti-magic aura that continuously damages the dragon. Each healer can create an aura that continuously restores the health of all magicians on the battlefield.
While a magician maintains their spell, the power of their aura (damage or healing per unit time) increases linearly, but cannot exceed a specific maximum for that magician. When a magician stops maintaining the spell, the power of their aura decreases linearly until it falls to zero; it cannot become negative.
Auras of different magicians are independent. The total damage to the dragon equals the sum of damages from all attackers' auras. Similarly, the total healing each magician receives equals the sum of healing from all healers' auras. Magicians' hit points cannot exceed their initial values, which are the same for all magicians.
During the battle, the dragon uses spells in a fixed order. The same type of spell can be used multiple times in a row.
The first spell is Fire Storm. It creates a wall of fire across the field, except for a small plot at its center. Magicians in the fire receive constant damage equal to the spell's power and cannot cast spells. There is enough room in the center to fit all the magicians, who can cast spells without damage. The center may move to different locations each time the spell is used.
The second spell is Dragon's Breath. While this is in effect, all magicians receive constant damage equal to the spell's power. There are some relatively safe locations where magicians can cast spells (nowhere else can they do so); each safe location accommodates only one magician, and their number equals the number of magicians. The safe locations may change each time. The dragon never uses Dragon's Breath more than twice in succession.
Eventually, the dragon gets bored and kills all the magicians instantly with a tail strike.
A dragon attack is one of the two spells or a tail strike. The first attack starts at time . Each subsequent attack starts when the previous one ends. At the precise moment of switching attacks, the previous attack still takes effect.
Magicians run immediately toward the storm center along straight lines when a Fire Storm starts. For Dragon's Breath, each magician chooses a safe spot and moves straight to it. Multiple magicians may pass through the same point simultaneously, but each safe location can be occupied by only one magician.
The duration of each spell is enough for magicians to move from any previous safe spot to any current one (but not necessarily to survive). For Fire Storm, the duration also suffices for all auras to reach maximum strength and for all magicians' health to be fully restored. Spell power is always strictly greater than the maximal possible healing per second from all healers combined.
If any magician's hit points reach zero at any time, all magicians die. Killing the dragon is tougher: its health must reach zero, and then a final spell must be cast. All magicians must gather at the storm's center to perform this final spell, and must be alive. The final spell is instantaneous.
At time : all magicians start at the origin; each healer's aura begins at maximum power; each attacker's aura begins at zero.
The first line contains non-negative integers , , —the number of attackers, healers, and total dragon attacks (1 \le n + m \le 10; 1 \le k \le 10).
The second line contains , , —the initial hit points and speed (for every magician), and the dragon's initial hit points (1 \le hp\_m, hp\_d \le 10^9; 1 \le v \le 10^6).
Each of the next lines describes attackers: the -th line has dps_i, id_i, dd_i—maximum aura power, aura's power increment per unit time when spell is maintained, and decrement rate while running (1 \le dps_i, id_i, dd_i \le 10^6).
Each of the next lines describes healers: the -th line has hps_i, ih_i, dh_i (analogous to attacker stats, same constraints).
Then follow blocks describing dragon's attacks, in order. - If the attack is Fire Storm: the block has Storm on the first line, then and (spell power, duration: 1 \le d, t \le 10^6), then , (storm center: -1000 \le x, y \le 1000). - If the attack is Dragon's Breath: Breath on the first line, then and as above, then n+m lines with x_i and y_i (-1000 \le x_i, y_i \le 1000) for safe locations (all distinct). - If the attack is a Tail Strike: Tail on a line by itself.
It is guaranteed that there is exactly one Tail Strike, which is last; and there are never more than two Dragon's Breaths in a row.
Durations are seconds; coordinates in meters; velocities in meters per second. Aura powers and spell powers are hit points per second; increments/decrements are hit points per second squared.
Note: although all input values are integers, all processes are continuous.
If magicians cannot kill the dragon, print You are not prepared. Otherwise, print No useful loot again then on the next line the minimum attack number during which the dragon can die (attacks are -indexed).
Example 1