Toru proposes Hori again this Valentine. Hori being an intelligent girl, gives Toru a long nonsense game so that he stops bothering her.
Hori gives him a string and $$Q$$ queries.
For each query there are two integers $$l$$ and $$r$$
Toru is supposed to create a new string of 26 characters for each query using following rules:
He needs to count the occurrence of each alphabet from l to r
The 1st position in the new string is for occurrence of ‘a’ , second for ‘b’ and so on.
If ‘a’ occurs x times in the range l to r , the first position in the string will be the x%26 +1, character of the english alphabet.
For each query, Toru needs to determine the longest prefix which is also the suffix of newly created string.
The first line of input contains two integers $$N$$ and $$Q$$ denoting length of the string and total number of queries.
The second line contains the string.
$$Q$$ lines, one for each query follows
For each query, two integers are provided $$l$$ and $$r$$ $$ 0 \lt l \le r \le N $$
For each query, print the longest prefix which is also a suffix of newly created string. Print Q lines , one for each query. If no such prefix exist, print "None" for that query.
$$ 0 \lt l \le r \le N $$
String contains only lowercase English alphabets.
Subtask $$1$$: $$20$$ Points
$$ 1\le N,Q \le 1000 $$
Subtask $$2$$: $$80$$ Points
$$ 1\le N,Q \le 50000 $$
Note : Do not consider the whole string as prefix or suffix.
Every alphabet is present once in the string
Hence, newly formed string is 'bbbbbbbbbbbbbbbbbbbbbbbbbb'
And the largest prefix which is also suffix of string is 'bbbbbbbbbbbbbbbbbbbbbbbbb'