سقوط سیب‌ها

Time Limit: 1 Second    Memory Limit: 32768 KB

‫شما یک شبکهٔ دوبعدی مستطیلی دارید. در هر خانهٔ شبکه یا یک سیب یا یک مانع وجود دارد یا خانه خالی است. شما باید جاذبه را با قوانین زیر شبیه‌سازی کنید:
‫• موانع جابه‌جا نمی‌شوند.
‫• هرگاه بلافاصله زیر یک سیب خانه‌ای خالی وجود داشته باشد، سیب به خانهٔ خالی منتقل می‌شود.
‫وضعیت نهایی صفحه را بعد از این که همهٔ سیب‌ها به مکان نهایی‌شان رسیدند نمایش دهید. توجه کنید که تکرار مرحله‌به‌مرحلهٔ قواعد گرانش برای مجموعه‌داده‌های بزرگ احتمالاً زمان زیادی طول خواهد کشید.

Input

‫ورودی با خطی شامل R و C آغاز می‌شود که تعداد سطرها و ستون‌های شبکه را نشان می‌دهند. بعد از این خط، R خط خواهد آمد که سطور شبکه را از بالا به پایین توصیف می‌کنند. هر خط شامل C نویسه می‌شود که هر کدام یکی از نویسه‌های .، a یا # هستند. خانه‌های خالی با .، سیب‌ها با a و موانع با # نمایش داده می‌شوند.

Output

‫خروجی باید شامل R خط باشد که وضعیت نهایی را توصیف می‌کنند.

Sample Input

3 3
aaa
#..
..#

___________________________________________________________________________________________________________________
4 5
aaa.a
aa.a.
a.a..
...a.

Sample Output

a..
#.a
.a#

___________________________________________________________________________________________________________________
.....
a....
aaaa.
aaaaa
Submit