There are $N$ buckets numbered $1$ through $N$. The buckets contain balls; each ball has a color between $1$ and $K$. Let's denote the number of balls with color $j$ that are initially in bucket $i$ by $a_{i, j}$.
For each $i$ from $1$ to $N-1$ (in this order), someone draws a ball uniformly at random from bucket $i$ and puts it into bucket $i+1$, then continues to draw the next ball. After putting a ball in bucket $N$, this person draws a ball, again uniformly at random, from bucket $N$.
For each color from $1$ to $K$, find the probability that the ball drawn from bucket $N$ has this color.

-----Input-----
- The first line of the input contains two space-separated integers $N$ and $K$. 
- $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains $K$ space-separated integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, K}$.

-----Output-----
Print a single line containing $K$ space-separated real numbers. For each valid $i$, the $i$-th of these numbers should denote the probability that the last drawn ball has color $i$. your answer will be considered correct if absolute or relative error does not exceed $10^{-6}$

-----Constraints-----
- $1 \le N, K \le 1,000$
- $0 \le a_{i, j} \le 10$ for each valid $i, j$
- initially, there is at least one ball in bucket $1$

-----Subtasks-----
Subtask #1 (30 points): $1 \le N, K \le 100$
Subtask #2 (70 points): original constraints

-----Example Input-----
2 2
0 1
1 1

-----Example Output-----
0.333333 0.666667

-----Explanation-----

Difficulty: interview

Starter code:

Solutions:
import sys
import math

def main(arr):
 
 k=len(arr[0])
 n=len(arr)
 dp=[[0]*k for i in range(n+1)]
 
 summation_arr=[]
 for i in range(len(arr)):
  a=1 if i!=0 else 0
  summation_arr.append(sum(arr[i])+a)
 
 for i in range(1,len(dp)):
  for j in range(len(dp[0])):
   dp[i][j]=(dp[i-1][j]+arr[i-1][j])/summation_arr[i-1]
 ans=[]
 
 for i in range(k):
  ans.append(dp[-1][i])
 print(*ans)


 
n,k=input().split()
n=int(n)
arr=[]
for i in range(n):
 arr.append(list(map(int,input().split())))
(main(arr))
 
 


n,k=map(int,input().split())
dp=[[0]*k for i in range(n)]
for i in range(n):
 dp[i]=[int(x) for x in input().split()]
#print(dp)
sumr=[0]*n
for i in range(n):
 sumr[i]=sum(dp[i])
#print(sumr)
for i in range(k):
 for j in range(n):
  if j==0:
   prev=dp[0][i]/sumr[0]
  else:
   curr=(prev)*(dp[j][i]+1)/(sumr[j]+1)+(1-prev)*dp[j][i]/(sumr[j]+1)
   prev=curr
 print(prev,end=" ")


"""
  Url: https://www.codechef.com/problems/BUCKETS
"""


__author__ = "Ronald Kaiser"
__email__ = "raios dot catodicos at gmail dot com"


N, K = list(map(int, input().split()))
a = list(map(int, input().split())) 
s = sum(a)
p = list([v/s for v in a]) 
for _ in range(N-1):
 a = list(map(int, input().split()))
 sa = sum(a) + 1
 p = [(p[i] + a[i])/sa for i in range(K)]
print(*p)


"""
  Url: https://www.codechef.com/problems/BUCKETS
"""


__author__ = "Ronald Kaiser"
__email__ = "raios dot catodicos at gmail dot com"


N, K = list(map(int, input().split()))
a = list(map(int, input().split())) 
s = sum(a)
p = list([v/s for v in a]) 
for _ in range(N-1):
 a = list(map(int, input().split()))
 sa = sum(a) + 1
 p = [p[i]*(a[i] + 1)/sa + (1-p[i])*(a[i]/sa) for i in range(K)]
print(*p)


"""
  Url: https://www.codechef.com/problems/BUCKETS
"""


__author__ = "Ronald Kaiser"
__email__ = "raios dot catodicos at gmail dot com"


N, K = list(map(int, input().split()))
a = list(map(int, input().split())) 
s = sum(a)
p = list([v/s for v in a]) 
for _ in range(N-1):
 a = list(map(int, input().split())) 
 s = []
 sa = sum(a) + 1
 for i in range(K):
  s.append((p[i]*((a[i] + 1)/sa) + (1 - p[i])*(a[i]/sa)))
 p = s
print(*p)


"""
  Url: https://www.codechef.com/problems/BUCKETS
"""


__author__ = "Ronald Kaiser"
__email__ = "raios dot catodicos at gmail dot com"



def solve(px, y, K):
 s = []
 sy = sum(y)
 for i in range(K):
  s.append((px[i]*((y[i] + 1)/(sy + 1)) + (1 - px[i])*(y[i]/(sy + 1))))
 return s


N, K = list(map(int, input().split()))
a = list(map(int, input().split())) 
s = sum(a)
p = list([v/s for v in a]) 
for _ in range(N-1):
 a = list(map(int, input().split())) 
 p = solve(p, a, K)
print(*p)


# cook your dish here
n,k=list(map(int,input().split()))
a=[[]for i in range (n)]
for i in range (n):
 a[i]=list(map(int,input().split()))
f = []
p=[]
for i in range(n):
 s1 = 0
 for j in range(k):
  s1+=a[i][j]
 f.append(s1)
for i in range(k):
 s = []
 l = a[0][i]/f[0]
 s.append(l)
 for j in range(1,n):
  s.append((l + a[j][i])/(f[j]+1))
  l = s[j]
 p.append(s[n-1])
r = str(p[0])+' '
for i in range (1,k):
 r+=(str(p[i])+ ' ')
print(r)
 


# cook your dish here
n,k=list(map(int,input().split()))
a=[[]for i in range (n)]
for i in range (n):
 a[i]=list(map(int,input().split()))
f = []
p=[]
for i in range(n):
 s1 = 0
 for j in range(k):
  s1+=a[i][j]
 f.append(s1)
for i in range(k):
 s = []
 l = a[0][i]/f[0]
 s.append(l)
 for j in range(1,n):
  s.append((l + a[j][i])/(f[j]+1))
  l = s[j]
 p.append(s[n-1])
r = str(p[0])+' '
for i in range (1,k):
 r+=(str(p[i])+ ' ')
print(r)
 


N,K = map(int,input().split(" "))


ball =[]
for i in range(N):
 ball.append(list(map(int,input().split(' '))))

prob =[[0 for i in range(K)] for j in range(N)]

for i in range(N):
 temp = 0
 for j in range(K):
  temp += ball[i][j]
 ball[i].append(temp)

for i in range(K):
 prob[0][i] = ball[0][i]/ball[0][K]

for i in range(1,N):
 c = ball[i][K]
 for j in range(0,K):
  b = ball[i][j]
  prob[i][j] = (b + prob[i-1][j])/(c+1)
 

# print(ball)

# print("jeiasjf")

# print(prob)

for i in range(K):
 print("%.6f" % prob[N-1][i] , end=" ")
# print(*prob[N-1])

# nexus01
n, k=input().split()
n, k=int(n), int(k)
test=n
slist=[]
sumlist=[]
while test:
 test-=1
 sum=0
 x=[float(a) for a in input().strip().split(' ')]
 slist.append(x)
 for a in x:
  sum+=a
 sumlist.append(sum)

for c in range(0, k):
 prob=0
 base=1
 for i in range(0, n):
  if i==n-1:
   base*=sumlist[n-i-1]
  else:
   base*=(sumlist[n-i-1]+1)
  prob+=(slist[n-i-1][c]/base)
 print(prob, end=' ')