Đếm xâu con tốt

Cho xâu $s$ gồm các chữ cái la-tinh thường. Một xâu $t$ được gọi là tốt nếu nó thỏa mãn tất cả $n$ luật cho trước. Mỗi luật được mô tả bởi bộ ba $(p,l,r)$ trong đó $p$ là một xâu và $l,r$ là hai số nguyên ($l\le r$): xâu $t$ thỏa luật $(p,l,r)$ nếu số lần xuất hiện của $t$ trong $p$ nằm trong đoạn $[l,r]$ (kể cả hai đầu).

Số lần xuất hiện của xâu $t$ trong xâu $p$ là số cặp $(l,r)$ thỏa $1\le l\le r\le |p|$ và $p[l..r]=t$ (các vị trí xuất hiện có thể chồng lấp nhau).

Hãy đếm số xâu con phân biệt của $s$ là xâu tốt. Hai xâu con $s[x..y]$ và $s[z..w]$ được coi là khác nhau nếu và chỉ nếu $s[x..y]\ne s[z..w]$ (tức là so sánh dạng xâu, không phải so sánh vị trí).

Dữ liệu vào

• Dòng đầu chứa xâu $s$.
• Dòng thứ hai chứa số nguyên $n$.
• $n$ dòng tiếp theo, mỗi dòng chứa một luật gồm xâu $p_i$ và hai số nguyên $l_i,r_i$ cách nhau bởi khoảng trắng.

Các xâu chỉ gồm chữ cái la-tinh thường và đều khác rỗng.

Dữ liệu ra

• In ra một số nguyên duy nhất — số xâu con phân biệt của $s$ là xâu tốt.

Ràng buộc

• $1\le |s|\le 200$
• $0\le n\le 10$
• $1\le |p_i|\le 200$
• $0\le l_i\le r_i\le |p_i|$

Ví dụ