404645: GYM101597 H Compass

Memory Limit:64 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Compasstime limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

The university of Algoland is located in a single huge building. It is great. It is the best building in the world. It only uses the best angles: the right angle! But the building is so huge that it is also very confusing to new students, because it is very easy to get lost.

The rector of Algoland's university, a former professor in physics, had a great idea to prevent students from getting lost in the future: He bought an incredibly strong magnet with the intention of placing it somewhere inside the building and using it as an emergency meeting point. On the first day of the semester, every student gets a free compass. With that compass the student can always tell the direction towards the magnet (the magnet is so strong that it completely dominates the earth's magnetic field). If a student gets lost, she can follow the following simple procedure to get to the emergency meeting point at the magnet's location:

  • Move straight into the direction towards the magnet until you either reach the magnet, or bump into a wall.
  • If your path is blocked by a wall, follow the direction alongside the wall that brings you closer towards the magnet, until you either reach the end of the wall or your path becomes orthogonal to the compass direction.
  • If the wall is perfectly orthogonal to the compass direction, or you end up in a corner, you are stuck. Scream as loud as you can!

In the corner case where you want to walk parallel to a wall at the exact coordinate of a wall, you are not stopped by the wall. We assume here that you are infinitesimally small (which is true in proportion to the size of the building).

The rector now wants your help to place the magnet inside the building in such a way that every student can reach it (following the procedure above) no matter where inside the building the student gets lost. Actually, you just have to decide if this is possible or not.

Input

The first line contains an integer N, the number of points, 4 ≤ N ≤ 103.

Each of the following N lines contains two coordinates x and y (0 ≤ x ≤ 103 and 0 ≤ y ≤ 103). Each line describes a corner point of the single wall that delimits the inside from the outside of the building. The points are given in clockwise order and all the angles are guaranteed to be 90 degrees.

Output

Print a single line containing a single word: either SAFETY if it is possible to place the magnet such that one is always able to find it, or DANGER otherwise.

ExamplesInput
12
1 0
1 3
2 3
2 1
3 1
3 2
4 2
4 1
5 1
5 3
6 3
6 0
Output
SAFETY
Input
12
0 4
5 4
5 0
2 0
2 2
3 2
3 1
4 1
4 3
1 3
1 1
0 1
Output
DANGER
Input
14
6 4
6 0
3 0
3 1
2 1
2 0
1 0
1 2
4 2
4 1
5 1
5 3
1 3
1 4
Output
SAFETY
Note

加入题单

上一题 下一题 算法标签: