Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Palindrome and Queries

By moshiur_cse15 · Limits 2s, 256 MB

You’ll be given an array A of N strings containing lowercase english letters only and Q queries. In each query, you have to find the length of the longest palindromic substring which appears in at least L strings and at most R 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 T, the number of testcases. The first line of each case will contain two integers N and Q. Then each of the next N lines will contain a string, ith line will contain the string Ai. Then the folowing Q lines will contain two integers each L and R, as described in the statement.

1 ≤ T≤ 15
1 ≤ N ≤ 105
1 ≤ Q ≤ 105
1 ≤ L ≤ R ≤ N
1 ≤ |Ai| ≤ 105
Sum of length over all N strings per case will be ≤ 106

Subtask 1 (10 points):
1 ≤ T≤ 15, 1 ≤ N ≤ 10, 1 ≤ Q ≤ 100, 1 ≤ L ≤ R ≤ N, 1 ≤ |Ai| ≤ 20
Sum of length over all N strings per case will be ≤ 100

Subtask 2 (30 points):
1 ≤ T≤ 15, 1 ≤ N ≤ 100, 1 ≤ Q ≤ 10000, 1 ≤ L ≤ R ≤ N, 1 ≤ |Ai| ≤ 4100
Sum of length over all N strings per case will be ≤ 10000

Subtask 3 (60 points): Original constraints.

Output

For each query, print 1 line, ith line is the answer to the ith 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

Dataset is huge, use faster I/O methods.

Discussion

Statistics


67% Solution Ratio

alamkhanEarliest, 1M ago

aniks2645Fastest, 0.5s

omar24Lightest, 37 MB

aniks2645Shortest, 2263B

Submit

Login to submit

Related Contests