Palindrome and Queries

moshiur_cse15 Practise Contest 01
Limits 2s, 512 MB

You'll be given an array AA of NN strings containing lowercase English letters only and QQ queries. In each query, you have to find the length of the longest palindromic substring which appears in at least LL strings and at most RR strings. If there is no such palindromic substring, print 0.

A palindrome is a word which reads the same backward and forward, such as “madam”, “abba” etc. A substring is a string of character(s) that is contained in another string. For example, “abc” has 6 substrings: “a”, “ab”, “abc”, “b”, “bc”, “c”.

A palindromic substring is a substring which reads the same backward and forward. For example, “taka” has 4 unique palindromic substrings: “t”, “a”, “k”, “aka”.

Input

There will be multiple testcases. The first line of the input will contain an integer TT (1T151 ≤ T≤ 15), the number of testcases. The first line of each case will contain two integers NN (1N1051 ≤ N ≤ 10^5) and QQ (1Q1051 ≤ Q ≤ 10^5). Then each of the next NN lines will contain a string, ii-th line will contain the string AiA_i (1Ai1051 ≤ |A_i| ≤ 10^5). Then the following QQ lines will contain two integers each LL and RR (1LRN1 ≤ L ≤ R ≤ N), as described in the statement.

Sum of length over all NN strings per case will be 106≤ 10^6.

Output

For each query, print 1 line, ii-th line is the answer to the ii-th query.

Sample

InputOutput
1
3 6
aaac
aaabbbbbb
abbaaa
1 1
1 2
1 3
2 2
2 3
3 3
6
6
6
2
3
3

Data set is huge, use faster I/O methods.

Submit

Login to submit.

Contributors

Statistics

71% Solution Ratio
alamkhanEarliest, Mar '20
mdshadeshFastest, 0.0s
samiulsamiLightest, 76 kB
mumith_fahim99Shortest, 1807B
Toph uses cookies. By continuing you agree to our Cookie Policy.