#include<iostream>
#include<cstring>
#include<climits>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<fstream>
#include<algorithm>

using namespace std;

int workTime;
const int MAXN = 105;

struct state
{
    int dogs, index;
    long long score;
};

struct dog
{
    int grid = 0;
    string way = "";
    pair <int, int> start;

    bool changed = false;
};

struct cat
{
    int value;
    pair <int, int> position;
};

cat A;
priority_queue <cat> Q;

int k, f;
char a[105][MAXN][MAXN];
int prize[105], n[105], m[105];

int dist[MAXN][MAXN];

queue <state> q;
queue < pair <int, int> > BFSq;

bool usedCat[10005];
vector < pair <int, int> > cats[105];

bool used[105][105];

int memo[505][105];
int predecessor[505][105];
bool calculated[505][105], calculatedStates[505][105];

dog action[505], action1[505];

int add;
int precompute[505][105];

bool mode;

bool operator<(const state A, const state B)
{
    if(A.dogs!=B.dogs) return A.dogs<B.dogs;
    if(A.index!=B.index) return A.index<B.index;
//    if(A.level!=B.level) return A.level<B.level;
    if(A.score!=B.score) return A.score<B.score;
}

bool operator != (const state A, const state B)
{
    if(A.dogs!=B.dogs) return true;
//    if(A.level!=B.level) return true;
    if(A.index!=B.index) return true;
    if(A.score!=B.score) return true;

    return false;
}

bool cmp1(const state A, const state B)
{
    if(A.dogs!=B.dogs) return A.dogs<B.dogs;

    if(A.score!=B.score) return A.score<B.score;
    if(A.index!=B.index) return A.index<B.index;
//    if(A.level!=B.level) return A.level<B.level;
}

bool cmp2(const state A, const state B)
{
    if(A.score!=B.score) return A.score<B.score;

    if(A.dogs!=B.dogs) return A.dogs<B.dogs;
    if(A.index!=B.index) return A.index<B.index;
//    if(A.level!=B.level) return A.level<B.level;
}

bool operator <(const cat A, const cat B)
{
    if(A.value!=B.value) return A.value<B.value;
    return A.position<B.position;
}

int dist2Nearest;
pair <int, int> BFS(pair <int, int> x, int index)
{
    pair <int, int> answer;
    memset(dist, false, sizeof(dist));

    while(BFSq.empty()==false) BFSq.pop();

    BFSq.push(x);
    dist[x.first][x.second] = 1;

    answer.first = -1;
    while(BFSq.empty()==false)
    {
        x = BFSq.front();BFSq.pop();

        //cout << x.first << " " << x.second << " ---> " << dist[x.first][x.second] << '\n';
        //cout << used[x.first][x.second] << " " << answer.first << " " << dist[x.first][x.second] << '\n';

        if(used[x.first][x.second]==false && answer.first==-1 && dist[x.first][x.second]>1
           && a[index][x.first][x.second]!='.' && a[index][x.first][x.second]!='#')
        {
            answer = make_pair(x.first, x.second);
            dist2Nearest = dist[x.first][x.second];

            //cout << "Ok " << answer << '\n';
            if(mode==false) return answer;
        }
        //if(a[index][x.first][x.second]!='.' && a[index][x.first][x.second]!='#') continue;

        if(x.first-1>0 && a[index][x.first-1][x.second]!='#' && dist[x.first-1][x.second]==0)
        {
            dist[x.first-1][x.second] = dist[x.first][x.second] + 1;
            BFSq.push(make_pair(x.first-1, x.second));
        }
        if(x.first+1<=n[index] && a[index][x.first+1][x.second]!='#' && dist[x.first+1][x.second]==0)
        {
            dist[x.first+1][x.second] = dist[x.first][x.second] + 1;
            BFSq.push(make_pair(x.first+1, x.second));
        }

        if(x.second-1>0 && a[index][x.first][x.second-1]!='#' && dist[x.first][x.second-1]==0)
        {
            dist[x.first][x.second-1] = dist[x.first][x.second] + 1;
            BFSq.push(make_pair(x.first, x.second-1));
        }
        if(x.second+1<=m[index] && a[index][x.first][x.second+1]!='#' && dist[x.first][x.second+1]==0)
        {
            dist[x.first][x.second+1] = dist[x.first][x.second] + 1;
            BFSq.push(make_pair(x.first, x.second+1));
        }
    }

    return answer;
}

string generateWay(pair <int, int> x, int index)
{
    string answer = "";

    int i = x.first;
    int j = x.second;

    while(dist[i][j]!=1)
    {
        if(i-1>0 && dist[i-1][j]+1==dist[i][j]) {i--;answer += "D";}
        else if(i+1<=n[index] && dist[i+1][j]+1==dist[i][j]) {i++;answer += "U";}
        else if(j-1>=0 && dist[i][j-1]+1==dist[i][j]) {j--;answer += "R";}
        else if(j+1<=m[index] && dist[i][j+1]+1==dist[i][j]) {j++;answer += "L";}
    }

    reverse(answer.begin(), answer.end());
    return answer;
}

int initialDogs;
vector < pair <int, int> > copyCats;

int useDogs(int dogs, int index)
{
    int startDogs = dogs, reached;
    if(dogs==0) return 0;

    int start = clock();

    int limit = cats[index].size()/dogs, catsByDog;
    if(limit==0) limit = 1;

    bool outOfTime = false;
    long long score, answer = 0, w;

    copyCats = cats[index];

    if(n[index]*m[index]<=1005) add = 1;
    else if(n[index]*m[index]>=3000) add = sqrt(limit);
    else add = limit/15;

    if(add==0) add++;

    pair <int, int> x;
    for(int c = (limit);c<=limit;c+=add)
    {
        if(clock()-start>=workTime) break;

        if(outOfTime==true) break;
        for(int style = 0;style<1;style++)
        {
            if(clock()>=((mode==true)?4900:((f>=2 && f<=100)?4550:3600))) break;

            while(Q.empty()==false) Q.pop();
            for(int i = 0;i<cats[index].size();i++)
            {
                A.position = cats[index][i];
                A.value = a[index][ cats[index][i].first ][ cats[index][i].second ];

                Q.push(A);
            }

            if(mode==true)
            {
                for(int i = 0;i<k;i++)
                {
                    action1[i].grid = 0;
                    action1[i].way = "";

                    action1[i].changed = false;
                }
            }

            w = 0;score = 0;dogs = startDogs;reached = 0;
            memset(usedCat, false, sizeof(usedCat));
            memset(used, false, sizeof(used));

            catsByDog = c;bool toDo = false;
            if(catsByDog==0) catsByDog++;

            while(Q.empty()==false)
            {
                if(clock()-start>=workTime) break;

                while(Q.empty()==false && used[ Q.top().position.first ][ Q.top().position.first ]==true) Q.pop();
                if(Q.empty()==true) break;

                x = Q.top().position;Q.pop();

                if(dogs==0) break;
                if(used[ x.first ][ x.second ]==false)
                {
                    dogs--;score += a[index][ x.first ][ x.second ] - '0';;
                    if(dogs==0 && startDogs<cats[index].size() && style==0) catsByDog += cats[index].size()%startDogs;

                    if(mode==true)
                    {
                        action1[k-(initialDogs-dogs)].grid = index + 1;
                        action1[k-(initialDogs-dogs)].start = x;

                        action1[k-(initialDogs-dogs)].changed = true;
                    }

                    //if(c==4 && style==0)cout << "---" << '\n';
                    for(int j = 0;j<catsByDog;j++)
                    {
                        if(clock()>=((mode==true)?4900:((f>=2 && f<=100)?4550:3600))) break;

                        reached++;
                        toDo = false;
                        //cout << x.first << " " << x.second << " || " <<  a[index][ x.first ][ x.second ] - '0' << " -> " << '\n';

                        //usedCat[i1] = true;
                        used[ x.first ][ x.second ] = true;


                        x = BFS(x, index);

                        if(x.first==-1 || j==catsByDog-1) break;
                        //cout << x.first << " " << x.second << " - " << dist[ x.first ][ x.second ] << "\n";

                        /*
                        i1++;
                        if(i1>=cats[index].size() || i1>=i+catsByDog) break;
                        */

                        /*
                        i1 = findNearest(index);
                        if(i1==-1) break;
                        */

                        if(mode==true)
                        {
                            action1[k-(initialDogs-dogs)].way += generateWay(x, index);
                            if(action1[k-dogs-1].way.size()>=19505) break;
                        }

                        toDo = true;
                        w += dist2Nearest - 1;
                        score += a[index][ x.first ][ x.second ] - '0';
                    }

                    if(x.first!=-1 && toDo==true)
                    {
                        //usedCat[i1] = true;
                        used[ x.first ][ x.second ] = true;
                    }

                }
            }

            //if(c==4 && style==0) cout << score << " " << w << '\n';
            score = 2*score - w + ((reached==cats[index].size())?prize[index]:0);
            //if(score==97) {cout << c << " " << style << " - " << w << " " << catsByDog << " " << t << '\n';exit(0);}

            if(answer<score && mode==true)
            {
                answer = score;
                for(int i = 0;i<k;i++)
                {
                    if(action1[i].changed==true) {action[i] = action1[i];}
                }

            }
            else answer= max(answer, score);
        }
    }

    int i1;
    if(cats[index].size()<=6)
    {
        pair <int, int> x;

        do
        {
            for(int c = (limit);c<=limit;c+=add)
            {
                if(clock()-start>=workTime) break;

                if(outOfTime==true) break;
                for(int style = 0;style<1;style++)
                {
                    if(clock()>=((mode==true)?4900:((f>=2 && f<=100)?4550:3600))) break;

                    if(mode==true)
                    {
                        for(int i = 0;i<k;i++)
                        {
                            action1[i].grid = 0;
                            action1[i].way = "";

                            action1[i].changed = false;
                        }
                    }

                    w = 0;score = 0;dogs = startDogs;reached = 0;
                    memset(usedCat, false, sizeof(usedCat));
                    memset(used, false, sizeof(used));

                    catsByDog = c;bool toDo = false;
                    if(catsByDog==0) catsByDog++;

                    for(int i = 0;i<cats[index].size();i++)
                    {
                        if(dogs==0) break;
                        if(used[ cats[index][i].first ][ cats[index][i].second ]==false)
                        {
                            dogs--;score += a[index][ cats[index][i].first ][ cats[index][i].second ] - '0';;
                            if(dogs==0 && startDogs<cats[index].size() && style==0) catsByDog += cats[index].size()%startDogs;

                            if(mode==true)
                            {
                                action1[k-(initialDogs-dogs)].grid = index + 1;
                                action1[k-(initialDogs-dogs)].start = cats[index][i];

                                action1[k-(initialDogs-dogs)].changed = true;
                            }

                            //if(c==4 && style==0)cout << "---" << '\n';
                            x = cats[index][i];
                            for(int j = 0;j<catsByDog;j++)
                            {
                                if(clock()>=((mode==true)?4900:((f>=2 && f<=100)?4550:3600))) break;

                                reached++;
                                toDo = false;
                                //cout << x.first << " " << x.second << " || " <<  a[index][ x.first ][ x.second ] - '0' << " -> " << '\n';

                                //usedCat[i1] = true;
                                used[ x.first ][ x.second ] = true;


                                x = BFS(x, index);

                                if(x.first==-1 || j==catsByDog-1) break;
                                //cout << x.first << " " << x.second << " - " << dist[ x.first ][ x.second ] << "\n";

                                /*
                                i1++;
                                if(i1>=cats[index].size() || i1>=i+catsByDog) break;


                                /*
                                i1 = findNearest(index);
                                if(i1==-1) break;
                                */

                                if(mode==true)
                                {
                                    action1[k-(initialDogs-dogs)].way += generateWay(x, index);
                                    if(action1[k-dogs-1].way.size()>=19505) break;
                                }

                                toDo = true;
                                w += dist2Nearest - 1;
                                score += a[index][ x.first ][ x.second ] - '0';
                            }

                            if(x.first!=-1 && toDo==true)
                            {
                                //usedCat[i1] = true;
                                used[ x.first ][ x.second ] = true;
                            }

                        }
                    }

                    //if(c==4 && style==0) cout << score << " " << w << '\n';
                    score = 2*score - w + ((reached==cats[index].size())?prize[index]:0);
                    //if(score==97) {cout << c << " " << style << " - " << w << " " << catsByDog << " " << t << '\n';exit(0);}

                    if(answer<score && mode==true)
                    {
                        answer = score;
                        for(int i = 0;i<k;i++)
                        {
                            if(action1[i].changed==true) {action[i] = action1[i];}
                        }

                    }
                    else answer= max(answer, score);
                }
            }
        }
        while(next_permutation(cats[index].begin(), cats[index].end()));
    }
    else
    {

        pair <int, int> x;
        bool toDo;

        int r;


        for(int r = 0;r<30;r++)
        {
            if(clock()-start>=workTime) break;
            if(clock()>=((mode==true)?4900:((f>=2 && f<=100)?4550:3600))) break;

            for(int c = (limit);c<=limit;c+=add)
            {
                if(clock()-start>=workTime) break;

                if(outOfTime==true) break;
                for(int style = 0;style<1;style++)
                {
                    if(clock()>=((mode==true)?4900:((f>=2 && f<=100)?4550:3600))) break;

                    if(mode==true)
                    {
                        for(int i = 0;i<k;i++)
                        {
                            action1[i].grid = 0;
                            action1[i].way = "";

                            action1[i].changed = false;
                        }
                    }

                    w = 0;score = 0;dogs = startDogs;reached = 0;
                    memset(usedCat, false, sizeof(usedCat));
                    memset(used, false, sizeof(used));

                    catsByDog = c;toDo = false;
                    if(catsByDog==0) catsByDog = 1;

                    for(int i = 0;i<cats[index].size();i++)
                    {
                        if(dogs==0) break;
                        if(used[ cats[index][i].first ][ cats[index][i].second ]==false)
                        {
                            dogs--;score += a[index][ cats[index][i].first ][ cats[index][i].second ] - '0';;
                            if(dogs==0 && startDogs<cats[index].size() && style==0) catsByDog += cats[index].size()%startDogs;

                            if(mode==true)
                            {
                                action1[k-(initialDogs-dogs)].grid = index + 1;
                                action1[k-(initialDogs-dogs)].start = cats[index][i];

                                action1[k-(initialDogs-dogs)].changed = true;
                            }

                            //if(c==4 && style==0)cout << "---" << '\n';
                            x = cats[index][i];
                            for(int j = 0;j<catsByDog;j++)
                            {
                                if(clock()>=((mode==true)?4900:((f>=2 && f<=100)?4550:3600))) break;

                                reached++;
                                toDo = false;
                                //cout << x.first << " " << x.second << " || " <<  a[index][ x.first ][ x.second ] - '0' << " -> " << '\n';

                                //usedCat[i1] = true;
                                used[ x.first ][ x.second ] = true;
                                x = BFS(x, index);

                                if(x.first==-1 || j==catsByDog-1) break;
                                //cout << x.first << " " << x.second << " - " << dist[ x.first ][ x.second ] << "\n";

                                /*
                                i1++;
                                if(i1>=cats[index].size() || i1>=i+catsByDog) break;

                                /*
                                i1 = findNearest(index);
                                if(i1==-1) break;
                                */

                                if(mode==true)
                                {
                                    action1[k-(initialDogs-dogs)].way += generateWay(x, index);
                                    if(action1[k-dogs-1].way.size()>=19505) break;
                                }


                                toDo = true;
                                w += dist2Nearest - 1;
                                score += a[index][ x.first ][ x.second ] - '0';
                            }

                            if(x.first!=-1 && toDo==true)
                            {
                                //usedCat[i1] = true;
                                used[ x.first ][ x.second ] = true;
                            }

                        }
                    }

                    //if(c==4 && style==0) cout << score << " " << w << '\n';
                    score = 2*score - w + ((reached==cats[index].size())?prize[index]:0);
                    //if(score==83) {cout << c << " " << style << " - " << w << " " << catsByDog << '\n';exit(0);}

                    if(answer<score && mode==true)
                    {
                        answer = score;
                        for(int i = 0;i<k;i++)
                        {
                            if(action1[i].changed==true) {action[i] = action1[i];}
                        }

                    }
                    else answer= max(answer, score);
                }
            }

            shuffle(cats[index].begin(), cats[index].begin(), default_random_engine(r*r));
            //prev_permutation(cats[index].begin(), cats[index].end());
        }
    }



    cats[index] = copyCats;

    //cout << "---" << '\n';
    //for(int i = 0;i<cats[index].size();i++)
    //    cout << copyCats[index].first << " " << copyCats[index].second << '\n';

    return answer;
}


int calcSate(int dogs, int index, int score)
{
    //cout << dogs << " " << index << " -> " << score << '\n';

    if(index==f) return score;
    if(calculated[dogs][index]==true) return memo[dogs][index] + score;

    int maxScore = 0, pred, current;
    for(int i = 0;i<=dogs;i++)
    {
        if(clock()>=((f>=2 && f<=100)?4550:3600))
        {
            memo[dogs][index] = maxScore - score;
            predecessor[dogs][index] = pred;

            return maxScore;
        }
        if(i>cats[index].size()) break;

        if(calculatedStates[i][index]==false)
        {
            calculatedStates[i][index] = true;
            precompute[i][index] = useDogs(i, index);
        }

        current = calcSate(dogs-i, index+1, score+precompute[i][index]);
        if(current>maxScore)
        {
            maxScore = current;
            pred = i;
        }
    }

    memo[dogs][index] = maxScore - score;
    predecessor[dogs][index] = pred;
    calculated[dogs][index] = true;

    return maxScore;
}

int main()
{
    int start, stop;
    long long answer = 0;;

    ifstream cin("catsdogs.in");
    ofstream cout("catsdogs.out");

    start = clock();

    cin >> f >> k;
    for(int t = 0;t<f;t++)
    {
        cin >> n[t] >> m[t] >> prize[t];
        cin.get();

        for(int i = 1;i<=n[t];i++)
        {
            for(int j = 1;j<=m[t];j++)
                cin.get(a[t][i][j]);
            cin.get();
        }

        for(int i = 1;i<=n[t];i++)
        {
            for(int j = 1;j<=m[t];j++)
            {
                if(a[t][i][j]!='.' && a[t][i][j]!='#')
                {
                    cats[t].push_back(make_pair(i, j));
                }

            }
        }
    }

    if(k==1) workTime = 3700/f;
    else if(f<=1) workTime = 3700/k;
    else if(f<=50) workTime = 125;
    else workTime = 65;

    calcSate(k, 0, 0);

    mode = true;
    int dogs = k, index = 0;

    for(int i = 0;i<f;i++)
    {
        initialDogs = dogs;
        useDogs(predecessor[dogs][i], i);

        dogs -= predecessor[dogs][i];
    }

    for(int i = 0;i<k;i++)
    {
        if(action[i].grid==0) cout << action[i].grid << '\n';
        else
        {
            cout << action[i].grid << '\n';
            cout << action[i].start.first << " " << action[i].start.second << '\n';

            if(action[i].way=="") cout << "STAY" << '\n';
            else
            {
                //reverse(action[i].way.begin(), action[i].way.end());
                cout << action[i].way << '\n';
            }
        }
    }

    return 0;
}
/*
1 8
3 3 0
999
999
99#
*