Chouti и его одноклассникам скоро предстоит поступать в университет. Чтобы попрощаться друг с другом, класс устроил большую прощальную вечеринку, на которой одноклассники, учителя и родители пели и танцевали.
Chouti вспомнил, что в этой вечеринке приняли участие \(n\) человек. Чтобы сделать вечеринку смешнее, каждый надел одну шляпу из \(n\) разновидностей странных шляп с номерами \(1, 2, \ldots n\). Возможно, что одну разновидность шляпы надели несколько человек. Некоторые разновидности шляп могли остаться невостребованными кем-либо.
После вечеринки \(i\)-й человек сказал, что было ровно \(a_i\) людей, на которых была надета шляпа, отличающаяся от его собственной.
Прошло несколько дней, поэтому Chouti забыл, кто был в каких шляпах, но ему очень интересно что-то про это вспомнить! Пусть \(b_i\) будет видом той шляпы, которую надел \(i\)-й человек. Chouti хочет, чтобы вы нашли какие-нибудь \(b_1, b_2, \ldots, b_n\), которые не противоречат утверждениям каждого человека. Так как у некоторых людей могут быть проблемы с памятью, решения может не существовать.
Выходные данные
Если решения не существует, выведите «Impossible».
Иначе, выведите «Possible» а затем \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) (\(1 \le b_i \le n\)).
Если существует несколько возможных решений, вы можете вывести любое из них.
Примечание
В ответе к первому примеру, все носили шляпу одного и того же типа, поэтому каждый скажет, что не было людей со шляпами, отличными от типа \(1\).
В ответе ко второму примеру, первый и второй человек носили шляпу типа \(1\), а все остальные носили шляпу типа \(2\).
Поэтому первые два человека скажут, что было три человека, с видом шляпы, отличным от их. Аналогично, три последних человека скажут, что было два человека с отличным видом шляпы.
Можно показать, что ответа на третий пример не существует.
В первых двух примерах существуют и другие варианты ответа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 0 0
|
Possible
1 1 1
|
|
2
|
5
3 3 2 2 2
|
Possible
1 1 2 2 2
|
|
3
|
4
0 1 2 3
|
Impossible
|