#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <limits.h>

#include <iostream>
#include <atomic>
#include <thread>
#include <vector>

#define INFINITE 0
#define MULTIPLE 0

#if INFINITE
#define DBG2
#endif

#if INFINIT || MULTIPLE
#define DBG3
#endif

#define MAX_CH      200
#define CHAR_SET    ('z'-'a'+1)
char kbd_init[CHAR_SET+1] = "";
//                     0  1   2   3   4   5   6   7   8   9   10 11  12  13  14  15  16  17  18  19  20  21  22  23  24  25
int x_cor[CHAR_SET] = {85,123,161,199,237,275,313,351,389,427,95,133,171,209,247,285,324,362,400,122,160,198,236,275,313,351};
//                     0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
int y_cor[CHAR_SET] = {0,0,0,0,0,0,0,0,0,0,39,39,39,39,39,39,39,39,39,79,79,79,79,79,79,79};
#define get_x(a) x_cor[a]
#define get_y(a) y_cor[a]

//                        0  1  2 3 4  5  6  7  8 9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
int priority[CHAR_SET] = {0,1,10,11,2,12,19,20,3,13,21,4 ,14,22,5, 15,23,6, 16,24,7, 17,25,8, 18,9};
//int priority[CHAR_SET] = {12,13,3,2,11,20,21,22,4,14,1 ,19,10,0 ,5, 23,15,6, 24,16,7, 25,17,8, 18,9};

int dist[CHAR_SET][CHAR_SET];
//int pairs[CHAR_SET][CHAR_SET];

int     inch_cnt = 0;
int     inch_dif = 0;
char    inch[MAX_CH+1] = "";

void read_file()
{
FILE *fh;

        fh = fopen("keyboard.in","r");
        if (!fh)
        {
            printf("Err opening input file !\n");
            exit(1);
        }
        else
        {
            fscanf(fh,"%d",&inch_cnt);
            fscanf(fh,"%s",inch);
            inch[inch_cnt] = 0;
            fclose(fh);
#ifdef DBG
            printf("%d\n%s\n",inch_cnt,inch);
#endif
        }

}

inline int distance(int pos1, int pos2)
{
    int x1 = get_x(pos1);
    int y1 = get_y(pos1);
    int x2 = get_x(pos2);
    int y2 = get_y(pos2);

    if (x1==x2) return abs(y1-y2);
    else if (y1==y2) return abs(x1-x2);

    int dx = x1-x2;
    int dy = y1-y2;

    return sqrt((double)(dx*dx + dy*dy))+0.5;
}

void misc_calcs()
{
        //---------------------------------------------
        for (int p1=0;p1<CHAR_SET;p1++)
            for (int p2=0;p2<CHAR_SET;p2++)
                dist[p1][p2] = distance(p1,p2);

        //---------------------------------------------
        int kbd_set[CHAR_SET];
        memset(kbd_set,0, sizeof(kbd_set));
        inch_dif = 0;
        char *p = inch;
        while (int idx = *p++)
        {
            idx -= 'a';
            if (!kbd_set[idx])
            {
                kbd_set[idx] = 1;
                kbd_init[inch_dif++] = idx+'a';
            }
        }
        int j = inch_dif;
        for (int i=0;i<CHAR_SET;i++)
        {
            if (!kbd_set[i]) kbd_init[j++] = i+'a';
        }
        kbd_init[j] = 0;
#if 0
        printf("kbd_init: %s (%d,%d)\n",kbd_init,inch_dif,j);
#endif

}

char    chset_min[CHAR_SET+1];

int run(int flin, int frin, char *ch, int *chidx)
{
    int fl = flin;
    int fr = frin;
    int d1, d2;
    int sum = 0;
    while (int sym = *ch++)
    {
        int cp = chidx[sym-'a'];
        if (get_x(cp) <= get_x(fl))
        {
            d1 = dist[fl][cp];
            sum += d1;
            fl = cp;
        }
        else if (get_x(cp) >= get_x(fr))
        {
            d2 = dist[fr][cp];
            sum += d2;
            fr = cp;
        }
        else
        {
            d1 = dist[fl][cp];
            d2 = dist[fr][cp];
            if (d1<=d2)
            {
                sum += d1;
                fl = cp;
            }
            else
            {
                sum += d2;
                fr = cp;
            }
        }
    }
    return sum;
}

void kbd_shuffle(char *chset, int *chidx)
{
char rnd_src[CHAR_SET+1];

    int n = inch_dif;
    memcpy(rnd_src, kbd_init, n);
    for (int i=0;i<inch_dif;i++)
    {
       int p = rand() % n;
       int idx = priority[i];
       chset[idx] = rnd_src[p];
       chidx[chset[idx]-'a'] = idx;
       memmove(&rnd_src[p], &rnd_src[p+1], n-p);
       n--;
    }
    for (int i=inch_dif;i<CHAR_SET;i++)
    {
       int idx = priority[i];
       chset[idx] = kbd_init[i];
       chidx[chset[idx]-'a'] = idx;
    }
    chset[CHAR_SET] = 0;
#if 0
    printf("chset: %s\n",chset);
#endif
}

char    chset[CHAR_SET+1];
int     chidx[CHAR_SET];

int main()
{
    time_t t1,t2;
    float seconds = 0;
    read_file();
    misc_calcs();
//    srand(time(NULL));

    int l_min = 0, r_min = 0;
    do {
        time(&t1);

        int res_min = INT_MAX;
        int cnt = 0;
        do {
            kbd_shuffle(chset, chidx);

            int lfp = chidx[kbd_init[0]-'a'];
            for (int rf=1; rf<inch_dif; rf++)
            {
                int rfp = chidx[kbd_init[rf]-'a'];
                if (get_x(lfp)>=get_x(rfp)) continue;
                int L_start = lfp;
                int R_start = rfp;
                int res = run(L_start, R_start, inch, chidx);
                if (res<res_min)
                {
                    res_min = res;
                    l_min = L_start;
                    r_min = R_start;
                    memcpy(chset_min, chset, sizeof(chset_min));
#ifdef DBG2
                    printf("D%d: %s\n",rfp,chset);
                    printf("%d,%d -> %d (%d)\n",l_min,r_min,res_min,cnt);
#endif
                }
            }
            //-------------------------------------------
            int rfp = chidx[kbd_init[0]-'a'];
            for (int lf=1; lf<inch_dif; lf++)
            {
                int lfp = chidx[kbd_init[lf]-'a'];
                if (get_x(lfp)>=get_x(rfp)) continue;
                int L_start = lfp;
                int R_start = rfp;
                int res = run(L_start, R_start, inch, chidx);
                if (res<res_min)
                {
                    res_min = res;
                    l_min = L_start;
                    r_min = R_start;
                    memcpy(chset_min, chset, sizeof(chset_min));
#ifdef DBG2
                    printf("D%d: %s\n",lfp,chset);
                    printf("%d,%d -> %d (%d)\n",l_min,r_min,res_min,cnt);
#endif
                }
            }

            //-------------------------------------------
            time(&t2);
            seconds = difftime(t2,t1);
            cnt++;
        } while (INFINITE || seconds<=2.95);
#ifdef DBG3
        printf("Time: %.3f s, Cnt: %d, Min: %d\n",seconds,cnt,res_min);
        printf("%s\n%d %d\n", chset_min, l_min+1, r_min+1);
#endif
    } while (MULTIPLE);

    FILE *fw = fopen("keyboard.out","w");
    if (!fw) printf("Err opening output file !\n");
    else
    {
        fprintf(fw,"%s\n%d %d\n", chset_min, l_min+1, r_min+1);
        fclose(fw);
    }

    return 0;
}