E. Пишущая машинка из будущего
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даню назначили главным редактором школьной стенгазеты в ретро-стиле. Для аутентичности Даня решил набирать ее на пишущей машинке. Старую пишущую машинку Дане найти не удалось, поэтому он заказал в онлайн-магазине современную программируемую пишущую машинку.

Клавиатура машинки представляет собой $$$m$$$ клавиш, расположенных в один ряд и пронумерованных от $$$1$$$ до $$$m$$$. Дане для очередного выпуска стенгазеты нужно набрать текст $$$s = s_1 s_2 \ldots s_n$$$, состоящий из первых $$$m$$$ строчных букв английского алфавита. Машинку можно программировать под свой текст. Для этого каждую из $$$m$$$ букв нужно назначить ровно одной клавише, причём разные буквы должны находиться на разных клавишах. Если две последовательные буквы текста расположены на клавишах с номерами $$$x$$$ и $$$y$$$, то время перехода между ними равно $$$|x - y|$$$. Время набора первой буквы не учитывается. Таким образом, если символ $$$c$$$ расположен на позиции $$$p_c$$$, то полное время набора текста равно $$$$$$ \sum_{i=1}^{n-1} \left|p_{s_i} - p_{s_{i+1}}\right|. $$$$$$

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

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

В первой строке входных данных находятся целые числа $$$n$$$ и $$$m$$$ — длина текста и количество букв в алфавите ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 20$$$).

Во второй строке находится строка $$$s$$$ длины $$$n$$$, состоящая из первых $$$m$$$ строчных букв английского алфавита.

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

Выведите два целых числа — минимальное и максимальное возможное время набора текста.

Примеры
Входные данные
7 3
abacaba
Выходные данные
6 10
Входные данные
5 1
aaaaa
Выходные данные
0 0
Примечание

В первом примере всего существует $$$6$$$ вариантов назначения позиций для букв «a», «b» и «c»:

  • Если $$$p_{\text{a}} = 1$$$, $$$p_{\text{b}} = 2$$$, $$$p_{\text{c}} = 3$$$: $$$|1 - 2| + |2 - 1| + |1 - 3| + |3 - 1| + |1 - 2| + |2 - 1| = 1 + 1 + 2 + 2 + 1 + 1 = 8$$$.
  • Если $$$p_{\text{a}} = 1$$$, $$$p_{\text{b}} = 3$$$, $$$p_{\text{c}} = 2$$$: $$$|1 - 3| + |3 - 1| + |1 - 2| + |2 - 1| + |1 - 3| + |3 - 1| = 2 + 2 + 1 + 1 + 2 + 2 = 10$$$.
  • Если $$$p_{\text{a}} = 2$$$, $$$p_{\text{b}} = 1$$$, $$$p_{\text{c}} = 3$$$: $$$|2 - 1| + |1 - 2| + |2 - 3| + |3 - 2| + |2 - 1| + |1 - 2| = 1 + 1 + 1 + 1 + 1 + 1 = 6$$$.
  • Если $$$p_{\text{a}} = 2$$$, $$$p_{\text{b}} = 3$$$, $$$p_{\text{c}} = 1$$$: $$$|2 - 3| + |3 - 2| + |2 - 1| + |1 - 2| + |2 - 3| + |3 - 2| = 1 + 1 + 1 + 1 + 1 + 1 = 6$$$.
  • Если $$$p_{\text{a}} = 3$$$, $$$p_{\text{b}} = 1$$$, $$$p_{\text{c}} = 2$$$: $$$|3 - 1| + |1 - 3| + |3 - 2| + |2 - 3| + |3 - 1| + |1 - 3| = 2 + 2 + 1 + 1 + 2 + 2 = 10$$$.
  • Если $$$p_{\text{a}} = 3$$$, $$$p_{\text{b}} = 2$$$, $$$p_{\text{c}} = 1$$$: $$$|3 - 2| + |2 - 3| + |3 - 1| + |1 - 3| + |3 - 2| + |2 - 3| = 1 + 1 + 2 + 2 + 1 + 1 = 8$$$.

Минимальное время набора среди всех раскладок равно $$$6$$$, а максимальное равно $$$10$$$.

Во втором примере существует единственная раскладка $$$p_{\text{a}} = 1$$$ с временем набора $$$0$$$.