题目背景

$$\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$		无
$6 \sim 9$	$10^5$		初始法术只有一种元素
$10 \sim 20$			无

对于 $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……）