The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

ABBYY Cup 3.0 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

string suffix structures

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/03/2023 17:25:00 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|