<|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\in\{-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 needed to solve the problem

### 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\cdot T)\bmod 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 = \(\left\lfloor \dfrac{p+T}{L}\right\rfloor\)
- if \(d=-1\): wraps = number of times it crosses 0 going backward, which can be computed as  
  \[
  \left\lfloor \frac{(L-p)+T-1}{L}\right\rfloor
  \]
  (with a careful special-case when \(p=0\), same formula but conceptually it “crosses immediately”)

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 based on the observations

### 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)\bmod 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:
      - let `ccw_final = slot_pos[i]`
      - pick candidate clockwise: first in `cw_info` with `final_pos > ccw_final`, wrap to begin if none
      - let its initial position be `p0`
      - earliest meeting time:
        - clockwise distance from `p0` to `q` (CCW start) is:
          - `dist = q - p0` if `q>=p0` else `q + L - p0`
        - meeting time `t0 = dist/2` (integer division is enough for the inequality check used here)
      - if `t0 <= T` then CCW takes that CW’s color, else keeps own

### Step 4 — Assign real identities by rotating slots
Sort indices `slot_order` by `slot_pos[]` (these are physical positions at time \(T\)).

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]`.

This yields arrays `final_pos[i], final_color[i], final_dir[i]` **in sorted-initial order**.

### 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++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    long long L;
    cin >> n >> L;

    vector<long long> p(n), c(n), d(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i] >> c[i] >> d[i]; // d is +1 or -1
    }
    long long T;
    cin >> T;

    auto mod = [&](long long x, long long m) -> long long {
        x %= m;
        if (x < 0) x += m;
        return x;
    };

    // 1) Sort chameleons by initial position => fixed cyclic order.
    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<long long> sp(n), sc(n), sd(n);
    for (int i = 0; i < n; i++) {
        sp[i] = p[order[i]];
        sc[i] = c[order[i]];
        sd[i] = d[order[i]];
    }

    // 2) Collect clockwise chameleons info: (cw_final_pos, sorted_index)
    vector<pair<long long,int>> cw_info;
    cw_info.reserve(n);
    for (int i = 0; i < n; i++) {
        if (sd[i] == 1) {
            long long f = mod(sp[i] + T, L);
            cw_info.push_back({f, i});
        }
    }
    sort(cw_info.begin(), cw_info.end());

    // 3) Compute cyclic shift by wrap counting on the unwrapped line.
    long long shift = 0;
    for (int i = 0; i < n; i++) {
        if (sd[i] == 1) {
            // number of times it passes multiples of L going forward
            shift += (sp[i] + T) / L;
        } else {
            // number of times it passes 0/multiples of L going backward
            // use the same careful ceiling-like formula as the known solution
            if (sp[i] == 0) shift -= (L + T - 1) / L;
            else           shift -= (L - sp[i] + T - 1) / L;
        }
    }
    shift = mod(shift, n); // normalize to [0, n)

    // 4) Build "slots": pass-through final positions, directions, and final colors.
    vector<long double> slot_pos(n);
    vector<long long> slot_dir(n), slot_color(n);

    for (int i = 0; i < n; i++) {
        slot_pos[i] = (long double)mod(sp[i] + sd[i] * T, L);
        slot_dir[i] = sd[i];

        if (sd[i] == 1) {
            // Clockwise never "receives" color.
            slot_color[i] = sc[i];
        } else {
            // Counter-clockwise might receive color from the last CW it meets.
            if (cw_info.empty()) {
                slot_color[i] = sc[i];
            } else {
                long long q = sp[i];
                long long ccw_final = (long long)slot_pos[i];

                // Find first clockwise final position strictly greater than ccw_final, wrap around.
                auto it = lower_bound(cw_info.begin(), cw_info.end(),
                                      make_pair(ccw_final + 1, -1));
                if (it == cw_info.end()) it = cw_info.begin();

                int cw_idx = it->second;      // index in sorted arrays
                long long p0 = sp[cw_idx];    // its initial position

                // Earliest meeting time on circle:
                // distance along clockwise direction from p0 to q, divided by 2.
                long long dist = (q >= p0) ? (q - p0) : (q + L - p0);
                long long t0 = dist / 2;

                if (t0 <= T) slot_color[i] = sc[cw_idx];
                else         slot_color[i] = sc[i];
            }
        }
    }

    // 5) Sort slots by their final positions (physical arrangement at time T).
    vector<int> slot_order(n);
    iota(slot_order.begin(), slot_order.end(), 0);
    sort(slot_order.begin(), slot_order.end(),
         [&](int a, int b) { return slot_pos[a] < slot_pos[b]; });

    // 6) Apply rotation shift to map initial identities to final slots.
    vector<long double> final_pos(n);
    vector<long long> final_color(n), final_dir(n);
    for (int i = 0; i < n; i++) {
        int slot = slot_order[(i + (int)shift) % n];
        final_pos[i] = slot_pos[slot];
        final_dir[i] = slot_dir[slot];
        final_color[i] = slot_color[slot];
    }

    // 7) Map back to original input order.
    vector<int> inv_order(n);
    for (int i = 0; i < n; i++) inv_order[order[i]] = i;

    cout << fixed << setprecision(10);
    for (int orig = 0; orig < n; orig++) {
        int idx = inv_order[orig]; // sorted-by-position index
        // Position must be in [0, L) (our mod ensures that).
        cout << (double)final_pos[idx] << " " << final_color[idx] << " " << final_dir[idx] << "\n";
    }

    return 0;
}
```

---

## 5) Python implementation with detailed comments

```python
import sys
import bisect

def mod(x: int, m: int) -> int:
    """Modulo in [0, m)."""
    x %= m
    if x < 0:
        x += m
    return x

def solve() -> None:
    data = sys.stdin.read().strip().split()
    it = iter(data)

    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))

    # 1) 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]

    # 2) 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

    # 3) 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

    # 4) 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]

    # 5) 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])

    # 6) 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]

    # 7) 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]
        # Print with enough precision; floats are accepted with 1e-9 tolerance.
        out.append(f"{final_pos[idx]:.10f} {final_color[idx]} {final_dir[idx]}")
    sys.stdout.write("\n".join(out))

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

If you want, I can also provide a small proof sketch for why the “candidate clockwise = first CW final position strictly greater than CCW final position” corresponds to the last meeting, and why the wrap-counting correctly yields the rotation on a circle.