Welcome to ZOJ
50 - ZOJ Monthly, February 2006 - 1007
Tower Defense

Time Limit: 5 Seconds      Memory Limit: 32768 KB

Tower Defense(TD) is a kind of rpg game in the warcraft3, which is very popular. in this game, you can build some tower near the road, and the enemy come along the road. when the enemy in the tower's attack range, the tower can attack the enemy. and each attack the enemy's life will reduce as the damage of the tower. When the enemy's life less than or equals 0, it dies. The mission of TD is kill all the enemies.

Now let's consider an easy situation. In the X-Y reference frame, there are n towers, each has a coordinate (x,y), an attack range, an attack type. m enemies come from (0,0) to (-10,0), in a line, with the length 2, and the enemies are come one by one. For example, in time 0 the all m enemies in (0,0), then in time 1 the first enemy go to (-2,0), in time 2 the first enemy go to (-4,0), the second enemy go to (-2,0), and so on, when an enemy go to (d,0)(d<=-10), we failed, even if it is still poisoned at this time, or we succeed. when the eneny in (0,0) and (d,0)(d<=-10), the tower can not attack, even if the enemy is in the tower's attack range. To simplify the problem, at each time each tower can attack once. when more than one enemy in its range, we can control it to attack any one, or even control it not attack, with the best strategy.

There are three attack type:
   common attack: when an enemy is attacked, the life is reduced by the damage of the tower.
   poison attack: when an enemy is attacked, the life is first reduced by the damage of the tower. And in the next 2 times, the enemy's life will be reduced by the poison damage. if the enemy poisoned more than once, the damage will not double. For example, the enemy's life is 200, tower's damage is 100, poison damage is 20, in time 1, the enemy be attacked, then in time 1, the enemy's life is 100(200-100), in time 2 the enemy's life is 80(100-20), in time 3 the enemy's life is 60(100-20).
   freezing attack: when an enemy is attacked, the life is first reduced by the damage of the tower. And in next 2 times, the enemy's speed is reduced by half. For example, an enemy be attacked in (-2,0), then it first go to (-3,0), (-4,0), then go to (-6,0), the freezing can not double, too. The problem is give us n towers and m enemies, can we successful in the tower defense?


The first line of the input is n, m,life and poison_damage, the number of the towers, the number of the enemies, the life of enemy and the poison damage of poison attack. n<6, m<6, life<1000, 0<poison_damage<1000. Next n lines is the description of each tower, the first 5 number is x, y, range, damage, attack_type, the attack_type can be 0, 1, 2, which denote common attack, poison attack, freezing attack. 0<damage<1000. All are integers. a line with n=m=life=0 denoted the end of input.


If we succeed in the tower defense, output "succeed", or output "fail", in a separate line.

Sample Input:
1 1 10 5
1 1 20 10 0
1 1 20 5
-2 0 1 10 0
2 2 40 5
-3 0 1 30 0
-7 0 1 10 0
0 0 0 5
Sample Output:

Author: LAI Chunbo
Submit    Status