Будівництво хмарочосів#8645
Сучасний мегаполіс планує масштабну реконструкцію центру міста. У місті є унікальна будівельна система: коли будівельні бригади додають поверхи до будівлі, будівля виростає рівно на стільки поверхів, скільки було додано. Іншими словами, якщо будівля має поверхів і ви додаєте до неї поверхів, то будівля матиме h + x поверхів.
Центр міста організований у вигляді сітки n \times m, де кожна комірка містить один хмарочос. Будівельна система має n + m вежових кранів: один кран для кожного рядка і один для кожного стовпця. Кожна будівельна операція використовує один кран для додавання однакової кількості поверхів до всіх будівель уздовж його рядка або стовпця.
Міський планувальник хоче перетворити панораму центру міста, виконуючи будівельні операції. Для кожної будівлі ви знаєте її поточну висоту (кількість поверхів) і бажану висоту. Ваше завдання — знайти послідовність будівельних операцій, яка перетворить панораму міста відповідно до бажаної конфігурації.
Перший рядок містить два цілі числа і (1 \le n, m \le 1000) — розміри міської сітки.
Далі слідують рядків, кожен з яких містить цілих чисел a_{i,j} (1 \le a_{i,j} \le 10^9) — поточна кількість поверхів у кожній будівлі.
Далі слідують ще рядків, кожен з яких містить цілих чисел b_{i,j} (1 \le b_{i,j} \le 10^9) — бажана кількість поверхів у кожній будівлі.
Перший рядок повинен містити кількість операцій (0 \le k \le 10^6), за яким слідують рядків з описом операцій:
"" — Додати поверхів до всіх будівель у рядку (1 \le r \le n, 1 \le x \le 10^9).
"" — Додати поверхів до всіх будівель у стовпці (1 \le c \le m, 1 \le x \le 10^9).
Якщо неможливо перетворити панораму міста у бажану конфігурацію, виведіть .
Приклад 1
Приклад 2
Приклад 3
Не потрібно мінімізувати кількість операцій, просто переконайтеся, що вона не перевищує 10^6.