Kayıp Liste#13113

Kayıp Liste

1 saniye
256 megabayt

Bir kayak merkezinde 'den 'e kadar numaralandırılmış diklik seviyesine (daha büyük numara daha dik pist anlamına gelir) ve 'den 'e kadar numaralandırılmış uzunluk seviyesine (daha büyük numara daha uzun pist anlamına gelir) sahip pistler vardır. Diklik seviyesi ve uzunluk seviyesi olan bir pistin türü olarak adlandırılır.

Her kayakçının iki sınırı vardır: kaymayı kabul ettiği en büyük diklik seviyesi ve en büyük uzunluk seviyesi (1 \le x \le n, 1 \le y \le m). Sınırları olan bir kayakçı, i \le x ve j \le y ise türündeki bir pisti uygun bulur. Farklı kayakçıların sınırları aynı olabilir.

Merkez bir anket yaptı: her pist türü için onu kaç kayakçının uygun bulduğu bilinmektedir ve bu sayı a_{i, j}'dir. Kayakçıların listesi kayboldu. Her sınır çifti için tam olarak bu sınırlara sahip kaç kayakçı olduğunu bulun ya da anketin tutarsız olduğunu, yani hiçbir kayakçı kümesinin bu sayıları vermediğini bildirin.

Giriş

İlk satırda bir tam sayı (1 \le t \le 100) — test durumlarının sayısı verilir.

Her test durumunun ilk satırında iki tam sayı ve (1 \le n, m \le 1000) — diklik seviyelerinin sayısı ve uzunluk seviyelerinin sayısı verilir.

Sonraki satırın -incisinde tam sayı a_{i, 1}, a_{i, 2}, \ldots, a_{i, m} (0 \le a_{i, j} \le 10^9) — diklik seviyesi ve uzunluk seviyeleri 1, 2, \ldots, m olan pistleri uygun bulan kayakçıların sayıları verilir.

Tüm test durumları üzerinden n \cdot m toplamı 10^6'yı aşmaz.

Çıktı

Her test durumu için, anket tutarsızsa, tek bir satırda sayısını yazdırın.

Aksi hâlde her birinde sayı bulunan satır yazdırın: -inci satırda c_{x, 1}, c_{x, 2}, \ldots, c_{x, m} bulunmalıdır; burada c_{x, y}, sınırları olan kayakçıların sayısıdır.

Örnekler

Örnek 1

Loading
Loading

Not

İlk test durumunda dört kayakçı vardır: biri sınırlarına, ikisi sınırlarına ve biri sınırlarına sahiptir. Şekilde, bu kayakçı türlerinin her biri için uygun olan pistler solda çerçeve içine alınmıştır, cevap ise sağdadır. Örneğin, türündeki pist hepsi için, yani 1 + 2 + 1 = 4 kayakçı için uygundur; türündeki pist ise yalnızca sınırlarına sahip iki kayakçı için uygundur.