509. Chameleons All Around

Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

There are n chameleons moving along a circle of length L with speed 1, each moving either clockwise or counter-clockwise. i-th chameleon is initially located at point pi and has color ci, which is represented by an integer number.

When two chameleons meet, the following happens:
  • The one that was traveling counter-clockwise changes color to the color of the clockwise one.
  • They turn around, so the one that was traveling counter-clockwise now travels clockwise, and vice versa.

    It's not so difficult to figure out that the ordering of chameleons among the circle always stays the same, and it is impossible for more than two chameleons to meet at the same point.

    What will be the locations and colors of all chameleons at time T (the input data describes time 0)?

    Input
    The first line of the input file contains an integer n, . The second line contains an integer L, 1 ≤ L ≤ 109. The next n lines contain 3 integers each, pi, ci, di — the location, color and direction of i-th chameleon, 0 ≤ pi < L, 1 ≤ ci ≤ 109, di is either -1 or 1. The last line contains an integer T, 0 ≤ T ≤ 1018.

    The coordinate system is chosen in such a way that increasing one's coordinate means moving clockwise, and points on the circle have coordinates between 0 (inclusive) and L (exclusive). di can take one of two values: 1 for moving clockwise, and -1 for moving counter-clockwise.

    All pi are different.

    Output
    Output n lines with 3 numbers each, one floating-point (location) and two integers (color and direction), having the same meaning as the input numbers, but describing time T. The chameleons should be described in the same order as in the input file. It is guaranteed that no chameleons will meet at exactly T. Your answer will be accepted when each number is within 10-9 relative or absolute error of the correct answer. Please note that the coordinate you output should always be more than or equal to 0 and strictly less than L. Your answer will not be accepted when you output a coordinate very close to L but the correct answer is 0.

    Example(s)
    sample input
    		 
    sample output
    		 
    4
13
2 1 1
0 2 -1
12 3 1
5 2 1
23

    2.000 2 1
12.000 1 1
9.000 3 1
3.000 3 -1