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

Open Ural FU Championship 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

K. Spacious Office

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

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.

Output

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.”

Samples

inputoutput
3
40 50 60
30 70
20 40
60 60
Perfect!
2 1 3
3
40 50 70
30 70
20 50
60 60
Let's search for another office.
Problem Author: Alexander Klepinin
Problem Source: Open Ural FU Championship 2011
To submit the solution for this problem go to the Problem set: 1872. Spacious Office