Надіслати розв'язок

Бали: 18
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Василько не мріє бути програмістом – він хоче стати мільйонером. І не десь там у далекому майбутньому, а вже цього року. Для втілення своєї мрії Василько організував фірму, яка під Новий рік буде займатися поставкою новорічних ялинок. Оскільки мільйон треба заробити уже цього року, Василько вирішив обійтися без посередників. Бізнес-план вийшов дивовижно простий: сам рубаю, сам доставляю і сам продаю. Василько сміливо взявся за справу, але коли отримав угоду на вирубку ялинок, то задумався. За один раз йому дозволили вивозити рівно \(K\) \((0 \le K \le 10000)\) ялинок і партія Зелених домоглася певних обмежень на вирубку: ялинки можна рубати тільки рухаючись на схід або на південь; починати вирубку слід в одному кутку і закінчувати у будь-якому іншому. Ділянки мають форму прямокутника із сторонами \(N, M\) \((1 \le N, M \le 100)\) , сторони якого були орієнтовані чітко на захід, схід, північ та південь. Василько зразу ж помітив, що забезпечити собі гарний результат вирубки можна лише тоді, коли починаєш рубати із північно-західного кутка і закінчуєш у південно-східному :) «Зелені» добре подумали над тим, щоб виконати угоду по вирубці йому було складно. Василько це побачив і пошкодував, що не став спочатку програмістом.

Допоможіть Василькові правильно провести вирубку і стати мільйонером, або повідомте, що на цій ділянці краще не рубати.

Формат вихідних даних

У першому рядку вхідного потоку дано три цілих числа \(N, M, K\), розділених пропусками.

Далі у \(N\) рядках міститься по \(M\) символів: «.» - це вільне місце, а «#» - позначає місце знаходження ялинки.

Формат вихідних даних

У вихідний потік у випадку наявності правильного варіанту вирубки вивести послідовність координат, які виводити по одній у кожному рядку. Перша координата завжди (1,1), остання – \((N, M)\). В іншому випадку вивести повідомлення «To not cut !»

Приклад вхідних даних

4 4 3
....
#...
###.
####

Приклад вихідних даних

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

Приклад вхідних даних

3 4 1
#...
..#.
#.##

Приклад вихідних даних

To not cut!

Коментарі

Ще немає коментарів.