#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <ctime>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <math.h>
#include <stack>
#include <deque>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <bitset>

using namespace std;

const int MOVES[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const char MOVES_CHAR[4] = { 'D', 'R', 'U', 'L' };
const clock_t TIME_LIMIT = (clock_t) (4.0 * CLOCKS_PER_SEC);
const clock_t HARD_LIMIT = (clock_t) (4.85 * CLOCKS_PER_SEC);
clock_t BEGIN_TIME;

/*
'U' (x, y) to (x-1, y). [Up]
'R' (x, y) to (x, y+1). [Right]
'D' (x, y) to (x+1, y). [Down]
'L' (x, y) to (x, y-1). [Left]
*/

int F, K, PRINTED_DOGS = 0;
int Ni[101], Mi[101], Bi[101];
char Fr[101][101][101];
int FrO[101][101][101];

inline bool isCat(int bfield, int x, int y) {
    return Fr[bfield][x][y] <= '9' && Fr[bfield][x][y] >= '1';
}

typedef pair<int, int> Cat;

struct Path {
    Cat fromCat, toCat;
    string str;
    bool marked;
    Path() {
        marked = false;
    }
    Path& operator= (const Path& oth) {
       if (this != &oth) {
         fromCat = oth.fromCat;
         toCat = oth.toCat;
         str = oth.str;
         marked = oth.marked;
       }
       return *this;
    }
};

struct Field {
    int bField;
    vector<Cat> cats;
    vector<Path> paths;
	 int points;
	 int pointsPlusPathPrice;
    int dogs;
	 Field() {
		 points = 0;
       dogs = 0;
		 pointsPlusPathPrice = 0;
	 }
    void print1Dog() {
      int bestResult = pointsPlusPathPrice;
      vector<Path> bestPaths = paths;
      for (int iter = 0; clock() - BEGIN_TIME < HARD_LIMIT && iter < 10; ++iter) {
         int BASELINE = iter * 1000000;
         int startingCatIdx = iter == 0
               ? (int) cats.size() - 1
               : rand() % cats.size();
         int curPts = points;
         vector<Path> curPaths;
         Cat cur = cats[startingCatIdx];
         int taken = 1;
         set<Cat> visCats;
         visCats.insert(cur);
         queue<Cat> q;
         q.push(cur);
         while (taken < (int) cats.size()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int mv = 0; mv < 4; ++mv) {
               int nx = x + MOVES[mv][0];
               int ny = y + MOVES[mv][1];
               if (nx < 0 || nx >= Ni[bField]
                   || ny < 0 || ny >= Mi[bField]
                   || Fr[bField][nx][ny] == '#') continue;
               int valueInPaths = FrO[bField][nx][ny];
               if (valueInPaths > BASELINE + ((taken - 1) * 4)) continue;
               FrO[bField][nx][ny] = BASELINE + ((taken - 1) * 4) + 1 + mv;
               Cat newCat = make_pair(nx, ny);
               q.push(newCat);
               if (isCat(bField, nx, ny) && !visCats.count(newCat)) {
                  curPaths.push_back(Path());
                  Path& P = curPaths.back();
                  visCats.insert(newCat);
                  taken++;
                  int mx = nx, my = ny;
                  string& curPath = P.str;
                  while (mx != cur.first || my != cur.second) {
                     int mov = FrO[bField][mx][my];
                     mov -= BASELINE + (taken - 2) * 4 + 1;
                     curPath += MOVES_CHAR[mov];
                     mx -= MOVES[mov][0];
                     my -= MOVES[mov][1];
                  }
                  reverse(curPath.begin(), curPath.end());
                  curPts -= (int) curPath.size();
                  P.fromCat = cur;
                  P.toCat = newCat;
                  cur = newCat;
                  q = queue<Cat>();
                  q.push(newCat);
                  break;
               }
            }
         }
         if (curPts > bestResult) {
            bestResult = curPts;
            bestPaths = curPaths;
         }
      }
      printf("%d\n%d %d\n", bField + 1,
            bestPaths[0].fromCat.first + 1,
            bestPaths[0].fromCat.second + 1);
      bool shouldPrintStay = true;
      for (int i = 0; i < (int) bestPaths.size(); ++i) {
         Path& p = bestPaths[i];
         printf("%s", p.str.c_str());
         shouldPrintStay = false;
      }
      if (shouldPrintStay) {
         printf("STAY\n");
      } else {
         printf("\n");
      }
    }

    void printDogs() {
      if (!dogs) return;
      if (dogs == 1 && paths.size()) {
         print1Dog();
         return;
      }
      printf("%d\n%d %d\n", bField + 1,
            cats[0].first + 1,
            cats[0].second + 1);
      PRINTED_DOGS++;
      bool shouldPrintStay = true;
      for (int i = 0; i < (int) paths.size(); ++i) {
         Path& p = paths[i];
         if (p.str == "*") {
            if (shouldPrintStay) {
               printf("STAY\n%d\n%d %d\n",
                     bField + 1,
                     p.toCat.first + 1,
                     p.toCat.second + 1);
               PRINTED_DOGS++;
            } else {
               printf("\n%d\n%d %d\n",
                     bField + 1,
                     p.toCat.first + 1,
                     p.toCat.second + 1);
               PRINTED_DOGS++;
            }
            shouldPrintStay = true;
            continue;
         }
         printf("%s", p.str.c_str());
         shouldPrintStay = false;
      }
      if (shouldPrintStay) {
         printf("STAY\n");
      } else {
         printf("\n");
      }
    }
};

struct BField {
    int num, bonus;
    vector<Field> fields;
    // Index is number of dogs, Value is value that this BField gives based on number of dogs.
    vector<int> numDogsValue;
    // Index is dog number, Pair.first is field number, Pair.second is field path idx
    // (path.toCat for every except the first, the first is first cat of that field)!
    // -1 on pair.second means that the dog is the on first cat.
    vector<pair<int, int> > dogsPositions;
    BField() {
       numDogsValue = vector<int>(1, 0);
    }
};

typedef pair<pair<int, int>, int> triplet;
inline triplet newTriplet(int x, int y, int z) {
    return make_pair(make_pair(x, y), z);
}

void distributeDogsRandomly(vector<int>& result) {
   fill(result.begin(), result.end(), 0);
   for (int i = 0; i < K; ++i) {
      result[rand() % F]++;
   }
}

void solveLines() {
    vector<BField> bfields(F);
    int numFields = 0;
	 vector<vector<int> > bfieldDogsPoints(F, vector<int>(1, 0));
    for (int bfield = 0; bfield < F; ++bfield) {
        bfields[bfield].bonus = Bi[bfield];
        bfields[bfield].num = bfield;
        vector<vector<bool> > vis(
            Ni[bfield],
            vector<bool>(Mi[bfield], false));
        for (int x = 0; x < Ni[bfield]; ++x) {
            for (int y = 0; y < Mi[bfield]; ++y) {
                if (vis[x][y] || !isCat(bfield,x,y)) continue;
                vis[x][y] = 1;
                bfields[bfield].fields.push_back(Field());
                Field& f = bfields[bfield].fields.back();
					 f.points += Fr[bfield][x][y] - '0';
                f.bField = bfield;
                numFields++;
                Cat cur = make_pair(x, y);
                f.cats.push_back(cur);
                queue<pair<int, int> > q;
                q.push(cur);
                while(q.size()) {
                    // BFS
                    int nx = q.front().first;
                    int ny = q.front().second;
                    q.pop();
                    for (int mv = 0; mv < 4; ++mv) {
                        int nnx = nx + MOVES[mv][0];
                        int nny = ny + MOVES[mv][1];
                        if (nnx < 0 || nnx >= Ni[bfield]
                            || nny < 0 || nny >= Mi[bfield]
                            || vis[nnx][nny]
                            || Fr[bfield][nnx][nny] == '#')
                            continue;
                        Cat cc = make_pair(nnx, nny);
                        q.push(cc);
                        vis[nnx][nny] = 1;
                        if (isCat(bfield, nnx, nny)) {
									f.points += Fr[bfield][nnx][nny] - '0';
                           f.cats.push_back(cc);
                        }
                    }
                }
            }
        }
    }

    ;
    vector<pair<int, triplet> > pathsForSort;

    for (int bfield = 0; bfield < F; ++bfield) {
        vector<vector<int> > paths(
                Ni[bfield], vector<int>(Mi[bfield], 0));
        for (int fieldIdx = 0;
             fieldIdx < (int) bfields[bfield].fields.size();
             ++fieldIdx) {
            Field& field = bfields[bfield].fields[fieldIdx];
				field.pointsPlusPathPrice = field.points;
            Cat cur = field.cats[0];
            int taken = 1;
            set<Cat> visCats;
            visCats.insert(cur);
            queue<Cat> q;
            q.push(cur);
            while (taken < (int) field.cats.size()) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                for (int mv = 0; mv < 4; ++mv) {
                    int nx = x + MOVES[mv][0];
                    int ny = y + MOVES[mv][1];
                    if (nx < 0 || nx >= Ni[bfield]
                        || ny < 0 || ny >= Mi[bfield]
                        || Fr[bfield][nx][ny] == '#') continue;
                    int valueInPaths = paths[nx][ny];
                    if (valueInPaths > ((taken - 1) * 4)) continue;
                    paths[nx][ny] = ((taken - 1) * 4) + 1 + mv;
                    Cat newCat = make_pair(nx, ny);
                    q.push(newCat);
                    if (isCat(bfield, nx, ny)
									&& !visCats.count(newCat)) {
                        field.paths.push_back(Path());
                        Path& P = field.paths.back();
                        visCats.insert(newCat);
                        taken++;
                        int mx = nx, my = ny;
                        string& curPath = P.str;
                        while (mx != cur.first || my != cur.second) {
                            int mov = paths[mx][my];
                            mov -= (taken - 2) * 4 + 1;
                            curPath += MOVES_CHAR[mov];
                            mx -= MOVES[mov][0];
                            my -= MOVES[mov][1];
                        }
                        reverse(curPath.begin(), curPath.end());
								field.pointsPlusPathPrice -= (int) curPath.size();
                        pathsForSort.push_back(
                            make_pair(curPath.size(),
                            newTriplet(bfield, fieldIdx,
                                       -1 + (int) field.paths.size())));

                        P.fromCat = cur;
                        P.toCat = newCat;
                        cur = newCat;
                        q = queue<Cat>();
                        q.push(newCat);
                        break;
                    }
                }
            }
        }
    }
    // distribution by dogs on fields
    // vector is dogs for bfield, first is fieldIdx, second is pathIdx
    vector<vector<pair<int, int> > > bfieldDogsDistributions(F);

	// Fill bfieldDogsPoints map.
	// first sort all fields by points with path prices by bfields
	// for all bfields make if #dogs == #fields then sum plus bonus.
	// if #dogs > #fields then start removing prices from longest paths from fields.
	// if #dogs < #fields then start removing fields with lowest rewards
   priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
   int requiredDogs = 0;
   for (int bfield = 0; bfield < F; ++bfield) {
      vector<int>& curDogsPoints = bfieldDogsPoints[bfield];
      vector<pair<int, int> >& curDogsDistributions = bfieldDogsDistributions[bfield];
      BField &bf = bfields[bfield];
      vector<pair<int, int> > fieldPts;
      // first is path len, second.first is field idx, second.second is field path
      vector<pair<int, pair<int, int> > > bfPathsForSort;
      for (int fldIdx = 0; fldIdx < (int) bf.fields.size(); ++fldIdx) {
         Field& fld = bf.fields[fldIdx];
         fieldPts.push_back(make_pair(fld.pointsPlusPathPrice, fldIdx));
         for (int pIdx = 0; pIdx < (int) fld.paths.size(); ++pIdx) {
            bfPathsForSort.push_back(make_pair(
                  fld.paths[pIdx].str.size(),
                  make_pair(fldIdx, pIdx)));
         }
      }
      sort(bfPathsForSort.begin(), bfPathsForSort.end());

      sort(fieldPts.begin(), fieldPts.end());
      for (int dogs = 1; dogs <= K; ++dogs) {
         int prevScore = curDogsPoints.back();
         if (dogs < (int) fieldPts.size()) {
            curDogsDistributions.push_back(make_pair(fieldPts[(int) fieldPts.size() - dogs].second, -1));
            curDogsPoints.push_back(prevScore + fieldPts[(int) fieldPts.size() - dogs].first);
            bf.numDogsValue.push_back(curDogsPoints.back());
            bf.dogsPositions.push_back(curDogsDistributions.back());
         } else if (dogs == fieldPts.size()) {
            curDogsDistributions.push_back(make_pair(fieldPts[0].second, -1));
            curDogsPoints.push_back(prevScore + fieldPts[0].first + bf.bonus);
            bf.numDogsValue.push_back(curDogsPoints.back());
            bf.dogsPositions.push_back(curDogsDistributions.back());
         } else {
            int extra = dogs - (int) fieldPts.size();
            if (extra > (int) bfPathsForSort.size()) {
               break;
            } else {
               curDogsDistributions.push_back(make_pair(
                  bfPathsForSort[(int) bfPathsForSort.size() - extra].second.first,
                  bfPathsForSort[(int) bfPathsForSort.size() - extra].second.second));
               curDogsPoints.push_back(prevScore + bfPathsForSort[(int) bfPathsForSort.size() - extra].first);
               bf.numDogsValue.push_back(curDogsPoints.back());
               bf.dogsPositions.push_back(curDogsDistributions.back());
            }
         }
      }
      requiredDogs += (int) curDogsPoints.size() - 1;
      if (curDogsPoints.size() > 1) {
         pq.push(make_pair(
            curDogsPoints[(int) curDogsPoints.size() - 1] - curDogsPoints[(int) curDogsPoints.size() - 2],
            bfield));
      }
   }

   vector<int> bestDistribution(F);
   int bestResult = 0;
   // HERE WE NEED TO SIMULATE RANDOM DISTRIBUTIONS AND CHECK bf.numDogsValue and bf.dogsPositions...
   int optimizationIterations = 10;
   while (/*optimizationIterations-- > 0 && */clock() - BEGIN_TIME < TIME_LIMIT) {
      vector<int> randomDogDistribution(F);
      distributeDogsRandomly(randomDogDistribution);
      bool change = true;
      while (change) {
         change = false;
         int best = 0;
         int bestIdx = -1;
         for (int bfieldIdx = 0; bfieldIdx < F; ++bfieldIdx) {
            BField& bfield = bfields[bfieldIdx];
            int dogsAtBfield = randomDogDistribution[bfieldIdx];
            if (dogsAtBfield < (int) bfield.numDogsValue.size() - 1
                  && bfield.numDogsValue[dogsAtBfield + 1] - bfield.numDogsValue[dogsAtBfield] > best) {
               best = bfield.numDogsValue[dogsAtBfield + 1] - bfield.numDogsValue[dogsAtBfield];
               bestIdx = bfieldIdx;
            }
         }
         if (bestIdx == -1) break;
         int worst = 2000000000;
         int worstIdx = -1;
         for (int bfieldIdx = 0; bfieldIdx < F; ++bfieldIdx) {
            if (bfieldIdx == bestIdx) continue;
            BField& bfield = bfields[bfieldIdx];
            int dogsAtBfield = randomDogDistribution[bfieldIdx];
            if (dogsAtBfield >= (int) bfield.numDogsValue.size()) {
               worst = 0;
               worstIdx = bfieldIdx;
               continue;
            }
            if (dogsAtBfield && bfield.numDogsValue[dogsAtBfield] - bfield.numDogsValue[dogsAtBfield - 1] < worst) {
               worst = bfield.numDogsValue[dogsAtBfield] - bfield.numDogsValue[dogsAtBfield - 1];
               worstIdx = bfieldIdx;
            }
         }
         if (best > 0 && worstIdx > -1 && best > worst) {
            change = true;
            randomDogDistribution[bestIdx]++;
            randomDogDistribution[worstIdx]--;
         }
      }
      // TEST randomDogDistribution SOLUTION!!!
      int curDistributionResult = 0;
      for (int bfIdx = 0; bfIdx < F; ++bfIdx) {
         BField& bfield = bfields[bfIdx];
         if (randomDogDistribution[bfIdx] >= (int) bfield.numDogsValue.size()) {
            curDistributionResult += bfield.numDogsValue.back();
         } else {
            curDistributionResult += bfield.numDogsValue[randomDogDistribution[bfIdx]];
         }
      }
      if (curDistributionResult > bestResult) {
         bestDistribution = randomDogDistribution;
         bestResult = curDistributionResult;
      }
   }
   // NOW WE ONLY NEED TO PRINT BEST DOG DISTRIBUTION.
   for (int bfIdx = 0; bfIdx < F; ++bfIdx) {
      BField& bfield = bfields[bfIdx];
      for (int i = 0; i < bestDistribution[bfIdx]; ++i) {
         if (i >= (int) bfield.dogsPositions.size()) {
            printf("0\n");
            continue;
         }
         int fieldIdx = bfield.dogsPositions[i].first;
         bfield.fields[fieldIdx].dogs++;
         int pathIdx = bfield.dogsPositions[i].second;
         if (pathIdx > -1) {
            bfield.fields[fieldIdx].paths[pathIdx].str = "*";
         }
      }
   }
   for (int bfield = 0; bfield < F; ++bfield) {
      BField& bf = bfields[bfield];
      for (int field = 0; field < (int) bf.fields.size(); ++field) {
         bf.fields[field].printDogs();
      }
   }
/* OLD GREEDY ALGO
   while (requiredDogs > K) {
      int forRemove = pq.top().second; pq.pop();
      vector<int>& curDogsPoints = bfieldDogsPoints[forRemove];
      if (curDogsPoints.size()) {
         curDogsPoints.pop_back();
			bfieldDogsDistributions[forRemove].pop_back();
      }
      if (curDogsPoints.size() > 1) {
         int diff = curDogsPoints[(int) curDogsPoints.size() - 1] - curDogsPoints[(int) curDogsPoints.size() - 2];
         pq.push(make_pair(diff, forRemove));
      }
      requiredDogs--;
   }
   for (int bfield = 0; bfield < F; ++bfield) {
      vector<pair<int, int> > &curDogsDistributions = bfieldDogsDistributions[bfield];
		vector<bool> vis(bfields[bfield].fields.size(), false);
      for (int dg = 0; dg < (int) curDogsDistributions.size(); ++dg) {
         bfields[bfield].fields[curDogsDistributions[dg].first].dogs++;
			if (!vis[curDogsDistributions[dg].first]) {
				vis[curDogsDistributions[dg].first] = true;
				continue;
			}
			bfields[bfield].fields[
				curDogsDistributions[dg].first].paths[
					curDogsDistributions[dg].second].str = "*";
      }
   }



   // PRINT UNASSIGNED DOGS
   for (int i = PRINTED_DOGS; i < K; ++i) {
      printf("0\n");
   }
*/
}

int main() {
   BEGIN_TIME = clock();
	srand(15485863);
	freopen("catsdogs.in", "r", stdin);
	freopen("catsdogs.out", "w", stdout);
	scanf("%d %d", &F, &K);
	for (int i = 0; i < F; ++i) {
		scanf("%d %d %d\n", &Ni[i], &Mi[i], &Bi[i]);
		for (int j = 0; j < Ni[i]; ++j) {
			fgets(Fr[i][j], 10024, stdin);
		}
	}
   memset(FrO, 0, sizeof(FrO));
   solveLines();

	return 0;