تجاوز هوایی (Invasion)

کشور اسپادانا، مورد حمله تعدادی گروه تروریستی قرار گرفته است که هر گروه تروریستی شامل تعدادی هوایپمای جنگنده است.
می‌دانیم جنگنده‌ها وارد جو زمین شده‌اند و قصد حمله به اسپادانا را دارند. خشایارشاه، پادشاه اسپادانا، هم‌اکنون متوجه حضور دشمنان در مرز هوایی کشورش شده است. لذا به مگنولیا، مشاور اعظم، دستور روشن کردنِ دستگاه «مگنول‌خفن» را داده است.

با روشن کردن این دستگاه، موتور تمام جنگنده‌ها از کار می‌افتد و تنها تحت تاثیر جاذبه و فقط به سمت پایین سقوط می‌کنند لذا با این تدبیر هوشمندانه، توطئه دشمن به کلی ساقط می شود.

آسمان اسپادانا به صورت یک جدول $n \times m$ است که در هر خانه از این جدول یا یک جنگنده قرار دارد یا خالی است. در پایین جدول هم سطح زمین اسپادانا قرار دارد.

در مورد حرکت گروه‌های تروریستی مگنولیا اطلاعات زیر را جمع‌آوری کرده است.

• همه ‌جنگنده‌های یک گروه تروریستی به صورت یکسان حرکت می‌کنند، یعنی وضعیت نسبی جنگنده‌های یک گروه تروریستی تغییر نمی‌کند.
• هیچ دو جنگنده‌ای نمی‌توانند از روی هم عبور کنند و یا در یک جا قرار بگیرند.
• جنگنده‌ها تحت تاثیر جاذبه تا حد امکان به سمت پایین سقوط می‌کنند.

مگنولیا جهت چاپلوسی بیشتر خدمت خشایارشاه، می‌خواهد وضعیت نهایی جنگنده‌ها را به خشایار‌شاه گزارش دهد. شما این وضعیت نهایی را برای مگنولیا چاپ کنید.

پس از مطالعه شیوه گرفتن ورودی و نمایش خروجی، جهت فهم بهتر سوال، تست‌های نمونه را نیز مشاهده کنید.

خط اول وروی شامل دو عدد $n, m$ است که ابعاد آسمان دوبعدی اسپادانا را معلوم می‌کند.

سپس در $n$ سطر هر سطر $m$ عدد می‌آید که اطلاعات آسمان است. در ستون $1 \le j \le m$ از سطر $i+1$ اُم ورودی عدد $a_{i, j}$ می‌آید که شماره گروه جنگنده موجود در آن مکان است. اگر $a_{i, j} = 0$ یعنی آن مکان خالی است. و جنگنده‌ای در آن نقطه وجود ندارد.

خروجی باید وضعیت نهایی آسمان اسپادانا باشد. یعنی در $n$ سطر و در هر سطر $m$ عدد نمایش دهید که وضعیت نهایی آن خانه را نشان می‌دهد. یعنی باید یا شماره گروه یک جنگنده را نمایش دهید یا اگر آن خانه خالی است $0$ چاپ کنید.

• زیرمسئله اول (۵ نمره): $n = 2$.
• زیرمسئله دوم (۵ نمره): $a_{i, j} \le 2$.
• زیرمسئله سوم (۱۵ نمره): $a_{i, j} \le 10$ و $n \times m \le 1000$.
• زیرمسئله چهارم (۲۰ نمره): $a_{i, j} \le 200$.
• زیرمسئله پنجم (۲۵ نمره): برای هر گروه تروریستی، جنگنده‌های این گروه تشکیل یک مستطیل در آسمان اسپادانا می‌دهند.
• زیرمسئله ششم (۳۰ نمره): بدون محدودیت اضافی.

• $1 \le n, m \le 1000$.
• $0 \le a_{i, j} \le n \times m$.

2 2
1 2
0 2

0 2
1 2

4 3
1 1 1
1 2 1
1 1 1
0 0 0

0 0 0
1 1 1
1 2 1
1 1 1

5 5
1 1 1 0 0
0 0 2 2 1
3 0 0 0 4
3 0 4 0 0
0 0 0 0 0

0 0 0 0 0
1 1 1 0 0
0 0 0 0 1
3 0 2 2 4
3 0 4 0 0

3 2
1 2
2 1
0 0

0 0
1 2
2 1

در مثال اول، جنگنده گروه $1$ سقوط می‌کند و جنگنده‌های گروه $2$ ثابت می‌مانند.

در مثال دوم جنگنده‌های هر دو گروها یک واحد سقوط می‌کنند.

در مثال سوم جنگنده‌های گروه $1, 3, 4$ یک واحد، جنگنده‌های گروه $2$ دو واحد سقوط می‌کنند.