ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

NEERC 2012, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Titan Ruins: Serial Control

Time limit: 2.0 second
Memory limit: 64 MB
`It seems that we're in a trap,' said Alba.
`That was my phrase,' Soren replied.
Alba and Soren were in a strange room, which, apparently, had been used for experimenting on serial remote control. There was a row of n magic rings along each of two opposite walls. All the rings in one of the rows were accessible, while the rings in the other row were protected by an impenetrable magic field, and it was impossible to approach them.
Alba rotated one of the accessible rings a little, and all the rings in the protected row rotated in different ways. He rotated another ring, and the protected rings rotated in another way. He continued the experiments and found out that a rotation of any ring in the open row produced a rotation of each ring in the protected row by a certain angle, which was proportional to the angle by which the open ring was rotated. The directions of rotations could be both clockwise and counterclockwise.
While Alba was studying the rings, Soren tried to figure out how they could get out of the room. There were two doors, and, apparently, each door was controlled by an energy flow passing through a row of rings. One of the flows passed through the open row, while the other passed through the protected row.
An energy flow could pass through a row and open a door only if each ring in this row was in a certain position. If a ring was rotated from this `correct' position by an integer number of complete turns, the energy flow could still pass freely, but if a ring was rotated by a fraction of a complete turn, the flow was blocked. Soren understood that the flows of magic energy had once kept the doors open, but later the energy generator had become weaker, and there wasn't enough energy to keep both doors open. It was necessary to block one of the flows so that the remaining flow could use all the energy produced by the generator. Then the flow would open one of the doors.
Alba and Soren needed to go through the door leading further down the dungeon. That door was controlled by the flow passing through the protected row.

Input

The first line contains the number n of rings in each row (1 ≤ n ≤ 100). In each of the following n lines you are given n integers separated with a space. A counterclockwise rotation of the i-th accessible ring produces Aij counterclockwise rotations of the j-th protected ring, where Aij is the i-th integer in the j-th line. The absolute values of Aij do not exceed 100. The initial positions of all the rings allow a flow of magic energy pass freely through them.

Output

If the wizards can't get further, output “Death”. Otherwise, output “Power of magic saves lives”.

Sample

inputoutput
3
1 2 0
4 3 0
0 0 0
Power of magic saves lives

Notes

Mages can rotate the first accessible ring 6/5 turns clockwise, the second ring 8/5 turns counterclockwise, and keep the third one still. As a result the first protected ring will make 2 full turns counterclockwise, while the second and the third rings will end up in their initial positions.
Problem Author: Alexander Ipatov (prepared by Dmitry Ivankov)
Problem Source: NEERC 2012, Eastern subregional contest
To submit the solution for this problem go to the Problem set: 1914. Titan Ruins: Serial Control