小红的陡峭值（三）hard

题号：NC289519
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 本题为《C.小红的陡峭值（三）》的困难版本，两题的唯一区别在于本题的数据范围更大。

$\hspace{15pt}$ 小红定义一个字符串的陡峭值为：每两个相邻字符，Ascii 码差值的绝对值之和。例如， $\texttt{$ 的陡峭值是 $|\texttt{`c'}-\texttt{`b'}|+|\texttt{`a'}-\texttt{`c'}|=1 + 2 = 3$ 。
$\hspace{15pt}$ 现在小红拿到了一个长度为 $n$ ，仅由小写字母构成的字符串 $s$ 。她希望你求出这个字符串所有长度为 $k$ 的连续子串的陡峭值之和，你能帮帮她吗？

$\hspace{15pt}$ 连续子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

输入描述:

第一行输入两个正整数  代表字符串的长度、子串的长度。
第二行输入一个长度为 ，仅由小写字母组成的字符串 。

输出描述:

输出一个整数，代表所有长度为  的连续子串的陡峭值之和。

示例1

输入

复制

3 2
bca

输出

复制

说明

在这个样例中，全部长度为  的连续子串如下：
，陡峭值为 ；
，陡峭值为 。
因此，所有长度为  的连续子串的陡峭值之和为 。