Діма та рядки
Хлопчик Діма вивчає алгоритми пошуку входження одного рядка в інший. Більш формально — він хоче знайти пари індексов (i, j) такі, що підрядок рядка t, який починається з символу з індексом i і завершується символом з індексом j, співпадав з рядком s.
Діма намагається придумати новий швидкий алгоритм, який розв'язує дану задачу. Основна ідея алгоритму — провести порівняння лише деяких символів, при цьому значно зменшивши кількість можливих пар індексів, які підходять. Він вже провів декілька порівнянь і тепер хоче взнати — скільки ще залишилось пар індексів, які є відповіддю до задачі і не суперечать ориманим ним даним.
Пом'ятайте, Діма ще маленький хлопчик, так що міг помилитись у вимірюваннях. Якщо вхідні дані суперечливі виведіть 0.
Алфавіт, яким користується Діма, містить рівно 10^100 літер.
Вхідні дані
Перший рядок містить три цілих числа n, l_s, l_t (0 ≤ n ≤ 100, 1 ≤ l_s ≤ l_t ≤ 10^9). n — це кількість проведених порівнянь, l_s — довжина рядкі s і l_t — довжина рядка t. Наступні n рядків містять інформацію про одне порівняння. Кожен рядок містить число i, 1 ≤ i ≤ l_s, пропуск, символ "=" або "!", пропуск і число j, 1 ≤ j ≤ l_t. Якщо використано символ "=", то s_i = t_j, а якщо символ "!", то s_i ≠ t_j.
Вихідні дані
Одне число — відповідь на питання Діми.