====== Coloring 2: Electric Boogaloo ======

===== 풀이 =====
  * 특정 열이나 행을 두 번 뒤집으면 안 뒤집은 것과 동일하다. 어떤 열이나 행을 10000번 뒤집는다고 해도, 그동안 가질 수 있는 상태는, 뒤집혔거나 안 뒤집혔거나의 두 가지 밖에 없다. 
  * 어떤 열을 뒤집었을때의 효과는 모든 행에 동일하게 적용된다. 행과 열을 바뀌도 마찬가지. 그러므로 어떤 격자판에서 유의미하게 구분되는 행동은 안뒤집힌 행을 뒤집는다, 뒤집힌 행을 되돌린다, 안뒤집힌 열을 뒤집는다, 뒤집힌 열을 되돌린다 의 네가지 밖에 없다. 
  * 안 뒤집힌 행을 뒤집는 행동을 취할 때, 검은색 칸의 개수가 어떻게 바뀌는지는 뒤집혀진 열의 개수에만 의존한다. x개의 열이 뒤집혀져 있는 경우에, 안 뒤집힌 행 안에는 x개의 검은색 칸과 n-x개의 흰색 칸이 있다. 이것을 뒤집으면 검은색 칸의 개수는 n-x개가 되고, 바꿔 말하면 검은색 칸의 개수가 n-2x 개만큼 늘어난다. 반대로 뒤집힌 행을 되돌릴 때는 검은색 칸의 개수가 n-2x 개만큼 줄어든다. 행과 열을 바꿔도 마찬가지.
  * 격자판 전체를 기준으로 생각하면, 격자판의 상태는 뒤집힌 행의 개수, 뒤집힌 열의 개수만으로 표현할수 있다. 취할수 있는 행동도 이것으로 결정된다. 4가지 가능한 행동중 모든 행이 뒤집혀 있다면, 행을 뒤집는 행동은 취할수 없고, 모든 행이 안 뒤집혀있다면, 행을 되돌리는 행동은 취할수 없다. 
  * 이제 각 $Q_i$ 에 대해서 가능한 행동중에서 저 값을 만족시키는 행동이 있다면 그 행동을 취하고 뒤집힌 행과 열의 개수를 업데이트해주고, 만족시키는 행동이 없다면 불가능을 출력하는 식으로 처리하면, 주어진 Q가 가능한 수열인지 불가능한 수열인지의 여부를 쉽게 파악할 수 있다.
    * $Q_i$를 만족시키는 행동이 여러가지가 있을 수도 있다. 이것 때문에 백트래킹 등을 동원해서 모든 경우를 다 확인해야 해야 할지 걱정할수도 있으나, 문제에서 주어진 n은 홀수라는 조건 때문에 그러한 경우는 없다. 각 행동에서 일어날수 있는 검은칸 개수의 변화량은 n-2r, 2r-n, n-2c, 2c-n 뿐인데 (r은 뒤집힌 행 개수, c는 뒤집힌 열 개수), 이 중에서 두개 이상이 같은 값을 가지는 경우는 r==c 인 경우 밖에 없다. 그리고 r==c 라면 그냥 열을 뒤집는 것과 행을 뒤집는 행위는 본질적으로 동일하다. (행을 뒤집고 그냥 격자판을 90도 회전시키면 열을 뒤집는 것과 동일). 그래서 r==c 일경우에 열을 뒤집어서 수열을 구성할수 있다면, 행을 뒤집어서도 수열을 구성할수 있다. 
  * 문제에서 요구한 것은 수열의 구성 가능 여부가 아니라, 진짜로 수열을 구성하라는 것이다. 그렇다면 뒤집힌 행과 열의 개수 뿐만 아니라, 어떤 열과 행이 뒤집혔는지를 상태로 저장하고 있어야 뒤집을 열과 행을 정할수 있을것이라 생각할수도 있지만, 간단한 트릭으로 해결 가능하다. 항상 1~r번째 열은 뒤집힌 상태, r~N번째 열은 안 뒤집힌 상태로 유지하면 된다. 안뒤집힌 열을 뒤집어야 할 경우에는 r번째 열을 뒤집고 r을 1 증가시키면 되고, 뒤집힌 열을 되돌릴 때에는 r-1번째 열을 되돌리고 r을 1 감소시키면 되므로, 결국 r,c만 유지하고 있으면 수열 구성도 똑같이 가능하다
  * 각 Q_i에 대해서 어떤 행동을 취할지 결정하고, 행동을 취한 뒤의 상태를 업데이트하는 것까지 O(1)에 처리 가능하므로, 총 시간복잡도는 O(Q)이다.


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 32381. Coloring 2: Electric Boogaloo".

- Problem link: https://www.acmicpc.net/problem/32381
- Solution link: http://www.teferi.net/ps/problems/boj/32381
"""


def main():
    N, Q = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    black_counts = [int(x) for x in input().split()]

    flipped_col_count = flipped_row_count = 0
    black_count_cur = 0
    answer = []
    for b in black_counts:
        black_count_prev, black_count_cur = black_count_cur, b
        inc = black_count_cur - black_count_prev
        if inc == N - (flipped_col_count * 2) and flipped_row_count < N:
            answer.append(f'R {flipped_row_count + 1}')
            flipped_row_count += 1
        elif inc == -(N - (flipped_col_count * 2)) and flipped_row_count > 0:
            answer.append(f'R {flipped_row_count}')
            flipped_row_count -= 1
        elif inc == N - (flipped_row_count * 2) and flipped_col_count < N:
            answer.append(f'C {flipped_col_count + 1}')
            flipped_col_count += 1
        elif inc == -(N - (flipped_row_count * 2)) and flipped_col_count > 0:
            answer.append(f'C {flipped_col_count}')
            flipped_col_count -= 1
        else:
            print('-1')
            break
    else:
        print('\n'.join(answer))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}