要有光

$$ \text{Der mir zeigt wo ich bin}$$ $$_\texttt{告诉我身在何方} $$ $$\text{Divano}$$ $$_\texttt{神啊}$$ $$\text{Sei mein Licht} $$ $$_\texttt{做我的光}$$ $$\text{Ich sm chte mich dir schenken}$$ $$_\texttt{我愿将自己赐予与你}$$ $$\text{Noch vor dem Sonnenaufgang}$$ $$_\texttt{在晨曦来临之前}$$   那时正值春深，丛林里生灵闹哄哄地雀跃，享受着空气中升腾的灵气。   “嗖”的一声，一团银灰色的小东西突然从她眼前的地面划过，要不是腾起的尘土在阳光下悠闲地闪烁，她甚至怀疑是自己花了眼。   紧接着，又“嗖”的一声，这次她看清楚了，是一只雪白的幼龄狐妖，“还……有点可爱。”   “真走运，捉了这只，就可以交差啦。”她，虽年少却赫赫有名的除妖师，绫，急忙跟了上去。

万物有灵，法术亦是如此。任何法术都等价为一段**仅包括大小写字母**的字符串 $S=s_1s_2\dots s_n$，现规定如下几种法术记号： - **元素**。即字符串中的每个字符。在本题中，元素仅为大小写字母。 - **法术大小**。即字符串长度。记号为 $|S|$ 。 - **空法术**。大小为 $0$ 的法术为空法术。 - **等法术**。对于法术 $S,T$ 。当且仅当 $|S|=|T|,\forall i \leq |S| , s_i = t_i$ 时，称 $S$ 与 $T$ 为等法术，记为 $S=T$ 。 - **逆法术**。设现有法术 $S=s_1s_2\dots s_n$，称法术 $T$ 是 $S$ 的逆法术，当且仅当 $|S|=|T|$ 且 $\forall i \leq |S| , s_i=t_{n-i+1}$。本题将 $T$ 记作 $S_r$。 - **逆法术对**。称两法术 $S$，$T$ 构成逆法术对 $(S,T)$，当且仅当 $T=S_r$。 - **归法术**。设现有法术 $S$，称 $S$ 为归法术当且仅当 $S$ 对应的字符串为**回文串**。特别地，**空法术被视作归法术**。 - **子法术**。设现有法术 $S$ ，则对于 $1\le i\le j\le |S|$ ，称 $T=s_is_{i+1}\dots s_j$ 为 $S$ 的子法术，并规定子法术的记号 $S[i,j]$ 。当 $i>j$ 时，$S[i,j]$ 为空法术。 --- 现在，绫有一个法术源 $S_0$, 而她已经凝练出了一个初始的法术 $S=S_0$。对于每种妖魔，都有一个法术弱点 $T$。绫的法术性火，而火系法术又以淬光之术为上等。所以绫想要练习淬光之术。只要绫通过以下淬光法术变换使 $S=T$，就能轻易击败妖魔： - **光归**。对于**任意非空法术** $S$，保留其**最大归法术后缀**。若$|S|=n$即取一个最小的 $i \in [1,n]$ 使得 $S[i+1,n]$ 为归法术，并令 $S \leftarrow T$。**允许 $T$ 为空法术**。消耗时间 $A$。 - **光辉**。对于**归法术** $S$，在 $S_0$ 中寻找一个**子归法术** $T$，满足 $S$ 为 $T$ 的**最大归法术后缀**（其定义见 "光归" ），并令 $S\leftarrow T$。**空法术**被认为是**任何法术的后缀**。消耗时间 $B$。 - **光隐**。对于**非空归法术** $S$，$|S|=n$ 删去其长度相等且长度**不大于 $k$ **的**前缀与后缀**。即取一个 $i\in[1,\min\{k,\lfloor\frac{n-1}2\rfloor\}]$，使 $T=S[1+i,n-i]$，并令 $S\leftarrow T$。特别地，$T$ **不可以为空法术**，消耗时间 $C$。 - **光腾**。对于**非空归法术** $S,|S|=n$，在其左右加上一对逆法术对。即取一逆法术对 $(P,Q)$，设 $|P|=|Q|=l$，使 $T=p_1p_2\dots p_ls_1s_2\dots s_nq_1q_2\dots q_l$，且 $T$ **须为 $S_{0}$ 的子法术** ，并令 $S\leftarrow T$。消耗时间 $D$。 - **光弋**。对于**任意非空法术** $S,|S|=n$ ，在其前端加入任意元素。即取一个元素 $a$，使 $T=as_1s_2\dots s_n$，并令 $S\leftarrow T$，消耗时间 $E$。光弋变换玄妙莫测，绫还没有熟练掌握此法术变换。所以**在使用此变换之后，无法再使用其它类型的法术变换**。 现在绫想知道，对于不同妖魔的法术弱点 $T$，自己至少要消耗多少时间进行如上法术变换使 $S=T$。**每组询问间互不干扰**。

第一行输入一个**仅包含大小写字母**的字符串，表示绫的法术源 $S_0$。由题意，初始法术 $S=S_0$。 第二行输入一个正整数 $k$，表示**光隐**变换所允许删去前缀后缀的最长长度。 第三行输入五个正整数 $A,B,C,D,E$，表示每种法术变换的消耗时间。 第四行一个正整数 $q$，表示询问组数。 接下来 $q$ 行，每行包含两个正整数 $l,r$，表示一种妖魔的法术弱点为 $T=S_0[l,r]$。

对于每个询问，输出一行一个整数，表示第 $i$ 个询问的答案。

ababa
2
3 2 4 2 1
3
1 5
2 3
1 3

0
5
3

aaaaaa
1
3 1 4 1 10
2
2 4
2 3

7
8

#### 样例解释 #1 对于第一个询问，因为 $T=\texttt{"ababa"}=S$，不需要操作。 对于第二个询问，$T=\texttt{"ba"}$，最优策略为先使用一次**光隐**，得到 $S'=\texttt{"a"}$；接着使用一次**光弋**，在 $S'$ 前添加元素 $\texttt{'b'}$ 得到 $S''=\texttt{"ba"}=T$，耗时 $4+1=5$。 对于第三个询问，$T=\texttt{"aba"}$，最优策略为使用一次**光归**，得到 $S'=\texttt{"aba"}=T$。耗时 $3$。 ------------ #### 数据范围 对于不同的测试点，我们约定数据规模如下: | 测试点编号 | $\left\vert S \right\vert,\left\vert T \right\vert \le$ | $q\le$ | 特殊限制 | |:-:|:-:|:-:|:-:| | $1 \sim 5$ | $10^3$ | $10^3$ | 无 | | $6 \sim 9$ | $10^5$ | $10^5$ | 初始法术只有一种元素 | | $10 \sim 20$ | $10^5$ | $10^5$ | 无 | 对于 $100\%$ 的数据，$1 \le q,|S| \leq 10^5$，$1 \leq A,B,C,D,E \leq 10^9$，$1 \leq l \leq r \leq |S|$，$1 \leq k \leq 5$。 ------------ ### 题目背景 ( 续 )   这边，绫还在摸索着变换法术，却感觉腰间的令牌被抓了一下。“喂？！”   只见一个披头散发的少女正半跪着扒在她的腰间，左手还提着银灰色毛发的小兔子的一对耳朵，“你……是刚才那只狐狸？”绫尴尬地收回法术，不自觉地伸出手揉了揉少女头顶雪白的兽耳，心想着这只狐狸精得有多傻。“我可是除妖师哟，你不怕吗？”   “……绫？”少女并没有理会绫的话，只是努力地认出了令牌上刻着的名字。   绫好奇的目光撞上了少女璀璨的碧绿双眸，又不经意间扫过小巧的鼻梁，玲珑的小嘴，白皙的脖子，但再随着如凝的肌肤滑下……   一直被视作男儿的绫哪见过这般风景，只觉得自己大脑当了机，还隐约嗅到出自鼻腔的铁锈味儿，身体便向后靠倒在一棵树干上，连忙用双手捂住滚烫的脸颊。   “绫？绫？你怎么啦？！”少女心急地凑上去，绫吓得下意识往后退，却忘记身后是一棵粗壮的树干。“欸，绫手上的，是血吗……”双眼紧闭的绫听得出来少女像是被吓到了，看来还是一只没开过荤的狐狸精呢。   “绫……你没事吧……”少女分明带着哭腔，小心翼翼地学着自己还是小狐狸的时候妈妈照顾自己的方式，在绫的身上东摸西摸。   “我，我没事……”绫已经不敢想象究竟是哪些部位在触碰自己的皮肤了，“你……你先变回狐狸……快！”绫当然想把少女推开，却又怎么敢伸出手触碰少女呢？   少女闻言，一怔，但还是乖乖变回了一只狐狸，还不忘叼起几欲逃走的兔子。   绫赶忙收拾了自己的窘相，惊恐地扶着树干，确认自己的人身安全后，轻轻捏住小狐狸的后颈，提起在地上的两小只。   “以后不许再胡乱变成人形了，听到没有！”绫后怕地警告着小狐狸，却见右手的小狐狸直勾勾地盯着左手的小兔子，而左手的小兔子好像想钻进自己的手心里，哪有听她的话呀……   “哎，算了……”绫把小狐狸放在肩头，把似乎吓晕的小兔子递给她，“一会儿再吃哦。”（雨兔兔：我好难qwq。）   “就算……捡了一只宠物吧。”绫心里想着。   （未完待续www……）