Загублений список#13113

Загублений список

1 секунда
256 мегабайтів

На гірськолижному курорті є траси рівнів крутизни, пронумерованих від до (більший номер означає крутішу трасу), і рівнів довжини, пронумерованих від до (більший номер означає довшу трасу). Кажуть, що траса з рівнем крутизни і рівнем довжини має тип .

Кожен лижник має два обмеження: найбільший рівень крутизни і найбільший рівень довжини , на яких він погоджується кататися (1 \le x \le n, 1 \le y \le m). Лижник з обмеженнями вважає трасу типу придатною, якщо i \le x і j \le y. Різні лижники можуть мати однакові обмеження.

Курорт провів опитування: для кожного типу трас відомо, скільки лижників вважають його придатним, і це число дорівнює a_{i, j}. Список лижників загубився. Для кожної пари обмежень знайдіть, скільки лижників мають саме такі обмеження, або повідомте, що результати опитування суперечливі, тобто жодна множина лижників не дає таких чисел.

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 100) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить два цілі числа та (1 \le n, m \le 1000) — кількість рівнів крутизни та кількість рівнів довжини.

-й з наступних рядків містить цілих чисел a_{i, 1}, a_{i, 2}, \ldots, a_{i, m} (0 \le a_{i, j} \le 10^9) — кількості лижників, які вважають придатними траси з рівнем крутизни і рівнями довжини 1, 2, \ldots, m.

Сума n \cdot m за всіма тестовими випадками не перевищує 10^6.

Вихідні дані

Для кожного тестового випадку, якщо результати опитування суперечливі, виведіть один рядок з числом .

Інакше виведіть рядків по чисел: -й рядок має містити c_{x, 1}, c_{x, 2}, \ldots, c_{x, m}, де c_{x, y} — кількість лижників з обмеженнями .

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку є чотири лижники: один з обмеженнями , двоє з обмеженнями і один з обмеженнями . На рисунку ліворуч обведено траси, придатні для лижників кожного з цих видів, а праворуч наведено відповідь. Наприклад, траса типу придатна для всіх них, тобто для 1 + 2 + 1 = 4 лижників, а траса типу придатна лише для двох лижників з обмеженнями .