eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Діма та рядки

Діма та рядки

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Хлопчик Діма вивчає алгоритми пошуку входження одного рядка в інший. Більш формально — він хоче знайти пари індексов (i, j) такі, що підрядок рядка t, який починається з символу з індексом i і завершується символом з індексом j, співпадав з рядком s.

Діма намагається придумати новий швидкий алгоритм, який розв'язує дану задачу. Основна ідея алгоритму — провести порівняння лише деяких символів, при цьому значно зменшивши кількість можливих пар індексів, які підходять. Він вже провів декілька порівнянь і тепер хоче взнати — скільки ще залишилось пар індексів, які є відповіддю до задачі і не суперечать ориманим ним даним.

Пом'ятайте, Діма ще маленький хлопчик, так що міг помилитись у вимірюваннях. Якщо вхідні дані суперечливі виведіть 0.

Алфавіт, яким користується Діма, містить рівно 10^100 літер.

Вхідні дані

Перший рядок містить три цілих числа n, l_s, l_t (0n100, 1l_sl_t10^9). n — це кількість проведених порівнянь, l_s — довжина рядкі s і l_t — довжина рядка t. Наступні n рядків містять інформацію про одне порівняння. Кожен рядок містить число i, 1il_s, пропуск, символ "=" або "!", пропуск і число j, 1jl_t. Якщо використано символ "=", то s_i = t_j, а якщо символ "!", то s_it_j.

Вихідні дані

Одне число — відповідь на питання Діми.

Приклад

Вхідні дані #1
6 3 10
1 ! 1
1 = 10
2 = 10
3 = 10
1 ! 5
1 ! 8
Вихідні дані #1
1
Автор Єгор Куліков
Джерело Зимова Школа Харків 2012