30 февраля в Центр олимпиадной подготовки программистов (ЦОПП) Берляндского государственного университета пришли n студентов. Они приходили по одному один за другим. Каждый из них, зайдя внутрь, прежде чем сесть за рабочее место, здоровался с присутствующими, пожимая руку. Каждый из пришедших студентов оставался в ЦОПП до конца дня, не покидая его.
В любой момент времени любые три студента могли объединиться и начать писать командный контест, который длился до конца дня. Команда не отвлекалась от контеста ни на минуту, поэтому очередной зашедший студент, здоровающийся с присутствующими, не пожимал руку участникам команд, пишущим контест. Каждая команда состояла ровно из трех студентов, а каждый студент мог стать членом не более чем одной команды. Разные команды могли начать писать контест в разное время.
Зная, скольким присутствующим каждый студент пожал руку, найдите возможный порядок, в котором студенты могли приходить в ЦОПП. Если такого порядка не существует, то сообщите, что это невозможно.
Обратите внимание, что какие-то студенты могли до конца дня работать самостоятельно, не участвуя в командном контесте.
Выходные данные
Если искомый порядок студентов существует, в первую строку выведите «Possible», а во вторую строку — перестановку номеров студентов, задающую порядок, в котором студенты приходили в центр. Число i стоящее левее числа j в этой перестановке будет означать, что i-й студент пришел раньше j-го студента. Если ответов несколько, выведите любой.
Если искомого порядка студентов не существует, в единственную строку выведите «Impossible».
Примечание
В первом примере из условия порядок событий мог быть следующим:
- пришел студент с номером 4 (a4 = 0), здороваться ему было не с кем;
- пришел студент с номером 5 (a5 = 1), пожал руку студенту с номером 4;
- пришел студент с номером 1 (a1 = 2), пожал руку двум студентам (с номерами 4, 5);
- пришел студент с номером 3 (a3 = 3), пожал руку трем студентам (с номерами 4, 5, 1);
- студенты с номерами 4, 5, 3 объединились в команду и начали писать контест;
- пришел студент с номером 2 (a2 = 1), пожал руку одному студенту (с номером 1).
Во втором примере из условия порядок событий мог быть следующим:
- пришел студент с номером 7 (a7 = 0), здороваться ему было не с кем;
- пришел студент с номером 5 (a5 = 1), пожал руку студенту с номером 7;
- пришел студент с номером 2 (a2 = 2), пожал руку двум студентам (с номерами 7, 5);
- студенты с номерами 7, 5, 2 объединились в команду и начали писать контест;
- пришел студент с номером 1 (a1 = 0), здороваться ему было не с кем (все писали контест);
- пришел студент с номером 6 (a6 = 1), пожал руку студенту с номером 1;
- пришел студент с номером 8 (a8 = 2), пожал руку двум студентам (с номерами 1, 6);
- пришел студент с номером 3 (a3 = 3), пожал руку трем студентам (с номерами 1, 6, 8);
- пришел студент с номером 4 (a4 = 4), пожал руку четырем студентам (с номерами 1, 6, 8, 3);
- студенты с номерами 8, 3, 4 объединились в команду и начали писать контест;
- пришел студент с номером 9 (a9 = 2), пожал руку двум студентам (с номерами 1, 6).
В третьем примере из условия порядок событий восстанавливается однозначно:
- пришел студент с номером 1 (a1 = 0), здороваться ему было не с кем;
- пришел студент с номером 3 (или с номером 4) (a3 = a4 = 1), пожал руку студенту с номером 1;
- пришел студент с номером 2 (a2 = 2), пожал руку двум студентам (с номерами 1, 3 (или 4));
- оставшийся студент с номером 4 (или с номером 3), должен пожать руку одному студенту (a3 = a4 = 1), однако это невозможно, так как существует всего два варианта событий: либо образовалась команда, и он ни с кем не поздоровается, либо он поздоровается со всеми тремя присутствующими, работающими индивидуально.