Точность прогноза кормления

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

Некоторые прогнозы отсутствуют: вместо вероятности указано -. Такие строки не участвуют ни в сортировке, ни в вычислении метрики.

Для каждого запроса с параметром K требуется вычислить метрику precision@K. Сначала животные с имеющимся прогнозом сортируются по убыванию вероятности. В первые K позиций попадают животные с наиболее высокими прогнозами. Если среди этих K животных ровно c действительно нуждались во внеплановом кормлении, то

precision@K = c / K.

При равенстве вероятностей раньше располагается животное, которое раньше встретилось во входных данных.

Значение precision@K необходимо округлить до трёх знаков после точки по правилу ближайшего значения. Если следующая цифра равна 5, округление производится вверх. Каждый ответ выводится ровно с тремя знаками после точки.

Формат ввода

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

В следующих n строках содержатся три значения: имя животного name, вероятность внепланового кормления score и факт need.

score имеет вид 0.xxx или 1.000, где после точки ровно три цифры, либо равен -, если прогноз отсутствует. Значение need равно 1, если внеплановое кормление действительно потребовалось, и 0 иначе.

В последних q строках содержатся запросы: по одному целому числу K в строке.

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

Выведите q строк. В строке с номером запроса выведите соответствующее значение precision@K с тремя знаками после точки.

Ограничения

1 ≤ n ≤ 4000.

1 ≤ q ≤ 1000.

Длина имени name от 1 до 20 символов, имя не содержит пробелов.

Для имеющегося прогноза 0.000 ≤ score ≤ 1.000, после точки записано ровно три цифры.

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

Хотя бы одна строка имеет имеющийся прогноз.

Для каждого запроса 1 ≤ K ≤ m, где m — количество строк с имеющимся прогнозом.