eolymp
bolt
Try our new interface for solving problems
Məsələlər

Дима и строки

Дима и строки

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

Дима пытается придумать новый быстрый алгоритм, решающий данную задачу. Основная идея алгоритма — провести сравнение лишь некоторых символов, при этом значительно уменьшив количество возможных подходящих пар индексов. Он уже провел несколько сравнений и теперь хочет узнать — сколько еще осталось пар индексов, являющихся ответом на задачу и не противоречащих полученным им данным.

Помните, Дима еще маленький мальчик, так что мог ошибиться в измерениях. Если входные данные противоречивы выведите 0.

Алфавит, которым пользуется Дима, содержит ровно 10^100 букв.

Giriş verilənləri

Первая строка содержит три целых числа 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.

Çıxış verilənləri

Одно число — ответ на вопрос Димы.

Nümunə

Giriş verilənləri #1
6 3 10
1 ! 1
1 = 10
2 = 10
3 = 10
1 ! 5
1 ! 8
Çıxış verilənləri #1
1
Müəllif Егор Куликов
Mənbə Зимняя Школа Харьков 2012