Ma5termind likes playing with strings a lot. He thinks that he is so good with strings that nobody can challenge him with a string problem. One fine day, ma5termind's best friend shasha came up with an interesting string problem and decided to challenge him.
Shasha gave him a string S consisting of N lower case letters and an integer Q denoting number of queries to be processed. Each query consists of 2 integers X and Y denoting the indices in the string S. For each query, ma5termind is asked to report the length of longest common prefix between the suffixes starting at position X and position Y.
That day, ma5termind came to know about the truth that he is not good with strings but to show off in front of his friend, he desperately wants to solve this problem. Can you please help him solving this problem ?
Input:
First line will contain two integers N and Q
Next line will contain a string S of length N.
Next Q line will contain two space-seperated integers X and Y.
Ouput:
For each query, print a single integer denoting the length of longest common prefix between the suffixes starting at position X and position Y.Constraints:
- 1 ≤ N, Q ≤ 105
- 1 ≤ X, Y ≤ 105
- S contains only lower case letters
See sample I/O for more clarification.
Scoring:
- Subtask 1: 1 ≤ N, Q ≤ 1000 ( 40 pts )
- Subtask 2: 1 ≤ N, Q ≤ 105 ( 60 pts )
Q1 : "aabbccaabbcc" is the longest common prefix.
Q2 : "a" is the longest common prefix.
Q3 : "aabbcc" is the longest common prefix.
Q4 : "b" is the longest common prefix.
Q5 : "bbcc" is the longest common prefix.
