На пути к школе Карен зациклилась на одной игре в телефоне!
Игра описывается следующими правилами. На каждом уровне есть таблица с n строками и m столбцами. Каждая ячейка содержит изначально число 0.
Ход состоит в выборе одной строки или одного столбца и прибавлении 1 ко всем ячейкам этого столбца или строки.
Чтобы пройти уровень, нужно, чтобы после всех ходов число в j-й ячейке i-го столбца равнялось gi, j.
Карен застряла на одном из уровней, и хочет пройти его за минимальное число ходов. Помогите ей!
Выходные данные
Если уровень нельзя пройти, выведите -1.
Иначе выведите на первой строке одно число k — минимальное число ходов, необходимое для прохождения уровня.
Каждая из следующих k строк должна содержать описание одного хода в одном из следующих форматов:
- row x, (1 ≤ x ≤ n) — ход «выбрать строку x».
- col x, (1 ≤ x ≤ m) — ход «выбрать столбец x».
Если есть несколько оптимальных решений, выведите любое.
Примечание
В первом примере таблица имеет 3 строки и 5 столбцов. Карен может выполнить следующие 4 хода, чтобы пройти уровень:
Во втором примере в таблице 3 строки и 3 столбца. Ясно, что невозможно пройти уровень, так как любой ход создаст три 1 в таблице, но необходимо получить только одну 1 по центру.
В третьем тесте у Карен таблица с 3 строками и 3 столбцами. Она может выполнить следующие 3 хода, чтобы пройти уровень:
Это не единственное решение, например, другое — выполнить ходы col 1, col 2, col 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
2 2 2 3 2
0 0 0 1 0
1 1 1 2 1
|
4
row 1
row 1
col 4
row 3
|
|
2
|
3 3
0 0 0
0 1 0
0 0 0
|
-1
|
|
3
|
3 3
1 1 1
1 1 1
1 1 1
|
3
row 1
row 2
row 3
|