400463: GYM100187 C Very Spacious Office

Memory Limit:256 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Very Spacious Officetime limit per test2.0 smemory limit per test256 megabytesinputstandard inputoutputstandard output

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 (1 ≤ n ≤ 100000). In the second line you are given n numbers, which are the areas of all the rooms in the new office. The i-th of the following n lines contains two numbers, which are the minimum and maximum areas of the room in which the team of the i-th 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 109.

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 i-th element must be the number of the room assigned to the team of the i-th 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.»

ExamplesInput
3
40 50 60
30 70
20 40
60 60
Output
Perfect!
2 1 3
Input
3
40 50 70
30 70
20 50
60 60
Output
Let's search for another office.

加入题单

上一题 下一题 算法标签: