Background

Problem Description

Since you cannot swap bodies, you need to solve a problem.

Let $\operatorname{occ}(u,v)$ be the number of occurrences of string $\boldsymbol v$ in string $\boldsymbol u$. Let $t[l,r]$ denote the substring of string $t$ consisting of the $l$-th to the $r$-th characters.

Given a sequence of strings $(s_1,\dots,s_n)$, a sequence of positive integers $(a_1,\dots,a_n)$, and a string $t$, there are $q$ queries. Each query has four parameters $l_1,r_1,l_2,r_2$. Compute:

$$\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)$$

For the subtask with $o=1$, you need to support online queries.

Input Format

There are $n+q+3$ lines in total.

• The first line contains six positive integers $\text{sid},n,q,o,L,R$. Here $\text{sid}$ indicates the Subtask ID of the test point. In particular, for the sample, $\text{sid}=0$. The meanings of the other values are as described in the statement.

• Lines $2$ to $n+1$: $n$ strings $(s_1,\dots,s_n)$.

• Line $n+2$: a string $t$.

• Line $n+3$: $n$ positive integers $(a_1,\dots,a_n)$.

• Lines $n+4$ to $n+q+3$: each line contains four positive integers $L_1,R_1,L_2,R_2$, describing a query.

For the $i$-th query, let the answer to the $(i-1)$-th query be $\text{lst}$ (if $i=1$, then $\text{lst}=0$). Then $l_1,l_2,r_1,r_2$ are computed as:

• $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$.

If $l_1>r_1$, swap $l_1,r_1$. Do the same for $l_2,r_2$.

When $L\ne -1$, you need to change all $l_1$ to $L$; when $R\ne -1$, you need to change all $r_1$ to $R$ (if the initial $l_1>r_1$, this operation is performed after swapping $l_1,r_1$).

Output Format

There are $q$ lines. The $i$-th line gives the result of the $i$-th query in the formal statement.

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

Hint

Sample Explanation #1

Take the last query as an example: $t[7,12] = \texttt{ababaa}$. The needed $\text{occ}$ values are:

• $\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$.

So the answer is $114\times 1+51\times 1+41\times 0 + 41\times 1 + 41\times 1 = 247$.

Constraints

This problem uses bundled testdata.

Let $m=\sum\limits_{i=1}^n\lvert s_i\rvert$.

$\text{sid}=$	$n,m,\lvert t\rvert\le$	$q\le$	$a_i\le$	$o=$	Special Properties	Score	Subtask Dependencies
$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$

Special Property $\text{A}$: both $s_i$ and $t$ are a.

Special Property $\text{B}$: $L=1$.

Special Property $\text{C}$: $R=n$.

For $100\%$ of the data: $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$, and $1\le L,R\le n$ or $L,R=-1$.

Translated by ChatGPT 5