Programmers at the company “Perimeter” are working on n software projects.
Their boss Shiftman understands the importance of comfortable working conditions.
There is neither dress code nor fixed work schedule in the company, but there always is
tea and fresh kiwis in the kitchen. When the team of the “Diplodocus” project
complained that their room was too crowded after new employees had joined the company,
Shiftman understood that it was time to search for a new spacious office.
A new office building was found quickly. It was located near a subway station and a nice park.
In addition, there was a large underground parking. The number of rooms in the office
was the same as the number of projects in the company, so Shiftman decided to assign a room
to each project, thus creating a unique work atmosphere for the teams. Project managers
had their own notions of ideal room for their projects. Of course, the room should not be too small.
However, if the room would be too big, the programmers might be afraid that a new team
would be added to their room. Help the managers to assign the rooms quickly and without
the boss's meddling.
The first line contains the number n of projects in the company (2 ≤ n ≤ 1 000).
In the second line you are given n numbers, which are the areas of all the rooms in
the new office. The ith of the following n lines contains two numbers, which are
the minimum and maximum areas of the room in which the team of the ith project agrees to work
(of course, the minimum area does not exceed the maximum area). All the areas
are positive integers and do not exceed 10 000.
If there is only one way to assign the rooms to the teams, output “Perfect!”
in the first line and a permutation of integers from 1 to n in the second line.
In this permutation, the ith element must be the number of the room assigned to the team of the ith project.
The rooms are numbered from 1 to n in the order in which they are described in the input.
If there are several ways to assign the rooms, output “Ask Shiftman for help.”
If it is impossible to assign the rooms as required, output “Let's search for another office.”
40 50 60
2 1 3
40 50 70
Let's search for another office.
Problem Author: Alexander Klepinin
Problem Source: Open Ural FU Championship 2011