Problem Description

Ringo is watching N ants walking on an infinitely long rod. Currently, the i-th ant is at coordinate \( X_i \) with speed \( S_i \) moving in direction \( D_i \). \( D_i \) being R means the ant is moving in the direction of increasing coordinates, and \( D_i \) being L means the ant is moving in the direction of decreasing coordinates.

Ringo can remove \( K \) ants from the rod. Find the maximum time until the first collision between the ants.

Input Format

The input is given from the standard input in the following format:

\( N \) \( K \) \( X_1 \) \( S_1 \) \( D_1 \) \( X_2 \) \( S_2 \) \( D_2 \) : \( X_N \) \( S_N \) \( D_N \)

• The first line contains two integers \( N\ (2\ ≦\ N\ ≦\ 10^5) \) and \( K\ (1\ ≦\ K\ ≦\ N-1) \) separated by a space, indicating \( N \) ants and \( K \) ants that Ringo can remove.
• The next \( N \) lines provide information about the ants. The \( i \)-th line ( \( 1\ ≦\ i\ ≦\ N \) ) contains integers \( X_i\ (0\ ≦\ X_i\ ≦\ 10^9) \), \( S_i\ (1\ ≦\ S_i\ ≦\ 10^6) \), and a character \( D_i \) ( \( D_i \) is either L or R ). This indicates that the \( i \)-th ant is initially at coordinate \( X_i \), moving at speed \( S_i \) in direction \( D_i \). It is guaranteed that all \( X_i \) are distinct.

Output Format

Output the maximum time until the first collision between the ants in one line. The output is accepted if the absolute or relative error is at most \( 10^{−6} \). If it is possible to prevent any collisions between the ants, output Infinity instead. End the output with a newline.

Sample Input and Output

Sample Input #1

3 1
4 2 R
7 1 L
0 4 R

Sample Output #1

2.000000000000000

Sample Input #2

7 2
1 3 L
2 3 R
3 2 L
4 2 L
5 4 R
6 5 L
9 1 R

Sample Output #2

1.333333333333333

Sample Input #3

2 1
0 1000000 R
1000000000 1000000 R

Sample Output #3

Infinity

Notes/Hints

Sample Explanation 1

When the second ant is removed, the time until the first collision between the ants is maximized.

Sample Explanation 2

Any number of decimal places in the output is acceptable.

见题面 Input 部分

见题面 Output 部分