İtmiş siyahı#13113

İtmiş siyahı

1 saniyə
256 meqabayt

Xizək kurortunda -dən -ə qədər nömrələnmiş diklik səviyyəsi (daha böyük nömrə daha dik trassa deməkdir) və -dən -ə qədər nömrələnmiş uzunluq səviyyəsi (daha böyük nömrə daha uzun trassa deməkdir) olan trassalar var. Diklik səviyyəsi və uzunluq səviyyəsi olan trassanın tipi sayılır.

Hər xizəkçinin iki məhdudiyyəti var: sürüşməyə razı olduğu maksimal diklik səviyyəsi və maksimal uzunluq səviyyəsi (1 \le x \le n, 1 \le y \le m). məhdudiyyətlərinə malik xizəkçi tipli trassanı, əgər i \le x və j \le y olarsa, uyğun hesab edir. Müxtəlif xizəkçilərin məhdudiyyətləri eyni ola bilər.

Kurort sorğu keçirib: hər trassa tipi üçün onu neçə xizəkçinin uyğun hesab etdiyi məlumdur və bu say a_{i, j}-ə bərabərdir. Xizəkçilərin siyahısı itib. Hər məhdudiyyət cütü üçün dəqiq bu məhdudiyyətlərə malik xizəkçilərin sayını tapın və ya sorğunun ziddiyyətli olduğunu, yəni heç bir xizəkçi çoxluğunun bu ədədləri vermədiyini bildirin.

Giriş

Birinci sətirdə bir tam ədəd (1 \le t \le 100) — test hallarının sayı verilir.

Hər test halının birinci sətrində iki tam ədəd və (1 \le n, m \le 1000) — diklik səviyyələrinin sayı və uzunluq səviyyələrinin sayı verilir.

Növbəti sətrin -cisində tam ədəd a_{i, 1}, a_{i, 2}, \ldots, a_{i, m} (0 \le a_{i, j} \le 10^9) — diklik səviyyəsi və uzunluq səviyyələri 1, 2, \ldots, m olan trassaları uyğun hesab edən xizəkçilərin sayları verilir.

Bütün test halları üzrə n \cdot m cəmi 10^6-dan çox deyil.

Çıxış

Hər test halı üçün, əgər sorğu ziddiyyətlidirsə, bir sətirdə ədədini çap edin.

Əks halda hər birində ədəd olan sətir çap edin: -ci sətirdə c_{x, 1}, c_{x, 2}, \ldots, c_{x, m} olmalıdır, burada c_{x, y} — məhdudiyyətlərinə malik xizəkçilərin sayıdır.

Nümunələr

Nümunə 1

Loading
Loading

Qeyd

Birinci test halında dörd xizəkçi var: biri məhdudiyyətləri ilə, ikisi məhdudiyyətləri ilə və biri məhdudiyyətləri ilə. Şəkildə solda bu növ xizəkçilərin hər biri üçün uyğun olan trassalar çərçivəyə alınıb, sağda isə cavab göstərilib. Məsələn, tipli trassa onların hamısı üçün, yəni 1 + 2 + 1 = 4 xizəkçi üçün uyğundur, tipli trassa isə yalnız məhdudiyyətlərinə malik iki xizəkçi üçün uyğundur.