C. Прыжки по плиткам
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарпу дали ряд из плиток. На каждой плитке находится по одной строчной букве латинского алфавита. Вся последовательность из плиток образует строку $$$s$$$.

Иными словами, вам задана строка $$$s$$$, состоящая из строчных букв латинского алфавита.

Изначально Поликарп находится на первой плитке ряда и хочет попасть на последнюю, прыгая по плиткам. Прыжок от плитки $$$i$$$ к плитке $$$j$$$ имеет стоимость равную $$$|index(s_i) - index(s_j)|$$$, где $$$index(c)$$$ означает индекс буквы $$$c$$$ в алфавите (например, $$$index($$$'a'$$$)=1$$$, $$$index($$$'b'$$$)=2$$$, ..., $$$index($$$'z'$$$)=26$$$).

Поликарп хочет добраться до $$$n$$$-й плитки за минимальную суммарную стоимость, но при этом сделать максимальное количество прыжков.

Иными словами, среди всех возможных способов добраться до последней плитки за минимальную суммарную стоимость, он выберет такой, в котором количество прыжков максимально.

Поликарп может посетить каждую плитку не более одного раза.

Поликарп просит вас помочь — выведите последовательность индексов строки $$$s$$$, по которым он должен прыгать.

Входные данные

Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Каждый набор данных задаётся строкой $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$), где $$$|s|$$$ — длина строки $$$s$$$. Строка $$$s$$$ состоит из строчных букв латинского алфавита.

Гарантируется, что сумма длин строк $$$s$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Ответ на каждый набор входных данных состоит из двух строк.

В первой строке выведите два целых числа $$$cost$$$, $$$m$$$, где $$$cost$$$ — минимальная суммарная стоимость пути, а $$$m$$$ — максимальное количество плиток, которые Поликарп может посетить, чтобы добраться до $$$n$$$-й плитки за минимальную суммарную стоимость $$$cost$$$ (т.е. количество прыжков равно $$$m-1$$$).

В следующей строке выведите $$$m$$$ различных чисел $$$j_1, j_2, \dots, j_m$$$ ($$$1 \le j_i \le |s|$$$) — последовательность индексов плиток по которым будет прыгать Поликарп. Первым числом последовательности должна быть $$$1$$$ (то есть $$$j_1=1$$$), а последним числом должно быть значение $$$|s|$$$ (то есть $$$j_m=|s|$$$).

Если вариантов ответа несколько, выведите любой из них.

Пример
Входные данные
6
logic
codeforces
bca
aaaaaaaaaaa
adbaadabad
to
Выходные данные
9 4
1 4 3 5
16 10
1 8 3 4 9 5 2 6 7 10
1 2
1 3
0 11
1 8 10 4 3 5 7 2 9 6 11
3 10
1 9 5 4 7 3 8 6 2 10
5 2
1 2
Примечание

В первом наборе входных данных примера искомый путь соответствует картинке:

В данном случае достигается минимальная возможная суммарная стоимость пути. Так как $$$index($$$'l'$$$)=12$$$, $$$index($$$'o'$$$)=15$$$, $$$index($$$'g'$$$)=7$$$, $$$index($$$'i'$$$)=9$$$, $$$index($$$'c'$$$)=3$$$, то суммарная стоимость пути равна $$$|12-9|+|9-7|+|7-3|=3+2+4=9$$$.