Задача A. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

Известно, что водовод представляет собой последовательность ячеек, имеющих общую сторону. Первая его ячейка находится в первом столбце клеток карты, последняя — в последнем. Водовод не проходит дважды через одну и ту же ячейку.

Дана карта, составленная по результатам работ. Необходимо определить, можно ли однозначно восстановить водовод по карте.

Формат входного файла

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

Формат выходного файла

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида r_i, c_i, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

Если существует несколько способов восстановить положение водовода, то выведите сначала слово MULTIPLE, а затем два различных описания водовода в любом порядке. Если существует более двух вариантов, выведите любые два из них.

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

Примеры тестов

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO

Задача B. День бульдозериста ≡

Условие

В некотором городе однажды выпал снег. Неожиданно выяснилось, что вся снегоуборочная техника находится на ремонте, и для расчистки улиц было решено привлечь тяжёлые гусеничные бульдозеры.

Задача осложняется тем, что асфальтовое покрытие улиц может выдержать только один проход такого бульдозера.

Город представляет из себя N площадей и M отрезков улиц между ними. Бульдозер может начинать расчистку с любой площади, и не должен ехать по уже расчищенным улицам (но может проезжать уже расчищенные площади). Если бульдозер оказывается на площади, все улицы которой уже расчищены, бульдозерист считает свой рабочий день законченным, бросает бульдозер и уходит.

Требуется определить минимально необходимое число бульдозеров.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 3
1 2 
2 3 
3 1

1

5 2 
1 2 
3 4

3

Задача C. Суперагент ≡

Условие

Женя Борин учится в школе юных суперагентов. На занятии по избавлению от слежки Борин получил такое теоретическое задание:

Зал аэропорта на плане имеет вид прямоугольника шириной W и высотой H метров. Пол разделён на клетки размером 1 × 1 метр. Клетка в северо-западном углу имеет координаты (1, 1).

На западной и северной стене через каждые два метра укреплены видеокамеры, обозревающие горизонтальную или вертикальную полосу шириной в одну клетку до противоположной стены. Таким образом, клетки, хотя бы одна координата которых чётна, просматриваются видеокамерами. Если агент попадёт в поле зрения камеры, поднимется тревога.

В зале находится N пассажиров. Пассажиры двигаются по залу, перемещаясь за 1 секунду на одну клетку по горизонтали или вертикали. Если между камерой и агентом есть хотя бы один пассажир, то агент остаётся незамеченным этой камерой.

Агент находится в точке с координатами (1, y_a) и желает попасть в точку с координатами (W, y_a), не подняв тревоги и затратив не более T секунд. Требуется написать программу, которая определит необходимую последовательность перемещений агента по известным координатам и перемещениям пассажиров.

Произвольное количество пассажиров может находиться одновременно в одной клетке, однако агент не может находиться в одной клетке с пассажиром.

Формат входного файла

Первая строка входного файла содержит числа W H T y_a N. Следующие N строк содержат значения x_i y_i p_i, где x_i, y_i — координаты i-го пассажира в начальный момент времени, p_i — строка из T символов, описывающая перемещения пассажиров в течении T секунд. Каждый символ равен "n", если пассажир перемещается на север, "s" — на юг, "w" — на запад, "e" — на восток, "z" — стоит на месте.

Формат выходного файла

Выходной файл должен содержать строку длиной не более T символов, описывающую движение агента в том же формате, что и движения пассажиров, либо строку IMPOSSIBLE, если решения не существует. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ W, H, T, N ≤ 100, y_a и W — нечётные, 1 ≤ x_i ≤ W, 1 ≤ y_i, y_a ≤ H

Примеры тестов

7 6 20 3 2
2 1 eeeeewwwwwweeeeeewww
3 2 ssssnnnnnsssssnnnnns

zzzzzzzzzzzeeeeee

3 4 5 3 1
1 1 zzzzz

IMPOSSIBLE