ИнноДерево
ИнноДерево
В Иннополисе удивительные деревья. Если полить иннодерево (иннополисовское дерево), оно вырастет ровно на столько, сколько литров воды было использовано для полива. Другими словами, если вы возьмете иннодерево высотой h и польете его x литрами воды, тогда его высота станет равна h + x.
Иннолес (иннополисовский лес) представляет собой сетку n * m, каждая ячейка которой содержит одно иннодерево. Ирригационная система в иннолесу содержит n + m каналов: по одному для каждой строки и столбца. Ирригационная система за одну операцию может полить все деревья вдоль одного из каналов одним и тем же количеством воды.
Мэр Иннополиса хочет преобразовать иннолес, выполняя некоторые операции с ирригационной системой. Для каждого дерева в иннолесу вы знаете его текущую высоту и желаемую высоту. Ваша задача - найти последовательность операций, которая преобразует иннолес в желаемое состояние.
Входные данные
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 1000) - размеры иннолеса.
Затем следуют n строк, каждая из которых содержит m целых чисел ai,j
(1 ≤ ai,j
≤ 109
) - текущие высоты деревьев в иннолесу.
Затем следуют другие n строк, каждая из которых содержит m целых чисел bi,j
(1 ≤ bi,j
≤ 109
) - желаемые высоты деревьев.
Выходные данные
Первая строка должна содержать число операций k (0 ≤ k ≤ 106
), следующие k строк содержат
описание операций.
- "**R r x**" Полить r-ю строку x литрами воды (1 ≤ r ≤ n, 1 ≤ x ≤
109
). - "**C c x**" Полить c-й столбец x литрами воды (1 ≤ c ≤ m, 1 ≤ x ≤
109
).
Если невозможно привести иннолес в желаемое состояние, выведите -1.
Обратите внимание, что в задаче не требуется минимизировать число операций, но оно не должно превосходить 106
.
1 1 4 9
1 R 1 5
3 3 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
-1
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