Діма та рядки#2932
Діма вивчає алгоритми пошуку підрядків у рядках. Зокрема, він хоче знайти всі пари індексів такі, що підрядок рядка , який починається з індексу і закінчується індексом , збігається з рядком .
Діма намагається винайти новий, швидкий алгоритм для розв'язання цієї задачі. Основна ідея — порівнювати лише певні символи, що значно зменшує кількість можливих пар індексів. Він уже провів декілька порівнянь і тепер хоче дізнатися, скільки пар індексів залишилося, які все ще можуть бути відповідями і не суперечать зібраним ним даним.
Пам'ятайте, Діма ще юний хлопець, тому міг допустити помилки у своїх вимірюваннях. Якщо вхідні дані суперечливі, виведіть 0.
Діма використовує алфавіт, що містить рівно 10^{100} літер.
У першому рядку містяться три цілі числа , l_s, l_t (0 \leq n \leq 100, 1 \leq l_s \leq l_t \leq 10^9), де — кількість зроблених порівнянь, l_s — довжина рядка , l_t — довжина рядка .
Наступні рядків описують кожне порівняння. Кожен рядок містить число , 1 \leq i \leq l_s, пропуск, символ "" або "", ще один пропуск та число , 1 \leq j \leq l_t. Якщо використано символ "", то s_i = t_j; якщо символ "", то s_i \neq t_j.
Виведіть єдине число — відповідь на питання Діми.
Приклад 1