Программисты компании «Периметр» работают над n проектами. Начальник программистов Шифтмэн прекрасно понимает, насколько важны комфортные условия для продуктивной работы — в компании нет ни дресс-кода, ни фиксированного рабочего графика, зато на кухне всегда есть чай и свежие киви. А когда команда проекта «Диплодок» стала жаловаться на то, что после выхода на работу новых сотрудников в комнате не протолкнуться, Шифтмэн понял — пора искать более просторный офис.
Новое офисное здание нашлось быстро. Оно расположено недалеко от метро, возле уютного парка. Кроме того, в подвале здания много парковочных мест. Узнав, что в новом офисе n больших комнат, Шифтмэн решил выделить по комнате каждому проекту, чтобы сотрудники создали там уникальную для каждого проекта рабочую атмосферу. Менеджер каждого проекта знает, какая комната идеально подойдет для его команды — с одной стороны, комната должна быть не слишком тесной, а с другой — не слишком большой, чтобы сотрудники не боялись того, что к ним могут подселить новый проект. Помогите менеджерам поделить комнаты самим, быстро и без вмешательства начальства.
В первой строке записано целое число n — количество проектов в «Периметре» (1 ≤ n ≤ 100000). Во второй строке записаны n целых чисел — площади всех комнат в новом офисе. В i-ой из следующих n строк записаны два целых числа — минимальная и максимальная площади комнаты, в которой согласна сидеть команда i-ого проекта (естественно, минимальная площадь не превосходит максимальной). Все указанные площади положительные и не превосходят 109.
Если существует единственный способ рассадить команды по комнатам так, чтобы все команды остались довольны, в первой строке выведите «Perfect!», а во второй строке — перестановку чисел от 1 до n. i-ое число должно обозначать номер комнаты, которую должна занять команда i-ого проекта. Комнаты занумерованы числами от 1 до n в том порядке, в котором они описаны во входных данных.
Если возможных вариантов рассадки несколько, выведите «Ask Shiftman for help.»
Если рассадить команды требуемым образом нельзя, выведите «Let's search for another office.»
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.
