Qədim təqvim#3156
2012-ci ildə qədim təqvimlərə maraq artmışdı, xüsusən də 2012-ci ildə bitməyənlərə. Tatarıstanda arxeoloqlar qeyri-adi bir tapıntı etdilər: qədim qəbiristanlıqda düzbucaqlı lövhə tapdılar və qorunub saxlanılmış simvollar deşifrə olunduqdan sonra bu lövhə sətirdən ibarət, hər biri onluq rəqəmli olan bir cədvəl kimi qeyd edildi. Lakin bəzi rəqəmlər aşındığı üçün oxuna bilmədi və bu rəqəmlərin yerinə cədvəldə "*" işarəsi yazıldı.
Tədqiqatçılar hesab edirlər ki, bu lövhə qədim bir təqvimdir. Burada hər bir -rəqəmli ədəd bir dövr ərzində günün sıra nömrəsini göstərir. Birinci sətirdəki ədəd birinci günün nömrəsidir, və cədvəldə hər bir növbəti ədəd əvvəlkindən tam olaraq bir vahid böyükdür. Bu təqvimə görə heç bir qiyamət yoxdur: dənə doqquzluq rəqəmdən ibarət gündən sonra növbəti gün dənə sıfırla ifadə olunur.
Sizdən tələb olunan proqram, cədvəldəki bilinməyən rəqəmləri elə bərpa etsin ki, cədvəldə ikinci sətirdən başlayaraq hər bir növbəti ədəd əvvəlkindən tam bir vahid böyük olsun. Proqram bərpa olunmuş təqvimin birinci gününün nömrəsini çıxışda verməlidir.
Birinci sətirdə təbii ədədlər və — cədvəldəki sətirlərin sayı və hər bir sətirin uzunluğu verilir (1 \leq N \leq 100000, 1 \leq M \leq 100000, M \times N \leq 100000). Sonra sətir verilir, hər biri simvoldan ibarət, yalnız onluq rəqəmlər və "*" işarəsi ola bilər.
Çıxışda bir sətirdə rəqəm olmalıdır — təqvimin bərpa olunmuş birinci gününün nömrəsi. Əgər bir neçə müxtəlif bərpa variantı varsa, istənilən birini çıxış edə bilərsiniz. Zəmanət verilir ki, ən azı bir həll variantı mövcuddur.
Nümunə 1