Snipe the Sniper

Time Limit: 1000MS

Memory Limit: 65536K

Description

Sniper is a hero from a very famous game called DotA (Defence of the Ancient). Although his name is "Sniper", in most cases he is the one who get sniped. Now the sniper is surrounded by his enemies once more, your task is to write a program to determine whether the sniper can successfully escape. Let's put the game into a coordinate system. We assume that at the beginning of the game, the Sniper is positioned at the origin (0,0). When the game starts, the Sniper will start moving straight to the point (100,0) along the x-axis at the speed of 1 unit per second. Once he PASSED the point, he is considered safe. There are totally n enemies who want to kill the Sniper before he passes the safe point. Each of them has its own coordinate (Xi, Yi) at the beginning of the game. Their move speed is the same with the Sniper's (1 unit per second). And each one of them can cast one and only one spell to reduce some of the Sniper's Health Point and stun the Sniper for a period of time( That means, in this period of time, the Sniper will stop moving). Each enemy's spell has its own range, the enemy can only cast the spell if the distance between him and the Sniper is not longer than the range. We assume all the Sniper's enemies are clever enough and they will use the best strategy.

Input

In the beginning of each case is a integer N(1≤N≤100), indicates the number of the Sniper's enemies. In each line of next N lines, there are 5 numbers, Xi, Yi, Si, Ri. Di, (Xi, Yi) is the initial coordinate of the i-th enemy. Si, Ri, Di are the stun time, range and damage of the i-th enemy's spell. The last line of each case is consist of one integer, HP, indicate the initial Health Point of the Sniper.

Output

For each case, if the Sniper can successfully pass the safe point, output "Safe!". If the Sniper will die before pass the safe point, output "Danger!".

Sample Input

2
50.0 50.0 10 0.0 0
100 210 0 100 100
100
3
50 50 10 50 50
50 50 10 50 50
200 200 100 50 100
150

Sample Output

Danger!
Safe!

Hint

The picture above provided a possible strategy for the enemies to kill the Sniper in 1st case.

Source

PKU Campus 2009 (POJ Monthly Contest – 2009.0

提交代码