Problem: 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=a;i<b;++i)
#define for_rev(i,a,b) for(int i=a;i>=b;--i)
#define allof(a) a.begin(),a.end()
#define minit(a,b) memset(a,b,sizeof(a))
#define size_of(a) (int)a.size()

typedef long long lint;
typedef pair<int, int> pii;
typedef double Double;

inline int POPCNT(int _x) { return __builtin_popcount(_x); }
inline int POPCNT(lint _x) { return __builtin_popcountll(_x); }

const int iINF = 1L << 30;
const lint lINF = 1LL << 60;
const Double EPS = 1e-9;

int N, M, L;
int P[110], T[110], V[110];

Double prob[110][55];
Double goal[110][55];

lint combination(int n, int m) {
	lint res = 1;
	if (2 * m > n) m = n - m;
	for_(i,0,m) res = res * (n - i) / (i + 1);
	return res;
}

Double calc_prob(int p, int s) {
	Double res = 1.0;
	
	Double time_p = goal[p][s];
	
	for_(i,0,N) {
		if (i == p) continue;
		Double sum = 0.0;
		int ind = upper_bound(goal[i], goal[i] + M + 1, time_p) - goal[i];
		for_(j,ind,M+1) sum += prob[i][j];
		res *= sum;
	}
	
	return res;
}

void solve() {
	for_(i,0,N) {
		Double f_goal = (Double)L / (Double)V[i];
		
		for_(j,0,M + 1) {
			prob[i][j] = (Double)combination(M, j) * pow((Double)P[i] / 100.0, j) * pow((Double)(100 - P[i]) / 100.0, M - j);
			goal[i][j] = f_goal + (Double)j * (Double)T[i];
		}
	}
	/*
	for_(i,0,N) {
		for_(j,0,M + 1) cout << prob[i][j] << " ";
		cout << endl;
	}
	*/
	
	for_(i,0,N) {
		Double ansi = 0.0;
		for_(j,0,M + 1) ansi += calc_prob(i, j) * prob[i][j];
		printf("%.9lf\n", ansi);
	}
}

int main() {
	cin >> N >> M >> L;
	for_(i,0,N) cin >> P[i] >> T[i] >> V[i];
	solve();
	return 0;
}