After a long day, Adam is on his way home. However, after suffering a sudden bout of amnesia, he has forgotten the name of the street where he lives!
Fortunately, he has a list of potential names, from to , which are composed of lowercase Latin characters, all with equal length. He also has a set of quirky constraints that the street name should satisfy; each constraint is of the form , meaning that the substring from to should be a palindrome. (Recall that a palindrome is a string which reads the same forwards and backwards, like
Can you help Adam figure out the total number of strings on his list that satisfy these constraints?
For all subtasks:
, for all integer from to .
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
The first line will contain the values for , , and , denoting the number of strings, number of queries, and the length of each string.
The next lines will contain , the string Adam is considering.
The next lines after that will contain two numbers and , denoting the substring from to which must be a palindrome.
Print out, on a single line, the number of strings that Adam is considering which satisfies the constraints.
Sample Input 1
3 2 8 maineste aracecar reeeeeee 3 3 2 8
Sample Output 1
Explanation for Sample Output 1
Though all three candidate strings satisfy the first constraint, only the second and third strings satisfy the to letter being also a palindrome.
Sample Input 2
2 2 3 aaa aba 1 3 2 3
Sample Output 2
Explanation for Sample Output 2
Only the first string satisfies both the string itself being a palindrome and the substring also being a palindrome.