Фермер Джон решил использовать данные о своём стаде коров,
чтобы построить автоматический распознаватель, имеет корова
пятна или нет.
К несчастью, ФД не ученье удачно собрал данные о своих коровах
Для каждой из его N(1 <= N <= 50,000) коров, всё что он знает, это
вес коровы и имеет или нет она пятна. Все его коровы имеют
различный вес. По этим данным он построил то, что он назвал,
"классификатор ближайшего соседа". Чтобы угадать, есть у новой
коровы C пятно или нет, он сначала находит в своём стаде корову С'
такую, что её вес ближайший к C'. Если корова C' имеет пятна,
то ФД предполагает, что корова C имеет пятна, если корова C'
не имеет пятен, то ФД предполагает, что и корова C не имеет пятен.
Если же уникального ближайшего соседа нет, а есть две коровы
на одинаковом минимальном расстоянии от C', тогда ФД предполагает,
что корова C имеет пятна, если одна из двух ближайших коров
также имеется пятна.
ФД хочет проверить свой автопредсказатель пятнистости на группе
новых коров, которые только что прибыли на его ферму.
После взвешивания новых коров он обнаружил, что они имеют веса
всех целых чисел в интервале от A до B включительно.
Пожалуйста, определите, сколько из этих коров будут классифицированы
как имеющие пятна. Заметим, что классификатор делает предсказание,
основываясь на данных об N существующих коровах.
Также заметим, что A и B могут быть достаточно большими числами,
так что просто проверка всех чисел по одному от A до B не пройдёт
по времени.
Формат входных данных
Первая строка ввода содержит три целых числа N,A,B
(1 <= A <= B <= 1,000,000,000).
Каждая из следующих N строк описывают одну корову. Каждая строка
содержит либо S W, означающее, что корова с весом W имеет пятна
или NS W, означающее, что корова с весом W не имеет пятен.
Все веса - целые числа в интервале 1 ... 1 000 000 000.
Формат выходных данных
Одно целое число - количество коров из прибывших,
которых алгоритм ФД классифицирует как пятнистых.
В приведенном примере новые коровы с весами
1, 2, 7, 8, 9, 10
будут классифицированы как пятнистые.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 10
S 10
NS 4
S 1
|
6
|