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:
/*
 * Author:  xioumu
 * Created Time:  2012/10/8 15:34:52
 * File Name: d.cpp
 * solve: d.cpp
 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define sz(v) ((int)(v).size())
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repf(i, a, b) for (int i = (a); i <= (b); ++i)
#define repd(i, a, b) for (int i = (a); i >= (b); --i)
#define clr(x) memset(x,0,sizeof(x))
#define clrs( x , y ) memset(x,y,sizeof(x))
#define out(x) printf(#x" %d\n", x)
typedef long long lint;
const int maxint = -1u>>1;
const double esp = 1e-13;
const int maxn = 100 + 10;
const int maxm = 50 + 10;
double p[maxn], t[maxn], v[maxn];
int n, m, L;
double con[maxm][maxm];
double pow_p[maxn][maxm], pow_np[maxn][maxm], f[maxn][maxm], sum[maxn][maxm];
double ans[maxn];
double times[maxn][maxm];
int zore[maxn];
int sgn(double x) {
    return (x > esp) - (x < -esp);
}
bool cmp(const double &a, const double &b) {
    return sgn(a - b) < 0;
}
void init() {
    rep (i, n) {
        scanf("%lf%lf%lf", &p[i], &t[i], &v[i]);
        p[i] /= 100;
        zore[i] = 0;
        if(sgn(v[i]) == 0) {
            zore[i] = 1;
        }
    }
    con[0][0] = 1;
    repf (i, 1, m) {
        con[i][0] = con[i][i] = 1;
        repf (j, 1, i - 1)
            con[i][j] = con[i - 1][j] + con[i - 1][j - 1];
    }
    
    rep (i, n) {
        if(zore[i]) continue;
        pow_p[i][0] = 1;
        pow_np[i][0] = 1;
        times[i][0] = L * 1.0 / v[i];
        repf (j, 1, m) {
            pow_p[i][j] = pow_p[i][j - 1] * p[i];
            pow_np[i][j] = pow_np[i][j - 1] * (1 - p[i]);
            times[i][j] = times[i][j - 1] + t[i];
        }
    }
    
    rep (i, n) {
        if(zore[i]) continue;
        sum[i][0] = f[i][0] = con[m][0] * pow_np[i][m] * pow_p[i][0];
        repf (j, 1, m) {
            f[i][j] = con[m][j] * pow_np[i][m - j] * pow_p[i][j];
            sum[i][j] = sum[i][j - 1] + f[i][j];
        }
    }
}
double gao(double lim, int w) {
    //int h = m + 1;
    if(zore[w]) return 1;
    int h = upper_bound(times[w], times[w] + m + 1, lim, cmp) - times[w];
    //rep (i, m + 1)
        //if(sgn(times[w][i] - lim) > 0) {
            //h = i;
            //break;
        //}
    //printf("%d %d %f %f %f %f\n", h, hh, lim, times[w][h], times[w][hh], 1 - sum[w][h - 1]);
    //out(h);
    if(h - 1 < 0)  return 1;
    else return 1 - sum[w][h - 1];
}
int main()  {
    int blank = 0;
    while( scanf("%d%d%d", &n, &m, &L) == 3) {
        //if(blank) printf("\n");
        init();
        //if(n == 1) {
            //printf("%.8f\n", 1.0);
            //continue;
        //}
        rep (i, n) {
            ans[i] = 0;
            if(!zore[i]) 
                repf (j, 0, m) {
                    double res = 1;
                    rep (k, n) {
                        if(k == i) continue;
                        res *= gao(times[i][j], k);
                        //if(i == 1) printf("%f %f %d\n", gao(times[i][j], k), times[i][j], k);
                    }
                    //printf("%f %f %d %d\n", res, f[i][j], i, j);
                    ans[i] += res * f[i][j];
                }
            printf("%.12f\n", ans[i]);
            //if(i != n - 1) printf("\n");
        }
        //blank = 1;
    }
    return 0;
}