# Practice on Toph

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

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, **i ^{th}** line will contain the string

1 ≤ T≤ 15

1 ≤ N ≤ 10^{5}

1 ≤ Q ≤ 10^{5}

1 ≤ L ≤ R ≤ N

1 ≤ |A_{i}| ≤ 10^{5}

Sum of length over all N strings per case will be ≤ 10^{6}

Subtask **1** (**10** points):

1 ≤ T≤ 15, 1 ≤ N ≤ 10, 1 ≤ Q ≤ 100, 1 ≤ L ≤ R ≤ N, 1 ≤ |A_{i}| ≤ 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 ≤ |A_{i}| ≤ 4100

Sum of length over all N strings per case will be ≤ 10000

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

For each query, print **1** line, **i ^{th}** line is the answer to the

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

Login to submit