tco10

#pragma GCC optimize ("O3")

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
#include <set>
#include <string>
#include <random>
#include <queue>
#include <string.h>

//#define DEBUG
const double TL = 10.0;

using namespace std;
typedef long long int ll;
typedef pair<int, int> pi;

const unsigned long long int cycle_per_sec = 2800000000;

unsigned long long int getCycle() {
    unsigned int low, high;
    __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
    return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}

double getTime (unsigned long long int begin_cycle) {
    return (double)(getCycle() - begin_cycle) / cycle_per_sec;
}

class XorShift {
public:
    unsigned int x;
    unsigned int y;
    unsigned int z;
    unsigned int w;
    unsigned int t;
    
    XorShift(int tmp) {
        mt19937 rnd(tmp);
        x = rnd();
        y = rnd();
        z = rnd();
        w = rnd();
        t = 1;
    }
    
    int rand() {
        t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
        return w & 0x7fffffff;
    }
} engine(rand());

inline double exp1(double x) {
    x = 1.0 + x / 16.0;
    x *= x; x *= x; x *= x; x *= x;
    return x;
}

constexpr int INF = 1000000000;
constexpr int dx[4] = {1, 0, -1, 0};
constexpr int dy[4] = {0, 1, 0, -1};
constexpr int bx[4] = {1, -1, -1, 1};
constexpr int by[4] = {1, -1, 1, -1};
constexpr int kx[8] = {2, 1, -2, -1, -2, -1, 2, 1};
constexpr int ky[8] = {1, 2, 1, 2, -1, -2, -1, -2};
constexpr int ddx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
constexpr int ddy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

constexpr int MAXN = 50;
constexpr int MAXN2 = 52;
constexpr int MAXC = 8;
int N, C;
char GRID[MAXN2][MAXN2];
int POINTS[5];

struct UF {
    int si[MAXN2*MAXN2];
    int par[MAXN2*MAXN2];

    void init() {
        for (int i = 0; i < MAXN2; i++) {
            for (int j = 0; j < MAXN2; j++) {
                si[i*MAXN2+j] = 1;
                par[i*MAXN2+j] = i*MAXN2+j;
            }
        }
    }

    int find (int x) {
        while (par[x] != x) x = par[x] = par[par[x]];
        return x;
    }

    void unite (int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (si[x] < si[y]) swap(x,y);
        si[x] += si[y];
        par[y] = x;
    }
} uf;


/*
struct CELL {
    int id; // -1 .. none, 0 .. king, 1 .. queen, 2 .. rook, 3 .. bishop, 4 .. knight, 5 .. wall
    int pl; 
};
*/

struct STATE {
    int score;
    int pscore[MAXC];
    int cpiece[MAXN2][MAXN2];
    int cperson[MAXN2][MAXN2];

    void init () {
        score = 0;
        for (int i = 0; i < N+2; i++) {
            for (int j = 0; j < N+2; j++) {
                if (GRID[i][j] == '#') cpiece[i][j] = 5;
                else cpiece[i][j] = -1;
                cperson[i][j] = -1;
            }
        }
        memset(pscore, 0, sizeof(pscore));
    }

    void copy (STATE &st) {
        score = st.score;
        for (int i = 0; i < C; i++) pscore[i] = st.pscore[i];
        for (int i = 0; i < N+2; i++) {
            for (int j = 0; j < N+2; j++) {
                cpiece[i][j] = st.cpiece[i][j];
                cperson[i][j] = st.cperson[i][j];
            }
        }
    }

    void output() {
        cout << 2*N*N << endl;
        for (int i = 1; i < N+1; i++) {
            for (int j = 1; j < N+1; j++) {
                if (cpiece[i][j]== -1) cout << "." << endl;
                if (cpiece[i][j]== 0) cout << "K" << endl;
                if (cpiece[i][j]== 1) cout << "Q" << endl;
                if (cpiece[i][j]== 2) cout << "R" << endl;
                if (cpiece[i][j]== 3) cout << "B" << endl;
                if (cpiece[i][j]== 4) cout << "N" << endl;
                if (cpiece[i][j]== 5) cout << "#" << endl;
            }
        }
        for (int i = 1; i < N+1; i++) {
            for (int j = 1; j < N+1; j++) {
                cout << max(0,cperson[i][j]) << endl;
            }
        }
    }
};


void input() {
    cin >> N >> C;
    for (int i = 0; i < N+2; i++) {
        for (int j = 0; j < N+2; j++) {
            GRID[i][j] = '.';
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> GRID[i+1][j+1];
        }
    }
    for (int i=0; i<5; i++) cin >> POINTS[i];    

}

void init() {
}

inline pair<int,int> king_put (int piece, int person, STATE& state, int x, int y) {
    if (state.cpiece[x][y] != -1) return pi(-1,-1);
    bool force = false;
    int ret = 0;
    for (int dir = 0; dir < 8; dir++) {
        int nx = x + ddx[dir], ny = y + ddy[dir];
        if (state.cpiece[nx][ny] == 5) {
            continue;
        }
        if (state.cpiece[nx][ny] != -1) {
            if (state.cperson[nx][ny] == person) {
                ret++;
                bool ok = true;
                for (int d = 0; d < 8; d++) {
                    int tx = nx + ddx[d], ty = ny + ddy[d];
                    if (tx == x && ty == y) continue;
                    if (tx != 0 && tx != N+1 && ty != 0 && ty != N+1 && state.cpiece[tx][ty] == -1) ok = false;
                }
                if (ok) ret += 100;
                continue;
            }
            force = true;
        }
    }
    return pi(ret,force);
}

void king_put_affect (int piece, int person, STATE& state, int x, int y) {
    bool queen = true;
    for (int dir = 0; dir < 8; dir++) {
        int nx = x + ddx[dir], ny = y + ddy[dir];
        if (nx == 0 || nx == N+1 || ny == 0 || ny == N+1) continue;
        if (state.cpiece[nx][ny] == 5) {
            continue;
        }
        if (state.cpiece[nx][ny] != -1) {
            if (state.cperson[nx][ny] == person) {
                bool ok = true;
                for (int d = 0; d < 8; d++) {
                    int tx = nx + ddx[d], ty = ny + ddy[d];
                    if (tx == x && ty == y) continue;
                    if (tx != 0 && tx != N+1 && ty != 0 && ty != N+1 && state.cpiece[tx][ty] == -1) ok = false;
                }
                if (ok) {
                    state.pscore[person] += POINTS[1]-POINTS[0];
                    state.cpiece[nx][ny] = 1;
                }
            }
        } else {
            queen = false;
        }
    }
    if (queen) {
        state.pscore[person] += POINTS[1];
        state.cpiece[x][y] = 1;
        state.cperson[x][y] = person;
    } else {
        state.pscore[person] += POINTS[0];
        state.cpiece[x][y] = 0;
        state.cperson[x][y] = person;
    }
}

void force_king_put_affect (int piece, int person, STATE& state, int x, int y) {
    bool queen = true;
    for (int dir = 0; dir < 8; dir++) {
        int nx = x + ddx[dir], ny = y + ddy[dir];
        if (nx == 0 || nx == N+1 || ny == 0 || ny == N+1) continue;
        if (state.cpiece[nx][ny] == 5) {
            continue;
        }
        if (state.cpiece[nx][ny] != -1) {
            if (state.cperson[nx][ny] == person) {
                bool ok = true;
                for (int d = 0; d < 8; d++) {
                    int tx = nx + ddx[d], ty = ny + ddy[d];
                    if (tx == x && ty == y) continue;
                    if (tx != 0 && tx != N+1 && ty != 0 && ty != N+1 && state.cpiece[tx][ty] == -1) ok = false;
                }
                if (ok) {
                    state.pscore[person] += POINTS[1]-POINTS[0];
                    state.cpiece[nx][ny] = 1;
                }
            } else {
                queen = false;
                int victim = state.cperson[nx][ny];
                state.cpiece[nx][ny] = -1;
                state.cperson[nx][ny] = -1;
                state.pscore[victim] -= POINTS[0];
                for (int d = 0; d < 8; d++) {
                    int tx = nx + ddx[d], ty = ny + ddy[d];
                    if (state.cpiece[tx][ty] == 1) {
                        state.cpiece[tx][ty] = 0;
                        state.pscore[victim] -= POINTS[1]-POINTS[0];
                    }
                }
            }
        } else {
            queen = false;
        }
    }
    if (queen) {
        state.pscore[person] += POINTS[1];
        state.cpiece[x][y] = 1;
        state.cperson[x][y] = person;
    } else {
        state.pscore[person] += POINTS[0];
        state.cpiece[x][y] = 0;
        state.cperson[x][y] = person;
    }
}

void init_put (STATE& state) {
    for (int i = 0; i < C; i++) {
        while (true) {
            int x = engine.rand() % N + 1;
            int y = engine.rand() % N + 1;
            if (state.cpiece[x][y] != -1) continue;
            bool ok = true;
            for (int d = 0; d < 8; d++) {
                int tx = x + ddx[d], ty = y + ddy[d];
                if (state.cpiece[tx][ty] != -1 && state.cpiece[tx][ty] != 5) ok = false;
            }
            if (!ok) continue;
            state.cpiece[x][y] = 0;
            state.cperson[x][y] = i;
            state.pscore[i] += POINTS[0];
            break;
        }
    }
}

bool can_put (int piece, int person, STATE& state, int x, int y) {
    if (piece == 0) { // king
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) continue;
                if (state.cpiece[x+i][y+j] != -1 && state.cpiece[x+i][y+j] != 5) {
                    if (state.cperson[x+i][y+j] != person) return false;
                }
            }
        }
    } else if (piece == 1) { // queen
        for (int dir = 0; dir < 8; dir++) {
            int nx = x+ddx[dir], ny = y+ddy[dir];
            while (true) {
                if (nx == 0 || nx == N+1 || ny == 0 || ny == N+1) break;
                if (state.cpiece[nx][ny] == 5) break;
                if (state.cpiece[nx][ny] != -1) {
                    if (state.cperson[nx][ny] == person) break;
                    else return false;
                }
                nx += ddx[dir];
                ny += ddy[dir];
            }
        }
    } else if (piece == 2) { // rook
        for (int dir = 0; dir < 4; dir++) {
            int nx = x+dx[dir], ny = y+dy[dir];
            while (true) {
                if (nx == 0 || nx == N+1 || ny == 0 || ny == N+1) break;
                if (state.cpiece[nx][ny] == 5) break;
                if (state.cpiece[nx][ny] != -1) {
                    if (state.cperson[nx][ny] == person) break;
                    else return false;
                }
                nx += dx[dir];
                ny += dy[dir];
            }
        }
    } else if (piece == 3) { // bishop
        for (int dir = 0; dir < 4; dir++) {
            int nx = x+bx[dir], ny = y+by[dir];
            while (true) {
                if (nx == 0 || nx == N+1 || ny == 0 || ny == N+1) break;
                if (state.cpiece[nx][ny] == 5) break;
                if (state.cpiece[nx][ny] != -1) {
                    if (state.cperson[nx][ny] == person) break;
                    else return false;
                }
                nx += bx[dir];
                ny += by[dir];
            }
        }

    } else { // knight
        for (int dir = 0; dir < 8; dir++) {
            int nx = x+kx[dir], ny = y+ky[dir];
            if (nx == 0 || nx == N+1 || ny == 0 || ny == N+1) continue;
            if (state.cpiece[nx][ny] == 5) continue;
            if (state.cpiece[nx][ny] != -1) {
                if (state.cperson[nx][ny] != person) return false;
            }
        }
    }
    return true;

}

void solve() {
    unsigned long long int start_cycle = getCycle();
    STATE state;
    state.init();
    pi pieces[5];
    for (int i = 0; i < 5; i++) {
        pieces[i] = pi(POINTS[i], i);
    }
    sort(pieces, pieces+5, greater<pi>());

    init_put(state);

    STATE best_state;
    
    int loop = 0;
    /*
    int ord[MAXN2*MAXN2];
    for (int i = 0; i < MAXN2*MAXN2; i++) {
        ord[i] = i;
    }
    */
    while (getTime(start_cycle) < 4.5) {
        loop++;
        pi priop[MAXC];
        for (int x = 0; x < C; x++) {
            priop[x] = pi(state.pscore[x], x);
        }
        sort(priop, priop+C);
        {
            int nowp = priop[0].second;
            int pie = 0;
            int bestval = 0;
            int bestx, besty = 0;
            int fbestval = 0;
            int fbestx, fbesty = 0;
            int i_dir = engine.rand()%2;
            int j_dir = engine.rand()%2;
            for (int i = 1; i < N+1; i++) {
                for (int j = 1; j < N+1; j++) {
                    pi val = king_put(pie, nowp, state, i, j);
                    if (val.first <= 0) continue;
                    val.first += engine.rand()%300;
                    if (!val.second) {
                        if (val.first > bestval) {
                            bestval = val.first;
                            bestx = i;
                            besty = j;
                        }
                    } else {
                        if (val.first > fbestval) {
                            fbestval = val.first;
                            fbestx = i;
                            fbesty = j;
                        }
                    }
                }
            }
            if (bestval != 0) {
                king_put_affect(pie, nowp, state, bestx, besty);
            } else if (fbestval != 0) {
                force_king_put_affect(pie, nowp, state, fbestx, fbesty);
            }
        }
        state.score = INF;
        for (int i = 0; i < C; i++) state.score = min(state.score, state.pscore[i]);
        if (state.score > best_state.score) {
            best_state.copy(state);
        }
    }
    state.init();

    while (getTime(start_cycle) < TL-1.0) {
        loop++;
        pi priop[MAXC];
        for (int x = 0; x < C; x++) {
            priop[x] = pi(state.pscore[x], x);
        }
        sort(priop, priop+C);
        {
            int nowp = priop[0].second;
            int pie = 0;
            int bestval = -1;
            int bestx, besty = 0;
            int fbestval = -1;
            int fbestx, fbesty = 0;

            int i_dir = engine.rand()%2;
            int j_dir = engine.rand()%2;

            for (int i = 1; i < N+1; i++) {
                for (int j = 1; j < N+1; j++) {
                    pi val = king_put(pie, nowp, state, i, j);
                    if (val.first == -1) continue;
                    val.first += engine.rand()%300;
                    if (!val.second) {
                        if (val.first > bestval) {
                            bestval = val.first;
                            bestx = i;
                            besty = j;
                        }
                    } else {
                        if (val.first > fbestval) {
                            fbestval = val.first;
                            fbestx = i;
                            fbesty = j;
                        }
                    }
                }
            }
            if (bestval != -1) {
                king_put_affect(pie, nowp, state, bestx, besty);
            } else if (fbestval != -1) {
                force_king_put_affect(pie, nowp, state, fbestx, fbesty);
            }
        }
        state.score = INF;
        for (int i = 0; i < C; i++) state.score = min(state.score, state.pscore[i]);
        if (state.score > best_state.score) {
            best_state.copy(state);
        }
    }
    cerr << loop << endl;

    while (getTime(start_cycle) < TL-0.5) {
        pi priop[MAXC];
        for (int x = 0; x < C; x++) {
            priop[x] = pi(best_state.pscore[x], x);
        }
        sort(priop, priop+C);

        int nowp = priop[0].second;
        bool done = false;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (done) break;
                if (best_state.cpiece[i][j] != 0 || best_state.cperson[i][j] != nowp) {
                    continue;
                }
                for (int k = 0; k < 5; k++) {
                    if (POINTS[pieces[k].second] <= POINTS[0]) continue;
                    if (can_put(pieces[k].second, nowp, best_state, i, j)) {
                        best_state.cpiece[i][j] = pieces[k].second;
                        best_state.pscore[nowp] += POINTS[pieces[k].second]-POINTS[0];
                        done = true;
                        break;
                    }
                }
            }
        }
    }
    best_state.output();
}

int main() {
    input();
    init();
    solve();
}