## Returning Home

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 512M

Authors:
Problem type

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 racecar or tacocat).

Can you help Adam figure out the total number of strings on his list that satisfy these constraints?

#### Constraints

, for all integer from to

#### Input Specification

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.

#### Output Specification

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

2

#### 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

1

#### Explanation for Sample Output 2

Only the first string satisfies both the string itself being a palindrome and the substring also being a palindrome.