5. Obrovitánsky smäd

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.