Overview

Instead of simulating reflections directly, consider an “unfolded diagram” where the table is mirrored and laid out alternately left and right. In this representation, the ball’s movement becomes a simple straight-line motion.
For each shot, count “how many boundaries were crossed,” then fold the position back into \([0,M]\) to obtain the final position and reflection count in \(O(1)\).

Analysis

The tricky part of this problem is that many reflections can occur during a single shot.

For example, if \(M=1\) and \(A_i=10^9\), an extremely large number of reflections can occur in just one shot.
Therefore, naive approaches such as:

• Moving one cell at a time
• Processing each reflection one by one

are far too slow.

Key Insight: Reflections become a straight line in the “unfolded diagram”

Instead of reflecting at the endpoints of the interval \([0,M]\), consider mirroring and laying out copies of the interval side by side.

For example, if \(M=5\), the unfolded diagram looks like:

• \([0,5]\)
• \([5,10]\) is left-right reversed
• \([10,15]\)
• \([15,20]\) is left-right reversed
• …

In this unfolded diagram, movements that actually involve reflections can be represented as simple straight-line motion.

Example

Suppose \(M=5\), starting at position \(2\), moving right by \(9\).

On the actual table:

• \(2 \to 5\): reflection
• \(5 \to 0\): reflection
• \(0 \to 1\)

On the other hand, in the unfolded diagram, we simply move in a straight line:

• \(2 \to 11\)

Since we cross the “boundaries at every multiple of \(M\)” at \(5\) and \(10\) during this movement, we know the reflection count is 2.

---

However, be careful about hitting outward from an endpoint

The problem statement has a special rule:

• Position is \(0\) and direction is L
• Position is \(M\) and direction is R

In these cases, the ball immediately reverses direction without consuming any distance, and this counts as 1 reflection.

For example:

• \(x=0\), direction L, \(A=6\)

First, there is an in-place reflection (1 reflection), then the ball moves right by 6.

This “in-place reflection” does not correspond to crossing a boundary in the unfolded diagram, so we add 1 separately and then process it as if the direction were reversed.

Also, when \(A_i=0\), the problem statement explicitly states “no reflection occurs,” so we exclude this case first.

---

The reflection count is “how many multiples of \(M\) are crossed”

In the unfolded diagram, let \(y_0\) be the starting position and \(y_1\) be the ending position of a shot.

Reflections occur each time the ball passes through a “boundary” at \(0, M, 2M, 3M, \dots\).

However, there is one important caveat:

• Even if the endpoint is exactly on a boundary, if movement ends there, no reflection occurs

The problem statement says reflection happens “if the ball reaches an endpoint and still has remaining distance.”
Therefore, the boundary at the endpoint itself should not be counted.

When moving right

If \(y_0 < y_1\), the reflection count is:

\[ \left\lfloor \frac{y_1-1}{M} \right\rfloor - \left\lfloor \frac{y_0}{M} \right\rfloor \]

We use \(y_1-1\) so that if \(y_1\) is exactly on a boundary, it is not counted.

When moving left

If \(y_1 < y_0\), the reflection count is:

\[ \left\lfloor \frac{y_0-1}{M} \right\rfloor - \left\lfloor \frac{y_1}{M} \right\rfloor \]

---

The final position folds back with period \(2M\)

Even after finding position \(y_1\) in the unfolded diagram, we need to map it back to \([0,M]\) on the actual table.

Since the reflection pattern repeats with period \(2M\):

\[ r = y_1 \bmod 2M \]

Then:

• If \(0 \le r \le M\), the position is simply \(r\)
• If \(M < r < 2M\), fold back to get \(2M-r\)

In other words:

\[ x = \begin{cases} r & (r \le M) \\ 2M-r & (r > M) \end{cases} \]

Algorithm

For each shot, do the following:

1. If \(A_i=0\), do nothing and move to the next shot.
2. Let the current position be \(x\), and set the starting position in the unfolded diagram as \(y_0=x\).
3. Determine the ending position \(y_1\) in the unfolded diagram based on the direction.
   • For L:
     • If \(x=0\), add 1 in-place reflection, and since the ball now moves right: \(y_1=x+a\)
     • Otherwise: \(y_1=x-a\)
   • For R:
     • If \(x=M\), add 1 in-place reflection, and since the ball now moves left: \(y_1=x-a\)
     • Otherwise: \(y_1=x+a\)
4. Count how many multiples of \(M\) are crossed between \(y_0\) and \(y_1\), and add to the reflection count.
   • If \(y_0<y_1\): $\( \left\lfloor \frac{y_1-1}{M} \right\rfloor - \left\lfloor \frac{y_0}{M} \right\rfloor \)$
   • If \(y_1<y_0\): $\( \left\lfloor \frac{y_0-1}{M} \right\rfloor - \left\lfloor \frac{y_1}{M} \right\rfloor \)$
5. Fold \(y_1\) back into \([0,M]\) to get the new position \(x\).
   • \(r = y_1 \bmod 2M\)
   • If \(r \le M\), then \(x=r\)
   • Otherwise, \(x=2M-r\)

Repeat this \(N\) times.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• \(A_i=0\) should be excluded first with highest priority. Even if at an endpoint facing outward, no reflection occurs in this case.

• The in-place reflection when hitting outward from an endpoint is added as 1 separately from boundary crossings.

• Since the endpoint being exactly on a boundary should not count as a reflection, the formulas use \(y_1-1\) or \(y_0-1\) for adjustment.

• Coordinates in the unfolded diagram can become negative, but in Python, // and % handle this correctly without issues.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    N = int(next(it))
    M = int(next(it))
    x = int(next(it))

    total_reflections = 0
    period = 2 * M

    for _ in range(N):
        c = next(it)
        a = int(next(it))

        if a == 0:
            continue

        y0 = x

        if c == b'L':
            if x == 0:
                total_reflections += 1
                y1 = x + a
            else:
                y1 = x - a
        else:  # c == b'R'
            if x == M:
                total_reflections += 1
                y1 = x - a
            else:
                y1 = x + a

        if y0 < y1:
            total_reflections += (y1 - 1) // M - y0 // M
        else:
            total_reflections += (y0 - 1) // M - y1 // M

        r = y1 % period
        x = r if r <= M else period - r

    print(x, total_reflections)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.