E. Future Typewriter
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Danya was appointed the chief editor of the school wall newspaper in a retro style. For authenticity, Danya decided to type it on a typewriter. He could not find an old typewriter, so he ordered a modern programmable typewriter from an online store.

The keyboard of the typewriter consists of $$$m$$$ keys arranged in a row and numbered from $$$1$$$ to $$$m$$$. For the next issue of the wall newspaper, Danya needs to type a text $$$s = s_1 s_2 \ldots s_n$$$, consisting of the first $$$m$$$ lowercase English letters. The typewriter can be programmed for his text. To do this, each of the $$$m$$$ letters must be assigned to exactly one key, and different letters must be placed on different keys. If two consecutive letters of the text are located on keys with numbers $$$x$$$ and $$$y$$$, then the transition time between them is $$$|x - y|$$$. The time to type the first letter is not counted. Thus, if the character $$$c$$$ is located at position $$$p_c$$$, then the total time to type the text is $$$$$$ \sum_{i=1}^{n-1} \left|p_{s_i} - p_{s_{i+1}}\right|. $$$$$$

Danya noticed that the typing time depends on how he assigned the letters on the typewriter. He would like to compute the minimum and maximum possible typing time among all possible keyboard layouts. Danya got too carried away with journalism, so he does not have time to solve this problem himself; help him do it.

Input

The first line of the input contains integers $$$n$$$ and $$$m$$$ — the length of the text and the number of letters in the alphabet ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 20$$$).

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of the first $$$m$$$ lowercase English letters.

Output

Print two integers — the minimum and maximum possible typing time.

Examples
Input
7 3
abacaba
Output
6 10
Input
5 1
aaaaa
Output
0 0
Note

In the first example, there are exactly $$$6$$$ possible assignments of positions for the letters «a», «b», and «c»:

  • If $$$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$$$.
  • If $$$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$$$.
  • If $$$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$$$.
  • If $$$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$$$.
  • If $$$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$$$.
  • If $$$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$$$.

The minimum typing time among all layouts is $$$6$$$, and the maximum is $$$10$$$.

In the second example, there is only one layout, $$$p_{\text{a}} = 1$$$, with typing time $$$0$$$.