Boring Business

Boring is a type of drilling — specifically, the drilling of a tunnel, well, or hole in the earth. Using the technique known as geosteering, drill operators can drill wells vertically, horizontally, or even on a slanted angle.

A well plan is prepared before drilling. It specifies a sequence of line segments representing the geometrical shape of the future well. As new information becomes available during drilling, the model can be updated and the well plan modified.

Your task is to write a program that verifies the validity of a well plan by checking that the borehole will not intersect itself. A two-dimensional well plan represents a vertical cross-section of the borehole, and the drill point always moves one unit at a time along integer coordinates.

The well that has already been drilled (shown in the figure below) is the polyline connecting, in order, the integer points:

(0, -1) → (0, -3) → (3, -3) → (3, -5) → (5, -5) → (5, -3) → (7, -3) → (7, -7) → (-1, -7) → (-1, -5)

That is, the existing borehole starts at (0, -1) and ends at (-1, -5). The borehole is the set of every integer lattice point this polyline passes through. Your program continues drilling from the borehole's endpoint, (-1, -5), which is already part of the borehole.

The input is a sequence of drilling command pairs. Each pair begins with one of four direction indicators, followed by a positive integer length.

• d (down) — y decreases
• u (up) — y increases
• l (left) — x decreases
• r (right) — x increases

There is an additional command indicated by q (quit) followed by any integer, which means the program should stop execution.

You may assume the input is such that the drill point will never:

• rise above the ground,
• go more than 200 units below the ground,
• go more than 200 units to the left of the original starting point, nor
• go more than 200 units to the right of the original starting point.

The program continues to monitor drilling, assuming the well in the figure has already been made. As noted above, (-1, -5) is the starting position for your program.

For each command, the drill advances the given length in the given direction, one unit at a time. If at any point during this movement the drill enters an integer lattice point that already belongs to the borehole, a self-intersection has occurred.

After each command, output the x and y coordinates of the drill's new position separated by a space, followed by one of two comments on the same line: safe if this move never met a previous borehole location, or DANGER if it met one at least once. The reported coordinates are the position after completing the command in full. After detecting and reporting a self-intersection with DANGER, the program must stop.