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 $N$ potential names, from $S_1$ to $S_n$, which are composed of lowercase Latin characters, all with equal length. He also has a set of $M$ quirky constraints that the street name should satisfy; each constraint is of the form $[L_i,R_i]$, meaning that the substring from $L_i$ to $R_i$ 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:

$1\le N\le 5000$

$1\le M\le 500000$

$1\le |S_i|\le 30$, $|S_i|=|S_{i+1}|$ for all integer $i$ from $1$ to $N-1$.

$1\le L_i\le R_i\le |S_i|$

Subtask 1 [20%]

$1\le M\le 30$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain the values for $N$, $M$, and $|S_i|$, denoting the number of strings, number of queries, and the length of each string.

The next $N$ lines will contain $S_i$, the $i^{\text{th}}$ string Adam is considering.

The next $M$ lines after that will contain two numbers $L_i$ and $R_i$, denoting the substring from $L_i$ to $R_i$ 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 $2^{\text{nd}}$ to $8^{\text{th}}$ 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 $[2,3]$ also being a palindrome.