พร้อมกับโชคชะตาที่บิดเบี้ยว Nadeko มีสตริง $s$ ซึ่งประกอบด้วยตัวอักษรพิมพ์เล็ก ความปรารถนาสูงสุดของเธอคือการสร้างสตริง $t$ ที่สอดคล้องกับเงื่อนไขต่อไปนี้:
- $t$ ไม่มี $s$ เป็นลำดับย่อย (subsequence)
- ทุกลำดับย่อยของ $s$ ที่ไม่ตรงกับ $s$ ทั้งหมด จะต้องปรากฏเป็นลำดับย่อยใน $t$
จงช่วยเธอหาสตริง $t$ ที่มีความยาวน้อยที่สุดที่เป็นไปได้ หากมีสตริงดังกล่าวหลายแบบ คุณสามารถแสดงผลสตริงใดก็ได้
ข้อมูลนำเข้า
บรรทัดเดียวของข้อมูลนำเข้าประกอบด้วยสตริง $s$ ($2 \le |s| \le 10^6$) — สตริงของ Nadeko รับประกันว่า $s$ ประกอบด้วยตัวอักษรพิมพ์เล็กเท่านั้น
ข้อมูลส่งออก
ในบรรทัดเดียว ให้แสดงผลสตริง $t$ ใดก็ได้ที่มีความยาวน้อยที่สุดและสอดคล้องกับเงื่อนไขของโจทย์
ตัวอย่าง
ข้อมูลนำเข้า 1
aaaa
ข้อมูลส่งออก 1
aaa
ข้อมูลนำเข้า 2
bba
ข้อมูลส่งออก 2
bab
หมายเหตุ
ในตัวอย่างที่สอง สตริง bab มี bb, ba, a, b เป็นลำดับย่อย แต่ไม่มี bba และเห็นได้ชัดว่าเป็นไปไม่ได้ที่จะสร้างลำดับที่ถูกต้องที่มีความยาว $2$ ดังนั้น bab จึงเป็นคำตอบที่เป็นไปได้