Torpaq Satışı
Absurdistan ölkəsi, bildiyiniz kimi, qəribəliklərlə doludur. Məsələn, ölkə tamamilə ot və ya bataqlıq olan kvadratlara bölünə bilər. Bu ölkə həm də bacarıqsız bürokratları ilə məşhurdur. Əgər bir torpaq sahəsi (parsel) almaq istəyirsinizsə, yalnız düzbucaqlı bir sahə ala bilərsiniz, çünki onlar digər formaları idarə edə bilmirlər. Parselin qiyməti onların tərəfindən müəyyən edilir və sahəni hesablaya bilmədikləri üçün qiymət parselin perimetri ilə mütənasibdir, çünki bürokratlar tam ədədləri vurmağı bacarmırlar.
Per, bataqlıqla əhatə olunmuş Absurdistan'da bir parselə sahibdir və onu mümkün qədər hissələrə bölərək bəzi alıcılara satmaq istəyir. Torpağının düzbucaqlı bir hissəsini satdıqda, bunu yerli bürokratlara elan etməlidir. Onlar əvvəlcə ona satmalı olduğu qiyməti bildirəcəklər. Sonra yeni sahibin adını və satılan parselin cənub-şərq küncünün koordinatlarını qeyd edəcəklər. Əgər artıq həmin yerdə cənub-şərq küncü olan bir parsel başqa birinə məxsusdursa, bürokratlar mülkiyyət dəyişikliyini rədd edəcəklər.
Per başa düşür ki, sistemi asanlıqla aldada bilər. O, üst-üstə düşən sahələri sata bilər, çünki bürokratlar yalnız cənub-şərq künclərinin eyni olub-olmadığını yoxlayırlar. Lakin, heç kim bataqlıq olan bir parsel almaq istəmir.
Bu nümunədə, qaranlıq kvadratlar bataqlığı təmsil edir. Məsələn, Per 2 × 1, 2 × 4 və 4 × 1 ölçülərində üç üst-üstə düşən boz sahəni sata bilər. Ümumi perimetr 6 + 12 + 10 = 28-dir.
Qeyd edək ki, daha çox torpaq sataraq daha çox pul qazana bilər. Bu şəkil nümunə girişindəki vəziyyətə uyğundur.
İndi Per hər perimetrdən neçə parsel satmalı olduğunu bilmək istəyir ki, mənfəətini maksimuma çatdırsın. Ona kömək edə bilərsinizmi? Siz hər bir torpaq parçası üçün, bataqlıq olmadığı müddətcə, həmişə bir alıcı tapa biləcəyini qəbul edə bilərsiniz. Həmçinin, Per əmindir ki, onun parselindəki heç bir kvadrat başqasına məxsus deyil.
Giriş verilənləri
Birinci sətirdə müsbət bir tam ədəd: test hallarının sayı, ən çox 100. Bundan sonra hər test halı üçün:
Bir sətirdə iki tam ədəd n və m (1 ≤ n, m ≤ 1 000): Per'in parselinin ölçüləri.
n sətir, hər biri m simvoldan ibarət. Hər simvol ya '#' ya da '.' olacaq. i-ci sətirdəki j-ci simvol, əgər mövqe (i, j) bataqlıqdırsa '#', ot isə '.' olacaq. Per'in parselinin şimal-qərb küncü (1, 1) koordinatlarına, cənub-şərq küncü isə (n, m) koordinatlarına malikdir.
Çıxış verilənləri
Hər test halı üçün:
Per'in mənfəətini maksimuma çatdırmaq üçün hər perimetrdən neçə parsel satmalı olduğunu tam siyahı şəklində verən sıfır və ya daha çox sətir. Daha dəqiq desək, əgər optimal həllə görə Per i perimetrli p_i parsel satmalıdırsa, "p_i × i" şəklində bir sətir çıxarın. Sətirlər i artan sıra ilə sıralanmalıdır. Eyni i dəyərinə malik iki sətir olmamalıdır və p_i = 0 olan sətirləri çıxarmamalısınız.