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 <math.h>
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# include <algorithm>
# include <iostream>

# define For(i,x,y)   for((i)=(x);i<(y);(i)++)
# define MAX(x,y)   ((x)>(y)? (x):(y))
# define MIN(x,y)   ((x)<(y)? (x):(y))
# define sz(a)      (sizeof(a))
# define mem(a)     (memset((a),0,sizeof(a)))

# define fop freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
# define print(x) (printf("%d\n",x))
# define scan(x) (scanf("%d",&x))
# define printc(x) (printf("%c\n",x))
# define scanc(x) (scanf("%c",&x))
# define INF 0x7fffffff

using namespace std;

typedef long long           ll;
ll c[55][55];
double a[105][55],f[105][55],p[105];
int t[105],v[105];
int main()
{
    int i,j,k,n,m,l,ii,jj;
    double ans,tot,tmp;
    c[0][0]=1;
    for (i=1;i<=50;i++)
      for (j=0;j<=i;j++)
        c[i][j]=c[i-1][j]+c[i-1][j-1];
    scan(n);scan(m);scan(l);
    //print(n);print(m);print(l);
    For(i,1,n+1)
    {
        scanf("%lf",&p[i]);
        p[i]=p[i]/100.0;
        scan(t[i]);scan(v[i]);
    }
    For(i,1,n+1)
      For(j,0,m+1)
      {
          a[i][j]=pow(p[i],j)*c[m][j]*pow(1-p[i],m-j);
          if (v[i])
          {
              f[i][j]=(double)l/(double)v[i];
              f[i][j]+=j*t[i];
          }
          else f[i][j]=INF;
      }
    For (i,1,n+1)
    {
        ans=0;
        For (j,0,m+1)
        {
            tmp=a[i][j];
            For(ii,1,n+1) if (ii!=i)
            {

              tot=0;
              For (jj,0,m+1)
                if (f[i][j]<f[ii][jj])
                  tot+=a[ii][jj];
              tmp*=tot;
            }
            ans+=tmp;
        }
        printf("%.8lf\n",ans);
    }
    return 0;
}