`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
input | output |
---|
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