- محدودیت زمان: ۱.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
یک سالن سینما داریم که صندلیهای آن به شکل یه جدول \(n \times m\) است که دارای \(n\) ردیف و \(m\) ستون است. ردیفها از بالا به پایین با اعداد \(1\) تا \(n\)، و ستونها از چپ به راست با اعداد \(1\) تا \(m\)، شمارهگذاری شده است. برخی از صندلیها با تماشاچی پر شده و برخی خالی است.
هر بار که یک تماشاچی وارد سالن میشود، به دلیل شیوع کرونا، میخواهد روی صندلیای بنشیند که نزدیکترین تماشاچی همردیف آن، از چپ و راست؛ بیشترین فاصله را داشته باشد. اگر هیچ تماشاچی در یک ردیف نباشد، فاصله نزدیکترین تماشاچی به این صندلی را بینهایت در نظر بگیرید.
اگر چند صندلی با این ویژگی وجود دارد صندلی که شماره سطر آن کمینه باشد و اگر چند صندلی با این ویژگی در یک سطر وجود دارد، صندلی که شماره ستون آن کمینه است، الویت دارد.
حال وضعیت اولیه نشستن تماشاچیها به شما داده میشود و از شما میخواهیم جای نشستن \(k\) نفر بعدی را مشخص کنید. توجه کنید این \(k\) نفر یکی یکی وارد شده و تا نشستن نفر قبلی منتظر میمانند.
ورودی
در سطر اول ورودی سه عدد صحیح و مثبت \(n\)، \(m\) و \(k\) که با یک فاصله از هم جدا شدهاند آمده است. که به ترتیب نشاندهندهی تعداد ردیفها و ستونهای سالن و تعداد تماشاچیهایی است که میخواهند وارد سالن شوند.
\[ 1 \leq n, m \leq 1000\] \[1 \leq k \leq \min \{ n.m,100 \, 000 \}\]
تضمین میشود که حداقل \(k\) صندلی خالی در سالن سینما وجود دارد.
در \(n\) سطر بعدی در هر سطر \(m\) کاراکتر آمده که کاراکتر \(j\)ام آمده در سطر \(i\)ام، وضعیت صندلی سطر \(i\) و ستون \(j\) را نشان میدهد. اگر این کاراکتر برابر . باشد یعنی این صندلی خالی است و اگر # باشد یعنی این صندلی پر شده است.
خروجی
اگر \(k\) تعداد تماشاچیهایی که میخواهند وارد سالن شوند، باشد. خروجی \(k\) سطر دارد و در سطر \(i\)ام دو عدد \(r_i\) و \(c_i\) که با یک فاصله از هم جداشدهاند، چاپ کنید که نشاندهندهی شماره سطر و ستون صندلی است که تماشاچی \(i\)ام روی آن مینشیند.
مثالها
ورودی نمونه ۱
2 2 2
..
#.
خروجی نمونه ۱
1 1
1 2
توضیح نمونه ۱
مراحل نشستن این ۲ تماشاچی به ترتیب از چپ به راست نشان داده میشود.
ورودی نمونه ۲
3 5 11
...##
#...#
.....
خروجی نمونه ۲
3 1
3 5
1 1
2 3
3 3
1 2
1 3
2 2
2 4
3 2
3 4
توضیح نمونه ۲
