No tag edit access

G3. Good Substrings

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSmart Beaver recently got interested in a new word game. The point is as follows: count the number of distinct good substrings of some string *s*. To determine if a string is good or not the game uses rules. Overall there are *n* rules. Each rule is described by a group of three (*p*, *l*, *r*), where *p* is a string and *l* and *r* (*l* ≤ *r*) are integers. We’ll say that string *t* complies with rule (*p*, *l*, *r*), if the number of occurrences of string *t* in string *p* lies between *l* and *r*, inclusive. For example, string "ab", complies with rules ("ab", 1, 2) and ("aab", 0, 1), but does not comply with rules ("cd", 1, 2) and ("abab", 0, 1).

A substring *s*[*l*... *r*] (1 ≤ *l* ≤ *r* ≤ |*s*|) of string *s* = *s*_{1}*s*_{2}... *s*_{|s|} (|*s*| is a length of *s*) is string *s*_{l}*s*_{l + 1}... *s*_{r}.

Consider a number of occurrences of string *t* in string *p* as a number of pairs of integers *l*, *r* (1 ≤ *l* ≤ *r* ≤ |*p*|) such that *p*[*l*... *r*] = *t*.

We’ll say that string *t* is good if it complies with all *n* rules. Smart Beaver asks you to help him to write a program that can calculate the number of distinct good substrings of string *s*. Two substrings *s*[*x*... *y*] and *s*[*z*... *w*] are cosidered to be distinct iff *s*[*x*... *y*] ≠ *s*[*z*... *w*].

Input

The first line contains string *s*. The second line contains integer *n*. Next *n* lines contain the rules, one per line. Each of these lines contains a string and two integers *p*_{i}, *l*_{i}, *r*_{i}, separated by single spaces (0 ≤ *l*_{i} ≤ *r*_{i} ≤ |*p*_{i}|). It is guaranteed that all the given strings are non-empty and only contain lowercase English letters.

The input limits for scoring 30 points are (subproblem G1):

- 0 ≤
*n*≤ 10. - The length of string
*s*and the maximum length of string*p*is ≤ 200.

The input limits for scoring 70 points are (subproblems G1+G2):

- 0 ≤
*n*≤ 10. - The length of string
*s*and the maximum length of string*p*is ≤ 2000.

The input limits for scoring 100 points are (subproblems G1+G2+G3):

- 0 ≤
*n*≤ 10. - The length of string
*s*and the maximum length of string*p*is ≤ 50000.

Output

Print a single integer — the number of good substrings of string *s*.

Examples

Input

aaab

2

aa 0 0

aab 1 1

Output

3

Input

ltntlnen

3

n 0 0

ttlneenl 1 4

lelllt 1 1

Output

2

Input

a

0

Output

1

Note

There are three good substrings in the first sample test: «aab», «ab» and «b».

In the second test only substrings «e» and «t» are good.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/19/2018 17:50:59 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|