Overview

We maintain the “position, top face, and front face” for each die and sequentially simulate the rolling operations for the specified dice. Each operation can be processed in constant time.

Analysis

The dice do not affect each other, and multiple dice can occupy the same square. Therefore, we do not need to manage the state per square; maintaining the current state for each die is sufficient.

Furthermore, letting \(u\) be the current top face and \(f\) be the current front face, the state after rolling is determined as follows:

• + direction:

  • Increase the position by \(1\)
  • The new top face is \(7-f\)
  • The new front face is \(u\)

• - direction:

  • Decrease the position by \(1\)
  • The new top face is \(f\)
  • The new front face is \(7-u\)

Since the sum of numbers on opposite faces is \(7\), the back face (opposite to the front) is \(7-f\), and the bottom face (opposite to the top) is \(7-u\). Thus, it is not necessary to manage all six faces including the left and right faces.

For example, if a die with top face \(1\) and front face \(2\) is rolled in the + direction:

• New top face: \(7-2=5\)
• New front face: \(1\)

Since the number of squares \(M\) is up to \(10^9\), we cannot use an array indexed by squares. Also, searching for the target die on each operation would result in \(O(NQ)\) worst-case time complexity, which is too slow. By mapping the die index to an array index, we can update the target state in \(O(1)\) time.

Algorithm

1. For each die, store the following three values in arrays:
   • Current position pos
   • Current top face top
   • Current front face front
2. Process each operation \((d,c)\) in the order of input.
3. Save the top face of die \(d\) before the update as \(u\), and the front face as \(f\).
4. Update the state according to the direction.
   • For +:
     • pos[d] += 1
     • top[d] = 7 - f
     • front[d] = u
   • For -:
     • pos[d] -= 1
     • top[d] = f
     • front[d] = 7 - u
5. After processing all operations, output the position and top face of each die.

Complexity

• Time Complexity: \(O(N+Q)\)
• Space Complexity: \(O(N)\)

Implementation Notes

Before updating the state, you need to save the old top face and front face in variables u and f, respectively. If you overwrite top first and then update front using that new value, you will lose the original top face, resulting in an incorrect answer.

Also, if receiving input with sys.stdin.buffer.readline, the direction character will be bytes rather than a string. Therefore, use c == b'+' to check for +.

The problem guarantees that the position is always between \(1\) and \(M\) inclusive, so there is no need to separately check whether it is out of bounds.

Source Code

import sys

def main():
    input = sys.stdin.buffer.readline

    N, M, Q = map(int, input().split())

    pos = [0] * N
    top = [0] * N
    front = [0] * N

    for i in range(N):
        pos[i], top[i], front[i] = map(int, input().split())

    for _ in range(Q):
        d, c = input().split()
        i = int(d) - 1
        u = top[i]
        f = front[i]

        if c == b'+':
            pos[i] += 1
            top[i] = 7 - f
            front[i] = u
        else:
            pos[i] -= 1
            top[i] = f
            front[i] = 7 - u

    sys.stdout.write('\n'.join(
        f'{pos[i]} {top[i]}' for i in range(N)
    ))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.6-sol-high.