#define BUFSIZE 1000000
int Tests, cnum;
// #define USEWIN
#define MANYTESTS 0
// #define LINEBYLINE

#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

void ansicol16(int col, FILE *f = stdout) {
  int coltab[16] = {
    30, 34, 32, 36, 31, 35, 33, 37,
    30, 34, 32, 36, 31, 35, 33, 37
    };
  fprintf(f, "\033[%d;%dm", col >= 8 ? 1 : 2, coltab[col]);
  }  

void ansiclear(FILE *f = stdout) {
  fprintf(f, "\033[0m");
  }  

typedef long long ll;

#define LS <
#define Size(x) (int(x.size()))
#define LET(k,val) __typeof(val) k = (val)
// execute "act", and return "val" as an expression result
#define CLC(act,val) ([&] () {act; return (val); } ())

// All macros with parameters "k,a,b" run the "k" variable in range [a,b)
#define FOR(k,a,b) for(__typeof(a) k=(a); k LS (b); ++k)

// find the first k in [a,b) that satisfies cond, or b if none
#define FIRST(k,a,b,cond) CLC(LET(k, a); for(; k LS (b); ++k) if(cond) break, k)

#define INF  500000000

// Bit Count
int bitc(ll r) {return r == 0 ? 0 : (bitc(r>>1) + (r&1));}

// int to string
string its(int i) {char buf[200]; sprintf(buf, "%d", i); return buf;}

string getLine() {
  string s;
  while(!feof(stdin)) {
    char c = fgetc(stdin);
    if(c == 13) continue;
    if(c == 10) return s;
    s += c;
    }
  return s;
  }

int scanerr;

int getNum() {
#ifdef LINEBYLINE
  string s = getLine();
  return atoi(s.c_str());
#else
  int i;
  scanerr = scanf("%d", &i);
  return i;
#endif
  }

#ifndef BUFSIZE
#define BUFSIZE 1000000
#endif

char buf[BUFSIZE];

#include <sys/time.h>
ll getVa() {
  struct timeval tval;
  gettimeofday(&tval, NULL);
  return tval.tv_sec * 1000000 + tval.tv_usec;
  }

#line 9 "work.cpp"
#include <queue>

// ---- TEMPLATE ENDS HERE ----

//Eryx

// input limits
//--------------
#define MAXSON 32
#define MAXBOARD 64
#define MAXBOARD2 (MAXBOARD*MAXBOARD)
int X, Y, K; // actual parameters

// cell encoding
//---------------

// we encode a pair of coordinates with a single number; coordinates are 1-based 
// (zeros are used as guards)

#define XY(x,y) ((y)*MAXBOARD+x)
#define GETX(xy) (xy&(MAXBOARD-1))
#define GETY(xy) ((int)(((unsigned)xy)/MAXBOARD))
#define GETXY(xy) GETX(xy), GETY(xy)

// cardinal directions are represented as:

const int dxy[16] = {
  1,MAXBOARD,-1,-MAXBOARD,
  1,MAXBOARD,-1,-MAXBOARD,
  1,MAXBOARD,-1,-MAXBOARD,
  1,MAXBOARD,-1,-MAXBOARD,
  };

// eight directions are represented as:

const int dxy8[8] = {
  MAXBOARD-1, MAXBOARD, MAXBOARD+1, 1, 1-MAXBOARD, -MAXBOARD, -1-MAXBOARD, -1
  };

int pxy[2][MAXSON];       // positions of fountains (0,1 -- indices)
char kmap[MAXBOARD2];     // current map
char cetype[MAXBOARD2];   // cell type: 0,1 -- fountain, 2 - empty
int cid[MAXBOARD2];       // fountain id

int tryindex = 0;         // how many tries so far
int curtime;              // time elapsed so far
double bestscore;         // best score so far
char bestmap[MAXBOARD2];  // best map found so far

// other basics
//--------------

// exception (I simulate exceptions with bool excthrown because I got weird
// errors when I have been using exceptions -- these turned out to not be 
// actually related to exceptions, but the simulation remains)
bool excthrown; 

// a function to display the current state nicely
void debugshot();

// score and connectivity handling
//---------------------------------

int area[MAXSON];   // area for each son
int perim[MAXSON];  // perimeter for each son
double cursc;       // current score for local search

void calcap();              // compute area and perim
double compscore();         // compute the current score
void swtch(int xy, char c); // switch the location xy to group c, ancknowledge in area/perim
double getscore() { calcap(); return compscore(); }

void calcap() {
  for(int k=0; k<K; k++) area[k] = perim[k] = 0;
  FOR(y,1,Y+1) FOR(x,1,X+1) {
    int xy = XY(x,y);
    char c = kmap[xy];
    int id = c - 'a';
    if(id < 0 || id >= K) continue;
    area[id]++;
    FOR(d,0,4) if(kmap[xy+dxy[d]] != c) perim[id]++;
    }
  }

void ack(char we, char them, int delta) {
  if(we == them) return;
  int id = we - 'a';
  if(id < 0 || id >= K) return;
  perim[id] += delta;
  }

void ack4(int xy, int delta) {
  area[kmap[xy]-'a'] += delta; 
  FOR(d,0,4) {
    int xy0 = xy + dxy[d];
    ack(kmap[xy], kmap[xy0], delta);
    ack(kmap[xy0], kmap[xy], delta);
    }
  }

void swtch(int xy, char c) {
  ack4(xy, -1);
  kmap[xy] = c;
  ack4(xy, +1);
  }

double compscore() {
  double res = 0;
  FOR(k,0,K) res += area[k] / pow(perim[k], 2);
  res /= K; res *= 160000;
  return res;
  }
  
// verify connectivity
//---------------------

void floodfill(int xy, char c) {
  if(kmap[xy] != '.') return;
  kmap[xy] = c;
  FOR(d,0,4) floodfill(xy + dxy[d], c);
  }

void vercon(int xy, int v) {
  if(kmap[xy] != v) return;
  kmap[xy] = -kmap[xy];
  FOR(d,0,4) vercon(xy + dxy[d], v);
  }

char allgroups[32];

bool vercon() {
  int groups = 0;
  FOR(y,1,Y+1) FOR(x,1,X+1) {
    int xy = XY(x,y);
    if(kmap[xy] > 0) allgroups[groups++] = kmap[xy], vercon(xy, kmap[xy]);
    }
  FOR(y,1,Y+1) FOR(x,1,X+1) {
    int xy = XY(x,y);
    if(kmap[xy] < 0) kmap[xy] = -kmap[xy];
    }
  return groups == K;
  }

// FIRST PHASE: connect pairs
// --------------------------

// Rough idea: we use the hungarian method to connect pairs of fountains,
// then we use Dijkstra algorithm to connect pairs returned by hungarian method
// with paths, starting from the closest one. If it is impossible to connect
// a pair, one (or more) of the older paths is removed, squares on this path
// are given an extra penalty cost, and possibly
// assignments are switched.

// implementation of the hungarian algorithm (pre-written)

#define MAXIT MAXSON
#define MAXBID MAXSON

namespace hungarian {

#define PHI -1
#define NOL -2

int items, bidders;

int w[MAXIT][MAXBID];
bool x[MAXIT][MAXBID];

int asg[MAXIT];

void hungarian() {

  bool ss[MAXIT];
  bool st[MAXBID];
  
  int u[MAXIT];
  int v[MAXBID];
  int p[MAXBID];
  int ls[MAXIT];
  int lt[MAXBID];
  
  int f = 0;
  
  FOR(i,0,items) FOR(j,0,bidders) f = max(f, w[i][j]);
  
  FOR(i,0,items) FOR(j,0,bidders) x[i][j] = false;
  
  FOR(i,0,items) u[i] = f, ls[i] = PHI, ss[i] = false;

  FOR(j,0,bidders) v[j] = 0, p[j] = INF, lt[j] = NOL, st[j] = false;

  while(true) {
  
    f = -1;
    
    FOR(i, 0, items) if(ls[i] != NOL && !ss[i]) {
      f = i;
      break;
      }
    
    if(f != -1) {
      ss[f] = true;
      FOR(j, 0, bidders)
        if(!x[f][j] && u[f] + v[j] - w[f][j] < p[j])
          {
            lt[j] = f;
            p[j] = u[f] + v[j] - w[f][j];
          }
      }
    else {
    
      FOR(j, 0, bidders)
        if(lt[j] != NOL && !st[j] && p[j] == 0) {
          f = j;
          break;
          }
        
      if(f == -1) {
        int d1 = INF, d2 = INF, d;
        FOR(i, 0, items) d1 = min(d1, u[i]);
      
        FOR(j, 0, bidders) if(p[j] > 0) d2 = min(d2, p[j]);
        
        d = min(d1, d2);
        
        FOR(i, 0, items) if(ls[i] != NOL) u[i] -= d;
        
        FOR(j, 0, bidders) {
          if(p[j] == 0) v[j] += d;
          if(p[j] > 0 && lt[j] != NOL) p[j] -= d;
          }
 
        if(d2 >= d1) break;
        }
      else {
        st[f] = true;
        int s = -1;
        
        for(int i = 0; i < items && s == -1; i++)
          if(x[i][f])
            s = i;
 
        if(s == -1) {
          int r = f;

          while(true) {
            int l = lt[r];
            if(l < 0) break;
            x[l][r] = !x[l][r];
            
            r = ls[l];
            if(r < 0) break;
            x[l][r] = !x[l][r];
            }
            
          FOR(i,0,items) ls[i] = PHI, ss[i] = false;

          FOR(j,0,bidders) p[j] = INF, lt[j] = NOL, st[j] = false;
        
          FOR(i,0,items) {
            FOR(j,0,bidders) if(x[i][j]) { 
              ls[i] = NOL;
              break;
              }
            }
          }
        else {
          ls[s] = f;
          }
        }
      }
    }
 
  FOR(i,0,items) {
    asg[i] = -1;
    FOR(j,0,bidders) if(x[i][j]) asg[i] = j;
    }
  }

}

typedef vector<int> path;
path paths[MAXSON];       // the path used by each son
bool gotit[MAXSON];       // have we already connected the pair
int val[MAXSON];          // the value of each pair -- pairs with higher value are placed first
int ngotit;               // number of connected pairs (sum of gotit)
vector<int> pathsremoved; // paths we have recently removed 
int failedon[MAXSON];     // here we count the number of tries we failed to connect each pair

// use the hungarian method to find pairs, also set val's

void useHungarian() {  
  FOR(k0,0,K) FOR(k1,0,K)
    hungarian::w[k0][k1] = int(10000 - 100 * hypot(GETY(pxy[0][k0])-GETY(pxy[1][k1]), GETX(pxy[0][k0])-GETX(pxy[1][k1])));
  hungarian::hungarian();
  
  if(curtime > (bestscore > 0 ? 1500000 : 1700000)) {
    int reroutes = rand() % 10;
    for(int i=0; i<reroutes; i++)
      swap(hungarian::asg[rand() % K], hungarian::asg[rand() % K]);
    }
  
  int distsign = rand() % 3 - 1;
  int failval[5] = {0, 10, 100, 1000, 100000};
  int failv = failval[rand() % 5];

  FOR(k,0,K) {
    gotit[k] = false;
    val[k] = hungarian::w[k][hungarian::asg[k]] * distsign;
    val[k] += failv * failedon[k];
    }
  val[31] = -1000000000;
  ngotit = 0;
  }


// the cost of going through each square
// STEPCOST by default; cells already assigned gain CROSSCOST extra cost
// if a path has been placed and removed, its squares get a bonus cost
// of PENALTY/size each

int costmap[MAXBOARD2];
#define STEPCOST 10000
#define CROSSCOST (STEPCOST*1000)
#define PENALTY 15000
int bfsmap[MAXBOARD2]; // map for Dijkstra

void pathfind(int sxy, int txy, path& p) {
  p.clear();
  
  FOR(xy,0,MAXBOARD2) bfsmap[xy] = INF;

  priority_queue<pair<int, int>> pq;
  pq.emplace(0, sxy);
  
  while(!pq.empty()) {
    auto ent = pq.top();
    pq.pop();
    int xy = ent.second;
#if 0
    if(x<=0 || y<=0 || x > X || y > Y) {

#ifdef LOCAL
      printf("got out!\n");

      FOR(y,0,Y+2) {
        FOR(x,0,X+2) printf("%6d", min(bfsmap[y][x], 999999));
        printf("\n");
        }
      printf("\n");
    
      FOR(y,0,Y+2) {
        FOR(x,0,X+2) printf("%6d", min(costmap[y][x], 999999));
        printf("\n");
        }
      printf("\n");
#endif

      excthrown = true; return;
      }
#endif
    int val = -ent.first;
    if(bfsmap[xy] < val) continue;
    bfsmap[xy] = val;
    if(xy==txy) goto reached;
    for(int d=0; d<4; d++) {
      int xy1 = xy+dxy[d];
      int nval = val + costmap[xy1];
      if(bfsmap[xy1] > nval) {
        bfsmap[xy1] = nval;
        pq.emplace(-nval, xy1);
        }
      }
    }
  
#ifdef LOCAL
  printf("could not reach %d -> %d\n", sxy, txy);

  FOR(y,0,Y+2) {
    FOR(x,0,X+2) printf("%6d", min(bfsmap[y*MAXBOARD+x], 999999));
    printf("\n");
    }
  printf("\n");

  FOR(y,0,Y+2) {
    FOR(x,0,X+2) printf("%6d", min(costmap[y*MAXBOARD+x], 999999));
    printf("\n");
    }
  printf("\n");
#endif

  excthrown = true; return;
  
  reached:

  int xeach = abs(GETX(sxy)-GETX(txy));
  int tsteps = xeach + abs(GETY(sxy)-GETY(txy));
  int v = rand() % tsteps;
  
  while(true) {
    p.emplace_back(txy);
    if(bfsmap[txy] == 0) break;
    
    bool wd = false;
    v += xeach; if(v >= tsteps) v -= tsteps; else wd = true;
    
    for(int d0=0; d0<4; d0++) {
      int d = d0;
      if(wd) d ^= 1;
      int xy1 = txy+dxy[d];
      if(bfsmap[xy1] == bfsmap[txy] - costmap[txy]) {
        txy = xy1;
        goto nextstep;
        }
      }
    
#ifdef LOCAL    
    
    printf("failed while connecting (%d,%d cost=%d bfs=%d) \n", GETXY(txy), costmap[txy], bfsmap[txy]);

    for(int d0=0; d0<4; d0++) {
      int d = d0;
      int xy1 = txy+dxy[d];
      printf("-> %d\n", bfsmap[xy1]);
      }

    FOR(y,0,Y+2) {
      FOR(x,0,X+2) {
        int xy = XY(x,y);
        if(xy==txy) ansicol16(12);
        if(xy==sxy) ansicol16(10);
        printf("%6d", min(bfsmap[xy]/100, 999999));
        ansiclear();
        }
      printf("\n");
      }
    
    exit(1);
#endif

    // debugshot(); 
    excthrown = true;
    return;
    // throw failed0;
    nextstep: ;
    }
  }

void removepath(int id) {
  // printf("removing path %d of size %d\n", id, Size(paths[id]));
  pathsremoved.push_back(id);
  char c = id + 'a';
  path& p = paths[id];
  gotit[id]=0; ngotit--;
  int penalty = PENALTY / Size(p);
  for(auto& xy: p) {
    kmap[xy] = '.';
    costmap[xy] -= CROSSCOST;
    costmap[xy] += penalty;
    }
  if(0) FOR(y,0,Y+2) {
    FOR(x,0,X+2) 
      printf("%6d", min(costmap[XY(x,y)], 999999));
    printf("\n");
    }    
  }

void placepath(int id) {
  char c = id + 'a';
  path& p = paths[id];
  gotit[id]=true; ngotit++;
  for(auto& xy: p) {
    if(kmap[xy] != '.') removepath(kmap[xy] - 'a');
    kmap[xy] = c;
    costmap[xy] += CROSSCOST;
    }
  }

// SECOND PHASE: fill the remaining squares
//------------------------------------------

// angle fill: if two adjacent square are owned by the same son,
// we are also owned by this son

void anglefill(int xy) {
  if(kmap[xy] != '.') return;
  
  for(int d=0; d<4; d++) {
    int d0 = d+1;
    char c = kmap[xy+dxy[d]];
    if(c && c != '.' && c == kmap[xy+dxy[d0]]) {
      kmap[xy] = c; area[c-'a']++;
      for(int d2=2; d2<4; d2++) anglefill(xy+dxy[d+d2]);
      return;
      }
    }
  }

// mid fill: 

// ..          x.           xx
// xx  becomes xx (and then xx when anglefill is called)

void midfill(int xy) {
  if(kmap[xy] != '.') return;
  
  for(int d=0; d<4; d++) {
    int d0 = d+1;
    char c = kmap[xy+dxy[d]];
    if(c && c != '.' && c == kmap[xy+dxy[d]+dxy[d0]] && 
      kmap[xy+dxy[d0]] == '.') {
      kmap[xy] = c; area[c-'a']++;
      for(int d2=0; d2<4; d2++) anglefill(xy+dxy[d2]);
      for(int d2=0; d2<4; d2++) midfill(xy+dxy[d2]);
      return;
      }
    }
  }

// stupid fill: fill the remaining squares
// the color with the largest area is chosen by default, since
// this color is probably the one where the cost of losing compactness
// is the smallest

void stupidfill(int xy) {
  if(kmap[xy] != '.') return;
  
  char choi[8];
  int nchoi = 0, areav = 0;
  /* int ds[4] = {0,1,2,3};
  random_shuffle(ds, ds+4); */
  
  for(int d=0; d<4; d++) {
    char c = kmap[xy+dxy[d]];
    if(c && c != '.') {
      int q = area[c-'a'];
      if(q > areav) areav = q, nchoi = 0;
      if(q == areav) choi[nchoi++] = c;
      }
    }
  if(!nchoi) return;
  char c = nchoi == 1 ? choi[0] : choi[rand() % nchoi];  
  kmap[xy] = c; area[c-'a']++;
  for(int d1=0; d1<4; d1++) anglefill(xy+dxy[d1]);
  for(int d1=0; d1<4; d1++) midfill(xy+dxy[d1]);
  }

// THIRD PHASE: reassign squares between pairs to improve the overall value

// first method: just try to switch to another adjacent color,
// while making sure that the neighbors of our color remains (locally) connected;
// keep if the score improves. Assumes cursc = getscore()

bool tryswitch(int xy) {
  if(cetype[xy] != 2) return false;
  char c = kmap[xy];
  bool which[9];
  for(int d=0; d<8; d++) {
    int xy0 = xy+dxy8[d];
    which[d] = kmap[xy0] == c;
    }
  which[8] = which[0];
  int segs = 0;
  for(int d=0; d<8; d++) if(which[d] && !which[d+1]) segs++;
  if(segs != 1) return false;
  
  int dirs[4];
  for(int u=0; u<4; u++) dirs[u] = u;
  random_shuffle(dirs, dirs+4);
  for(int u=0; u<4; u++) {
    int d = dirs[u];
    char c1 = kmap[xy+dxy[d]];
    if(!c1) continue;
    if(c1 == c) continue;
    swtch(xy, c1);
    double newsc = compscore();
    if(newsc >= cursc) {
      bool better = newsc > cursc;
      cursc = newsc;
      return better;
      }
    else {
      swtch(xy, c);
      } 
    }
  return false;
  }

// Second method: find an edge between two colors, and switch one of them
// push it down. Rough idea:

// xaaaaaaaaaaaabbbbbx    xaaaaaaaaaaaabbbbbx
// xcccccccccccccccccx => xaaaaaaaaaaaabbbbbx
// xcccccccccccccccccx => xcccccccccccccccccx

// Has two modes. tsApprox checks that the remaining c's are locally connected,
// while tsFull uses vercon to fully verify connectivity.

enum tsmode { tsApprox, tsFull };

bool tryswitch2(int xy, tsmode t) {
  if(cetype[xy] != 2) return false;
  int dirs[4];
  for(int u=0; u<4; u++) dirs[u] = u;
  random_shuffle(dirs, dirs+4);
  char c = kmap[xy];
  for(int u=0; u<4; u++) {
    int d = dirs[u];
    int bxy = dxy[d];
    if(kmap[xy+bxy] == c) continue;
    if(t == tsApprox && kmap[xy-bxy] != c) continue;
    if(kmap[xy+bxy] == 0) continue;
    int dnext = (d+1);
    int sxy = dxy[dnext];
    if(t == tsApprox && kmap[xy-sxy] == c && kmap[xy-sxy-bxy] != c) continue;
    if(kmap[xy-sxy] == c && kmap[xy-sxy+bxy] != c) continue;
    int nxy = xy+sxy;
    while(true) {
      if(kmap[nxy] != c) break;
      if(cetype[nxy] != 2) break;
      if(kmap[nxy+bxy] == c) break;
      if(t == tsApprox && kmap[nxy-bxy] != c) break;
      nxy += sxy;
      }
    if(nxy == xy+sxy) continue;
    if(t == tsApprox && kmap[nxy] == c && kmap[nxy-bxy] != c) continue;
    for(int oxy = xy; oxy != nxy; oxy += sxy)
      swtch(oxy, kmap[oxy+bxy]);
    double newsc = compscore();
    if(newsc >= cursc && (t == tsApprox || (newsc > cursc && vercon()))) {
      /* if(!vercon()) {
        printf("connectivity lost:\n  [%s]\n", allgroups);
        debugshot();
        for(int oxy = xy; oxy != nxy; oxy += sxy)
          swtch(oxy, c);
        for(int oxy = xy; oxy != nxy; oxy += sxy) cetype[oxy] = 3;
        cetype[xy] = 4;
        debugshot();
        exit(1);
        } */
      // printf("switched2: %d: %lf -> %lf\n", (nxy-xy) / sxy, cursc, newsc);
      // debugshot();
      bool better = newsc > cursc;
      cursc = newsc;
      return better;
      }
    for(int oxy = xy; oxy != nxy; oxy += sxy)
      swtch(oxy, c);    
    }
  return false;
  }

// call one of the methods (tryswitch, tryswitch2 tsApprox, and tryswitch2 tsFull)
// for all squares in a random order

vector<int> freespots;  

bool tryswitchall(int id) {
  bool stop = false;
  random_shuffle(freespots.begin(), freespots.end());
  for(auto p: freespots) switch(id) {
    case 1:
      if(tryswitch(p)) stop = true;
      break;
    case 2:
      if(tryswitch2(p, tsApprox)) stop = true;
      break;
    case 3:
      if(tryswitch2(p, tsFull)) stop = true;
      break;
/*    case 4:
      if(tryswitch3(p)) stop = true;
      break; */
    }
  return stop;
  }

// ALTERNATIVE APPROACHES
//------------------------

// bad fill: an alternative to midfill/stupidfill
// find the color of the worst current quality, and fill all the squares
// adjacent to this color with it (might be called several times)
// idea: it is better to worsen just the worst color than many colors

pair<double, int> quality[20];

void calcquality() {
  FOR(k,0,K) quality[k].first = area[k] / pow(perim[k], 2.), quality[k].second = k;
  sort(quality, quality+K);
  }

bool badfill() {
  calcap(); calcquality();
  int pos[20];
  
  int dots = 0;
  FOR(k,0,K) pos[k] = 0;
  FOR(y,1,Y+1) FOR(x,1,X+1) {
    int xy = XY(x, y);
    if(kmap[xy] == '.') {
      dots++;
      FOR(d,0,4) if(kmap[xy+dxy[d]] && kmap[xy+dxy[d]] != '.') pos[kmap[xy+dxy[d]]-'a'] = xy;
      }
    }
  if(!dots) return false;
  
  FOR(ki,0,K) {
    int k = quality[ki].second;
    if(pos[k]) {
//      printf("floodfill %c at %d (%d dots)\n", 'a'+k, pos[k], dots);
//      debugshot();
      floodfill(pos[k], 'a'+k);
//      printf("result:\n");
//      debugshot();
//      exit(1);
      return true;
      }
    }
  }

// alternatively to useHungarian, instead of using the Hungarian method
// we take the currently best solution, take two or three adjacent colors
// (with preference for ones with worse quality) and remove them, and possibly
// switch their assignments

void reuseBest() {
  if(K == 1) { excthrown = true; return; }
  int adj[32];
  FOR(k,0,K) val[k] = 0, gotit[k] = true, area[k] = 0, perim[k] = 0, paths[k].clear(), adj[k] = 0;
  ngotit = K;
  val[31] = -1000000000;
  FOR(xy,0,MAXBOARD2) kmap[xy] = bestmap[xy];
  FOR(xy,0,MAXBOARD2) if(kmap[xy]) {
    char c = kmap[xy];
    int id = c - 'a';
    area[id]++;
    paths[id].push_back(xy);
    costmap[xy] = CROSSCOST + STEPCOST;
    if(cetype[xy] != 2) {
      costmap[xy] += INF;
      if(cetype[xy] == 1)  {
        hungarian::asg[id] = cid[xy];
        }
      /* if(cetype[xy] == 0) {
        printf("%d = %d\n", id, cid[xy]);
        } */
      }
    FOR(d,0,4) {
      char c1 = kmap[xy + dxy[d]];
      if(c1 && c1 != c)
        perim[id]++, adj[id] |= (1<<(c1-'a'));
      }
    }
  calcquality();
  int kpos = rand() % min(K, 5);
  int ka = quality[kpos].second;
  int bc = rand() % bitc(adj[ka]);
  int kb;
  FOR(k,0,K) if((adj[ka] >> k)&1) { if(!bc) kb = k; bc--; }  
  
  // printf("last best:\n"); debugshot();
  removepath(ka);
  removepath(kb);
  if(rand() % 100 < 50) swap(hungarian::asg[ka], hungarian::asg[kb]);
  
  if(rand() % 100 < 50) {
    int adjk = adj[ka] &~ (1<<kb);
    if(!adjk) return;
    int bc = rand() % bitc(adjk);
    int kc;
    FOR(k,0,K) if((adjk >> k)&1) { if(!bc) kc = k; bc--; }  
    removepath(kc);
    swap(hungarian::asg[ka], hungarian::asg[kc]);
    }
  // printf("ka=%c kb=%c\n", 'a'+ka, 'a'+kb);
  // printf("after removal:\n"); debugshot();
  }

// MAIN METHODS
//--------------

// we call this function repetitively, and return the best one
// some randomness is used so that returns of various calls are different

void findSolution() {

  // prepare the variables
  
  FOR(xy,0,MAXBOARD2) costmap[xy] = INF, kmap[xy] = 0;
  
  FOR(y,1,Y+1) FOR(x,1,X+1) {
    int xy = XY(x,y);
    kmap[xy] = '.',
    cetype[xy] = 2,
    costmap[xy] = STEPCOST;
    }
  FOR(u,0,2) FOR(k,0,K) 
    cetype[pxy[u][k]] = u,
    cid[pxy[u][k]] = k,
    costmap[pxy[u][k]] = INF+STEPCOST;
  
  hungarian::items = hungarian::bidders = K;

// phase I
  
  // we normally use Hungarian, but we can use reuseBest() 
  // if half the time has passed and we already have a solution
  
  if(bestscore > 0 && curtime > 1000000 && rand() % 100 < 25) 
    reuseBest();
  else 
    useHungarian();
  if(excthrown) return;
  
  int removals = 0;
  
  // connect paths, or remove old ones if impossible
  
  while(ngotit < K) {
    int best = 31;
    { 
    FOR(k0,0,K) if(!gotit[k0] && val[k0] > val[best]) best = k0; 
    vector<int> whichbest;
    FOR(k0,0,K) if(!gotit[k0] && val[k0] == val[best]) whichbest.push_back(k0);
    best = whichbest[rand() % Size(whichbest)];
    }

    int k0 = best;
    int k1 = hungarian::asg[k0];
    // printf("[%d-%d] %d,%d -> %d,%d <%d>\n", k0, k1, py[0][k0], px[0][k0], py[1][k1], px[1][k1], val[k0]);
    
    char c= 'a' + k0;
    
    int xy0 = pxy[0][k0];
    int xy1 = pxy[1][k1];
    kmap[xy0] = '.'; costmap[xy0] -= INF;
    kmap[xy1] = '.'; costmap[xy1] -= INF;
    pathfind(xy0,xy1,paths[k0]);
    costmap[xy0] += INF;
    costmap[xy1] += INF;
    if(excthrown) return;
    pathsremoved.clear();
    placepath(k0);
    if(Size(pathsremoved)) { 
      removals++;
      if(removals < 32) continue;
      if(curtime < 250000) { excthrown = true; return; }
      if(removals > 320 && bestscore > 0) { excthrown = true; return; }
      if(removals > 1000) { excthrown = true; return; }
      int r = rand() % 6;
      if(r == 0) {
        removepath(k0);
        int ipath = pathsremoved[rand() % Size(pathsremoved)];
        swap(hungarian::asg[k0], hungarian::asg[ipath]);
        }
      if(r == 1) {
        vector<int> stillin;
        for(int c=0; c<K; c++) if(c!=k0 && gotit[c]) stillin.push_back(c);
        if(Size(stillin)) {
          int ipath = stillin[rand() % Size(stillin)];
          removepath(k0);
          removepath(ipath);
          swap(hungarian::asg[k0], hungarian::asg[ipath]);
          }
        }
      if(r == 2) {
        vector<int> stillout;
        for(int c=0; c<K; c++) if(!gotit[c]) stillout.push_back(c);
        if(Size(stillout)) {
          int ipath = stillout[rand() % Size(stillout)];
          removepath(k0);
          swap(hungarian::asg[k0], hungarian::asg[ipath]);
          }
        }
      }    
    }
  
  // debugshot();
  freespots.clear();
  
  FOR(y,1,Y+1) FOR(x,1,X+1) 
    if(cetype[XY(x,y)] == 2)
      freespots.emplace_back(XY(x, y));
  random_shuffle(freespots.begin(), freespots.end());
  
  calcap();

// phase II
  
  for(auto p: freespots) anglefill(p);
  
  nextiter:
  if(rand() % 100 < 20) if(!badfill()) goto allfilled; else goto nextiter;

  for(auto p: freespots) midfill(p);

  nextiter2:
  if(rand() % 100 < 30) if(!badfill()) goto allfilled; else goto nextiter2;

  sfagain:
  for(auto p: freespots) stupidfill(p);

  FOR(y,1,Y+1) FOR(x,1,X+1) {
    int xy = XY(x,y);
    if(kmap[xy] == '.') goto sfagain;
    }

// phase III
  
  allfilled:
  calcap();
  cursc = compscore();
  again:
  while(tryswitchall(1)) ;
  if(tryswitchall(2)) { while(tryswitchall(2)) ; goto again; }
  if(tryswitchall(3)) { while(tryswitchall(3)) ; goto again; }
//  if(tryswitchall(4)) { while(tryswitchall(4)) ; goto again; }
  }

// the main function for solving a testcase

void solveCase() {
  int res = 0;

// read the data

  Y = getNum();
  X = getNum();
  K = getNum();

// for local testing: generate a test
  
  if(K < 0) {
    K = -K;
    int typ = getNum();
    int sd = getNum();
    if(sd == 0) sd = time(NULL);
    srand(sd);
    printf("seed = %d\n", sd);
    FOR(xy,0,MAXBOARD2) if(GETX(xy) == 0 || GETX(xy) > X || GETY(xy) == 0 || GETY(xy) > Y) kmap[xy] = 1;
    if(typ == 1) FOR(u,0,2) FOR(k,0,K) {
      again:
      int py = 1 + rand() % Y, px= 1 + rand() % X;
      int p = XY(px, py);
      if(kmap[p]) goto again;
      kmap[p] = 1;
      pxy[u][k] = p;
      }
    if(typ == 2) FOR(u,0,2) FOR(k,0,K) {
      again2:
      int py = 1 + rand() % Y, px= 1 + rand() % X;
      int p = XY(px, py);
      if(u == 1) p = pxy[0][k] + XY(rand() % 3 - 1, rand() % 3 - 1);
      if(kmap[p]) goto again2;
      kmap[p] = 1;
      pxy[u][k] = p;
      }
    if(typ == 3) FOR(u,0,2) FOR(k,0,K) {
      again3:
      int py = Y*(1+2*u)/5 + rand() % (Y/5), px=X*(1+2*u)/5  + rand() % (X/5);
      int p = XY(px, py);
      if(kmap[p]) goto again3;
      kmap[p] = 1;
      pxy[u][k] = p;
      }
    }
  else {
    FOR(u,0,2) FOR(k,0,K) {
      int py = getNum()+1;
      int px = getNum()+1;
      pxy[u][k] = XY(px, py);
      }
    }

// main findSolution() loop

  ll t= getVa();
  bestscore = -1;
  double avgscore = 0;
  int excs = 0;
  while(true) {
    curtime = getVa() - t;
    if(curtime > (tryindex >= 100 ? 1900000 : 1800000) && bestscore > 0) break;

    // try {
      tryindex++;
      excthrown = false;
      findSolution();
      if(excthrown) {excs++; continue; }
      double sc = getscore();
      avgscore += sc;
      if(sc > bestscore) {
        bestscore = sc;
        FOR(xy,0,MAXBOARD2) bestmap[xy] = kmap[xy];
        }
      // printf("res = %lf\n", getscore());
    //  }
    // catch(failed f) { }
    }

#ifdef LOCAL
  FOR(xy,0,MAXBOARD2) kmap[xy] = bestmap[xy];
  getscore();
  printf("bestval = %lf\n", bestscore);
  printf("avg val = %lf\n", avgscore / (tryindex-excs));
  printf("tryindex = %d (%d)\n", tryindex, excs);
  debugshot();

#else
  FOR(y,1,Y+1) 
    printf("%s\n", bestmap+y*MAXBOARD+1);
#endif
  }

#define P 1000000007

int main() {

  if(!MANYTESTS) Tests = 1;
  else Tests = getNum();
  
  for(cnum=1; cnum<=Tests; cnum++)
    solveCase();
    
  // finish
  return 0;
  }

void debugshot() {
  FOR(y,1,Y+1) {
    FOR(x,1,X+1) {
      int xy = XY(x,y);
      int t = cetype[xy];
      if(t == 0) ansicol16(9);
      if(t == 1) ansicol16(12);
      if(t == 3) ansicol16(10);
      if(t == 4) ansicol16(13);
      printf("%c", kmap[xy]);
      if(t != 2) ansiclear();
      }
    int k = y-1;
    if(k < K && perim[k]) {
      printf(" ");
      printf("%c: area=%4d peri=%4d %lf", 'a'+k, area[k], perim[k], 16*area[k] / pow(perim[k], 2)); 
      }
    printf("\n");
    }
  }