Поликарпу дали ряд из плиток. На каждой плитке находится по одной строчной букве латинского алфавита. Вся последовательность из плиток образует строку \(s\).
Иными словами, вам задана строка \(s\), состоящая из строчных букв латинского алфавита.
Изначально Поликарп находится на первой плитке ряда и хочет попасть на последнюю, прыгая по плиткам. Прыжок от плитки \(i\) к плитке \(j\) имеет стоимость равную \(|index(s_i) - index(s_j)|\), где \(index(c)\) означает индекс буквы \(c\) в алфавите (например, \(index(\)'a'\()=1\), \(index(\)'b'\()=2\), ..., \(index(\)'z'\()=26\)).
Поликарп хочет добраться до \(n\)-й плитки за минимальную суммарную стоимость, но при этом сделать максимальное количество прыжков.
Иными словами, среди всех возможных способов добраться до последней плитки за минимальную суммарную стоимость, он выберет такой, в котором количество прыжков максимально.
Поликарп может посетить каждую плитку не более одного раза.
Поликарп просит вас помочь — выведите последовательность индексов строки \(s\), по которым он должен прыгать.
Выходные данные
Ответ на каждый набор входных данных состоит из двух строк.
В первой строке выведите два целых числа \(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|\)).
Если вариантов ответа несколько, выведите любой из них.
Примечание
В первом наборе входных данных примера искомый путь соответствует картинке:
В данном случае достигается минимальная возможная суммарная стоимость пути. Так как \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|