E. Адские ограничения
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Катя совсем недавно начала придумывать задачи по программированию и делать свои контесты. Что ей не нравится — так это скучные и простые ограничения. «N не больше тысячи» и «сумма ai не больше миллиона» наскучили Кате, и она решила придумать что-нибудь посложнее.

В последней задаче на строки, придуманной Катей, входные данные — одна строка из маленьких латинских букв. Чтобы сделать условие подлиннее и вселить ужас в людей, решающих контест, Катя придумала следующий набор из k однотипных ограничений (символы в ограничениях могут повторяться, а некоторые ограничения могут и противоречить друг другу):

  • Количество символов c1 в строке не меньше l1 и не больше r1.
  • ...
  • Количество символов ci в строке не меньше li и не больше ri.
  • ...
  • Количество символов ck в строке не меньше lk и не больше rk.

Однако, решив, что и это слишком просто и наглядно, Катя дописала следующее условие: из вышеуказанного списка строка удовлетворяет не менее, чем L, и не более, чем R ограничениям.

Составлять сложные и подлые тесты Катя не любит, поэтому она просто взяла большую строку s и хочет добавить в тесты все ее подстроки, которые удовлетворяют ограничениям. Однако, запутавшись в собственных условиях, Катя попросила Вас посчитать, сколько подстрок строки s удовлетворяет этим условиям (каждое вхождение подстроки считается отдельно).

Входные данные

В первой строке записана непустая строка s, состоящая из маленьких латинских букв. Длина строки s не превышает 105.

Во второй строке записаны три целых числа, разделенных пробелами — k, L и R (0 ≤ L ≤ R ≤ k ≤ 500).

В следующих k строках в формате «ci li ri» записаны ограничения, придуманные Катей. Все буквы ci — маленькие латинские буквы, li и ri — целые числа (0 ≤ li ≤ ri ≤ |s|, где |s| — длина строки s). Буквы ci не обязательно различны.

Выходные данные

Выведите одно число — количество подстрок, удовлетворяющих ограничениям.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать поток cout или спецификатор %I64d.

Примеры
Входные данные
codeforces
2 0 0
o 1 2
e 1 2
Выходные данные
7
Входные данные
codeforces
2 1 1
o 1 2
o 1 2
Выходные данные
0
Примечание

В первом тесте требуется посчитать количество строк, не содержащих символов «e» и «o». Вот все такие строки (в порядке вхождения в исходную строку слева направо): «c», «d», «f», «r», «rc», «c», «s».

Во втором тесте нельзя добиться того, чтобы из двух одинаковых ограничений выполнялось ровно одно, поэтому ответ — 0.