Задача D. R2D2 ≡

Автор:М. Спорышев   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Перед сражением с ситхами Энакен Скайуокер решил протестировать своего дроида R2D2. Для проверки системы передвижения он решил поместить робота на специальную горизонтальную площадку, имеющую форму прямоугольника. Площадка разделена на квадратные клетки со сторонами длины 1. На некоторые клетки можно перемещаться, на некоторые - нет. R2D2 разрешено перемещаться только вверх, вперед, влево, вправо на соседние клетки.

Для первого теста Энакен хочет заставить робота пройти от начальной клетки площадки до конечной всеми возможными способами, проходя через каждую клетку ровно 1 раз. Чтобы заставить робота двигаться, юному джедаю надо записать все траектории, которые следует пройти роботу, в виде последовательностей символов 'l', 'r', 'u', 'd'. Символ 'l' означает, что робот должен перейти в левую соседнюю клетку, 'r', 'u', 'd' - в правую, верхнюю, нижнюю соответственно. Энакену лень записывать таким образом все способы перемещения, и он просит вас написать программу, которая напишет их за него.

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

Первая строка входного файла содержит два целых числа N, M - длины сторон прямоугольника. За ними следует N * M чисел A[i, j], которые равны 0, если в клетку с координатами i, j перемещаться нельзя, или 1 - можно. Первое число задает верхнюю левую клетку (она является начальной), последнее - нижнюю правую(конечная). Гарантируется, что есть хотя бы один путь из начальной клетки в конечную.

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

В выходной файл выведите число C - количество способов перемещения из начальной клетки в конечную, за которым следует C строк - способы перемещения в виде последовательностей символов 'l', 'r', 'u', 'd'. Последовательности можно выводить в любом порядке.

Ограничения

2 ≤ N,M ≤ 5

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
2 1
1
1
 
1
d
2 
2 2 
1 0
1 1
 
1 
dr
0.037s 0.008s 15