Дима и строки
Мальчик Дима изучает алгоритмы поиска вхождения одной строки в другую. Более формально — он хочет найти пары индексов (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.
Выходные данные
Одно число — ответ на вопрос Димы.