아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

이노포레스트

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

요약
각 행이나 열에 같은 양의 물을 주는 연산으로 격자 a를 격자 b로 바꿀 수 있는지 판정하고, 가능하면 연산 목록을 출력한다.
난이도

보통10점 중 6점

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

문제

이노폴리스의 나무는 특별해서, 이노트리(Innopolis Tree)에 물을 주면 준 물의 양만큼 자란다. 다시 말해 높이 hh인 이노트리에 xx리터의 물을 주면 새 높이는 h+xh + x가 된다.

이노포레스트(Innopolis Forest)는 n×mn \times m 격자이고, 각 칸에는 이노트리가 하나씩 있다. 이노포레스트의 관개 시스템에는 n+mn + m개의 수로가 있다. 각 행과 각 열에 하나씩이다. 관개 시스템은 한 번의 작업으로 수로 하나를 따라 있는 모든 나무에 같은 양의 물을 줄 수 있다.

이노폴리스 시장은 관개 시스템에 몇 번의 작업을 수행해 이노포레스트를 바꾸려고 한다. 이노포레스트의 각 나무에 대해 현재 높이와 원하는 높이를 알고 있다. 이노포레스트를 원하는 모양으로 바꾸는 작업 순서를 구하라.

입력

첫째 줄에 두 수 nn과 mm이 주어진다 (1≤n,m≤10001 \le n, m \le 1000).

그다음 nn개의 줄이 주어지고, 각 줄에는 mm개의 수 ai,ja_{i,j}가 있다. 이는 이노포레스트에 있는 나무의 현재 높이이다 (1≤ai,j≤1091 \le a_{i,j} \le 10^9).

그다음 nn개의 줄이 더 주어지고, 각 줄에는 mm개의 수 bi,jb_{i,j}가 있다. 이는 나무의 원하는 높이이다 (1≤bi,j≤1091 \le b_{i,j} \le 10^9).

출력

첫째 줄에는 작업의 수 kk를 출력한다 (0≤k≤1060 \le k \le 10^6). 그다음 kk개의 줄에는 작업의 설명을 출력한다.

  • "R r x" 시스템이 rr번째 행에 xx리터의 물을 준다. (1≤r≤n1 \le r \le n, 1≤x≤1091 \le x \le 10^9).
  • "C c x" 시스템이 cc번째 열에 xx리터의 물을 준다. (1≤c≤m1 \le c \le m, 1≤x≤1091 \le x \le 10^9).

이노포레스트를 원하는 모양으로 바꾸는 것이 불가능하면 정수 -1 하나만 출력한다.

작업의 수를 최소화할 필요는 없고, 10610^6을 넘지 않기만 하면 된다.

예제3

  1. 예제 1

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

    입력
    3 3
    2 2 2
    2 2 2
    2 2 2
    1 1 1
    1 1 1
    1 1 1
    
    예상 출력
    -1
    
  3. 예제 3

    입력
    3 3
    1 2 3
    4 5 6
    7 8 9
    2 4 4
    5 7 7
    7 9 9
    
    예상 출력
    3
    R 1 1
    R 2 1
    C 2 1