Катя совсем недавно начала придумывать задачи по программированию и делать свои контесты. Что ей не нравится — так это скучные и простые ограничения. «N не больше тысячи» и «сумма ai не больше миллиона» наскучили Кате, и она решила придумать что-нибудь посложнее.
В последней задаче на строки, придуманной Катей, входные данные — одна строка из маленьких латинских букв. Чтобы сделать условие подлиннее и вселить ужас в людей, решающих контест, Катя придумала следующий набор из k однотипных ограничений (символы в ограничениях могут повторяться, а некоторые ограничения могут и противоречить друг другу):
- Количество символов c1 в строке не меньше l1 и не больше r1.
- ...
- Количество символов ci в строке не меньше li и не больше ri.
- ...
- Количество символов ck в строке не меньше lk и не больше rk.
Однако, решив, что и это слишком просто и наглядно, Катя дописала следующее условие: из вышеуказанного списка строка удовлетворяет не менее, чем L, и не более, чем R ограничениям.
Составлять сложные и подлые тесты Катя не любит, поэтому она просто взяла большую строку s и хочет добавить в тесты все ее подстроки, которые удовлетворяют ограничениям. Однако, запутавшись в собственных условиях, Катя попросила Вас посчитать, сколько подстрок строки s удовлетворяет этим условиям (каждое вхождение подстроки считается отдельно).
Выходные данные
Выведите одно число — количество подстрок, удовлетворяющих ограничениям.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать поток cout или спецификатор %I64d.
Примечание
В первом тесте требуется посчитать количество строк, не содержащих символов «e» и «o». Вот все такие строки (в порядке вхождения в исходную строку слева направо): «c», «d», «f», «r», «rc», «c», «s».
Во втором тесте нельзя добиться того, чтобы из двух одинаковых ограничений выполнялось ровно одно, поэтому ответ — 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
codeforces
2 0 0
o 1 2
e 1 2
|
7
|
|
2
|
codeforces
2 1 1
o 1 2
o 1 2
|
0
|