#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <vector>
#include <cstdio>
#include <string>
using namespace std;

#define ll long long 
#define ull unsigned long long

/*------------------------------------------------------------------*/
 
bool myGreater(string& a, string&b)
{
   return(a[0] > b[0] || (a[0] == b[0] && a[1] > b[1]));
}

void mySwap(string &a, string& b)
{
   string c;
   if (myGreater(b,a))
   {
      c = a; 
      a = b;
      b = c;
   }
}

inline int toDigit(char c)
{
   if (c >= '0' && c <= '9') return c - '0';
   return (c - 'A' + 10);
}

inline char toChar(int c)
{
   if (c <= 9) return c + '0';
   return (c - 10 + 'A');
}

string diff(string a, string b)
{
   mySwap(a, b);
   string res = "";
   int minte = 0, pc;

   for(int i = 1; i>=0; --i)
   {
      pc = toDigit(a[i]) - toDigit(b[i]) - minte;
      if (pc < 0) pc += 16, minte = 1;
      else minte = 0;
      res += toChar(pc);
   }
   reverse(res.begin(), res.end());
   return res;
}

string lst[16];
unordered_map<string, char> besties;

void init()
{
   lst[0] = "11"; lst[1] = "22"; lst[2] = "33"; lst[3] = "44"; lst[4] = "55"; lst[5] = "66";
   lst[6] = "77"; lst[7] = "88"; lst[8] = "99"; lst[9] = "AA"; lst[10] = "BB"; lst[11] = "CC";
   lst[12] = "DD"; lst[13] = "EE"; lst[14] = "FF"; lst[15] = "00";

   string r, local, bestie;
   char sol;

   for(int i = 0; i<= 15; ++i)
   {
      for (int j = 0; j <= 15; ++j)
      {
         r = toChar(i);
         r += toChar(j);
         sol = '0';
         bestie = diff(r, lst[15]);
         for (int i = 0; i <= 14; ++i)
         {
            local = diff(r, lst[i]);
            if (myGreater(bestie, local))
            {
               sol = lst[i][0];
               bestie = local;
            }
         }
         besties[r] = sol;
      }
   }

}


void solve(string str)
{

   char sol;
   cout << "#";
   for(int j = 1; j<=6;j+=2)
   {
      cout << besties[str.substr(j,2)];
   }
}

int main()
{
   ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

   init();
   int n, m;
   cin >> n >> m;
   string s;

   for(int i = 1; i<=n; ++i)
   {
      for(int j = 1; j<=m; ++j)
      {
         cin >> s;
         solve(s);
         cout << " ";
      }
      cout << "\n";
   }

   return 0;
}