P6396 Let There Be Light.

$$ \text{Der mir zeigt wo ich bin}$$ $$_\texttt{Tell me where I am} $$ $$\text{Divano}$$ $$_\texttt{God}$$ $$\text{Sei mein Licht} $$ $$_\texttt{Be my light}$$ $$\text{Ich sm chte mich dir schenken}$$ $$_\texttt{I am willing to give myself to you}$$ $$\text{Noch vor dem Sonnenaufgang}$$ $$_\texttt{Before the sunrise arrives}$$   It was late spring. In the jungle, all kinds of creatures were chirping and jumping around, enjoying the rising spiritual energy in the air.   With a “whoosh”, a small silver-gray thing suddenly streaked across the ground in front of her eyes. If not for the dust it kicked up lazily glittering in the sunlight, she would have doubted her own eyes.   Right after that, another “whoosh”. This time she saw it clearly: it was a snow-white young fox spirit. “It’s... kind of cute.”   “What luck. If I catch this one, I can report back.” She, a young yet already famous demon exorcist, Ling, hurriedly chased after it.

All things have spirits, and spells are no exception. Any spell is equivalent to a string $S=s_1s_2\dots s_n$ that **contains only uppercase and lowercase letters**. The following spell notations are defined: - **Element**. Each character in the string. In this problem, elements are only uppercase and lowercase letters. - **Spell size**. The string length, denoted as $|S|$. - **Empty spell**. A spell of size $0$ is an empty spell. - **Equal spells**. For spells $S,T$, if and only if $|S|=|T|$ and $\forall i \leq |S|, s_i=t_i$, then $S$ and $T$ are equal spells, denoted as $S=T$. - **Reverse spell**. Given a spell $S=s_1s_2\dots s_n$, a spell $T$ is the reverse spell of $S$ if and only if $|S|=|T|$ and $\forall i \leq |S|, s_i=t_{n-i+1}$. In this problem, $T$ is denoted as $S_r$. - **Reverse spell pair**. Two spells $S$ and $T$ form a reverse spell pair $(S,T)$ if and only if $T=S_r$. - **Palindromic spell**. Given a spell $S$, $S$ is called a palindromic spell if and only if its string is a **palindrome**. In particular, **the empty spell is considered a palindromic spell**. - **Substring spell**. Given a spell $S$, for $1\le i\le j\le |S|$, $T=s_is_{i+1}\dots s_j$ is called a substring spell of $S$, and is denoted as $S[i,j]$. When $i>j$, $S[i,j]$ is the empty spell. --- Now, Ling has a spell source $S_0$, and she has already refined an initial spell $S=S_0$. For each kind of demon, there is a spell weakness $T$. Ling’s spell attribute is fire, and among fire spells, the “tempering light” technique is the best. So Ling wants to practice this technique. As long as Ling uses the following spell transformations to make $S=T$, she can easily defeat the demon: - **Light Return**. For **any non-empty spell** $S$, keep its **largest palindromic suffix**. If $|S|=n$, choose the smallest $i \in [1,n]$ such that $S[i+1,n]$ is a palindromic spell, and let $S \leftarrow T$. **$T$ is allowed to be the empty spell**. Time cost $A$. - **Radiance**. For a **palindromic spell** $S$, find a **palindromic substring spell** $T$ in $S_0$ such that $S$ is the **largest palindromic suffix** of $T$ (as defined in “Light Return”), and set $S \leftarrow T$. The **empty spell** is considered a **suffix of any spell**. Time cost $B$. - **Light Concealment**. For a **non-empty palindromic spell** $S$ with $|S|=n$, delete a **prefix and suffix** of equal length, with length **no greater than $k$**. That is, choose an $i\in[1,\min\{k,\lfloor\frac{n-1}2\rfloor\}]$, let $T=S[1+i,n-i]$, and set $S\leftarrow T$. In particular, $T$ **cannot be the empty spell**. Time cost $C$. - **Light Ascend**. For a **non-empty palindromic spell** $S$ with $|S|=n$, add a reverse spell pair to its left and right. That is, choose a reverse spell pair $(P,Q)$ with $|P|=|Q|=l$, let $T=p_1p_2\dots p_ls_1s_2\dots s_nq_1q_2\dots q_l$, and require that $T$ **must be a substring spell of $S_{0}$**, then set $S\leftarrow T$. Time cost $D$. - **Light Dart**. For **any non-empty spell** $S$ with $|S|=n$, add any element to its front. That is, choose an element $a$, let $T=as_1s_2\dots s_n$, and set $S\leftarrow T$. Time cost $E$. The Light Dart transformation is mysterious and hard to master, so Ling has not fully learned it yet. Therefore, **after using this transformation, no other types of spell transformations can be used anymore**. Now Ling wants to know: for different demons’ spell weaknesses $T$, what is the minimum time she must spend to perform the above transformations to make $S=T$? **Each query is independent and does not affect the others**.

The first line contains a string consisting of **only uppercase and lowercase letters**, representing Ling’s spell source $S_0$. By the statement, the initial spell is $S=S_0$. The second line contains a positive integer $k$, representing the maximum allowed length of the prefix and suffix that can be deleted in the **Light Concealment** transformation. The third line contains five positive integers $A,B,C,D,E$, representing the time costs of each spell transformation. The fourth line contains a positive integer $q$, representing the number of queries. The next $q$ lines each contain two positive integers $l,r$, meaning a demon’s spell weakness is $T=S_0[l,r]$.

For each query, output one integer per line, representing the answer to the $i$-th query.

#### Sample Explanation #1 For the first query, since $T=\texttt{"ababa"}=S$, no operation is needed. For the second query, $T=\texttt{"ba"}$. The optimal strategy is to first use **Light Concealment** once to obtain $S'=\texttt{"a"}$; then use **Light Dart** once, adding the element $\texttt{'b'}$ to the front of $S'$ to get $S''=\texttt{"ba"}=T$. The total time cost is $4+1=5$. For the third query, $T=\texttt{"aba"}$. The optimal strategy is to use **Light Return** once to obtain $S'=\texttt{"aba"}=T$. The time cost is $3$. ------------ #### Constraints For different test points, the constraints are as follows: | Test Point ID | $\left\vert S \right\vert,\left\vert T \right\vert \le$ | $q\le$ | Special Constraints | |:-:|:-:|:-:|:-:| | $1 \sim 5$ | $10^3$ | $10^3$ | None | | $6 \sim 9$ | $10^5$ | $10^5$ | The initial spell has only one kind of element | | $10 \sim 20$ | $10^5$ | $10^5$ | None | For $100\%$ of the testdata, $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$. ------------ ### Background (continued)   Over here, Ling was still exploring spell transformations when she felt the token at her waist get tugged. “Hey?!”   She saw a messy-haired girl half-kneeling and clinging to her waist. In the girl’s left hand, she was holding a pair of ears of a small rabbit with silver-gray fur. “You... are you that fox from just now?” Ling awkwardly pulled back her spell, and without thinking, reached out to rub the snow-white animal ears on top of the girl’s head, wondering how foolish this fox spirit could be. “I’m a demon exorcist, you know. Aren’t you afraid?”   “... Ling?” The girl did not respond to Ling’s words, only trying hard to make out the name carved on the token.   Ling’s curious gaze met the girl’s bright emerald eyes, then unintentionally swept over her small nose bridge, delicate lips, fair neck, and then slid down along her smooth skin...   Ling had always been treated as a boy. How could she have seen such a scene? She felt her brain crash, and even faintly smelled the rusty scent from her nose. Her body leaned back against a tree trunk, and she quickly covered her burning cheeks with both hands.   “Ling? Ling? What’s wrong?!” The girl anxiously leaned closer. Ling subconsciously retreated in fright, but forgot there was a thick tree trunk behind her. “Eh, on Ling’s hand... is that blood...” With her eyes tightly shut, Ling could tell the girl sounded scared. Looks like she was still an inexperienced fox spirit.   “Ling... are you okay...” The girl clearly had a sobbing tone, and cautiously copied the way her mother used to care for her when she was still a little fox, touching Ling here and there.   “I, I’m fine...” Ling no longer dared to imagine which parts were touching her skin. “You... you change back into a fox... now!” Of course Ling wanted to push the girl away, but how could she dare reach out and touch her?   The girl froze when she heard that, but still obediently changed back into a fox, and did not forget to pick up the rabbit that was about to escape.   Ling quickly tidied up her embarrassment. In fear, she held onto the tree trunk, and after confirming her own safety, gently pinched the little fox by the back of the neck and lifted the two small creatures on the ground.   “From now on, you’re not allowed to randomly change into human form, got it!” Ling warned the little fox with lingering fear, but the little fox in her right hand stared straight at the little rabbit in her left hand, while the little rabbit seemed to want to burrow into her palm. It clearly was not listening to her at all...   “Sigh, forget it...” Ling put the little fox on her shoulder and handed the seemingly frightened-fainted little rabbit to her. “Eat it later.” (Yu Tutu: Life is so hard qwq.)   “Maybe... I just picked up a pet.” Ling thought to herself.   (To be continued www...) Translated by ChatGPT 5