• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

یک رشته به طول $n$ از حروف کوچک انگلیسی به نام $s$ داریم. می‌خواهیم در $n$ عملیات این رشته را خالی کنیم.

در هر عملیات حرفی را حذف می‌کنیم که رشته فعلی را به رشته الفبایی کوچک‌تری تبدیل کند. اگر چند حرف چنین کاری را انجام می‌دهد با سمت راست ترین حرف این کار را می‌کنیم.

جایگشتی از $1$ تا $n$ را ارائه دهید که باید عناصر را به آن ترتیب حذف کرد.

ورودی

در سطر اول ورودی، عدد صحیح و مثبت $t$ آمده که تعداد تست‌های آمده در ورودی را نشان می‌دهد.

$$1 \leq t \leq 100 , 000$$

در $t$ سطر بعدی ورودی، در هر سطر رشته $s$ که تنها شامل حروف کوچک انگلیسی است، آمده است.

$$1 \leq |s| \leq 100 , 000$$

تضمین می‌شود مجموع طول این $t$ رشته از $100 , 000$ بیشتر نشود.

خروجی

خروجی در یک سطر جایگشتی را که ترتیب حذف کردن آن در هر مرحله ما را به رشته الفبایی کمینه می‌رساند، چاپ می‌کنیم.

مثال

ورودی نمونه ۱

3
abc
cba
quera

خروجی نمونه ۱

3 2 1
1 2 3
2 1 4 3 5

تست اول.

$$abc \to ab \to a$$

بنابراین جایگشتی که باید به آن ترتیب حذف کنیم، $[3, 2, 1]$ است.

تست دوم.

$$cba \to ba\to a$$

بنابراین جایگشتی که باید به آن ترتیب حذف کنیم، $[1, 2, 3]$ است.

تست سوم.

$$quera \to qera \to era \to ea \to a$$

بنابراین جایگشتی که باید به آن ترتیب حذف کنیم، $[2, 1, 4, 3, 5]$ است.