<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

<|response|>
1. Abridged Problem Statement
There are **n** chameleons on a circle of length **L**. Chameleon i starts at position p_i, has color c_i, and moves at speed 1 in direction d_i ∈ {-1,+1} (clockwise = +1).

When two chameleons meet:
- the one that was moving counter-clockwise takes the color of the one moving clockwise;
- both reverse direction.

No meeting happens exactly at time **T**.
Output, in the original input order, each chameleon's position (in [0,L)), color, and direction at time **T**.

2. Key Observations

Observation A — "Bounce" is equivalent to "pass-through" for positions
If two identical particles reverse direction upon collision, you can instead imagine they pass through each other; the set of occupied positions over time is unchanged.
Here collisions also change colors, but the position multiset at time T is still the same as in the pass-through model:
x_i(T) = (p_i + d_i*T) mod L

Observation B — Cyclic order is preserved
The statement hints it: chameleons never overtake each other. Thus, if you sort by position at time 0, then at time T the sorted order is the same up to a cyclic rotation.

So the real problem becomes:
1. compute all pass-through final positions,
2. sort them to get "slots on the circle" at time T,
3. figure out the rotation shift that maps initial cyclic order to final cyclic order.

Observation C — The rotation shift can be computed via wrap-counting
Work on an "unwrapped" line with copies every L. Each chameleon moving:
- clockwise: goes from p to p+T,
- counter-clockwise: goes from p to p-T.

Each time a trajectory crosses a multiple of L (equivalently crosses the cut at 0 on the circle), the cyclic order representation rotates by ±1:
- clockwise wrap contributes +1
- counter-clockwise wrap contributes -1

Counts:
- if d=+1: wraps = floor((p+T)/L)
- if d=-1: wraps = floor((L-p+T-1)/L) (careful special-case when p=0)

Summing these contributions over all chameleons gives `shift` (mod n).

Observation D — Color evolution is one-way: only CCW receives color
Rule: only the counter-clockwise chameleon changes color; it takes the color of the clockwise one it meets. Therefore:
- A chameleon moving clockwise in pass-through model keeps its original color.
- A counter-clockwise chameleon's final color becomes the color of the last clockwise chameleon it met before time T, if any.

In the unwrapped/pass-through viewpoint, for a counter-clockwise chameleon, that "last met clockwise" can be found by:
- looking at clockwise chameleons' final positions (pass-through),
- taking the first clockwise final position strictly greater than this CCW final position (wrapping around),
- verifying they indeed meet by time T using a simple meeting-time formula (distance/2).

3. Full Solution Approach

Step 0 — Sort by initial position
Create permutation `order` sorting indices by p_i. Build arrays sp, sc, sd in this cyclic order.

Step 1 — Precompute clockwise chameleons info (for colors)
For each chameleon with sd[i]==+1, compute its pass-through final position f_i = (sp[i]+T) mod L. Store pairs (f_i, i) in `cw_info` and sort by f_i.

Step 2 — Compute cyclic rotation shift
Initialize shift = 0.
For each chameleon in sorted order:
- if sd[i]==+1: shift += (sp[i]+T)/L
- else:
  - if sp[i]==0: shift -= (L+T-1)/L
  - else: shift -= (L - sp[i] + T - 1)/L

Finally shift = ((shift % n) + n) % n.

Step 3 — Compute pass-through "slot" data at time T
For each sorted chameleon i:
- slot_pos[i] = (sp[i] + sd[i]*T) mod L
- slot_dir[i] = sd[i] (pass-through model)
- compute slot_color[i]:
  - if sd[i]==+1: slot_color[i]=sc[i]
  - else (CCW):
    - if no clockwise chameleons: keep own color
    - else find candidate CW with first final_pos > ccw_final (wrap around)
    - compute t0 = clockwise-distance/2
    - if t0 <= T: CCW takes that CW's color, else keeps own

Step 4 — Assign real identities by rotating slots
Sort indices slot_order by slot_pos[]. Because real identities are a cyclic rotation of these slots:
- for each sorted-initial index i, its real output is slot slot_order[(i+shift)%n].

Step 5 — Map back to original input order
Build inverse mapping inv_order[original_index] = sorted_index. Output final_*[inv_order[i]] for i from 0..n-1.

Complexity: sorting and per-CCW binary searches → O(n log n), fits easily.

4. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
int64_t L, T;
vector<int64_t> p, c, d;

void read() {
    cin >> n >> L;
    p.resize(n);
    c.resize(n);
    d.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> p[i] >> c[i] >> d[i];
    }
    cin >> T;
}

void solve() {
    // The solution uses a semi-popular trick about problems where there are
    // moving people / objects and they bump each other which results in them
    // changing directions. Conceptually the trick is simple - instead of them
    // changing directions, we can actually assume they simply pass each other
    // and instead possibly swap some attributes. This way, we can think of the
    // process as a set of N linear functions with slopes 1 or -1 (cw and ccw).
    // The colors are also simple to deduce at each time T as none of the d=1
    // lines ever change their color, while the d=-1 lines' colors are always
    // based on the last d=1 they intersect, meaning we can binary search to
    // find this.
    //
    // Something we haven't mentioned yet is that we actually have a circle and
    // not an infinite line in terms of the intersections. To solve this, we can
    // model each chameleon as an infinite number of lines. Say the initial
    // location was y. We then will have copies of the line at y+c*L for any c
    // \in Z. This way at any T, we can only look at the lines that fall into y
    // \in [0, L) - we can prove easily that there are exactly N of them.
    //
    // We should be a bit careful about the order of the chameleons - when we go
    // to the concept of lines, we assume that they cross each other, while in
    // reality they turn around. We need this as we ultimately want to
    // reconstruct the answer. The core observation is that when the chameleons
    // bump, they never change their relative order. However, we still need to
    // find where at least one of these chameleons is. Let's look at the y=0
    // line, and the d=1 and d=-1 intersections with it. If the first
    // intersection is with d=-1, then the N-th chameleon crossed and became the
    // first. Then if the next intersection was with d=1, it means that that
    // same chameleon (note relative order is always the same so we know it's
    // that particular chameleon) crossed back and became the N-th again. This
    // argument can be further generalized, and we can see that each d=1
    // corresponds to right cyclic shift, and each d=-1 corresponds to a left
    // one. Therefore, for every line with binary search or simple math we can
    // figure out the number of c values (clones) that will intersect with y=0
    // until time T. Then we can sum the contributions based on d=1 and d=-1 and
    // get the final "cyclic" shift of the ordering.
    //
    // The above is enough to craft some solution running in O(N log N), but we
    // will now describe how to implement it cleanly.  For simplicity, let's
    // first sort all chameleons by their initial positions and we will remap
    // when we output. We have the invariant that every chameleon appears at
    // y+c*L is kept for any time T, so we know that we can simply get the set
    // of final positions as (p+T*d) mod L. The relative order is kept, so we
    // only want to find which of them is the first. Here comes the second
    // observation about intersections with y=0, and cyclic shifts. We should
    // be a bit careful about points with p=0 when we start.

    auto mod = [](int64_t x, int64_t m) { return ((x % m) + m) % m; };

    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [](int i, int j) { return p[i] < p[j]; });

    vector<int64_t> sorted_p(n), sorted_c(n), sorted_d(n);
    for(int i = 0; i < n; i++) {
        sorted_p[i] = p[order[i]];
        sorted_c[i] = c[order[i]];
        sorted_d[i] = d[order[i]];
    }

    vector<pair<int64_t, int>> cw_info;
    for(int i = 0; i < n; i++) {
        if(sorted_d[i] == 1) {
            int64_t final_pos = mod(sorted_p[i] + T, L);
            cw_info.push_back({final_pos, i});
        }
    }
    sort(cw_info.begin(), cw_info.end());

    vector<int64_t> cw_final;
    for(int i = 0; i < (int)cw_info.size(); i++) {
        cw_final.push_back(cw_info[i].first);
    }

    int64_t shift = 0;
    for(int i = 0; i < n; i++) {
        if(sorted_d[i] == 1) {
            shift += (sorted_p[i] + T) / L;
        } else {
            if(sorted_p[i] == 0) {
                shift -= (L + T - 1) / L;
            } else {
                shift -= (L - sorted_p[i] + T - 1) / L;
            }
        }
    }
    shift = mod(shift, n);

    vector<double> slot_pos(n);
    vector<int64_t> slot_dir(n);
    vector<int64_t> slot_color(n);

    for(int i = 0; i < n; i++) {
        slot_pos[i] = mod(sorted_p[i] + T * sorted_d[i], L);
        slot_dir[i] = sorted_d[i];

        if(sorted_d[i] == 1) {
            slot_color[i] = sorted_c[i];
        } else {
            if(cw_info.empty()) {
                slot_color[i] = sorted_c[i];
            } else {
                int64_t q = sorted_p[i];
                int64_t ccw_final_pos = slot_pos[i];
                auto it = lower_bound(
                    cw_info.begin(), cw_info.end(),
                    make_pair(ccw_final_pos + 1, -1)
                );
                if(it == cw_info.end()) {
                    it = cw_info.begin();
                }
                int64_t p = sorted_p[it->second];
                int64_t t0 = (q >= p) ? (q - p) / 2 : (q + L - p) / 2;
                if(t0 > T) {
                    slot_color[i] = sorted_c[i];
                } else {
                    slot_color[i] = sorted_c[it->second];
                }
            }
        }
    }

    vector<int> slot_order(n);
    iota(slot_order.begin(), slot_order.end(), 0);
    sort(slot_order.begin(), slot_order.end(), [&](int i, int j) {
        return slot_pos[i] < slot_pos[j];
    });

    vector<double> final_pos(n);
    vector<int64_t> final_color(n), final_dir(n);

    for(int i = 0; i < n; i++) {
        int slot = slot_order[mod(i + shift, n)];
        final_pos[i] = slot_pos[slot];
        final_dir[i] = slot_dir[slot];
        final_color[i] = slot_color[slot];
    }

    vector<int> inv_order(n);
    for(int i = 0; i < n; i++) {
        inv_order[order[i]] = i;
    }

    cout << fixed << setprecision(3);
    for(int i = 0; i < n; i++) {
        int idx = inv_order[i];
        cout << final_pos[idx] << " " << final_color[idx] << " "
             << final_dir[idx] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Solution
```python
import sys
import bisect

def mod(x: int, m: int) -> int:
    """Mathematical modulo in [0, m)."""
    return (x % m + m) % m

def solve() -> None:
    it = iter(sys.stdin.read().strip().split())
    n = int(next(it))
    L = int(next(it))

    p = [0] * n
    c = [0] * n
    d = [0] * n
    for i in range(n):
        p[i] = int(next(it))
        c[i] = int(next(it))
        d[i] = int(next(it))

    T = int(next(it))

    # Sort by initial position to get stable cyclic order.
    order = list(range(n))
    order.sort(key=lambda i: p[i])

    sp = [p[i] for i in order]
    sc = [c[i] for i in order]
    sd = [d[i] for i in order]

    # Collect clockwise info: (cw_final_pos, sorted_index).
    cw_info = []
    for i in range(n):
        if sd[i] == 1:
            cw_info.append((mod(sp[i] + T, L), i))
    cw_info.sort()
    cw_final_positions = [x for x, _ in cw_info]  # for bisect

    # Compute cyclic shift via wrap counting.
    shift = 0
    for i in range(n):
        if sd[i] == 1:
            shift += (sp[i] + T) // L
        else:
            if sp[i] == 0:
                shift -= (L + T - 1) // L
            else:
                shift -= (L - sp[i] + T - 1) // L
    shift %= n

    # Pass-through slots + compute final colors.
    slot_pos = [0]*n
    slot_dir = [0]*n
    slot_color = [0]*n

    for i in range(n):
        slot_pos[i] = mod(sp[i] + sd[i]*T, L)
        slot_dir[i] = sd[i]

        if sd[i] == 1:
            slot_color[i] = sc[i]
        else:
            if not cw_info:
                slot_color[i] = sc[i]
            else:
                q = sp[i]
                ccw_final = slot_pos[i]

                # first CW with final_pos > ccw_final, wrap around
                j = bisect.bisect_left(cw_final_positions, ccw_final + 1)
                if j == len(cw_info):
                    j = 0
                _, cw_idx = cw_info[j]

                p0 = sp[cw_idx]
                dist = (q - p0) if q >= p0 else (q + L - p0)
                t0 = dist // 2

                slot_color[i] = sc[cw_idx] if t0 <= T else sc[i]

    # Sort by final positions to get physical slot order at time T.
    slot_order = list(range(n))
    slot_order.sort(key=lambda i: slot_pos[i])

    # Apply rotation shift.
    final_pos = [0]*n
    final_dir = [0]*n
    final_color = [0]*n
    for i in range(n):
        slot = slot_order[(i + shift) % n]
        final_pos[i] = slot_pos[slot]
        final_dir[i] = slot_dir[slot]
        final_color[i] = slot_color[slot]

    # Map back to original input order.
    inv_order = [0]*n
    for sorted_i, orig_i in enumerate(order):
        inv_order[orig_i] = sorted_i

    out = []
    for orig_i in range(n):
        idx = inv_order[orig_i]
        out.append(f"{final_pos[idx]:.3f} {final_color[idx]} {final_dir[idx]}")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()
```
