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:
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <double,double> P;
typedef pair <int,P > PP;
 
int tx[] = {0,1,0,-1};//URDL
int ty[] = {-1,0,1,0};
 
static const double EPS = 1e-12;

class State{
public:
  double probability;
  double cost;
  State(double _p,double _c) : probability(_p),cost(_c){}
  bool operator<(const State& s) const{
    return cost < s.cost;
  }
  bool operator>(const State& s) const{
    return cost > s.cost;
  }
};

int main(){
  int total_players;
  int total_resting_places;
  int goal_distance;
  while(~scanf("%d %d %d",&total_players,&total_resting_places,&goal_distance)){

    vector<vector<State> > players;

    for(int player_idx=0;player_idx<total_players;player_idx++){
      int probability;
      int resting_duration;
      int speed;
      scanf("%d %d %d",&probability,&resting_duration,&speed);
      
      double dp[51][5001];
      vector<State> player;
      memset(dp,0,sizeof(dp));

      dp[0][0] = 1.0;
      for(int resting_place_idx=0;resting_place_idx<total_resting_places;resting_place_idx++){
	for(int total_resting_duration = 0; total_resting_duration <= 5000; total_resting_duration++){
	  if(dp[resting_place_idx][total_resting_duration] <= EPS) continue;

	  dp[resting_place_idx+1][total_resting_duration + resting_duration]
	    += dp[resting_place_idx][total_resting_duration] * (double)probability/100.0;

	  dp[resting_place_idx+1][total_resting_duration]
	    += dp[resting_place_idx][total_resting_duration] * (1.0 - (double)probability/100.0);
	}
      }

      for(int total_resting_duration = 0; total_resting_duration <= 5000; total_resting_duration++){
	if(dp[total_resting_places][total_resting_duration] != 0){
	  // printf("rest:%d prob:%lf\n",total_resting_duration,dp[total_resting_places][total_resting_duration]);
	  player.push_back(State(dp[total_resting_places][total_resting_duration],total_resting_duration + (double)goal_distance/(double)speed));
	}
      }
      sort(player.begin(),player.end());
      players.push_back(player);
    }

    for(int player_idx=0;player_idx<total_players;player_idx++){

      double win_prob = 0.0;
      for(int state_idx=0;state_idx<players[player_idx].size();state_idx++){
	double cost = players[player_idx][state_idx].cost;
	double player_prob = players[player_idx][state_idx].probability;

	double rival_prob = 1.0;
	for(int rival_idx=0;rival_idx<total_players;rival_idx++){
	  if(player_idx == rival_idx) continue;
	  double tmp_prob = 0.0;
	  for(int rival_state_idx=0;rival_state_idx<players[rival_idx].size();rival_state_idx++){
	    if(players[rival_idx][rival_state_idx].cost > cost){
	      tmp_prob += players[rival_idx][rival_state_idx].probability;
	    }
	  }

	  rival_prob *= tmp_prob;
	}
	win_prob += player_prob * rival_prob;
      }

      printf("%.7lf\n",win_prob);
    }
  }
}