D-Longest Common Prefix_2026年ICPC新疆维吾尔自治区大学生程序设计竞赛

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Given $n$ strings $s_1,s_2,\ldots,s_n$ consisting of $\texttt{0}$ , $\texttt{1}$ , or $\texttt{2}$ , you need to answer $q$ queries. In each query, given a string $t$ and interval endpoints $l$ and $r$ , find the value of the following expression:

$\sum_{i=l}^r \mathrm{lcp}(t,s_i)$

where $\mathrm{lcp}(a,b)$ denotes the length of the longest common prefix of $a$ and $b$ .

输入描述:

The first line of input contains an integer  (), denoting the number of test cases.

For each test case, the first line contains two integers  and  (), denoting the number of strings and the number of queries, respectively.

The next  lines each contain a string  consisting of , , or  (), as described above.

The next  lines each describe a query. Each line contains two integers  and  () and a string  consisting of , , or  (), representing the left and right boundaries of the interval to be summed and the query string.

It is guaranteed that the input satisfies  and .

输出描述:

For each query, output one line containing an integer representing the answer to the query.

示例1

输入

复制

输出

复制

10
0
2