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

1920. Titan Ruins: the Infinite Power of Magic

Time limit: 1.0 second
Memory limit: 64 MB
`It seems that our efforts were not in vain,' Alba said after studying an ancient volume. `I've found here a method for accumulating a tremendous amount of energy. And the idea is so simple that I wonder why nobody has discovered it. The usual problem is that magic energy is unstable and it's difficult to keep it in one place. But if we channel it along a closed path, it'll have no way out. We only have to choose the right length of the path to keep the flow stable. Then we can pump in as much energy as we want. And when we break the path we'll release a magic flow of enormous power. It'll be a real breakthrough in war magic!'
`Yes, but the path must be long enough and you can't drag a large device over a battlefield.'
`That's not a problem. The form of the path can be arbitrary. We can design a compact scheme of the device. Actually, the device is here already, it's there in the corner. We only have to adjust it.'
Indeed, there was a square grid with n × n nodes. At each node there was a prism that could be turned so as to either direct a flow of magic energy straightly or turn it by 90°. Soren and Alba had to position L prisms so that a cyclic flow of magic energy of length L could be directed through them.


You are given the integers n and L (2 ≤ n ≤ 100; 4 ≤ L ≤ 20 000).


If it is impossible to organize a cycle of required length, output “Unsuitable device”. Otherwise, output “Overwhelming power of magic” in the first line. In each of the following L lines give two integers in the range from 1 to n, which are the coordinates of the grid nodes through which energy should pass. The distances between two consecutive nodes and between the first and the last nodes must be equal to 1. The energy mustn't pass more than once through the same node, because this may produce unpredictable and, most likely, lethal effects.


2 6
Unsuitable device
3 6
Overwhelming power of magic
1 1
2 1
3 1
3 2
2 2
1 2
Problem Author: Alexey Samsonov (prepared by Dmitry Ivankov)
Problem Source: NEERC 2012, Eastern subregional contest