#577. 【ULR #1】打击复读

$s$ 的“复读程度”定义为所有子串复读程度的和，即：

$$\sum\limits_{i=1}^{|S|}\sum\limits_{j=i}^{|S|}w(s[i,j]).$$

样例一

input

5 0
ATATA
1 2 3 4 5
1 2 3 4 5



output

550



样例二

input

10 5
ACGTAGCGAG
3 2 7 8 0 8 0 1 9 9
8 1 1 9 8 9 8 8 8 9
2 2
3 6
10 9
10 2
5 3



output

5427
5427
5260
5260
4504
4927



限制与约定

1 $100$ $10^5$ $100$ $10$
2 $10^5$ $0$ 数据随机生成 $20$
3 $30$
4 $1.5\times 10^5$ $2^{64}-1$ $5\times 10^5$ $20$
5 $5\times 10^5$ $20$