Поликарп бол сошиал сүлжээнд цагийг үрэх маш дуртай нэгэн. Түүний дуртай сүлжээний чатны жагсаалт хийгдсэн ба найзруугаа мэссэж илгээсэн үед уг найзыг илэрхийлэх чат нь хуудасны хамгийн дээр гарч ирдэг. Бусад чатны харьцангуй байрлал өөрчлөгдөхгүй. Хэрвээ уг найзынх нь чат өмнө нь ерөөсөө байгаагүй бол шинэ чат нь жагсаалтын хамгийн эхэнд хялбархан гарч ирнэ.

Жагсаалт анх хоосон байсан гэж үзэх ба Поликарпусын мэссэжүүдийн дараалал нь чатны жагсаалтыг үүсгэх буюу бүх мэссэж явсны дараа. Ямар ч найз нь Поликарпусруу мэссэж бичээгүй гэж үз.

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 200 000$) байх ба Поликарпусын мэссэжүүдийн тоо. Дараагийн $n$ мөрөнд мэссэжүүдийг явуулсан дарааллаар хүлээн авагчид байна. Хүлээн авагч бүрийн нэр нь $10$-с ихгүй Англи цагаан толгойн жижиг үсгүүдээс бүрдсэн хоосон биш дараалал байна.

Гаралт

Поликарпын ярилцсан бүх хүмүүсийг жагсаалтад буй чатны дарааллаар нь дээрээс доош нь дараалалтай хэвлэ.

Эхний жишээн ээр Поликарпус эхлээд "$alex$" нэртэй найзруугаа бичсэн ба жагсаалт дараах байдлаар харагдана:

1. $alex$

Тэгээд Поликарпус "$ivan$" нэртэй найзруугаа бичсэн ба жагсаалт дараах байдлаар харагдана:

1. $ivan$
2. $alex$

Поликарпус гурав дахь мэссэжээ "$roman$" нэртэй найзруугаа бичсэн ба жагсаалт дараах байдлаар харагдана:

1. $roman$
2. $ivan$
3. $alex$

Поликарпус дөрөв дахь мэссэжээ "$ivan$" нэртэй найзруугаа бичсэн ба энэ найзруугаа өмнө нь бичсэн учраас чатны жагсаалт доорх байдлаар өөрчлөгдөнө:

1. $ivan$
2. $roman$
3. $alex$