Fipo raz pozeral video o tom, ako sa odlišuje spôsob pitia u psov a mačiek. Uvedomil si pritom, že napriek tomu, že mnohým z nás sa aj tak pri pití podarí nechtiac sa obliať, to v porovnaní so zvieratami nemáme až také ťažké. O koľko jednoduchšie by to však bolo, keby namiesto toho voda tiekla smerom ku nim!

Zrazu si predstavil horu, na ktorej bol prameň, z ktorého cez mnohé údolia tiekol potok smerom nadol. V niektorých údoliach sa ale nachádzali psíky pachtiace za každou kvapkou z prameňa, ktorá k nim stiekla. Nanešťastie bol však prameň už takmer vyschnutý a ešte k tomu sa jeho tok stále menil a prechádzal z údolia do údolia…

Úloha

Hora, ktorú si Fipo predstavil, mala $n$ údolí očíslovaných od $0$ po $n-1$. V údolí $0$ zároveň pramení potok. Z prameňa postupne po jednej steká ďalej $t$ kvapiek. Kvapky tečú údoliami a vždy, keď prídu do nejakého údolia, kde nie je psík, stečú do nejakého iného údolia pod ním. Ak je v nejakom údolí psík, tento psík kvapku vypije.

POZOR: Môže existovať aj vyššie položené údolie ako prameň (teda také, z ktorého by kvapky stiekli do údolia s prameňom).

Pre každé údolie $i$ poznáte zároveň hodnotu $k_i$. Ak $k_i = 0$, tak je v údolí psík. Inak dostanete pre údolie $i$ aj postupnosť údolí $A_i$. Po každých $k_i$ kvapkách, ktoré pritečú do údolia $i$, sa zmení to, do ktorého údolia kvapky odtiaľto potečú. Je to nasledujúce údolie v postupnosti $A_i$, pričom prvých $k_i$ kvapiek potečie do údolia $A_i[0]$, druhých $k_i$ kvapiek do $A_i[1]$, a tak ďalej… Zároveň viete, že postupnosť $A_i$ je dlhá $\lceil t/k_i \rceil$ (teda zaokrúhlené nahor). Všimnite si, že pri takejto dĺžke postupnosti $A_i$ sa nikdy nestane, že by niektorá z uvažovaných $t$ kvapiek už nemala kam ďalej tiecť.

Hoci sú psíky veľmi smädné, fyziku aj napriek tomu ešte zatiaľ nevedia oklamať. Preto voda v každom okamihu steká len z vyššie položeného údolia do nižšie položeného, takže nevie tiecť do cyklu. Zistite, koľko kvapiek sa napokon dostane ku každému psíkovi.

Formát vstupu

V prvom riadku vstupu dostanete medzerou oddelené čísla $n$ a $t$ - počet dolín a počet kvapiek stekajúcich z prameňa.

V každom z nasledujúcich $n$ riadkov je celé číslo $k_i$ ($0 \leq k_i \leq 2\cdot10^9$). Ak $k_i=0$, znamená to, že sa v danom údolí nachádza psík. Inak hodnota $k_i$ určuje, po koľkých kvapkách začne voda stekať do ďalšieho údolia. Na zvyšku riadku je $\lceil t/k_i \rceil$ čísel, pričom $m$-té z nich určuje, do ktorého údolia bude stekať $m \cdot k_i$-ta až $(m+1) \cdot k_i - 1$-vá kvapka, ktorá do tohto údolia pritečie ($m$ číslujeme od nuly).

Nech $z_i$ je počet údolí, do ktorých niekedy bude tiecť voda z údolia $i$. Označme potom $\sum z_i$ súčet hodnôt $z_i$ cez všetky údolia $i$, v ktorých sa nenachádza psík. Sú 4 sady vstupov, pričom v jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Pre každého psíka na samostatný riadok vypíšte, koľko kvapiek sa k nemu dostane. Tieto výsledky vypíšte v rovnakom poradí, v akom sú na vstupe údolia so psíkmi.

Príklady

Input:

4 10
3 1 2 3 2
0
2 3 1 3 1 3
0

Output:

5
5

Prvé tri kvapky pôjdu k prvému psíkovi. Ďalšie tri kvapky potom pôjdu najprv do údolia $2$ a odtiaľ prvé dve k druhému psíkovi a tretia k prvému psíkovi. Ďalšia trojica kvapiek pôjde priamo k druhému psíkovi. Posledná kvapka pôjde najprv do údolia $2$ a odtiaľ k prvému psíkovi, keďže je to už štvrtá kvapka, ktorá sa dostala do údolia $2$.

Input:

3 6
9 2
0
0

Output:

0
6

Z prameňa sa spustí $6$ kvapiek, no až po $9$ kvapkách sa má zmeniť smer odtekania vody, preto všetky kvapky skončia pri druhom psíkovi.

Input:

3 17
0
21 0
0

Output:

17
0

Priamo v údolí s prameňom sa nachádza psík, preto všetky kvapky vypije tento psík. Všimnite si, že údolie s prameňom sa nenachádza v najvyššie položenom údolí, keďže by doň stekala voda z údolia $1$, ak by sa do údolia $1$ nejaké kvapky dostali.