18985번 - Lyndon Substring 다국어

문제

A string $w$ is said to be a Lyndon word if $w$ is lexicographically smaller than any of its cyclic rotations.

The longest Lyndon substring of a string $s$ is the longest substring of $s$ which is a Lyndon word.

Chiaki has $n$ strings $s_1,s_2,\dots,s_n$. She has some queries: for some pair $(i,j),ドル find the length of the longest Lyndon substring of string $s_is_j$.

입력

There are multiple test cases. The first line of input contains an integer $T,ドル indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ $(1 \le n, m \le 10^5)$ -- the number of strings and the number of queries.

Each of the next $n$ lines contains a nonempty string $s_i$ $(1 \le s_i \le 10^5)$ consisting of lowercase English letters.

Each of the next $m$ lines contains two integers $i$ and $j$ (1ドル \le i, j \le n$) denoting a query.

It is guaranteed that in one test case the sum of all $|s|$ does not exceed 5ドル \times 10^5$ and that in all cases the sum of all $|s|$ does not exceed 5ドル \times 10^6$.

It is guaranteed that neither the sum of all $n$ nor the sum of all $m$ exceeds 10ドル^6$.

출력

For each query, output an integer denoting the answer.

제한

힌트