1488: Танець рядка


Submit solution


Points:30
Time limit:2.0s
Memory limit:500M
Author:

Problem type

Дано рядок S = s_1 , s_2 , ...s_n . Вам потрiбно зробити з ним один танцювальний рух такий, щоб вiн став лексикографiчно найменшим. Пiд танцювальним рухом будемо розумiти рiвно один розворот пiдрядка в рядку S. Формально кажучи, необхiдно вибрати пару iндексiв x, y (1 <= x <= y <= n), а потiм змiнити порядок символiв з iндексами вiд x до y включно на протилежний. Тобто пiдрядок s_x , s_(x+1) ...s_y замiнюється на s_y , s_(y−1) , ...s_x .

Ваша мета — отримати лексикографiчно найменший рядок iз можливих.

Формат вхідних даних

Перший рядок мiстить кiлькiсть T (1 <= T <= 10^5 ) наборiв вхiдних даних. Кожний набiр вхiдних даних розташований в окремому рядку вхiдного потоку i складається з одного непустого рядка S. Кожен символ рядку S — мала буква англiйського алфавiта (вiд a до z). Сума довжин рядкiв S по всiм наборам вхiдних даних не перевищує 10^6 .

Формат вихідних даних

Для кожного набору вхiдних даних виведiть один рядок з двома цiлими числами x i y. Якщо iснує декiлька оптимальних варiантiв вiдповiдей, виведiть будь-який iз них.

Приклад вхідних даних

1
abacaba

Приклад вихідних даних

2 7

Comments

There are no comments at the moment.