Aby zachęcić ludzi do częstszego uprawiania sportu, centrum sportowe w mieście CD, w którym mieszka Xiao Q, prowadzi długoterminowy program punktowy z nagrodami.
Centrum sportowe oferuje wiele dyscyplin, z których każda ma przypisaną stałą, nieujemną liczbę punktów. Za każdym razem, gdy ktoś bierze udział w danej dyscyplinie, gromadzi odpowiednią liczbę punktów. W każdym miesiącu centrum wprowadza nowy rodzaj nagrody. Jeśli w danym miesiącu łączna liczba punktów jest większa lub równa liczbie punktów wymaganej do odebrania nagrody, można wymienić zgromadzone punkty na nagrodę. Nagrodę w danym miesiącu można odebrać wielokrotnie, przy czym za każdym razem odejmowana jest ta sama liczba punktów. Aby zachęcić ludzi do terminowego odbierania nagród, punkty zdobyte w danym miesiącu można wykorzystać tylko w tym samym miesiącu; nie przechodzą one na kolejny miesiąc.
Xiao Q jest entuzjastą sportu, a jego hobby polega na zapraszaniu grupy przyjaciół do centrum sportowego na różne dyscypliny. Dzięki pomocy przyjaciół Xiao Q co miesiąc zdobywa wiele nagród.
Zbliża się nowy miesiąc, więc Xiao Q zaczął planować swoje aktywności sportowe. Niestety, odkrył, że zaginęła jego tabela z punktacją za poszczególne dyscypliny. Tabela ta była wynikiem całego roku zbierania danych i zawierała punkty za wszystkie dyscypliny sportowe w centrum.
Zrozpaczony Xiao Q przypomniał sobie, że miał zwyczaj zapisywania liczby uczestnictw w każdej dyscyplinie w każdym miesiącu. Później sprawdził na stronie internetowej centrum sportowego swoje pozostałe punkty z każdego miesiąca, czyli punkty, które zostały po odjęciu od całkowitej miesięcznej sumy punktów wielokrotności punktów wymaganych do odebrania nagrody. Xiao Q nie pamięta jednak, ile nagród odebrał w każdym miesiącu.
Xiao Q pomyślał, że być może na podstawie tych danych uda się wyznaczyć punkty za każdą dyscyplinę. Po przeprowadzeniu analizy odkrył, że jeśli zapisy z danego miesiąca są błędne, może dojść do sytuacji, w której nie ma rozwiązania. Ponieważ Xiao Q bierze udział w wielu dyscyplinach każdego miesiąca, drobne błędy w zapisach są czymś naturalnym.
Ostatecznie Xiao Q wymyślił kompromisowe rozwiązanie: wyznaczyć punkty za każdą dyscyplinę tak, aby spełniały one zapisy z jak największej liczby miesięcy.
Ponieważ Xiao Q musi dziś iść na trening, zadanie to, jak wiele innych, powierza Tobie – uczestnikowi zawodów informatycznych.
Wejście
To zadanie typu "odpowiedź w pliku" (ang. output-only). Wszystkie dane wejściowe sports1.in ~ sports10.in znajdują się w załączonych plikach.
Pierwsza linia wejścia zawiera dwie dodatnie liczby całkowite $n$ oraz $m$, oznaczające odpowiednio liczbę dyscyplin sportowych oraz liczbę miesięcy, dla których istnieją zapisy.
Następnie następuje $m$ linii, z których każda zawiera $n + 2$ nieujemne liczby całkowite, reprezentujące zapis z jednego miesiąca. Pierwsze $n$ liczb, z których $i$-ta oznacza liczbę uczestnictw Xiao Q w $i$-tej dyscyplinie w danym miesiącu, $(n + 1)$-sza liczba oznacza liczbę punktów potrzebną do odebrania jednej nagrody w tym miesiącu, a $(n + 2)$-ga liczba oznacza pozostałe punkty po odebraniu pewnej liczby nagród.
Gwarantuje się, że każda liczba w wejściu nie przekracza $2^{31} - 1$.
Na końcu pliku wejściowego znajduje się $8$ linii, z których każda zawiera jedną liczbę całkowitą, będącą parametrem $a_3, a_4, \dots, a_{10}$, których znaczenie opisano w sekcji dotyczącej punktacji.
Wyjście
Dla każdego z 10 plików wejściowych sports1.in ~ sports10.in należy przesłać odpowiedni plik wyjściowy sports1.out ~ sports10.out.
Każdy plik wyjściowy powinien zawierać $n$ linii, z których każda zawiera nieujemną liczbę całkowitą mniejszą niż $10^{10m}$ (nieprzekraczającą $10m$ cyfr). $i$-ta linia oznacza liczbę punktów za $i$-tą dyscyplinę sportową.
Należy pamiętać, że dla każdego zestawu danych plik wyjściowy nie może przekroczyć 1MB (1048576 bajtów), w przeciwnym razie zestaw zostanie uznany za błędny.
Przykład
Wejście 1
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
Wyjście 1
7 11
Uwagi
Zapis 1: $2 \times 7 + 0 \times 11 = 14$, po odebraniu $3$ nagród pozostają $2$ punkty;
Zapis 2: $0 \times 7 + 2 \times 11 = 22$, po odebraniu $7$ nagród pozostaje $1$ punkt;
Zapis 3: $5 \times 7 + 7 \times 11 = 112$, po odebraniu $4$ nagród pozostaje $16$ punktów;
Zapis 4: Niezależnie od ustawienia punktów za każdą dyscyplinę, nie da się spełnić tego zapisu.
Punktacja
Dla każdego zestawu danych ustaliliśmy $8$ parametrów punktacji $a_3, a_4, \dots, a_{10}$. Jeśli wyjście zawodnika jest nieprawidłowe, otrzymuje on zero punktów. W przeciwnym razie, niech $w_{\text{user}}$ oznacza liczbę miesięcy spełnionych w Twoim rozwiązaniu, a $w_{\text{std}}$ liczbę miesięcy spełnionych w naszym wzorcowym rozwiązaniu. Twój wynik zostanie obliczony zgodnie z poniższą tabelą:
| Wynik | Warunek | Wynik | Warunek |
|---|---|---|---|
| 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$ |
Jeśli spełnionych jest wiele warunków, przyznawany jest najwyższy możliwy wynik.