题目背景

题目描述

由于你不会交换身体，所以需要解决一道题目。

记 $\operatorname{occ}(u,v)$ 为字符串 $\boldsymbol v$ 在字符串 $\boldsymbol u$ 中的出现次数。并记 $t[l,r]$ 表示字符串 $t$ 由第 $l$ 到第 $r$ 个字符组成的子串。

给定字符串序列 $(s_1,\dots,s_n)$ 和正整数序列 $(a_1,\dots,a_n)$ 以及字符串 $t$，有 $q$ 次询问，每次询问有四个参数 $l_1,r_1,l_2,r_2$，求：

$$\sum\limits_{i=l_1}^{r_1}\left(\operatorname{occ}(s_i,t[l_2,r_2])\times\min\limits_{j=l_1}^{i}a_j\right) $$

对于 $o=1$ 的子任务，你需要支持在线询问。

输入格式

共 $n+q+3$ 行。

• 第一行六个正整数 $\text{sid},n,q,o,L,R$。其中 $\text{sid}$ 表示测试点所在 Subtask 编号。特别地，对于样例，$\text{sid}=0$。其余量意义如题所示。

• 第 $2\sim n+1$ 行 $n$ 个字符串 $(s_1,\dots,s_n)$。

• 第 $n+2$ 行一个字符串 $t$。

• 第 $n+3$ 行 $n$ 个正整数 $(a_1,\dots,a_n)$。

• 第 $n+4\sim n+q+3$ 行每行四个正整数 $L_1,R_1,L_2,R_2$，描述一个询问。

对于第 $i$ 个询问，记第 $i-1$ 个询问的答案为 $\text{lst}$（若 $i=1$ 则 $\text{lst}=0$），则 $l_1,l_2,r_1,r_2$ 为：

• $l_1=(L_1+o\times\text{lst}-1)\bmod n+1$。
• $r_1=(R_1+o\times\text{lst}-1)\bmod n+1$。
• $l_2=(L_2+o\times\text{lst}-1)\bmod |t|+1$。
• $r_2=(R_2+o\times\text{lst}-1)\bmod |t|+1$。

若 $l_1>r_1$，则交换 $l_1,r_1$。对于 $l_2,r_2$ 同理。

当 $L$ 不为 $-1$ 时，你需要将所有 $l_1$ 改为 $L$；当 $R$ 不为 $-1$ 时，你需要将所有 $r_1$ 改为 $R$（若初始的 $l_1>r_1$，本操作在交换 $l_1,r_1$ 之后进行）。

输出格式

共 $q$ 行，第 $i$ 行表示第 $i$ 场梦境的⌈结⌋，即形式化题意中第 $i$ 个询问的答案。

0 6 6 0 -1 -1
aaaaabababaabab
baaabaabababaabba
aabababbaabaabab
abaababababaabaaaba
baabababababaaababa
bababaababababaabab
baababababaaaaababbbaaababaabababaabb
114 51 41 91 98 10
1 6 16 18
2 5 11 12
3 4 1 2
1 5 4 6
3 5 3 4
1 5 7 12

955
614
492
895
820
247

0 6 6 1 -1 -1
aaaaabababaabab
baaabaabababaabba
aabababbaabaabab
abaababababaabaaaba
baabababababaaababa
bababaababababaabab
baababababaaaaababbbaaababaabababaabb
114 51 41 91 98 10
1 6 16 18
2 5 11 12
3 4 1 2
1 5 4 6
3 5 3 4
1 5 7 12

955
900
287
1344
820
41

0 6 6 1 1 -1
aaaaabababaabab
baaabaabababaabba
aabababbaabaabab
abaababababaabaaaba
baabababababaaababa
bababaababababaabab
baababababaaaaababbbaaababaabababaabb
114 51 41 91 98 10
1 6 16 18
2 5 11 12
3 4 1 2
1 5 4 6
3 5 3 4
1 5 7 12

955
1662
1358
824
1184
165

0 6 6 1 -1 6
aaaaabababaabab
baaabaabababaabba
aabababbaabaabab
abaababababaabaaaba
baabababababaaababa
bababaababababaabab
baababababaaaaababbbaaababaabababaabb
114 51 41 91 98 10
1 6 16 18
2 5 11 12
3 4 1 2
1 5 4 6
3 5 3 4
1 5 7 12

955
900
430
348
41
0

提示

【样例解释 #1】

以最后一组询问为例，$t[7,12] = \texttt{ababaa}$。给出要用的 $\text{occ}$ 数据：

• $\text{occ}(s_1,t[7,12])=\text{occ}(s_2,t[7,12])=\text{occ}(s_4,t[7,12])=\text{occ}(s_5,t[7,12])=1$。

• $\text{occ}(s_3,t[7,12])=0$。

答案为 $114\times 1+51\times 1+41\times 0 + 41\times 1 + 41\times 1 = 247$。

【数据范围】

本题采用捆绑测试。

记 $m=\sum\limits_{i=1}^n\lvert s_i\rvert$。

$\text{sid}=$	$n,m,\lvert t\rvert\le$	$q\le$	$a_i\le$	$o=$	特殊性质	分值	子任务依赖
$1$	$100$		$10^9$	$0$		$5$
$2$	$2\times 10^5$			$1$	$\text{A}$	$10$
$3$			$1$			$15$
$4$	$10^4$		$10^9$	$0$			$1$
$5$	$2\times 10^5$					$20$	$4$
$6$				$1$	$\text{B}$	$5$
$7$					$\text{C}$	$20$
$8$						$10$	$2,3,5,6,7$

特殊性质 $\text{A}$：$s_i$ 与 $t$ 均为 a。

特殊性质 $\text{B}$：$L=1$。

特殊性质 $\text{C}$：$R=n$。

对于 $100\%$ 的数据，$1\le n,m,\lvert t\rvert\le 2\times 10^5$，$1\le q\le 2\times 10^5$，$1\le a_i\le 10^9$，$o\in\{0,1\}$，$0\le \text{sid}\le 8$，$1\le L,R\le n$ 或 $L,R=-1$。