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 <map>
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;

int p[100];
int t[100];
int v[100];

double rui[100];
double ruitmp[100];
double ans[100];

int main(){
  int n,m,l;
  scanf("%d%d%d", &n, &m, &l);

  REP(i,n) scanf("%d%d%d", p+i, t+i, v+i);
  REP(i,n) rui[i] = ans[i] = 0.0;

  vector<pair<double,pair<int,int> > > vv;
  map<double, int> cnt;

  REP(i,n) REP(j,m + 1){
    double tm = (double)l / v[i] + t[i] * j;
    vv.push_back(make_pair(tm, make_pair(i, j)));
    cnt[tm]++;
  }

  sort(vv.begin(), vv.end());
  vector<pair<int, double> > buff;

  REP(i,vv.size()){
    {
      int id = vv[i].second.first;
      int rest = vv[i].second.second;
      
      double rp = 1.0; // p^rest * (1-p)^(m-rest) * m C rest
      REP(j,rest){
	rp *= (p[id] / 100.0);
	rp *= (double)(m - j) / (rest - j);
      }
      REP(j,m-rest){
	rp *= 1 - (p[id] / 100.0);
      }

      ruitmp[id] += rp;

      buff.push_back(make_pair(id, rp));
      rui[id] += rp;
    }

    if(i == vv.size() - 1 || vv[i].first != vv[i+1].first){
      REP(ii, buff.size()){
	double rp = buff[ii].second;
	int id = buff[ii].first;
	double prob = 1.0;
	REP(j,n) if(id != j){
	  prob *= (1.0 - rui[j]);
	}
	ans[id] += prob * rp;	
      }
      buff.clear();
    }
  }

  REP(i,n) printf("%.6f\n", ans[i]);

  return 0;
}