ROC-AUC для сектора теплицы

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

Оценка риска является целым числом от 0 до 1000: чем больше значение, тем выше предполагаемый риск. Значение -1 означает пропуск показаний, возникший из-за сбоя датчика. Такие записи не используются при вычислении метрики.

В конце входа указан номер сектора, для которого требуется вычислить ROC-AUC. Пусть после удаления пропусков в этом секторе имеется P записей с результатом 1 и N записей с результатом 0. ROC-AUC определяется как среднее по всем P·N парам из одной положительной и одной отрицательной записи: вклад пары равен 1, если оценка положительной записи больше, 0, если меньше, и 0.5, если оценки равны.

При равенстве оценок риска вклад соответствующей пары в ROC-AUC равен 0.5. Если после удаления пропусков в запрошенном секторе нет положительных записей или нет отрицательных записей, следует вывести 0.000.

Формат ввода

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

В следующих n строках даны три целых числа sector score result:

• sector — номер сектора теплицы;
• score — оценка риска, либо -1 для пропуска показаний;
• result — результат проверки: 1 означает обнаруженное заболевание, 0 означает его отсутствие.

В последней строке дано целое число q — номер сектора, для которого нужно вычислить ROC-AUC.

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

Выведите одно число — ROC-AUC для сектора q с ровно тремя знаками после десятичной точки.

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

Ограничения

1 ≤ n ≤ 4000.

1 ≤ sector, q ≤ 50.

score = -1 или 0 ≤ score ≤ 1000.

result равно 0 или 1.

Длина каждой строки входа не превышает 20 символов.