Implement Kac ring with O(1) color and kstep

You are implementing a Kac ring dynamical system.

Model

• There are N positions arranged in a circle, indexed clockwise: 0, 1, ..., N-1.
• Each position holds exactly one ball, whose color is either white or black.
• A subset of positions is marked.
• Initially (time t = 0), all balls are white.

One time step

At each step:

1. Every ball moves one position clockwise: a ball at position i moves to position (i + 1) mod N.
2. If a ball leaves a marked position (i.e., it was at a marked index before moving), it flips color (white ↔ black) as it moves.

Task

Implement a class/data structure with the following interface:

Initialization

KacRing(N, marked)

• N: number of positions.
• marked: a sorted list of distinct marked indices 0 <= y1 < ... < ym < N.

Methods

1. step()

   • Advances the system by exactly 1 time step.

2. kstep(k)

   • Advances the system by k time steps.
   • Must run in O(1) time per call (i.e., it must not loop for k steps).

3. color()

   • Returns the value:

$\frac{W - B}{N}$

 where `W` is the current number of white balls and `B` is the current number of black balls.

• Must run in O(1) time.

Notes / Constraints

• Assume 1 <= N.
• 0 <= len(marked) <= N.
• k can be very large (e.g., up to 10^18), so kstep cannot simulate step-by-step.
• You do not need to expose individual ball colors; only the required methods above.

Implement Kac Ring with O(1) color and kstep

You are simulating a Kac ring dynamical system. There are N positions in a circle, indexed 0 to N-1 clockwise. Each position holds one ball. A sorted list of distinct positions is marked. Initially, all balls are white.

In one time step, every ball moves one position clockwise, and any ball that leaves a marked position flips color (white <-> black).

In the original interview version, you would implement a class with methods step(), kstep(k), and color(). For judge compatibility, implement a function solution(N, marked, operations) that processes these method calls:

• ('step',) means call step()
• ('kstep', k) means call kstep(k)
• ('color',) means call color() and record its result

For each color query, return the exact value of (W - B) / N as a reduced string:

• use '0' for zero
• use an integer like '1' or '-1' if the denominator is 1
• otherwise use 'a/b' in lowest terms

Because k can be extremely large, kstep(k) must not simulate k individual steps. Under the constraints below, an O(N^2) preprocessing step is acceptable, but each processed operation should be O(1).

Examples

Example 1

Input: (5, [1, 3], [('color',), ('step',), ('color',), ('kstep', 3), ('color',), ('step',), ('color',)])
Output: ['1', '1/5', '1/5', '1']

Explanation: For this ring, the color sequence over one period is [1, 1/5, -3/5, -3/5, 1/5]. The queried times are 0, 1, 4, and 0 again.

Example 2

Input: (4, [], [('step',), ('kstep', 1000000000000000000), ('color',), ('step',), ('color',)])
Output: ['1', '1']

Explanation: With no marked positions, no ball ever flips, so all balls remain white forever.

Hints

1. After N steps, every ball has gone all the way around the ring once. What does that imply about the state, depending on whether the number of marked positions is even or odd?
2. For a fixed time t, a ball starting at position i flips once for each marked position in the cyclic window of length t starting at i. The total color value depends only on whether each such window contains an even or odd number of marked positions.

Approach

The trick is to compute the magnetization W - B as a function of the step count t in closed form, so every operation is just arithmetic on a time counter.

Sign cancellation. A ball's color is determined only by how many marked positions it has crossed: an even count means white, odd means black. The code encodes this with a prefix-sign array q over a doubled ring (2N+1 entries): q[i+1] = -q[i] when position i % N is marked, else q[i] = q[i+1]. Doubling the ring lets q[i+t] index past the end without manual wraparound.

Magnetization per step. A ball that started at i and has moved t steps has crossed exactly the marked positions in [i, i+t), so its color sign is q[i] * q[i+t] (the shared prefix cancels). Summing over all starting positions i gives magnetization[t] = W - B. The double loop over t and i is the allowed O(N²) preprocessing.

Period. Each marked position flips a ball once per lap. After N steps every ball has crossed len(marked) marks. If len(marked) is even, colors return to their step-0 pattern, so the magnetization sequence has period N. If odd, all colors invert, so magnetization[t+N] = -magnetization[t] and the true period is 2N — the code materializes both halves.

Queries. format_value reduces magnetization[t] / N with gcd ('0', integer, or 'a/b'). Each step/kstep just advances time = (time + k) % period (O(1), even for k up to 10¹⁸), and color reads values[time].

• Time complexity: O(N^2 + Q)
• Space complexity: O(N + Q)