#include <fstream>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <exception>
#include <algorithm>
#include <numeric>
#include <stdint.h>
#include <chrono>

const int MAX_N = 100;
const int MAX_M = 100;
const int MAX_B = 10000;
const int MAX_F = 100;
const int MAX_K = 500;
const int MAX_MOVES = 20000;
const char* STAY = "STAY";
const uint8_t wall = 255, no_wall = 0;

using namespace std;

class my_exception : exception
{
    const char* _msg;
public:
    my_exception(const char* msg) : _msg(msg) {}
    virtual const char* what() const throw() { return _msg; }
};

struct cat
{
    int X, Y, P;

    cat(int x, int y, int p) : X(x), Y(y), P(p)
    {
    }

    static int is_cat(uint8_t c) {
        return c >= 1 && c <= 9;
    }
    static int cat_power(uint8_t c) {
        return is_cat(c) ? c : 0;
    }
    int abs_dist(const cat& o) {
        int dx = X - o.X, dy = Y -o.Y;
        return abs(dx) + abs(dy);
    }
};

struct field
{
    int F, N, M, B;
//#define USE_VV
#ifdef USE_VV
    vector<vector<uint8_t>> map2;
#else
    vector<uint8_t> map1;
#endif

    void read(istream& s)
    {
        int n, m, b;
        s >> n >> m >> b;
        if (n < 1 || n > MAX_N)
            throw my_exception("N out of range");
        if (m < 1 || m > MAX_M)
            throw my_exception("M out of range");
        if (b < 1 || b > MAX_B)
            throw my_exception("B out of range");

        N = n;
        M = m;
        B = b;

#ifdef USE_VV
        map2.resize(n);
        for_each(map2.begin(), map2.end(), [m](vector<uint8_t>& row) { row.resize(m); });
#else
        map1.resize(n * m);
#endif
        for(int y=0; y < n; y++) {
            string l;
            s >> l;
            if ((int)l.size() != m)
                throw my_exception("field row incorrect size");
            for(int x=0; x < m; x++) {
                char c = l[x];
				uint8_t res;
                if (c == '.')
                    res = no_wall;
                else if (c == '#')
                    res = wall;
                else if (c >= '1' || c <= '9')
                    res = c - '0';
                else
                    throw my_exception("invalid field character");
				operator()(x, y) = res;
            }
       }
    }

    void find_cats(list<cat>& cats) const {
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < M; x++) {
                uint8_t c = operator()(x, y);
                if (cat::is_cat(c)) {
                    cats.push_back(cat(x, y, cat::cat_power(c)));
                }
            }
        }
    }
    bool has_cat() const {
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < M; x++) {
                uint8_t c = operator()(x, y);
                if (cat::is_cat(c)) {
                    return true;
                }
            }
        }
        return false;
    }
	inline uint8_t operator()(int x, int y) const
    { 
#ifdef USE_VV
        return map2[y][x];
#else
        return map1[x + y * M]; 
#endif
    }
	inline uint8_t& operator()(int x, int y)
    { 
#ifdef USE_VV
        return map2[y][x];
#else
        return map1[x + y * M]; 
#endif
    }
};

struct dog
{
    int F, X, Y;
    string path;

    dog() : F(0), X(0), Y(0) {}

    void write(ostream& s) const {
        if (F < 0)
            throw my_exception("invalid F set for dog");
        s << F << endl;
        if (F > 0) {
            s << Y + 1 << " " << X + 1 << endl;
            s << path << endl;
        }
    }

    void set_at_cat(int f, const cat& c) {
        F = f;
        X = c.X;
        Y = c.Y;
        path = STAY;
    }
};

struct solution
{
    int F, K;
    vector<field> fields;
    vector<dog> dogs;

    void read(istream& s) {
        s >> F >> K;
        if (F < 1 || F > MAX_F)
            throw my_exception("F out of range");
        fields.resize(F);

        if (K < 1 || K > MAX_K)
            throw my_exception("K out of range");
        dogs.resize(K);

        // load fields
        for (int f = 0; f < F; f++)
        {
            fields[f].F = f + 1;
            fields[f].read(s);
#ifdef DUMP
            dump(fields[f]);
#endif // DUMP
        }
    }

    void write(ostream& s) const {
        for (int k = 0; k < K; k++) {
            dogs[k].write(s);
#ifdef DUMP
            dump(dogs[k]);
#endif // DUMP
        }
    }

    int calc_all_dogs_score(const vector<dog>& dgs) const {
        vector<field> fc = fields;
        return accumulate(dgs.begin(), dgs.end(), 0, [this, &fc](int s, const dog& d) { return s + calc_dog_score(fc, d, true); }) +
               accumulate(fc.begin(), fc.end(), 0, [](int s, const field& f) { return s + (f.has_cat() ? 0 : f.B); });
    }

    int calc_dog_score(const dog& d) const {
        return calc_dog_score(const_cast<vector<field>&>(fields), d, false);
    }

    static int calc_dog_score(vector<field>& fc, const dog& d, bool update_field) {
        if (d.F == 0)
            return 0;

        if (d.F < 0 || d.F > (int)fc.size())
            throw my_exception("invalid field set for dog");
        field& f = fc[d.F - 1];

        int x = d.X, y = d.Y;
        int p = cat::cat_power(f(x, y)), tp = 2 * p;
		if (!d.path.empty() && d.path != STAY) {
            tp -= d.path.size();
            for(string::const_iterator ci = d.path.begin(); ci != d.path.end(); ci++) {
                char c = *ci;
                if (c == 'L')
                    x = x - 1;
                else if (c == 'R')
                    x = x + 1;
                else if (c == 'U')
                    y = y - 1;
                else if (c == 'D')
                    y = y + 1;
                else
                    throw my_exception("invalid move char for dog");
                if (x < 0 || x >= f.M || y < 0 || y >= f.N)
                    throw my_exception("step out of field for dog");
                uint8_t cf = f(x, y);
                if (cf == wall)
                    throw my_exception("step at wall for dog");
                int p = cat::cat_power(cf);
                tp += 2 * p;
                if (update_field && p > 0)
                    f(x, y) = 0;
            }
        }
        return tp;
    }

    struct cats_in_field
    {
        int F, B, TCP;
        list<cat> cats;

        void set(const field& f) {
            F = f.F;
            B = f.B;
            f.find_cats(cats);
            cats.sort([](const cat& l, const cat& r) { return l.P > r.P; });
            TCP = accumulate(cats.begin(), cats.end(), 0, [](int s, const cat& c) { return s + c.P; });
        }
    };

    void solve() {

		auto start = chrono::steady_clock::now();


        // cats in all fields
        int totalCats = 0;
        vector<cats_in_field> cats_per_field(F);
        for (int f = 0; f < F; f++) {
            cats_per_field[f].set(fields[f]);
            totalCats += cats_per_field[f].cats.size();
        }
        // sort fields per max cat power
        sort(cats_per_field.begin(), cats_per_field.end(), [this](const cats_in_field& l, const cats_in_field& r) {
            return l.B > r.B && K != 1 || l.B + l.TCP > r.B + r.TCP && K == 1 || (l.B == r.B && l.TCP > r.TCP);
        });

#ifdef DUMP
        for_each(cats_per_field.begin(), cats_per_field.end(), [this](const cats_in_field& cs) {
            for_each(cs.cats.begin(), cs.cats.end(), [this](const cat& c) { dump(c); });
        });
#endif // DUMP
        // if we have enough dogs set each at one cat
        if (totalCats <= K)
        {
            int k = 0;
            for_each(cats_per_field.begin(), cats_per_field.end(), [this, &k](const cats_in_field& cs) {
                for_each(cs.cats.begin(), cs.cats.end(), [this, &cs, &k](const cat& c) { dogs[k++].set_at_cat(cs.F, c); });
            });
            while (k < K) {
                dogs[k++].F = 0;
            }
            return;
        }

		int max_score = INT32_MIN;
        if (K == 1) {
            dog d;
            d.F = 0;
            for (vector<cats_in_field>::iterator ifcs = cats_per_field.begin(); not_expired(start) && ifcs != cats_per_field.end(); ifcs++) {
                list<cat> cso = ifcs->cats;
                int iF = ifcs->F;
                const field& f = fields[iF - 1];
                int nc = cso.size();
                if (nc == 0)
                    continue;
                int fcp = cso.front().P;
                for (int i = 0; i < nc && not_expired(start) && cso.front().P == fcp; i++) {
                    list<cat> cs = cso;
                    cso.push_back(cso.front());
                    cso.pop_front();
                    cat c = cs.front();
                    cs.pop_front();
                    d.set_at_cat(iF, c);

                    int my_score = calc_dog_score(d);
                    if (my_score > max_score) {
                        max_score = my_score;
                        dogs[0] = d;
                    }

                    list<cat> cs2 = cs;
                    string path;
                    path = find_direct_cats(f, cs2, c, start);
                    if (!path.empty()) {
                        d.path = path;

                        my_score = calc_dog_score(d);
                        if (my_score > max_score) {
                            max_score = my_score;
                            dogs[0] = d;
                        }
                    }
                    
                    path = find_all_reachable_cats(f, cs, c, start);
                    if (!path.empty()) {
                        d.path = path;

                        my_score = calc_dog_score(d);
                        if (my_score > max_score) {
                            max_score = my_score;
                            dogs[0] = d;
                        }
                    }
                }
            }
        } else {
            if (F == 1) {
                vector<dog> dgs(K);
                try_find_all_dogs(cats_per_field, dgs, false, start + chrono::milliseconds(4500));
                vector<dog> dgs2(K);
                try_find_all_dogs(cats_per_field, dgs2, true, start);
                dogs = calc_all_dogs_score(dgs) > calc_all_dogs_score(dgs2) ? dgs : dgs2;
            } else {
                vector<dog> dgs(K);
                try_find_all_dogs(cats_per_field, dgs, true, start);
                dogs = dgs;
            }
        }
    }

    void try_find_all_dogs(const vector<cats_in_field>& cats_per_field, vector<dog>& dgs, bool search_all, chrono::steady_clock::time_point start) const {
        for_each(dgs.begin(), dgs.end(), [](dog& dg) { dg.F = 0; });

        // set dog to directly eat cat
        auto ifcs = cats_per_field.begin();
        int k = 0;
        while (k < K) {
			if (!not_expired(start) || ifcs == cats_per_field.end()) {
                // time is up or no more cats
                dgs[k++].F = 0;
                continue;
            }

            list<cat> cso = ifcs->cats;
            int iF = ifcs->F;
            const field& f = fields[iF - 1];
            ifcs++;
            int nc = cso.size();
            if (nc == 0)
                continue;

            int max_score;
            dog d;
			while (k < K && not_expired(start) && !cso.empty()) {
                max_score = INT32_MIN;
                d.F = 0;
                list<cat> csr = cso;
                auto fc = cso.front();
                int fcp = fc.P;
                for (int i = 0; i < nc && not_expired(start) && (cso.front().P == fcp || nc <10); i++) {
                    list<cat> cs = cso;
                    cso.push_back(cso.front());
                    cso.pop_front();
                    cat c = cs.front();
                    cs.pop_front();
                    d.set_at_cat(iF, c);

                    int my_score = calc_dog_score(d);
                    if (my_score > max_score) {
                        max_score = my_score;
                        dgs[k] = d;
                        csr = cs;
                    }

                    list<cat> cs2 = cs;
                    string path;
                    path = find_direct_cats(f, cs2, c, start);
                    if (!path.empty()) {
                        d.path = path;

                        int my_score = calc_dog_score(d);
                        if (my_score > max_score) {
                            max_score = my_score;
                            dgs[k] = d;
                            csr = cs2;
                        }
                    }
                    
                    if (search_all) {
                        path = find_all_reachable_cats(f, cs, c, start);
                        if (!path.empty()) {
                            d.path = path;

                            int my_score = calc_dog_score(d);
                            if (my_score > max_score) {
                                max_score = my_score;
                                dgs[k] = d;
                                csr = cs;
                            }
                        }
                    }
                }
                k++;
                cso = csr;
            }
        }
    }

    static string find_all_reachable_cats(const field& f, list<cat>& cs, cat c, chrono::steady_clock::time_point start) {
        string path;
		while (not_expired(start) && !cs.empty()) {
            list<cat>::iterator ic = cs.begin(), inc = ic;
            int nd = c.abs_dist(*inc);
            while (++ic != cs.end()) {
                int d = c.abs_dist(*ic);
                if (d < nd) {
                    inc = ic;
                    nd = d;
                }
            }
			cat c1 = *inc;
            string chunk = path_to_cat(f, c, c1);
			if (chunk.empty()) {
                break;
            } else {
				clear_cats_on_path(f, c.X, c.Y, chunk, cs, start);
                path += chunk;
				c = c1;
            }
        }
        return path;
    }

    static string find_direct_cats(const field& f, list<cat>& cs, cat c, chrono::steady_clock::time_point start) {
        string path;
        list<cat>::iterator ic1 = cs.begin();
        while ((int)path.size() < MAX_MOVES && not_expired(start) && ic1 != cs.end()) {
			const cat& c1 = *ic1;
            int dx = c1.X - c.X, dy = c1.Y - c.Y;
            int adx = abs(dx), ady = abs(dy);
            if (adx + ady < 2 * c1.P) {
				string chunk;
                if (direct_path_to_cat(f, c, c1, chunk))
				{
					//clear_cats_on_path(f, c.X, c.Y, chunk, cs, end);
                    c = c1;
                    ic1 = cs.erase(ic1);
                    path += chunk;
                    continue;
                }
            }
            ic1++;
        }
        return path;
    }

	static void clear_cats_on_path(const field& f, int x, int y, string path, list<cat>& cs, chrono::steady_clock::time_point start) {
		for (auto i = path.begin(); not_expired(start) && i != path.end(); i++) {
			switch (*i)
			{
			case 'L': x--; break;
			case 'R': x++; break;
			case 'U': y--; break;
			case 'D': y++; break;
			default:
				throw my_exception("invalid direction");
			}
			if (x < 0 || x >= f.M || y < 0 || y >= f.N)
				throw my_exception("move outside field");
			uint8_t ch = f(x, y);
			if (ch == wall)
				throw my_exception("move to wall");
			if (cat::is_cat(ch)) {
				for (auto ic = cs.begin(); not_expired(start) && ic != cs.end(); ic++)
				{
					if (ic->X == x && ic->Y == y) {
						cs.erase(ic);
						break;
					}
				}
			}
		}
	}

    static inline bool not_expired(chrono::steady_clock::time_point start, chrono::milliseconds delay = chrono::milliseconds(4900)) { return chrono::steady_clock::now() < start + delay; }

	static inline bool can_move_to(const field& f, int x, int y)
	{
		return x >= 0 && x < f.M && y >= 0 && y < f.N && (f(x, y) & 0x80) == 0;
	}

    static string path_to_cat(const field& fs, const cat& c, const cat& c1) {
        field f = fs;
        string path;
        int x = c.X, y = c.Y, x1 = c1.X, y1 = c1.Y;
		bool lastH = false;
        while (x != x1 || y != y1) {
            int dx = x1 - x, dy = y1 - y;
            int sx = dx > 0 ? 1 : dx < 0 ? -1 : 0;
            int sy = dy > 0 ? 1 : dy < 0 ? -1 : 0;
            f(x, y) |= 0x80;
			bool canMoveX = sx != 0 && can_move_to(f, x + sx, y);
			bool canMoveY = sy != 0 && can_move_to(f, x, y + sy);
			if (canMoveX && !canMoveY) {
                path += sx > 0 ? 'R' : 'L';
                x += sx;
				lastH = true;
                continue;
			} else if (!canMoveX && canMoveY) {
                path += sy > 0 ? 'D' : 'U';
                y += sy;
				lastH = false;
                continue;
            } else if (canMoveX && canMoveY) {
				if (lastH) {
					path += sx > 0 ? 'R' : 'L';
					x += sx;
					continue;
				} else {
					path += sy > 0 ? 'D' : 'U';
					y += sy;
					continue;
				}
            } else {
				bool canMoveBackX = sx != 0 && can_move_to(f, x - sx, y);
				bool canMoveBackY = sy != 0 && can_move_to(f, x, y - sy);
				if (canMoveBackX && !canMoveBackY) {
					path += sx > 0 ? 'L' : 'R';
					x -= sx;
					lastH = true;
					continue;
				} else if (!canMoveBackX && canMoveBackY) {
					path += sy > 0 ? 'U' : 'D';
					y -= sy;
					lastH = false;
					continue;
				} else if (canMoveBackX && canMoveBackY) {
					if (lastH) {
						path += sx > 0 ? 'L' : 'R';
						x -= sx;
						continue;
					} else {
						path += sy > 0 ? 'U' : 'D';
						y -= sy;
						continue;
					}
				} else {
					if (sx != 0) {
						if (can_move_to(f, x, y + 1)) {
							path += 'D';
							y++;
							lastH = false;
							continue;
						} else if (can_move_to(f, x, y - 1)) {
							path += 'U';
							y--;
							lastH = false;
							continue;
						} else if (can_move_to(f, x - sx, y)) {
							path += sx > 0 ? 'L' : 'R';
							x -= sx;
							lastH = true;
							continue;
						}
					} else { // sy != 0
						if (can_move_to(f, x + 1, y)) {
							path += 'R';
							x++;
							lastH = true;
							continue;
						} else if (can_move_to(f, x - 1, y)) {
							path += 'L';
							x--;
							lastH = true;
							continue;
						} else if (can_move_to(f, x, y - sy)) {
							path += sy > 0 ? 'U' : 'D';
							y -= sy;
							lastH = false;
							continue;
						}
					}
				}
            }
            // if no moves back then return
            if (path.empty())
                return path;
            // move back one step
			char lastMove = path.back();
			path.pop_back();
            switch (lastMove) {
                case 'L': x += 1; break;
                case 'R': x -= 1; break;
                case 'U': y += 1; break;
                case 'D': y -= 1; break;
            }
        }

        return path;
    }

    static bool direct_path_to_cat(const field& f, const cat& c, const cat& c1, string& path) {
        int dx = c1.X - c.X, dy = c1.Y - c.Y;
        int adx = abs(dx), ady = abs(dy);
        int sx = dx > 0 ? 1 : dx < 0 ? -1 : 0;
        int sy = dy > 0 ? 1 : dy < 0 ? -1 : 0;
        char lr = dx > 0 ? 'R' : 'L';
        char ud = dy > 0 ? 'D' : 'U';
        path.reserve(adx + ady + 1);
        path.clear();
        if (sx == 0) {
            for(int y = c.Y; y != c1.Y; y += sy ) {
                if (f(c.X, y) == wall) {
                    path.clear();
                    return false;
                }
                path.push_back(ud);
            }
            return true;
        } else if (sy == 0) {
            for(int x = c.X; x != c1.X; x += sx ) {
                if (f(x, c.Y) == wall) {
                    path.clear();
                    return false;
                }
                path.push_back(lr);
            }
            return true;
        } else {
            for (int xe = c1.X; xe != c.X; xe -= sx) {
                bool move_in_x = true;
                int x = c.X, y = c.Y, xstop = xe;
                path.clear();
                while (true) {
                    if (move_in_x) {
                        while (x != xstop && f(x + sx, y) != wall) {
                            x += sx;
                            path.push_back(lr);
                        }
                        xstop = c1.X;
                    } else {
                        while (y != c1.Y && f(x, y + sy) != wall) {
                            y += sy;
                            path.push_back(ud);
                        }
                    }
                    if ((x == c1.X || f(x + sx, y) == wall) &&
                        (y == c1.Y || f(x, y + sy) == wall))
                        break;
                    move_in_x = !move_in_x;
                }
                if (x == c1.X && y == c1.Y) {
                    return true;
                }
            }
        }
        return false;
    }
#ifdef DUMP
    static void dump(const cat& c)
    {
        cout << "cat X=" << c.X << ", Y=" << c.Y << ", P=" << c.P << endl;
    }
    static void dump(const field& f) {
        cout << "field F:" << f.F << ", M:" << f.M << ", N:" << f.N << ", B:" << f.B << endl;
        for(int y = 0; y < f.N; y++) {
            cout << "   ";
			for (int x = 0; x < f.M; x++) {
				uint8_t c = f(x, y);
				cout << (char)(c >= 1 && c <= 9 ? c + '0' :
								c == no_wall ? '.' : c == wall ? '#' : '?');
			}
            cout << endl;
        }
    }
    void dump(const dog& d) const {
        cout << "dog F:" << d.F << ", X:" << d.X + 1 << ", Y:" << d.Y + 1<< ", P:" << d.path << ", S:" << calc_dog_score(d) << endl;
    }
#endif // DUMP
};

int main()
{
    try
    {
        solution s;

        fstream fin;
#if DUMP
		fin.open("catsdogs2.in", ios_base::in);
#else
		fin.open("catsdogs.in", ios_base::in);
#endif
        s.read(fin);

        s.solve();

        fstream fout;
        fout.open("catsdogs.out", ios_base::out);
        s.write(fout);

        return 0;
    }
    catch(exception& ex)
    {
        cerr << ex.what() << endl;
        return 1;
    }