ALGO KUN ( O(M sqrt(N)) )

#include <cstdio>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

namespace Mlxa
{
    using namespace std;
    typedef   long long         ll;

    #define read                cin
    #define eol                 '\n'
    #define endln               cout << eol

    template <class A>              inline void print   (A a)           { cout << a << ' '; }
    template <class A>              inline void println (A a)           { cout << a << eol; }
    template <class A, class... B>  inline void println (A a, B... b)   { print(a); println(b...); }
    template <class It> ostream&
    operator << (ostream& out, pair<It, It> &c) {
        out << "{ "; -- c.second;
        for (It i(c.first); i != c.second; ++ i)
            out << *i << ", ";
        out << *c.second << " }"; return out;
    }

    template <class A>              inline void err     (A a)         { cerr << a << ' '; }
    template <class A>              inline void errln   (A a)         { cerr << a << eol; }
    template <class A, class... B>  inline void errln   (A a, B... b) { err(a); errln(b...); }


    #ifdef AC
        #define add_log(...) errln("log | ", __VA_ARGS__)
    #else
        #define add_log(...) (void(0))
    #endif

    template <class A> inline ll get_size(A a) { return a.size(); }
    #define pb                  push_back
    #define mp                  make_pair
    #define all(x)              begin(x), end(x)

    #define openFiles(name)     freopen(name ".in", "r", stdin), freopen(name ".out", "w", stdout)
    #define fastIO              ios_base::sync_with_stdio(false), cin.tie(nullptr)
} using namespace Mlxa;

const ll max_n (2005);

string M[max_n];
ll dfs_cnt(0);
inline ll get_num (ll i, ll j)
{   i += 3, j += 3; return i * 100 + j; }
inline void get_pos (ll &a, ll &b, ll num)
{   a = num / 100; b = num % 100; a -= 3; b -= 3;   }

void paint2 (ll i, ll j, ll a, ll b)
{
    static char cnt = 'A';
    M[i][j] = M[a][b] = cnt;
    if (cnt == 'Z') cnt = 'a';
    else            ++ cnt;
    assert(cnt - 1 <= 'z');
}

namespace matching
{
    ll color(1), edg_size(0);
    set<ll> part[2];
    ll used[max_n], match[max_n];
    vector<ll> edges[max_n];

    void greed ()
    {
        for (ll i : part[0])
            for (ll j : edges[i])
            if (match[j] < 0) {
                match[i] = j;
                match[j] = i;
                break;
            }
    }

    bool dfs (ll v)
    {   add_log("dfs", v); ++ dfs_cnt;
        if (used[v] == color) return false;
        used[v] = color;
        for (ll u : edges[v])
        if (match[u] < 0 || dfs(match[u])) {
            match[v] = u;
            match[u] = v;
            return true;
        }
        return false;
    }

    void find (ll n)
    {
        fill(all(used), 0);
        fill(all(match), -1);
        greed();

        color = true;
        for (ll run(true); run; ++ color) {
            run = false;
            for (ll i : part[0])
            if (match[i] < 0 && dfs(i))
                run = true;
        }
    }

    bool save_results (ll n, ll m)
    {
        if ( ll(part[0].size() + part[1].size()) < n * m ) return false;
        for (ll i : part[0]) {
            if (match[i] < 0) return false;
            ll j = match[i];
            ll a, b, c, d;
            get_pos(a, b, i);
            get_pos(c, d, j);
            paint2(a,b, c,d);
        } return true;
    }
}

ll n, m;

void add_edge (ll i, ll j, ll a, ll b)
{   using namespace matching;
    ll pij = (i % 2 == j % 2), pab = (a % 2 == b % 2);
    assert(pij != pab);
    ++ edg_size;
    i = get_num(i, j);
    j = get_num(a, b);
    part[pij].insert(i);
    part[pab].insert(j);
    edges[i].push_back(j);
    edges[j].push_back(i);
}

void start ()
{
    fastIO;
    read >> n >> m;
    add_log("|V| =", n, "|E| =", m);
    for (ll i(0); i < n; ++ i)
        read >> M[i];
    for (ll i(0); i < n; ++ i)
        for (ll j(0); j < m; ++ j)
        {
            if (i && M[i][j] != M[i - 1][j]) add_edge(i, j, i - 1, j);
            if (j && M[i][j] != M[i][j - 1]) add_edge(i, j, i, j - 1);
        }
}

int main ()
{
    start();
    matching::find(n);
    if ( matching::save_results(n, m) ) {
        println("Yes");
        for (ll i(0); i < n; ++ i)
            println(M[i]);
    } else println("No");
    return 0;
}