Under construction

Still being built. Things may change

Sign Flip Table

Interview

Time limit2sMemory limit1024 MB

Summary
Find a sequence of row and column sign flips so every row and column sum of an integer table is non-negative, using at most 20000 moves.
Level

Medium5 of 10

Topics
Matrix, Greedy, Simulation
Solved
No attempts yet

Problem

In a new one-player math game called Number Table, a table with nn rows and mm columns is filled with integers. In one move, the player picks one row or one column and flips the sign of every number in that row or column.

The goal is to bring the table to a state where the sum of the numbers in every row and every column is non-negative. The number of moves does not need to be minimal, but at most 20000 moves may be made.

Your task is to write a program that, given the initial table, finds a sequence of moves that reaches the goal, or determines that the goal cannot be reached.

Input

The first line contains two integers nn and mm (2≤n,m≤1002 \le n, m \le 100). Each of the next nn lines contains mm integers ai,ja_{i,j} (∣ai,j∣≤100|a_{i,j}| \le 100).

Output

In the first line, print kk, the number of moves, or -1 if the goal cannot be reached. If the goal can be reached, print the kk moves in the following kk lines, one move per line. Each line contains the move type (R if a row is chosen, C if a column is chosen) and the number of that row or column. Rows and columns are numbered from 1, rows from top to bottom and columns from left to right.

The printed sequence must contain at most 20000 moves. It is guaranteed that if a sequence of moves reaching the goal exists, then a sequence satisfying this limit also exists.

Examples2

  1. Example 1

    Input
    2 2
    -1 -3
    1 -2
    
    Expected output
    1
    C 2
    
  2. Example 2

    Input
    3 2
    -1 -1
    -1 -1
    -1 -1
    
    Expected output
    3
    R 1
    R 2
    R 3