题目描述

有一天，Abwad决定和nbc鏖战字符串，比的是谁能更快地将一个“量子态的字符串”删除。“量子态的字符串”的每个字符都有一个删除难度$dif[i]$。“量子态的字符串”非常顽固，只能先分割成若干个子串，然后再通过以下两种方式删除： ① 假设子串的所有字符的删除难度之和为$x$，消耗$a×x^2+b$的时间可将子串扔进回收站。 ② 若子串中出现次数最多的字符出现的次数不少于$l$次且不多于$r$次，那么采用“量子态的py自动机”算法可以消耗$c×x+d$的时间将子串扔进回收站。 Abwad希望你求出删去每个前缀[$1,i]$的最少用时。

输入

第一行七个整数$n，a，b，c，d，l，r$，其中$n$表示字符串的长度。 第二行一行一个长度为$n$的字符串。 第三行一行$n$个整数，表示每个字符的删除难度$dif[i]$。

输出

$n$行，每行一个整数$ans$，表示删去前缀$[1,i]$最短的时间。

输入样例

5 1 3 1 5 1 1
abwad
1 1 1 1 1

输出样例

4
7
8
12
13

提示

【样例解释】 以前缀$[1,n]$为例，将串分为$a、bwad$两个子串，用方法①删去第一个子串，用方法②删去第二个子串，用时$1×1+3+1×4+5=13$ 【数据规模与约定】

测试点编号	n	特殊约定
1	n≤10	所有的字母都是a
2		所有的字母都是a或b
3
4
5	n≤2000	所有的字母都是a
6		所有的字母都是a或b
7		l=1,r=n
8
9
10
11	n≤100000	l=1,r=n
12
13
14
15		l>r
16
17
18
19
20

对于所有的数据，满足$n≤100000，1≤a,b,c,d≤233，1≤l,r≤n，0≤dif[i]≤50$,所有字符由小写字母组成。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。