#include <iostream>
#include <vector>
#include <string>
#include <random>
#include <ctime>
#include <map>
#include <set>

using grid = std::vector<std::vector<int64_t>>;

std::random_device rng_seed;
std::mt19937_64 rng(rng_seed());

int n, m, longest;
std::map<std::pair<int64_t, int>, int> s_map;

int64_t calc_hash(const std::string &s)
{
    int64_t hash = 0;
    for (int i = 0; i < static_cast<int>(s.size()); i++)
    {
        hash += (s.at(i) - 'A') << (3 * i);
    }
    return hash;
}

int calc_score(const grid &a)
{
    std::set<std::pair<int64_t, int>> s;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int64_t hx = 0, hy = 0;
            for (int k = 0; k < longest; k++)
            {
                hx += a.at(i).at((j + k) % n) << (3 * k);
                hy += a.at((i + k) % n).at(j) << (3 * k);
                s.emplace(hx, k + 1);
                s.emplace(hy, k + 1);
            }
        }
    }

    int res = 0;
    for (auto &&x : s)
    {
        res += s_map[x];
    }
    return round(1e8 * res / m);
}

int main()
{
    clock_t start = clock();
    auto progress = [&]()
    {
        return (clock() - start) / (2.5 * CLOCKS_PER_SEC);
    };
    std::cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        std::string si;
        std::cin >> si;
        s_map[std::make_pair(calc_hash(si), si.size())]++;
        longest = std::max<int>(longest, si.size());
    }
    grid best(n, std::vector<int64_t>(n)), ans = best;
    int maxscore = 0, t = 0;
    while (progress() < 1)
    {
        for (auto &&[k, v] : s_map)
        {
            auto [hash, len] = k;
            int sx = rng() % n, sy = rng() % n, dx = t, dy = 1 - t;
            for (int i = 0; i < len; i++)
            {
                ans.at((sx + i * dx) % n).at((sy + i * dy) % n) = hash >> (3 * i) & 7;
            }
        }

        int score = calc_score(ans);
        if (score > maxscore)
        {
            maxscore = score;
            best = ans;
        }
        t = 1 - t;
    }

    std::cerr << maxscore << std::endl;

    // 出力
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            putchar('A' + best.at(i).at(j));
        }
        puts("");
    }
    return 0;
}

#include<bits/stdc++.h>
#define fi                first
#define se                 second
#define ll               long long
#define mod              1000000007LL
#define endl              "\n"
#define fast               ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb                push_back
#define all(v)             v.begin(),v.end()
#define inp(V,n)      for(int i=0;i<n;i++){cin >> V[i];}
#define oup(V,n)     {for(int i=0;i<n;i++){cout <<  V[i] << " "  ;} cout << endl;}
#define pll              pair<long long,long long>
#define pi            3.141592653589793238
using namespace std;
//vector<ll> adj[5005];
//vector<bool> vis(5005,false);
ll factorial(ll n)
{
    return (n == 1 || n == 0) ? 1 : n * factorial(n - 1);
}
ll gcd(ll a, ll b)
{
    if (a == 0)
      return b;
    return gcd(b % a, a);
}
ll lcm(ll a, ll b)
{
   return (a*b)/gcd(a, b);
}
bool sortByVal(const pair<ll,ll> &a,
              const pair<ll,ll> &b)
{
      if(a.fi == b.fi)
        return a.se < b.se;
     else
        return a.fi > b.fi;
}
ll Powb(ll b,ll n)
{
    if(n==0) return 1LL;
    if(n==1) return b;
    ll temp = Powb(b,n/2);
    if(n%2==0){return (temp*temp)%mod;}
    else{return (b*((temp*temp)%mod))%mod;}
}
ll root(vector<ll> &a,ll i)
{
    while(a[i] != i)
    {
        a[i]=a[a[i]];
        i=a[i];
    }
    return i;

}
void wunion(vector<ll> &a,vector<ll> &size,ll i,ll j)
{

    ll root_i=root(a,i);
    ll root_j=root(a,j);
    if(root_i == root_j)
        return;
    if(size[root_i]<size[root_j])
    {
        a[root_i]=a[root_j];
        size[root_j] += size[root_i];
        size[root_i]=0;
    }
    else
    {
        a[root_j]=a[root_i];
        size[root_i] += size[root_j];
        size[root_j]=0;
    }

}
int main()
{
 fast;
     int t=1;
     //cin>>t;
     while(t--)
     {
     ll i,j,m,n,k,sum=0,c=0,d=0,e=0,f=0,g=0,h=0,maxi=0;
      cin>>n;
      string a;
      for(i=1;i<=1000000;i++)
      {
          a=to_string(i);
          d=a.size();
          c=Powb(10,d)*i;
          e=c+i;
          //cout<<e<<endl;
          if(e<=n)
            sum++;
          else
            break;
      }
      cout<<sum<<endl;



     }
}
