Coloring 2: Electric Boogaloo

시간 제한2초메모리 제한1024 MB

요약
홀수 N x N 격자에서 행이나 열을 뒤집은 뒤의 검은 칸 개수가 Q개 주어질 때, 가능한 뒤집기 순서를 복원하거나 불가능하면 -1을 출력한다.
난이도

보통10점 중 7점

유형
수학, 구현, 그리디, 해시맵
정답자
아직 제출이 없습니다

문제

병윤이는 N×NN \times N 크기의 격자판을 가지고 재밌는 놀이를 하고 있다.

병윤이는 처음에 모든 칸이 흰색인 격자판으로 놀이를 시작하며, 다음과 같은 행동을 QQ회 반복한다.

  • 격자판의 행 또는 열을 하나 골라, 해당하는 행 또는 열을 뒤집는다. 뒤집는다는 것은 행 또는 열에 속한 모든 흰색 칸을 검은색으로, 검은색 칸을 흰색 칸으로 바꾸는 것을 의미한다.
  • 현재 격자판에 있는 검은색 칸의 개수를 외친다.

병윤이가 QQ회에 걸쳐 외친 개수가 주어지면, 역으로 병윤이가 무슨 행동을 하였는지 알아내는 프로그램을 작성해 보자.

입력

첫째 줄에 정수 NN, QQ가 공백으로 구분되어 주어진다. (1≤N≤109,N(1 \le N \le 10^9, N은 홀수;1≤Q≤300,000); 1 \le Q \le 300\\,000)

둘째 줄에 QQ개의 정수 Q_iQ\_i가 공백으로 구분되어 주어진다. (0≤Q_i≤N×N)(0 \le Q\_i \le N \times N)

ii번째 정수는 병윤이가 ii번째로 외친 개수이다.

출력

병윤이가 수행한 행동을 QQ줄에 걸쳐 다음과 같은 형식으로 출력한다.

  • 병윤이가 ii번째에 xx행을 뒤집었을 경우, ii번째 줄에 R x를 출력한다.
  • 병윤이가 ii번째에 yy열을 뒤집었을 경우, ii번째 줄에 C y를 출력한다.

정답이 여러 개라면 아무거나 출력한다.

병윤이가 어떻게 행동해도 입력으로 주어진 수열을 구성할 수 없는 경우 첫째 줄에 -1만 출력한다.

예제3

  1. 예제 1

    입력
    3 4
    3 4 5 6
    
    예상 출력
    C 1
    R 1
    C 2
    C 3
    
  2. 예제 2

    입력
    3 5
    3 4 5 6 7
    
    예상 출력
    -1
    
  3. 예제 3

    입력
    987654321 3
    987654321 1975308642 2962962959
    
    예상 출력
    R 1
    R 2
    C 1