{"raw_statement":[{"iden":"statement","content":"Given a board of size N * M. The rows are numbered from 1 to N, and the columns are numbered from 1 to M. Each cell of the board contains either 0 or 1.\n\nYou can apply 2 types of operations: \n\nYou have a function _valid(x1, y1, x2, y2)_, which returns true if and only if every cell in the sub-board with 2 opposite corners (x1, y1), (x2, y2) contains all 1.\n\nYou need to find maximum value of (x0 + y0), such that it is possible to apply the operations, so that _valid(1, 1, x0, y0) = true_. However, everybody is only interested in solutions where x0 + y0 > max(m, n).\n\nOn the first line of input there are two integers N and M (1 ≤ N, M ≤ 1000) – the size of the matrix. On the following N lines there are M integers each – the elements of the matrix, either 0 or 1.\n\nOn the first line of output print the values x0 and y0 giving the maximal possible sum (x0 + y0).\n\nOn the next line of output print the number R – the number of operations.\n\nOn the following R lines output the operations itself in such format _T i j_, where T is the what is swapped (_'C'_ for columns and _'R'_ for rows), i and j are the indexes of rows/columns being swapped.\n\nIf there are multiple solutions, output any of them.\n\n*If there is no solution such that* x0 + y0 > max(m, n)*, print single line with \"0 0\"*.\n\n"},{"iden":"input","content":"On the first line of input there are two integers N and M (1 ≤ N, M ≤ 1000) – the size of the matrix. On the following N lines there are M integers each – the elements of the matrix, either 0 or 1."},{"iden":"output","content":"On the first line of output print the values x0 and y0 giving the maximal possible sum (x0 + y0).On the next line of output print the number R – the number of operations.On the following R lines output the operations itself in such format _T i j_, where T is the what is swapped (_'C'_ for columns and _'R'_ for rows), i and j are the indexes of rows/columns being swapped.If there are multiple solutions, output any of them.*If there is no solution such that* x0 + y0 > max(m, n)*, print single line with \"0 0\"*."},{"iden":"examples","content":"Input3 30 1 11 1 01 1 1Output1 31R 1 3Input3 1011Output0 0"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ be the dimensions of a binary matrix $ A \\in \\{0,1\\}^{N \\times M} $.  \nLet $ \\text{valid}(x_1, y_1, x_2, y_2) $ be a predicate returning true iff all cells in the submatrix with top-left $ (x_1, y_1) $ and bottom-right $ (x_2, y_2) $ are 1.  \n\n**Constraints**  \n1. $ 1 \\leq N, M \\leq 1000 $  \n2. Each entry $ A[i][j] \\in \\{0,1\\} $ for $ 1 \\leq i \\leq N $, $ 1 \\leq j \\leq M $  \n\n**Objective**  \nFind $ (x_0, y_0) \\in \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $ maximizing $ x_0 + y_0 $, such that after applying a sequence of row/column swaps,  \n$$\n\\text{valid}(1, 1, x_0, y_0) = \\text{true} \\quad \\text{and} \\quad x_0 + y_0 > \\max(N, M)\n$$  \nIf no such $ (x_0, y_0) $ exists, output `0 0`.  \n\nOtherwise, output:  \n- $ x_0, y_0 $  \n- Number of operations $ R $  \n- $ R $ operations of form `T i j`, where $ T \\in \\{R, C\\} $, swapping row/column $ i $ with $ j $  \n\n(Any valid sequence of swaps achieving the goal is acceptable.)","simple_statement":"Find the largest x0 + y0 > max(N, M) such that the sub-rectangle from (1,1) to (x0,y0) contains all 1s, by swapping rows and columns. Output x0, y0, number of swaps, and the swaps. If impossible, output \"0 0\".","has_page_source":false}