Cho xâu ký tự ~S~ gồm các chữ cái in thường tiếng Anh độ dài ~n~ và ~k~ cặp ký tự ~(b_1, e_1), ..., (b_k, e_k)~. Gọi ~S[i]~ là ký tự thứ ~i~ của xâu ~S~.

Gọi xâu ~f(i, j)~ gồm hai ký tự là xâu được tạo bởi thao tác ghép hai ký tự ~S[i]~ và ~S[j]~. Xâu ~f(i, j)~ được gọi là xâu đặc biệt nếu tồn tại chỉ số ~x \ (1 \le x \le k)~ sao cho ~S[i] = b_x~ và ~S[j] = e_x~.

Hãy đếm số cặp chỉ số ~i, j \ (1 \le i \lt j \le n)~ sao cho ~f(i, j)~ là xâu đặc biệt.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, k \ (k \le 500);~
• Dòng thứ hai gồm ~n~ ký tự của xâu ~S~ viết liền nhau~;~
• ~k~ dòng sau, dòng thứ ~i \ (1 \le i \le k)~ gồm hai ký tự ~b_i~ và ~e_i~ viết liền nhau.

Output

In ra kết quả của bài toán.

Scoring

• Subtask 1 [40%]: ~n \le 500;~
• Subtask 2 [60%]: ~n \le 10^5.~

Examples

Input

9 2
abcabcabc
ab
ac

Output

12

Giải thích

Các cặp chỉ số ~(i, j)~ thoả mãn: ~(1, 2), (1, 3), (1, 5), (1, 6), (1, 8), (1, 9), (4, 5), (4, 6), (4, 8), (4, 9), (7, 8), (7, 9).~