Вероятность выезда по сигналу датчика

На въездах и выездах парковки торгового центра установлены датчики направления. Датчик может выдать сигнал POSITIVE, означающий предполагаемый выезд, однако иногда такой сигнал возникает у въезжающего автомобиля.

В журнале для каждого проезда указано фактическое направление, восстановленное по камерам, и сигнал датчика. Значение UNKNOWN в поле фактического направления означает пропуск: камера не смогла определить направление. Такие записи не участвуют в расчёте вероятности.

Требуется для указанного в запросе шлагбаума найти вероятность того, что автомобиль действительно выезжал, если датчик этого шлагбаума выдал сигнал POSITIVE.

Используется формула Байеса в частотной записи:

P(EXIT | POSITIVE) = N(EXIT, POSITIVE) / (N(EXIT, POSITIVE) + N(ENTRY, POSITIVE)),

где N(direction, signal) — количество подходящих записей указанного шлагбаума с данным фактическим направлением и данным сигналом. Записи с UNKNOWN не учитываются ни в числителе, ни в знаменателе. Если несколько записей полностью совпадают, каждая из них учитывается отдельно.

Формат ввода

В первой строке дано целое число n — количество записей журнала.

В следующих n строках даны три значения через пробел:

gate direction sensor

где gate — идентификатор шлагбаума, direction — фактическое направление, sensor — сигнал датчика.

В последней строке дан идентификатор шлагбаума query_gate — запрос, для которого требуется вычислить вероятность.

Формат вывода

Выведите одно число: P(EXIT | POSITIVE) для шлагбаума из запроса.

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

Ограничения

1 <= n <= 2000.

Идентификатор каждого шлагбаума имеет вид G и от 1 до 4 цифр после буквы G, его длина от 2 до 5 символов.

direction равно одному из значений ENTRY, EXIT, UNKNOWN.

sensor равно одному из значений POSITIVE, NEGATIVE.

Идентификатор query_gate встречается хотя бы в одной записи. Среди записей шлагбаума query_gate имеется хотя бы одна запись с direction, равным ENTRY или EXIT, и с sensor, равным POSITIVE, поэтому деления на ноль не возникает.

Пример