Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P166PROJ - ROUND 6J - Trò chơi với xâu

Gấu gần đây rất thích thú với một trò chơi với xâu. Trò chơi như sau: Đếm số xâu con tốt phân biệt của xâu s. Ta định nghĩa xâu con tốt theo n nguyên tắc.

Mỗi nguyên tắc được mô tả bằng 3 thông số (p, l, r), ở đây p là string và 2 số nguyên l, r (1 <= l <= r <= |p|), ta gọi xâu t tuân theo nguyên tắc trên nếu, số lần xuất hiện của xâu t trong xâu p nằm trong đoạn [l, r].

Ví dụ: “ph” tuân theo nguyên tắc (“ph”, 1, 2) còn “a” thì không.

Một xâu con của xâu s là một dãy con gồm các kí tự liên trong xâu s.

Hai xâu con gọi là phân biệt nếu chúng khác nhau. Ví dụ: Cho xâu “ababfd” ta có s[1..2] = “ab” khác s[2..3] = “ba”, còn s[1..1] = “a” và s[3..3] =”a” thì không phân biệt.

Ta gọi xâu t là tốt nếu xâu t tuân theo của n nguyên tắc.

Các bạn hãy giúp Gấu chơi trò chơi này nhé!

Input

Dòng đầu tiên là xâu s.

Dòng thứ 2 là số nguyên n.

n dòng tiếp theo chứa n nguyên tắc, mỗi dòng đầu có dạng (p[i], l[i], r[i])

Độ dài xâu s và các xâu p[i] không quá 2000.

n không quá 10

Output

Số xâu con của s là xâu tốt.

Example

Input:

cccd

2

cc 0 0

ccd 1 1 Output: 3


Được gửi lên bởi:adm
Ngày:2016-03-31
Thời gian chạy:1s-4s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.