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>
#define N 101
#define M 51
using namespace std;
int n,m,l;
double p[N],t[N],d[N];
vector<double> A[N],B[N];

double nCr(int n, int r){
  if(r==0||n==r)return 1;
  double a=1;
  for(int i=0;i<r;i++) a*=(n-i)/(i+1.0);
  return a;
}

double DP(){
  double dp[N][M]={};
  for(int i=0;i<=m;i++)dp[0][i]=A[0][m-i]*B[0][i]*nCr(m,i);
  
  for(int i=1;i<n;i++)
    for(int j=0;j<=m;j++)
      for(int k=0;k<=m;k++)
	if(d[0]+j*t[0]<d[i]+k*t[i]) 
	  dp[i][j]+=dp[i-1][j]*A[i][m-k]*B[i][k]*nCr(m,k);

  double res=0;
  for(int i=0;i<=m;i++)res+=dp[n-1][i];
  return res;
}

int main(){
  cin>>n>>m>>l;
  for(int i=0;i<n;i++)cin>>p[i]>>t[i]>>d[i],p[i]/=100,d[i]=l/d[i];
  for(int i=0;i<n;i++) {
    //A???j?????????????????£????¢????
    //B???j?????????????¢???????
    A[i]=B[i]=vector<double>(m+1,0);
    A[i][0]=B[i][0]=1;
    for(int j=1;j<=m;j++){
      A[i][j]=A[i][j-1]*(1-p[i]);
      B[i][j]=B[i][j-1]*p[i];
    }
  }
  for(int i=0;i<n;i++){
      printf("%.10f\n",DP());
      swap(p[0],p[i+1]);
      swap(t[0],t[i+1]);
      swap(d[0],d[i+1]);    
      swap(A[0],A[i+1]);    
      swap(B[0],B[i+1]);    
  }
  return 0;
}