408039: GYM102966 C CLETS Patrols

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. CLETS Patrolstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The Corporation Of Ludicrously Evil Topography and Scouring (CLETS) is working on a new way to organize their henchmen's patrols so that they will be impossible to predict for a certain handsome british spy that would try to infiltrate their base. To that end, when a henchman reaches a post, a computer will randomly pick to which post the henchman should go next.

By some classified means, we have acquired the probability distributions that the computers use to choose where to send the henchmen next. Your task is to use this information to determine, for every post, the probability that a guard will be there after $$$M$$$ steps, so that our friend, the handsome british spy, can plan the safest route to the CLETS base.

A step is defined as moving from one post to another, or waiting in the same post, should the computer decide that. The Guard start their shift on the first post.

Input

The fist line contains two integers separated by a space, $$$N$$$ and $$$M$$$ where ($$$1 \leq N \leq 200$$$) and ($$$1 \leq M \leq 10000$$$): the number of posts, and the number of steps we are interested in. The next $$$N$$$ lines contain exactly $$$N$$$ numbers separated by a space where the $$$j$$$-th number on line $$$i+1$$$ represents the probability that the computer will send a guard to the $$$j$$$-th post from the $$$i$$$-th post.

Output

Print $$$N$$$ lines; in the $$$i$$$-th line, print the probability that a guard will be in post number $$$i$$$ after $$$M$$$ steps.

Your answer is considered correct if its absolute or relative error doesn't exceed $$$10^{-4}$$$.

ExampleInput
2 2
0.75 0.25
0.5 0.5
Output
0.6875
0.3125

加入题单

上一题 下一题 算法标签: