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 <cstdio>
#include <algorithm>
using namespace std;

const double EPS = 1e-8;
const int N = 105;
const int M = 55;

int n, m, l, t[N], v[N];
double dp[N][M];
double sum[N][M];

void gao(double p, double dp[], double sum[]) {
	double q = 1-p, f[2][M] = {};
	f[0][0] = 1;
	for (int i = 1, x = 1; i <= m; ++i, x^=1) {
		f[x][0] = f[!x][0] * q;
		for (int j = 1; j <= i; ++j) {
			f[x][j] = f[!x][j-1] * p + f[!x][j] * q;
		}
	}
	dp[m+1] = sum[m+1] = 0;
	for (int i = m, x = m & 1; i >= 0; --i) {
		sum[i] = sum[i+1] + (dp[i] = f[x][i]);
	}
}

// return true if (i,j) < (x,y)
bool faster(int i, int j, int x, int y) {
	return l*v[x] + t[i]*j*v[i]*v[x] < l*v[i] + t[x]*y*v[i]*v[x];
}

int binsearch(int i, int j, int k) {
	int l = -1, r = m+1, mid;
	while (l + 1 < r) {
		mid = (l+r)>>1;
		faster(i,j,k,mid) ? r=mid : l=mid;
	}
	return r;
}

void debug(double a[], int s, int t) {
	for(int i=s;i<t;++i)printf("%f ", a[i]);puts("");
}

int main() {
	while (3==scanf("%d%d%d", &n, &m, &l)) {
		for (int p,i = 0; i < n; ++i) {
			scanf("%d%d%d", &p, &t[i], &v[i]);
			gao(p/100., dp[i], sum[i]);
//			debug(dp[i], 0, m+2);
//			debug(sum[i], 0, m+2); 
		}
		for (int i = 0; i < n; ++i) {
			double ans = 0;
			for (int j = 0; j <= m; ++j) {
				double p = dp[i][j];
				for (int r,k = 0; k < n; ++k) {
					if (i == k) continue;
					r = binsearch(i, j, k);
					p *= sum[k][r];
				}
				ans += p;
			}
			printf("%.10f\n", ans);
		}
	}
}