Youtuber_TWK vừa đăng một video giới thiệu bài guitar mới tại: Click here to listen

Sau khi xem video, Youtuber_TWK ghi lại toàn bộ chuỗi ký tự mô tả quá trình luyện tập thành một xâu \(S\) có độ dài \(n\).

Tuy nhiên, trong quá trình biên tập, có một số đoạn ký hiệu bị lỗi hoặc không mong muốn. Những đoạn này được cho bởi \(m\) xâu cấm:

\(P_1, P_2, ..., P_m.\)

Youtuber_TWK gọi một đoạn nhật ký \(S[l..r]\) là đẹp nếu đồng thời thỏa mãn:

• \(S[l..r]\) là một palindrome.
• \(S[l..r]\) không chứa bất kỳ xâu cấm nào trong số \(P_1, P_2, ..., P_m\) làm xâu con.

Hãy giúp Youtuber_TWK đếm xem có bao nhiêu xâu con đẹp trong xâu \(S\).

Input

• Dòng đầu chứa xâu \(S\). \((1 ≤ |S| ≤ 10^6)\)
• Dòng tiếp theo chứa số nguyên \(m\). \((1 ≤ m ≤ 7 \cdot 10^6)\)
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa xâu cấm \(P_i\). \((1 ≤ |Pi|\) \(,\) \(∑|Pi| ≤ 10^6)\)

Output

• In ra số lượng xâu con đẹp của \(S\).

Example

abacaba
2
ba
cab

8

abacabaaabc
3
abaaca
cabbbb
c

15