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;

typedef int64_t i64;
const int NMAX = 1000;
const long double eps = 1e-9;

int N, M, L;
int P[NMAX], T[NMAX], V[NMAX];
long double answer[NMAX];
vector<long double> value[NMAX], prob[NMAX];

int getSign(long double value) {
	if (value < -eps)
		return -1;
	if (value > eps)
		return 1;
	return 0;
}

i64 repeatedPerm(int a, int b) {
	unordered_map<int, int> primeFact;
	int c = a + b;
	for (int i = 2; i <= c; ++i) {
		int currNum = i;
		for (int j = 2; j <= sqrt(currNum) + 0.5; j += 2) {
			while (currNum % j == 0) {
				++primeFact[j];
				currNum /= j;
			}
			if (j == 2)
				j = 1;
		}
		if (currNum > 1)
			++primeFact[currNum];
	}
	for (int i = 2; i <= a; ++i) {
		int currNum = i;
		for (int j = 2; j <= sqrt(currNum) + 0.5; j += 2) {
			while (currNum % j == 0) {
				--primeFact[j];
				currNum /= j;
			}
			if (j == 2)
				j = 1;
		}
		if (currNum > 1)
			--primeFact[currNum];
	}
	for (int i = 2; i <= b; ++i) {
		int currNum = i;
		for (int j = 2; j <= sqrt(currNum) + 0.5; j += 2) {
			while (currNum % j == 0) {
				--primeFact[j];
				currNum /= j;
			}
			if (j == 2)
				j = 1;
		}
		if (currNum > 1)
			--primeFact[currNum];
	}

	i64 answer = 1;
	for (auto it: primeFact) {
		int curr = it.second;
		while (curr--)
			answer *= it.first;
	}
	return answer;
}

int main() {
//	assert(freopen("debug.in", "r", stdin));
//	assert(freopen("debug.out", "w", stdout));

	int i, j, k, l;

	cin >> N >> M >> L;
	for (i = 1; i <= N; ++i)
		cin >> P[i] >> T[i] >> V[i];

	for (i = 1; i <= N; ++i) {
		long double time = L / (long double)V[i];
		for (j = 0; j <= M; ++j, time += T[i]) {
			i64 currCases = repeatedPerm(j, M - j);
			long double probability = pow(P[i] / (long double)100, j) * pow(1 - P[i] / (long double)100, M - j);
			prob[i].push_back(probability * currCases);
			value[i].push_back(time);
		}
	}

	for (i = 1; i <= N; ++i) {
		for (j = 0; j <= M; ++j) {
			long double currProb = prob[i][j];
			for (k = 1; k <= N; ++k) {
				if (i == k)
					continue;
				long double nowProb = 0;
				for (l = M; l >= 0 && value[k][l] > value[i][j]; --l)
					nowProb += prob[k][l];
				currProb *= nowProb;
			}
			answer[i] += currProb;
		}
	}

	cout << fixed << setprecision(8);
	for (i = 1; i <= N; ++i)
		cout << answer[i] << '\n';

	return 0;
}