534D орчуулах · Codeforces.mn

# Гар барих
Хоёрдугаар сарын 30нд Берландын Улсын Их сургуулийн Олимпиадын Програмчлагчдыг Сургах Төвд (CTOP) $n$ оюутан ирсэн. Тэд нэг нэгээрээ цувж ирсэн. Тэдний нэг бүр нь орж ирээд ширээндээ суухаасаа өмнө өрөөнд байгаа хүмүүстэй гар барин мэндлэнэ. CTOP-д ирсэн оюутнууд өдрийн төгсгөл хүртэл байх ба орхиж гарахгүй.

Хэдийд ч гурван оюутан нийлээд өдрийн төгсгөл хүртэл үргэлжлэх багийн тэмцээнд оролцож эхэлж болно. Баг тэмцээнээс нэг минут ч сатаарахгүй ба ирсэн оюутан байсан хүмүүстэй гар барьчихаад тэмцээнд оролцож буй багийн гишүүдтэй гар барихгүй. Баг бүр яг гурван оюутантай байх ба оюутан бүр нэгээс олон багийн гишүүн байж болохгүй. Ялгаатай багууд тэмцээнд ялгаатай цагт оролцож болно.

Оюутан бүр хэдэн хүнтэй гар барьсан нь өгөгдсөн бол оюутнууд CTOP-д ирэх боломжит дарааллыг ол. Хэрвээ ийм дараалал байхгүй бол энэ бол боломжгүй гэж хэвлэ.

Зарим оюутнууд багийн тэмцээнд оролцохгүйгээр өдрийн төгсгөл хүртэл ганцаараа бие даагаад ажиллаж болно.

## Оролт
Эхний мөрөнд $n$ ($1 ≤ n ≤ 2\*10^{5}$) байх ба CTOP-д ирсэн оюутнуудын тоо. Дараагийн мөрөнд $n$ ширхэг бүхэл тоон утгууд $a\_{1}, a\_{2}, ..., a\_{n}$ ($0 ≤ a\_{i} < n$) байх ба $a\_{i}$ нь $i$-р оюутантай гар барьсан оюутнуудын тоо.

## Гаралт
Оюутнуудын дараалал оршин байвал эхний мөрөнд "$Possible$" гэж хэвлэх ба хоёр дахь мөрөнд оюутнуудын төврүү нэвтэрсэн дарааллын байрлалын дугааруудыг хэвлэ. Уг дараалалд $i$ тоо $j$ тооны зүүн талд байрлах ба энэ нь $i$-р оюутан $j$-р оюутнаас эрт ирсэн гэсэн үг. Хэрвээ хэд хэдэн хариулт байвал алийг нь ч хэвлэж болно.

Хэрвээ оюутнуудын дараалал оршин байхгүй бол нэг мөрөнд "$Impossible$" гэж хэвлэ.

## Тэмдэглэл
Эхний жишээн дээрх нөхцөлөөс үйл явдлууд дараах байдалтай байж болно:

* 4-р оюутан ирсэн ($a\_{4} = 0$), мэндлэх хүн байгаагүй; 
  * 5-р оюутан ирсэн ($a\_{5} = 1$), тэр 4-р оюутантай мэндлэнэ; 
  * 1-р оюутан ирсэн ($a\_{1} = 2$), тэр хоёр оюутантай мэндлэнэ (4, 5-р оюутнууд); 
  * 3-р оюутан ирсэн ($a\_{3} = 3$), тэр гурван оюутантай мэндлэнэ (4, 5, 1-р оюутнууд); 
  * 4, 5, 3-р оюутнууд нийлж баг болоод тэмцээнд оролцож эхэлнэ; 
  * 2 comes in-р оюутан ирсэн ($a\_{2} = 1$), тэр нэг оюутантай мэндлэнэ (дугаар 1).

Хоёр дахь жишээн дээрх нөхцөлөөс үйл явдлууд дараах байдалтай байж болно:

* 7-р оюутан ирсэн ($a\_{7} = 0$), мэндлэх хүн байгаагүй; 
  * 5-р оюутан ирсэн ($a\_{5} = 1$), тэр 7-р оюутантай мэндлэнэ; 
  * 2-р оюутан ирсэн ($a\_{2} = 2$), тэр хоёр оюутантай мэндлэнэ (7, 5-р оюутнууд); 
  * 7, 5, 2-р оюутнууд баг үүсгэх ба тэмцээнд оролцож эхэлнэ; 
  * 1-р оюутан ирсэн ($a\_{1} = 0$), мэндлэх хүн байгаагүй (бүх хүмүүс тэмцээнд оролцоод завгүй байгаа); 
  * 6-р оюутан ирсэн ($a\_{6} = 1$), тэр 1 дугаартай оюутантай мэндлэнэ; 
  * 8-р оюутан ирсэн ($a\_{8} = 2$), тэр хоёр оюутантай мэндлэнэ (1, 6-р оюутнууд); 
  * 3-р оюутан ирсэн ($a\_{3} = 3$), тэр гурван оюутантай мэндлэнэ (1, 6, 8-р оюутнууд); 
  * 4-р оюутан ирсэн ($a\_{4} = 4$), тэр дөрвөн оюутантай мэндлэнэ (1, 6, 8, 3-р оюутнууд); 
  * 8, 3, 4-р оюутнууд баг үүсгэж тэмцээнд оролцож эхэлнэ; 
  * 9-р оюутан ирсэн ($a\_{9} = 2$), тэр хоёр оюутантай мэндлэнэ (1, 6-р оюутнууд).

Гуравдугаар жишээн дээрх нөхцөлөөс үйл явдлуудын дараалал тодорхой сэргээгдэнэ:

* 1-р оюутан ирсэн ($a\_{1} = 0$), мэндлэх хүн байгаагүй; 
  * 3-р оюутан ирсэн (эсвэл 4-р оюутан) ($a\_{3} = a\_{4} = 1$), тэр 1-р оюутантай мэндлэнэ; 
  * 2-р оюутан ирсэн ($a\_{2} = 2$), тэр хоёр оюутантай мэндлэнэ (1, 3 (эсвэл 4) дугаартай оюутнууд); 
  * үлдсэн оюутан буюу 4-р (эсвэл 3-р оюутан), нэг оюутантай мэндлэх ёстой ($a\_{3} = a\_{4} = 1$) боловч энэ нь боломжгүй ба хоёр зам байгаа нь: нэг бол баг бүрдэж түүнд мэндлэх хүн үлдэхгүй эсвэл тэр ганцаараа бие дааж ажиллаж байгаа гурван хүнтэй гурвуулантай нь мэндлэнэ.

-- Г.Мэндбаяр

Жишээ тэстүүд

Оролт

5
2 1 3 0 1

Гаралт

Possible
4 5 1 3 2

Оролт

9
0 2 3 4 1 1 0 2 2

Гаралт

Possible
7 5 2 1 6 8 3 4 9

Оролт

4
0 2 1 1

Гаралт

Impossible