#include <algorithm>
#include <vector>
#include <string>
#include <istream>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <queue>
#include <functional>
#include <limits>

typedef unsigned int uint;

struct VectorHash
{
	template <typename T>
	std::size_t operator()(T pos) const
	{
		std::hash<int> hasher;

		auto h1 = hasher(pos.x);
		auto h2 = hasher(pos.y);

		return std::hash<int>{}((h1 ^ h2) >> 2);
	}
};

struct vec2
{
	int x = 0, y = 0;

	vec2()
		: x(0), y(0) {}

	vec2(int x, int y)
		: x(x), y(y) {}

	vec2 operator+(const vec2& other) { return { x + other.x, y + other.y }; }
	const vec2 operator+(const vec2& other) const { return { x + other.x, y + other.y }; }
	vec2 operator-(const vec2& other) { return { x - other.x, y - other.y }; }
	const vec2 operator-(const vec2& other) const { return { x - other.x, y - other.y }; }

	bool operator==(const vec2& other) const { return x == other.x && y == other.y; }
	bool operator!=(const vec2& other) const { return !(*this == other); }

	bool operator<(const vec2& other) const { return x < other.x && y < other.y; }
	bool operator<=(const vec2& other) const { return x <= other.x && y <= other.y; }
	bool operator>(const vec2& other) const { return !(*this <= other); }
	bool operator>=(const vec2& other) const { return !(*this < other); }
};

template<typename T>
class Grid
{
private:
	uint m_Width;
	uint m_Height;
	std::vector<T> m_Data;
public:
	Grid(uint width, uint height)
		: m_Width(width), m_Height(height), m_Data(width * height) {}

	inline uint width() const { return m_Width; }
	inline uint height() const { return m_Height; }

	T& operator()(uint x, uint y) { return m_Data[y * m_Width + x]; }
	const T& operator()(uint x, uint y) const { return m_Data[y * m_Width + x]; }

	T& operator()(const vec2& pos) { return m_Data[pos.y * m_Width + pos.x]; }
	const T& operator()(const vec2& pos) const { return m_Data[pos.y * m_Width + pos.x]; }
};

template<typename T, typename priority_t>
struct PriorityQueue
{
	typedef std::pair<priority_t, T> PQElement;
	std::priority_queue<PQElement, std::vector<PQElement>, std::greater<PQElement>> elements;

	bool empty() const { return elements.empty(); }

	void put(T item, priority_t priority) { elements.emplace(priority, item); }

	T get()
	{
		T best_item = elements.top().second;
		elements.pop();
		return best_item;
	}
};

enum Direction
{
	NO = 0,
	LEFT = 1 << 0,
	RIGHT = 1 << 1,
	UP = 1 << 2,
	DOWN = 1 << 3
};
struct DirectionHash
{
	template <typename T>
	std::size_t operator()(T t) const
	{
		return static_cast<std::size_t>(t);
	}
};

const std::unordered_map<Direction, vec2, DirectionHash> g_Directions = {
	{ LEFT,{ 0, -1 } },{ RIGHT,{ 0, 1 } },{ UP,{ -1, 0 } },{ DOWN,{ 1, 0 } }
};
const std::unordered_map<Direction, char, DirectionHash> g_DirectionNames = {
	{ LEFT, 'L' },{ RIGHT, 'R' },{ UP, 'U' },{ DOWN, 'D' }
};

struct Front
{
	uint FrontNumber;
	uint Bonus;
	Grid<char> Board;

	Front(uint bonus, uint width, uint height)
		: Bonus(bonus), Board(Grid<char>(width, height))
	{
	}
};
std::istream& operator>>(std::istream& is, Front& front)
{
	int width, height, bonus;
	is >> width >> height >> bonus;

	front = Front(bonus, width, height);

	std::string junk;
	std::getline(is, junk);
	for (int n = 0; n < width; n++)
	{
		std::string line;
		std::getline(is, line);
		for (int m = 0; m < height; m++)
			front.Board(n, m) = line.at(m);
	}
	return is;
}

struct Dog
{
	uint Front;
	vec2 Start, Current;
	std::vector<char> Path;
};

int g_MaxDogs;
std::vector<Front> g_Fronts;
std::vector<Dog> g_Dogs;

void read_input()
{
	std::ifstream input("catsdogs.in");

	int fronts;
	input >> fronts >> g_MaxDogs;

	g_Fronts.reserve(fronts);
	for (int f = 0; f < fronts; f++)
	{
		Front front(0, 0, 0);
		input >> front;

		g_Fronts.emplace_back(std::move(front));
	}
	input.close();
}
void output_result()
{
	std::ofstream output("catsdogs.out");
	uint used_dogs = g_Dogs.size();
	for (int i = 0; i < g_MaxDogs; i++)
	{
		if (i > used_dogs - 1)
			output << "0\n";
		else
		{
			Dog& dog = g_Dogs[i];
			output << dog.Front << '\n';
			output << dog.Start.x + 1 << " " << dog.Start.y + 1 << '\n';
			for (char ch : dog.Path)
				output << ch;
			if (dog.Path.empty())
				output << "STAY";
			output << std::endl;
		}
	}
	output.close();
}

int get_neighbours(const vec2& pos, const Grid<char>& board)
{
	int result = 0;

	for (int dir = 0; dir < 4; dir++)
	{
		vec2 target = pos + g_Directions.at(Direction(1 << dir));
		if (target.x < 0 || target.y < 0 || target.x >= board.width() || target.y >= board.height())
			continue;
		if (isdigit(board(target)))
			result |= 1 << dir;
	}
	return result;
}
int get_num_neighbours(int neighbours)
{
	int result = 0;

	for (int dir = 0; dir < 4; dir++)
		if (neighbours & (1 << dir))
			result++;
	return result;
}

vec2 get_optimal_start_position(const Grid<char>& board)
{
	//for (uint x = 0; x < board.width(); x++)
	//	for (uint y = 0; y < board.height(); y++)
	//		if (isdigit(board(x, y)))
	//		{
	//			if (get_num_neighbours(get_neighbours({ (int)x, (int)y }, board)) == 1)
	//				return { (int)x, (int)y };
	//		}
	//for (uint x = 0; x < board.width(); x++)
	//	for (uint y = 0; y < board.height(); y++)
	//		if (isdigit(board(x, y)))
	//		{
	//			if (get_num_neighbours(get_neighbours({ (int)x, (int)y }, board)) == 2)
	//				return { (int)x, (int)y };
	//		}
	for (uint x = 0; x < board.width(); x++)
		for (uint y = 0; y < board.height(); y++)
			if (isdigit(board(x, y)))
				return { (int)x, (int)y };
	return { -1, -1 };
}
std::vector<vec2> get_nearest_cats(const vec2& pos, const Grid<char>& board)
{
	std::vector<vec2> result;

	int half_width = 16;
	int half_height = 16;

	int min = std::numeric_limits<int>::max();
	for (int x = -half_width; x < half_width + 1; x++)
	{
		int x1 = pos.x + x;
		if (x1 < 0 || x1 >= board.width())
			continue;

		for (int y = -half_height; y < half_height + 1; y++)
		{
			int y1 = pos.y + y;
			if (y1 < 0 || y1 >= board.height())
				continue;

			if (isdigit(board(x1, y1)))
			{
				//int neighbours = get_num_neighbours(get_neighbours(vec2(x1, y1), board));
				//if (!neighbours || neighbours == 1)
				{
					int dist = std::pow(pos.x - x1, 2) + std::pow(pos.y - y1, 2);
					if (dist < min)
					{
						min = dist;
						result.clear();
						result.emplace_back(x1, y1);
					}
					if (dist == min)
						result.emplace_back(x1, y1);
				}
			}
		}
	}
	return result;
}

std::vector<vec2> astar_neighbours(const vec2& pos, const Grid<char>& board)
{
	std::vector<vec2> result;

	for (auto& dir : g_Directions)
	{
		vec2 next = pos + dir.second;
		if (next.x < 0 || next.y < 0 || next.x >= board.width() || next.y >= board.height())
			continue;

		char a = board(next);
		if (a != '#')
			result.push_back(next);
	}
	return result;
}

int astar_heuristic(const vec2& a, const vec2& b) { return abs(a.x - b.x) + abs(a.y - b.y); }
int astar_distance(const vec2& a, const vec2& b) { return std::sqrt(std::pow(a.x - b.x, 2) + std::pow(a.y - b.y, 2)); }

bool astar_search(const vec2& start, const vec2& goal, std::unordered_map<vec2, vec2, VectorHash>& came_from, std::unordered_map<vec2, double, VectorHash>& cost_so_far, const Grid<char>& board)
{
	PriorityQueue<vec2, float> frontier;
	frontier.put(start, 0);

	came_from[start] = start;
	cost_so_far[start] = 0;

	while (!frontier.empty())
	{
		auto current = frontier.get();

		if (current == goal)
			break;

		for (auto& next : astar_neighbours(current, board))
		{
			float new_cost = cost_so_far[current] + astar_distance(current, next);
			if (!cost_so_far.count(next) || new_cost < cost_so_far[next])
			{
				cost_so_far[next] = new_cost;
				float priority = new_cost + astar_heuristic(next, goal);
				frontier.put(next, priority);
				came_from[next] = current;
			}
		}
	}
	return true;
}
std::pair<std::vector<char>, bool> astar_path(const vec2& start, const vec2& goal, const Grid<char>& board)
{
	std::unordered_map<vec2, vec2, VectorHash> came_from;
	std::unordered_map<vec2, double, VectorHash> cost_so_far;
	bool search = astar_search(start, goal, came_from, cost_so_far, board);
	if (!search)
		return { {}, false };

	std::vector<char> path;
	vec2 current, prev = goal;
	while (prev != start)
	{
		current = prev;
		prev = came_from[current];

		vec2 dir = current - prev;
		if (dir == vec2(0, 0))
			break;

		auto it = std::find_if(g_Directions.begin(), g_Directions.end(), [&](const std::unordered_map<Direction, vec2, DirectionHash>::value_type& vt)
		{ return vt.second == dir; });
		if (it != g_Directions.end())
			path.push_back(g_DirectionNames.at(it->first));
		else
			return { path, false };
	}
	return { path, true };
}

bool move_dog(Grid<char>& board, Dog& dog)
{
	int neighbours = get_neighbours(dog.Current, board);
	int num_neighbours = get_num_neighbours(neighbours);

	if (!num_neighbours)
	{
		board(dog.Current) = '.';
		std::vector<vec2> nearest = get_nearest_cats(dog.Current, board);
		
		if (!nearest.empty())
		{
			std::vector<char> shortest_path(200, 'a');

			for (auto& cat : nearest)
			{
				std::pair<std::vector<char>, bool> path = astar_path(dog.Current, cat, board);
				std::reverse(path.first.begin(), path.first.end());
				if (path.second && shortest_path.size() > path.first.size())
					shortest_path = path.first;
			}
			if (shortest_path[0] != 'a')
			{
				for (char dir : shortest_path)
				{
					auto it = std::find_if(g_DirectionNames.begin(), g_DirectionNames.end(), [&](const std::unordered_map<Direction, char, DirectionHash>::value_type& vt)
					{ return vt.second == dir; });
					dog.Current = dog.Current + g_Directions.at(it->first);
					board(dog.Current) = '.';
					dog.Path.push_back(dir);
				}
				return true;
			}
		}
	}
	else
	{
		std::pair<Direction, vec2> chosen_dir = [&]() -> std::pair<Direction, vec2>
		{
			for (int dir = 0; dir < 4; dir++)
			{
				vec2 target = dog.Current + g_Directions.at(Direction(1 << dir));
				if (target.x < 0 || target.y < 0 || target.x >= board.width() || target.y >= board.height())
					continue;
				if (isdigit(board(target)))
					return { Direction(1 << dir), target };
			}
			return { NO,{} };
		}();

		board(dog.Current) = '.';
		dog.Path.push_back(g_DirectionNames.at(chosen_dir.first));
		dog.Current = chosen_dir.second;

		return true;
	}
	return false;
}

int main()
{
	read_input();

	for (uint i = 0; i < g_Fronts.size(); i++)
		g_Fronts[i].FrontNumber = i + 1;

	std::sort(g_Fronts.begin(), g_Fronts.end(), [](const Front& a, const Front& b) -> bool {
		return a.Bonus > b.Bonus;
	});

	for (uint i = 0; i < g_Fronts.size(); i++)
	{
		Front& front = g_Fronts[i];

		vec2 start = get_optimal_start_position(front.Board);
		if (start == vec2(-1, -1))
			continue;

		if (g_Dogs.size() + 1 > g_MaxDogs)
			break;
		Dog dog = { front.FrontNumber, start, start,{} };
		front.Board(start) = '.';
		while (true)
		{
			if (!move_dog(front.Board, dog))
			{
				if (g_Dogs.size() + 1 > g_MaxDogs)
					break;
				g_Dogs.push_back(dog);
				vec2 start = get_optimal_start_position(front.Board);
				if (start == vec2(-1, -1))
					break;
				dog.Path.clear();
				dog.Start = start;
				dog.Current = start;
			}
		}
	}

	output_result();