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 subtasks:

, for all integer from to

##### Subtask 1 [20%]

##### Subtask 2 [80%]

No additional constraints.

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

## Comments