你是一位竞赛评委，正在为一场比赛构建题目集。你拥有一个候选题目池。对于每个题目，你已经确定了参赛队伍能够解决该题的概率，以及如果他们能够解决该题，完成解答所需的时间。所有题目的完成时间各不相同。

你知道所有参赛队伍在面对题目集时都会采取相同的策略。首先，他们会确定自己能够解决的题目集合（假设他们在比赛开始时能瞬间完成此判断）。然后，他们会在时间限制内尽可能多地解决这些题目。如果存在多个能在时间限制内解决的题目子集，他们会首先通过解决题目的数量来打破平局（优先选择题目数量更多的子集），如果数量仍然相同，则通过最小化解决这些题目所需的总时间来打破平局。

定义一个题目的“难度”（Difficulty）为：如果该题目被包含在一个大小为 $k$ 的题目集中（该题目集由该题目以及从题目池中随机均匀选择的另外 $k-1$ 个题目组成），参赛队伍能够解决该题目的概率。请计算所有题目的难度。

输入格式

输入的第一行包含三个整数 $n, k$ ($1 \le k \le n \le 50$) 和 $t$ ($1 \le t \le 2500$)，其中 $n$ 是题目池中的题目总数，$k$ 是要选择的题目集大小，$t$ 是比赛的时间限制。

接下来的 $n$ 行，每行包含一个实数 $p$ ($0.0 \le p \le 1.0$) 和一个整数 $s$ ($1 \le s \le t$)，描述一个题目，其中 $p$ 是队伍能够解决该题的概率，$s$ 是解决该题所需的时间。概率最多包含四位小数。所有题目的解决时间各不相同。

输出格式

输出 $n$ 行，每行包含一个实数，表示对应题目在输入顺序下的难度。每个值必须精确到绝对或相对误差不超过 $10^{-6}$。

样例

样例输入 1

3 1 100
0.3432 99
0.1231 100
0.5878 1

样例输出 1

0.343200
0.123100
0.587800

样例输入 2

3 2 100
0.3432 99
0.1231 100
0.5878 2

样例输出 2

0.242334
0.065797
0.587800