11. Управление маркетплейсом

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

• Спросом являются заявки, которые создаются пользователями. Эти заявки можно условно разделить на типы, например, в зависимости от того, к какому крупному клиенту они относятся (например, "доставка еды", "доставка продуктов из магазина", "доставка товаров из онлайн-магазина" и т.д.). В рамках нашей простой модели считаем, что нет отложенных заявок, и мы должны выполнить заказ как только он будет создан пользователем, все заявки мы успеваем доставить за час и пользователи никогда не отменяют созданные заявки.

• Предложение - это наши курьеры, которые возят заявки. Предполагаем, что нет батчевания заявок, то есть один курьер в конкретный момент времени может везти только одну заявку. Также будем пользоваться предположением, что доставка работает в очень маленьком городе - в нем любой курьер может возить любые заявки (заметим, что в реальной жизни назначение курьеров, конечно же, гораздо сложнее - мы не хотим назначать курьера на заказ, если они находят в противоположных концах города; для заказов на доставку еды обязательно наличие специальной термосумки и т.д.). Кроме того, считаем, что курьеров у нас некоторое константное количество, которое не зависит от дня недели и времени суток (представим, что доставка в нашем маленьком городе осуществляется роботами-доставщиками).

Тогда задача управления маркетплейсом на нашей простой модели состоит в том, чтобы предсказать, сколько заявок у нас будет создано в будущем, определить, сколько из созданных заявок мы можем вывести имеющимися курьерами, и с помощью различных механик (управление ценой, временем доставки и т.д.) "срезать" заявки, которые мы не можем вывести. Каждая из механик "срезания" заслуживает отдельного внимательного рассмотрения, поэтому останавливаться на них не будем, а попробуем сконцентрироваться на определении количества заявок, которое мы должны "срезать".

1. Предположим, что у нас есть некоторые исторические данные про создаваемые заявки каждого типа с гранулярностью до часа (подробнее описание этих данных можно почитать в разделе "формат ввода"). На основе этих исторических данных нужно научиться делать предсказания на будущее "сколько заявок каждого типа будет создано в рамках заданного часа".
2. На основе полученных предсказаний нужно понять, сколько заявок каждого типа мы не можем выполнить имеющимися курьерами. Считаем, что все типы заявок для нас одинаково важны и мы назначаем курьеров "равномерно" (то есть постепенно назначаем по одному курьеру на каждый тип заявок до тех пор, пока у нас не закончатся свободные курьеры или не закончатся заявки: например, если у нас три типа заявок с предсказанным количеством $10, 15, 20$ соответственно и $32$ курьера, то мы распределим 30 курьеров так, что останется $0, 5, 10$ заявок, а потом распределим оставшихся двух курьеров между вторым и третьем типом, в конечном счете получив, что нужно "срезать" $0, 4, 9$ заявок по типам).

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

В первой строке задаются два целых числа: $m$ $(1 \leq m \leq 10)$ — количество крупных клиентов, которые пользуются платформой доставки; и $s$ $(10 \leq s \leq 10000)$ — количество имеющихся курьеров.

Во второй строке задается целое число $n$ $(1 \leq n \leq 1680)$ — количество часов, для которых удалось собрать информацию о созданных заявках по историческим данным.

Далее следует $n$ строк, в каждой из которых записана информация о созданных заявок: сначала три целых числа $week_i$ $(1 \leq week_i \leq 10)$, $day_i$ $(1 \leq day_i \leq 7)$, $hour_i$ $(1 \leq hour_i \leq 24)$ - номер недели, дня и часа, для которых собрана информация о созданных заявках; а затем $m$ целых чисел $d_i^j$ $(0 \leq d_i^j \leq 1000)$ - число созданных заявок типа $j$ $(1 \leq j \leq m)$, созданных в данный период времени. Все числа разделены одиночными пробелами. Обратите внимание, что данных за некоторые часы может не быть.

После этого в отдельной строке задается целое $q$ $(1 \leq q \leq 1680)$ — количество запросов.

Далее следует $q$ строк, в каждой из которых задается запрос одного из двух видов:

• если первое число в строке $1$, то это запрос сообщает информацию о созданных заявках в разбивке по типам: далее в этой же строке следуют сначала три целых числа $week_i$ $(11 \leq week_i \leq 20)$, $day_i$ $(1 \leq day_i \leq 7)$, $hour_i$ $(1 \leq hour_i \leq 24)$ -- номер недели, дня и часа, для которых собрана информация о созданных заявках; а затем $m$ целых чисел $d_i^j$ $(0 \leq d_i^j \leq 1000)$ -- число созданных заявок типа $j$ $(1 \leq j \leq m)$, созданных в данный период времени.
• если первое число в строке $2$, то это запрос на получение предсказания: далее в этой же строке следуют сначала три целых числа $week_i$ $(11 \leq week_i \leq 20)$, $day_i$ $(1 \leq day_i \leq 7)$, $hour_i$ $(1 \leq hour_i \leq 24)$ -- номер недели, дня и часа, для которых нужно сделать предсказание.

Все числа разделены одиночными пробелами.

Выведите $m$ вещественных чисел, разделенных пробелами, - среднее количество заявок каждого типа, которое необходимо "срезать" в моменты времени, для которых приходил запрос второго типа.

Ответ считается правильным, если каждое число отличается от истинного не более, чем на $1$.

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