回文串指的是正着读和反着读一样的串，比如 "abcba" 和 “ddd” 都是回文串，但 "cyyakwzk" 不是。
ddd 现在获得了一个长度为 的、由小写字母组成的字符串 。wzk 给了他 个转换器，第 个转换器拥有参数 ，表示 ddd 可以用这个转换器将任意位置的字母 以 的代价变成 。同时 cyy 还给了他一个超级转换器，表示他可以以 的代价，将任意一个字母变为任意另外一个字母。
ddd 对回文串情有独钟，所以他给出了 个独立的询问，第 个询问表示：如果想把 中，以 开始的、长度为 的子串变为回文串，需要的最小代价是多少。ddd 认为回答这个问题太麻烦了，想委托你告诉他这些询问的答案之和是多少。