Find the Minimal Trench

In this problem, you are given an n×n grid representing the heights of buildings in a city. There exists a trench along either one of the rows or one of the columns. The cost of a trench is defined as the sum of the building heights along that row or column. Your task is to determine the trench (row or column) with the minimal total height. If there is a tie between the minimal row and column sums, choose the row (denoted by 'r'). The answer should report the minimal sum, the direction ('r' for row or 'c' for column), and the 1-indexed position of the trench.

The problem can be formulated with the following mathematical description:

Given a matrix (A) of size (n \times n), compute the row sums (R_i = \sum_{j=1}^{n} A_{ij}) and the column sums (C_j = \sum_{i=1}^{n} A_{ij}). Let (R_{min} = \min_{1\leq i\leq n} R_i) and (C_{min} = \min_{1\leq j\leq n} C_j). If (R_{min} \leq C_{min}), then output (R_{min}), 'r', and the smallest index (i) achieving (R_{min}); otherwise, output (C_{min}), 'c', and the smallest index (j) achieving (C_{min}).

inputFormat

The first line of input contains a single integer (n) (the size of the grid). Each of the next (n) lines contains (n) space-separated integers representing the heights of the buildings in that row.

outputFormat

Print three values separated by spaces: the minimal sum, a character indicating the trench type ('r' for a row or 'c' for a column), and the 1-indexed position of that row or column.## sample

3
1 2 3
4 5 6
7 8 9

6 r 1