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

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**.

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| ≤ 20Sum 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| ≤ 4100Sum of length over all N strings per case will be ≤ 10000

Subtask **3** (**60** points): Original constraints.

For each query, print **1** line, **ith** line is the answer to the **ith** query.

Input | Output |
---|---|

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.**

67% Solution Ratio

alamkhanEarliest,

TurinhstuFastest, 0.3s

hredhayxzLightest, 37 MB

phuleethanhShortest, 1903B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.