CSES - Lentomatka
  • Time limit: 2.00 s
  • Memory limit: 512 MB

Uolevi päätti tehdä x päivän pituisen matkan. Hän aloittaa matkansa kotikaupungistaan ja joka päivä hän joko viettää aikaa kaupungissa tai lentää toiseen kaupunkiin tiettyjen todennäköisyyksien mukaan. Tehtäväsi on laskea kullekin kaupungille todennäköisyys, että Uolevi päätyy sinne matkansa päätteeksi.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja x: kaupunkien määrä ja lentojen määrä. Kaupungit on numeroitu kokonaisluvuin 1,2,\ldots,n. Kaupunki 1 on Uolevin kotikaupunki.

Tämän jälkeen syötteessä on n riviä, jotka kuvaavat Uolevin toiminnan kussakin kaupungissa. Jokaisella rivillä on ensin luku k: moneenko kaupunkiin kaupungista pääsee lentämään. Tämän jälkeen rivillä on k lukuparia. Jokaisessa parissa on ensin kaupungin numero ja sitten todennäköisyys, että Uolevi päättää lentää sinne. Näistä jäljelle jäävä todennäköisyys kuvastaa sitä, että Uolevi jää kaupunkiin päiväksi.

Tuloste

Ohjelmasi tulee tulostaa jokaisen kaupungin todennäköisyys, että Uolevi päätyy sinne x päivän jälkeen. Vastauksen absoluuttinen virhe saa olla enintään 10^{-6}.

Rajat

1\leq n\leq 100
1\leq x\leq 10^6

Esimerkki

Syöte:

3 5
2 2 0.5 3 0.3
0
1 1 0.1

Tuloste:

0.03827
0.6791
0.28263