Стратифицированное разбиение заказов

Служба доставки еды готовит несколько вариантов валидационной выборки для проверки модели прогноза опозданий. Каждый заказ относится к одному из трёх результатов доставки: cancelled, delayed или delivered. Иногда результат заказа ещё не внесён в журнал и обозначается строкой NA.

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

Пусть после исключения строк NA осталось N заказов, а количество заказов класса k равно c_k. Для запроса с процентом p сначала определяется общий размер валидационной части: M = floor(N * p / 100). Затем для каждого класса вычисляются x_k = c_k * M / N и начальное количество b_k = floor(x_k). Пусть r = M - sum(b_k). По одному дополнительному заказу получают r классов с наибольшими дробными частями x_k - floor(x_k).

При равенстве дробных частей дополнительный заказ раньше получает класс с лексикографически меньшим названием: cancelled, затем delayed, затем delivered. Если некоторый класс отсутствует среди известных заказов, для него выводится ноль. Гарантируется, что среди строк журнала есть хотя бы один заказ с известным результатом.

Формат ввода

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

В следующих n строках дан результат одного заказа: cancelled, delayed, delivered или NA.

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

В следующих q строках дано по одному целому числу p — процент заказов, который должен попасть в валидационную часть.

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

Для каждого запроса выведите отдельную строку из трёх целых чисел: количество заказов классов cancelled, delayed, delivered в валидационной части в этом порядке.

Дробная часть при вычислении floor отбрасывается.

Ограничения

1 <= n <= 4000.

Длина каждой строки результата составляет от 2 до 9 символов.

1 <= q <= 1000.

0 <= p <= 100.

Среди n строк есть хотя бы одна строка, не равная NA.