N people run a marathon. There are M resting places on the way. For each resting place, the i-th runner takes a break with probability P_i percent. When the i-th runner takes a break, he gets rest for T_i time.

The i-th runner runs at constant speed V_i, and the distance of the marathon is L.

You are requested to compute the probability for each runner to win the first place. If a runner arrives at the goal with another person at the same time, they are not considered to win the first place.



Input

A dataset is given in the following format:

N M L
P_1 T_1 V_1
P_2 T_2 V_2
...
P_N T_N V_N


The first line of a dataset contains three integers N (1 \leq N \leq 100), M (0 \leq M \leq 50) and L (1 \leq L \leq 100,000). N is the number of runners. M is the number of resting places. L is the distance of the marathon.

Each of the following N lines contains three integers P_i (0 \leq P_i \leq 100), T_i (0 \leq T_i \leq 100) and V_i (0 \leq V_i \leq 100) describing the i-th runner. P_i is the probability to take a break. T_i is the time of resting. V_i is the speed.

Output

For each runner, you should answer the probability of winning. The i-th line in the output should be the probability that the i-th runner wins the marathon. Each number in the output should not contain an error greater than 10^{-5}.

Examples

Input

2 2 50
30 50 1
30 50 2


Output

0.28770000
0.71230000


Input

2 1 100
100 100 10
0 100 1


Output

0.00000000
1.00000000


Input

3 1 100
50 1 1
50 1 1
50 1 1


Output

0.12500000
0.12500000
0.12500000


Input

2 2 50
30 0 1
30 50 2


Output

0.51000000
0.49000000

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import bisect

def nCr(n, r):
	r = min(r, n - r)
	numerator = 1
	for i in range(n, n - r, -1):
		numerator *= i
	denominator = 1
	for i in range(r, 1, -1):
		denominator *= i
	return numerator // denominator
(n, m, l) = map(int, input().split())
data = [[0 for i in range(m + 1)] for i in range(n)]
for i in range(n):
	(p, t, v) = map(int, input().split())
	for j in range(m + 1):
		data[i][j] = (t * j + l / v if v != 0 else 9999999999999999, (p / 100.0) ** j * nCr(m, j) * (1 - p / 100.0) ** (m - j))
ans = []
for i in range(n):
	win = 0
	for j in range(m + 1):
		wintmp = data[i][j][1]
		for x in range(n):
			if i == x:
				continue
			tmp = 0
			for (a, b) in data[x][bisect.bisect_right(data[x], (data[i][j][0], 5)):]:
				tmp += b
			wintmp *= tmp
		win += wintmp
	ans.append(win)
for a in ans:
	print('%.8f' % a)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 13
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)
nm = {}

def nCr(n, b):
	if b > n - b:
		b = n - b
	key = (n, b)
	if key in nm:
		return nm[key]
	r = 1
	for k in range(n, n - b, -1):
		r = r * k
	d = 1
	for k in range(1, b + 1):
		d = d * k
	nm[key] = r / d
	return nm[key]

def main():
	rr = []
	(n, m, l) = LI()
	ps = [LI() for _ in range(n)]
	ts = []
	rs = []
	us = []
	for (p, t, v) in ps:
		if v == 0:
			ts.append(0)
			rs.append(0)
			us.append(0)
			continue
		p /= 100
		u = l / v
		ti = []
		ri = []
		for i in range(m + 1):
			ti.append(u + t * i)
			k = pow(1 - p, m - i) * pow(p, i) * nCr(m, i)
			ri.append(k)
		ts.append(ti)
		rs.append(ri)
		ui = ri[:]
		for i in range(1, m + 1):
			ui[i] += ui[i - 1]
		us.append(ui)
	for i in range(n):
		r = 0
		if ts[i] == 0:
			rr.append(r)
			continue
		for j in range(m + 1):
			tr = rs[i][j]
			tt = ts[i][j] + 1.0 / 10 ** 10
			for k in range(n):
				if i == k or ts[k] == 0:
					continue
				bi = bisect.bisect_left(ts[k], tt)
				if bi > 0:
					tr *= 1 - us[k][bi - 1]
			r += tr
		rr.append('{:.9f}'.format(r))
	return '\n'.join(map(str, rr))
print(main())