إلى جانب قدرها المتشابك، تمتلك Nadeko سلسلة نصية $s$ تتكون من أحرف صغيرة. أمنيتها القصوى هي بناء سلسلة نصية $t$ تتحقق فيها الشروط التالية:
- لا تحتوي $t$ على $s$ كمتتالية جزئية.
- كل متتالية جزئية من $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 هي إجابة ممكنة.