Стратифицированная проверочная выборка чеков

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

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

Используется стратифицированное разбиение. Пусть N — число чеков, встречающихся в обеих таблицах, а N_c — число таких чеков класса c. Для каждого класса сначала вычисляется квота q_c = k * N_c / N и выделяется floor(q_c) мест. Оставшиеся места выдаются классам с наибольшими дробными частями квот. Нужно вывести, сколько чеков каждого класса попадёт в проверочную выборку.

При равенстве дробных частей дополнительное место получает класс с лексикографически меньшим именем. Пустой класс получает 0 мест. Гарантируется, что существует хотя бы один чек, встречающийся в обеих таблицах, и 0 ≤ k ≤ N.

Формат ввода

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

В следующих n строках записаны три целых числа receipt_id, items_count, total_amount — идентификатор чека, число товаров и сумма чека в копейках.

В следующих m строках записаны receipt_id и class_name — идентификатор чека и его класс. Значение class_name равно одному из normal, return, suspicious.

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

Выведите три целых числа: количество чеков классов normal, return, suspicious в проверочной выборке, именно в этом порядке.

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

Ограничения

1 ≤ n, m, n + m ≤ 4000.

1 ≤ receipt_id ≤ 10^9.

Идентификаторы чеков внутри каждой из двух таблиц не повторяются.

0 ≤ items_count ≤ 500.

0 ≤ total_amount ≤ 10^8.

Длина class_name не превышает 10 символов.

0 ≤ k ≤ N, где N — число идентификаторов, встречающихся в обеих таблицах.