Чтобы поощрить людей заниматься спортом, спортивный центр города CD, где живет Сяо Ц., проводит долгосрочную акцию с начислением баллов и подарками.
В спортивном центре есть много видов спорта, каждый из которых имеет фиксированное неотрицательное целое количество баллов. За каждое участие в виде спорта начисляется соответствующее количество баллов. Каждый месяц спортивный центр выпускает новый подарок, и если накопленные за месяц баллы больше или равны стоимости подарка, их можно обменять на него. Подарки можно получать несколько раз в месяц, при этом каждый раз списывается одинаковое количество баллов. Чтобы стимулировать людей своевременно обменивать призы, баллы, полученные в текущем месяце, можно использовать только в этом же месяце; они не переносятся на следующий.
Сяо Ц. — большой любитель спорта, и его хобби — приглашать друзей в спортивный центр для участия в различных видах активности. Благодаря помощи друзей Сяо Ц. каждый месяц получает много подарков.
Скоро наступит новый месяц, и Сяо Ц. начал планировать свои спортивные занятия. Однако он обнаружил, что потерял таблицу, в которой записывал баллы за каждый вид спорта. Эта таблица была результатом годовой работы по сбору данных обо всех спортивных проектах центра.
В глубоком расстройстве Сяо Ц. внезапно вспомнил, что у него есть привычка записывать количество участий в каждом виде спорта за каждый месяц. Позже он зашел на сайт спортивного центра и узнал свои остатки баллов за каждый месяц — то есть количество баллов, оставшихся после вычета стоимости нескольких подарков из общей суммы баллов за месяц. Однако Сяо Ц. не помнит, сколько именно подарков он получил в каждом месяце.
Сяо Ц. подумал, что с помощью этих данных можно вычислить баллы за каждый вид спорта. Проведя расчеты, он понял, что если запись за какой-то месяц ошибочна, то задача может оказаться неразрешимой. Поскольку Сяо Ц. участвует во многих видах спорта каждый месяц, вполне естественно, что он мог допустить одну или две ошибки в записях.
В итоге Сяо Ц. придумал компромиссный вариант: найти такие баллы за каждый вид спорта, которые удовлетворяют записям за максимально возможное количество месяцев.
Поскольку Сяо Ц. нужно идти на тренировку, эту задачу, как и многие другие, предстоит решить вам, участникам олимпиады по информатике.
Входные данные
Данная задача является задачей с ответами в файлах (output-only). Все входные данные sports1.in ~ sports10.in доступны в прилагаемых файлах.
Первая строка входных данных содержит два целых положительных числа $n$ и $m$, обозначающих количество видов спорта и количество месяцев, за которые есть записи.
Далее следуют $m$ строк, каждая из которых содержит $n + 2$ неотрицательных целых числа, представляющих запись за один месяц. Первые $n$ чисел — это количество участий Сяо Ц. в каждом из $n$ видов спорта в этом месяце, $(n + 1)$-е число — стоимость одного подарка в этом месяце, а $(n + 2)$-е число — остаток баллов после обмена на некоторое количество подарков.
Гарантируется, что каждое число во входных данных не превышает $2^{31} - 1$.
В конце входного файла содержатся $8$ строк, каждая из которых содержит целое число — параметры $a_3, a_4, \dots, a_{10}$, смысл которых описан в разделе «Оценка».
Выходные данные
Для каждого из 10 входных файлов sports1.in ~ sports10.in вам необходимо предоставить соответствующие выходные файлы sports1.out ~ sports10.out.
Каждый выходной файл должен содержать $n$ строк, в каждой из которых записано неотрицательное целое число, меньшее $10^{10m}$ (не более $10m$ знаков). $i$-я строка содержит количество баллов за $i$-й вид спорта.
Обратите внимание, что размер каждого выходного файла не должен превышать 1 МБ (1048576 байт), иначе тест будет считаться неверным.
Примеры
Пример
2 4 2 0 4 2 0 2 3 1 5 7 24 16 2 0 4 5 2 2 1 1 0 0 0 0
7 11
Примечание
Запись 1: $2 \times 7 + 0 \times 11 = 14$, после обмена на $3$ подарка остаток $2$ балла;
Запись 2: $0 \times 7 + 2 \times 11 = 22$, после обмена на $7$ подарков остаток $1$ балл;
Запись 3: $5 \times 7 + 7 \times 11 = 112$, после обмена на $4$ подарка остаток $16$ баллов;
Запись 4: невозможно удовлетворить эту запись при любом выборе баллов за виды спорта.
Оценка
Для каждого набора данных заданы $8$ параметров оценки $a_3, a_4, \dots, a_{10}$. Если выходные данные участника некорректны, начисляется 0 баллов. В противном случае, пусть $w_{\text{user}}$ — количество месяцев, удовлетворяющих вашему решению, а $w_{\text{std}}$ — количество месяцев, удовлетворяющих нашему эталонному решению. Ваша оценка определяется по следующей таблице:
| Оценка | Условие | Оценка | Условие |
|---|---|---|---|
| 10 | $w_{\text{std}} - w_{\text{user}} \leq a_{10}$ | 5 | $w_{\text{std}} - w_{\text{user}} \leq a_5$ |
| 9 | $w_{\text{std}} - w_{\text{user}} \leq a_9$ | 4 | $w_{\text{std}} - w_{\text{user}} \leq a_4$ |
| 8 | $w_{\text{std}} - w_{\text{user}} \leq a_8$ | 3 | $w_{\text{std}} - w_{\text{user}} \leq a_3$ |
| 7 | $w_{\text{std}} - w_{\text{user}} \leq a_7$ | 2 | $w_{\text{user}} \geq 0$ |
| 6 | $w_{\text{std}} - w_{\text{user}} \leq a_6$ | 1 | $w_{\text{user}} \geq 0$ |
Если выполняется несколько условий, засчитывается наивысшая оценка.