Стратифицированная выборка продаж мороженого

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

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

Проверочная выборка строится стратифицированно: доли классов должны быть максимально близки к их долям среди записей с известным видом мороженого. Пусть N — число записей с известным видом, c_i — число записей класса i, а m — размер проверочной выборки. Сначала для каждого класса вычисляется квота

q_i = m * c_i / N.

В проверочную выборку класса i сначала назначается floor(q_i) записей. Затем остающиеся места распределяются по одному классам с наибольшими дробными частями q_i. Если дробные части равны, место получает класс с лексикографически меньшим названием. Требуется вывести окончательные количества записей каждого класса в проверочной выборке.

Формат ввода

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

В следующих n строках даны два значения: sale_id и ice_cream_type. Значение ice_cream_type равно одному из: сливочное, фруктовое, шоколадное, -.

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

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

Дробная часть квоты отбрасывается только на первом шаге, то есть используется floor(q_i). Других округлений нет.

Ограничения

1 ≤ n ≤ 4000.

1 ≤ sale_id ≤ 10^9; идентификаторы могут повторяться.

1 ≤ m ≤ N, где N — число строк, у которых ice_cream_type не равно -.

Длина значения ice_cream_type от 1 до 11 символов. Возможны пустые классы: для пустого класса выводится 0.

Хотя бы одна запись имеет известный вид мороженого. Пропуски обозначаются только символом - и не участвуют ни в подсчёте N, ни в распределении мест.