#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <errno.h>
#include <math.h>

#define _GNU_SOURCE
#include <string.h>

const double EPS = 1e-9;
inline int double_compare( const double a , const double b ){
    if( fabs(a - b) < EPS )
        return 0;
    else if( a + EPS < b )
        return -1;
    else
        return +1;
}

#define CHECKTIME(base, limit) double_compare(gt(base), limit)

unsigned int time_start;
inline double gt(unsigned int base) {
    //printf("gt %.2f, took %.2f\n", (double) clock(), (double)(clock() - time_start) / CLOCKS_PER_SEC);
    return (double)(clock() - base) / CLOCKS_PER_SEC;
}



#define NOW(ts) clock_gettime(CLOCK_MONOTONIC, (ts));


#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))

char *strndup (const char *s, size_t n){
  char *result;
  size_t len = strlen (s);

  if (n < len)
    len = n;

  result = (char *) malloc (len + 1);
  if (!result)
    return 0;

  result[len] = '\0';
  return (char *) memcpy (result, s, len);
}


void log_die(const char *msg, int logerr) {
    char *e = NULL;
    if (1 == logerr) e = strerror(errno);
    printf("%s %s\n", msg, NULL == e ? "" : e);
}

int calc_score(int N, char *c1, char *c2, int**cd) {
    int i, s=0;
    for(i=0; i<N; i++) s += cd[c1[i]-'a'][c2[i]-'a'];
    return s;
}

// inplace
void strrev2(char *p)
{
    char *q = p;
    while(q && *q) ++q;
    for(--q; p < q; ++p, --q)
        *p = *p ^ *q,
            *q = *p ^ *q,
            *p = *p ^ *q;
}
int N, K, T, V;
char *startSequence, *targetSequence;
int **charDifference;
char **dict, **dictr;

//operation
struct op {
    int cmd, p1, p2, p3;
};

struct op *ops_array;
int ops_count = 0;

int ms_total = 7800; // max ~8 seconds
int ms_per_op;
int ms_split_percent[6] = {0, 18 /*shift*/, 41 /*reverse*/, 0 /*del*/, 0 /*ins*/, 40/*dict*/}; // % time for each op to try
//int ms_split_percent[6] = {0, 80 /*shift*/, 10 /*reverse*/, 0 /*del*/, 0 /*ins*/, 10/*dict*/}; // % time for each op to try
//int ms_split_percent[6] = {0, 10 /*shift*/, 10 /*reverse*/, 0 /*del*/, 0 /*ins*/, 80/*dict*/}; // % time for each op to try
int ms_split[6]; // ms for each op
int total_ops[6] = {0, 0, 0, 0, 0, 0};
int best_ops[6] = {0, 0, 0, 0, 0, 0};

void read_input() {
    int i, j;
    FILE *f = fopen("fixdna.in", "r");
    if (NULL == f) log_die("err open(\"fixdna.in\")", 1);

    if (3 != fscanf(f, "%d %d %d\n", &N, &K, &T)) log_die("err 1", 0);
    startSequence = (char*) malloc(N+1);
    targetSequence = (char*) malloc(N+1);
    if (NULL == startSequence || NULL == targetSequence) log_die("err cant malloc sequences", 1);

    if (1 != fscanf(f, "%s\n", startSequence)) log_die("cant read startSequence", 0);
    if (1 != fscanf(f, "%s\n", targetSequence)) log_die("cant read targetSequence", 0);

#if 0
    for (i=0; i<N; i++) {
        startSequence[i] = toupper(startSequence[i]);
        targetSequence[i] = toupper(targetSequence[i]);
    }
#endif

    charDifference = (int**) malloc(K * sizeof(int*));
    for (i=0; i<K; i++) charDifference[i] = (int*) malloc(K*sizeof(int));

    for (i=0; i<K; i++) {
        for (j=0; j<K; j++) {
            if (1 != fscanf(f, "%d", &charDifference[i][j])) log_die("err cant read charDifference", 0);
        }
    }

#if 0 // dump charDifference
    for (i=0; i<K; i++) {
        for (j=0; j<K; j++) {
            printf("%d ", charDifference[i][j]);
        }
        printf("\n");
    }
#endif

    if (1 != fscanf(f, "%d\n", &V)) log_die("cant read V", 0);
    dict = (char**) malloc(V * sizeof(char*));
    dictr = (char**) malloc(V * sizeof(char*));
    for(i=0; i<V; i++) {
        char tmp[32000];
        if (1 != fscanf(f, "%s", &tmp)) log_die("cant read dict", 0);
        dict[i] = strdup(tmp);;
        //dictr[i] = strdup(dict[i]);
        //strrev(dictr[i]);
    }
#if 0 // dump dict
    printf("dict has %d entries\n", V);
    for(i=0; i<V; i++) {
        printf("%s\n", dict[i]);
        printf("%s\n", dictr[i]);
    }
#endif

    // mallocs
    ops_array = (op*) malloc(T * sizeof(struct op));

    //printf("%d %d %d %d\n%s\n%s\n", N, K, T, V, startSequence, targetSequence);
}

// OPS

// push (add) op
void op_push(struct op *o) {
    memcpy(&ops_array[ops_count++], o, sizeof(struct op));;
}

void op_pop() {
    ops_count--;
}

void op_do(struct op *o, char *str) {
    switch(o->cmd) {
    case 1:
        {
            assert(o->p2 > o->p1);
            size_t slen = strlen(str);
            size_t mlen = o->p2 - o->p1 + 1;
            char tmp[slen], res[slen];

            char *a, *b, *c, *d, *e;

            a = strndup(str, o->p1);
            c = strndup(str + o->p1, mlen);
            b = strndup(str + o->p2 + 1, slen - o->p2);
            //printf("a[%s] b[%s] c[%s]\n", a, b, c);

            memset(res, 0, slen);
            strcat(res, a); strcat(res, b);
            //printf("res is [%s]\n", res);

            d = (char*) strndup((char*) &res, o->p3);
            e = strndup(&res[o->p3], strlen(res) - o->p3);
            //printf("d[%s] e[%s]\n", d, e);

            sprintf(str, "%s%s%s", d, c, e);
            //printf("result:[%s]\n", str);

            free(a); free(b); free(c); free(d); free(e);
        }
        break;
    case 2: // reverse
        {
            assert(o->p2 > o->p1);
            size_t slen = o->p2 - o->p1; // length
            char tmp[slen+1];
            memset(&tmp, 0, slen+1);
            memcpy(&tmp, str+o->p1, slen);
            strrev2(tmp);
            memcpy(str+o->p1, &tmp, slen);
        }
        //sprintf(r, "%d %d %d\n", o->cmd, o->p1, o->p2);
        break;
    case 3: // delete
        {
            size_t slen = strlen(str);
            memmove(str+o->p1, str+o->p1+1, slen - o->p1);
            //str[slen-1] = 0;
        }
        break;
    case 4: //ins
        {
            //if (o->p1 == 63) asm("int $3");
            size_t slen = strlen(str);
            char buf[slen];
            memcpy(&buf, str, o->p1);
            buf[o->p1] = o->p2;
            memcpy(&buf[o->p1+1], str+o->p1, slen - o->p1);
            //sprintf(r, "%d %d %c\n", o->cmd, o->p1, o->p2);
            memcpy(str, buf, slen+1);
        }
        break;
    case 5: // dict insert
        {
            memcpy(str+o->p2, dict[o->p1], strlen(dict[o->p1]));

        }
        //sprintf(r, "%d %d %d\n", o->cmd, o->p1, o->p2);
        break;
    }
}

char *op2str(struct op *o) {
    char *r = (char*) malloc(15);

    switch(o->cmd) {
    case 1:
        sprintf(r, "%d %d %d %d\n", o->cmd, o->p1, o->p2, o->p3 );
        break;
    case 2:
        sprintf(r, "%d %d %d\n", o->cmd, o->p1, o->p2);
        break;
    case 3:
        sprintf(r, "%d %d\n", o->cmd, o->p1);
        break;
    case 4:
        sprintf(r, "%d %d %c\n", o->cmd, o->p1, o->p2);
        break;
    case 5:
        sprintf(r, "%d %d %d\n", o->cmd, o->p1, o->p2);
        break;
    }

    return r;
}


int brute(int operation, int best_score, int max_ms, char *sequence, struct op *o) {
    int i;
    struct op best_op, o2;
    char tmp[strlen(sequence)];
    unsigned int fn_start = clock();
    double limit_ms = (double)max_ms / 1000;

//printf("l %f CT(%f)\n", limit_ms, CHECKTIME(fn_start, limit_ms));
    while (-1 == CHECKTIME(fn_start, limit_ms)) {

        for(i=0; i<20; i++){
            sprintf(tmp, sequence, N); // fresh string

            switch (operation) {
                case 1:
                    {
                        int start = rand() % ( N>5 ? (N - 1) : 3);
                        int len = start + 1 + rand() % (1+(N-start-1));
                        //int len = start + 1 + rand() % (MIN(len, 1+rand()%3));
                        //int len = start + 3;
                        //len = MAX(len, 6); // limit max 8

                        //int target = 1 + rand() % (1 + (N-start - len));
                        int target = rand() % ( N>5 ? (N - 1) : 3);
                        //printf("do op1 %d %d %d, = %dchars\n", start, len, target, len - start);
                        o2.cmd = operation;
                        o2.p1 = start;
                        o2.p2 = len;
                        o2.p3 = target;
                        op_do(&o2, tmp);
                    }
                    break;
                case 2:
                    {
                        int pos = rand() % (N - 2);
                        int len = pos + 1 + rand() % (N-pos);
                        //len = MAX(len, 8); // limit max 8
                        o2.cmd = operation;
                        o2.p1 = pos; // start
                        o2.p2 = len; // end pos;
                        op_do(&o2, tmp);
                    }
                    break;
                case 5:
                    {
                        int use_dict = rand() % V;
                        int pos = rand() % (N - strlen(dict[use_dict]));
                        o2.cmd = operation;
                        o2.p1 = use_dict; // word idx
                        o2.p2 = pos; // insert pos;
                        op_do(&o2, tmp);
                    }
                    break;
            }


            /// got better ?
            int tmp_score = calc_score(N, tmp, targetSequence, charDifference);
            if (tmp_score < best_score) {
                //char *c = op2str(&o2);
                //printf("[%d]new best score: %d -> %d[%s]\n", operation, best_score, tmp_score, c);
                best_score = tmp_score;
                memcpy(&best_op, &o2, sizeof(o2));
            }

            total_ops[operation]++;
        } /* for */
    } /* while */

    memcpy(o, &best_op, sizeof(*o));
    return best_score;
}


int main(int argc, char **argv) {
    int i, s=0;
    int elapsed_ms;

    time_start = clock();
    srand( (int) time(NULL) ^ getpid());
    read_input();

    ms_per_op = ms_total / T;

    for (i=1; i<=5; i++) {
        ms_split[i] = ms_per_op * ms_split_percent[i] / 100;
    }

    //printf("~%dms per OP\n", ms_per_op);
    //printf("split: %d %d %d %d %d\n", ms_split[1], ms_split[2], ms_split[3], ms_split[4], ms_split[5]);


    int start_score = calc_score(N, startSequence, targetSequence, charDifference);
    //printf("start score %d\n", start_score);

#if 0 // test ops
    {
        char *string = strdup("abcbaaccbb"); // !!is r/o .. not freed
        char *result =        "abbaacccbb";
        struct op o2 = {1, 3, 6, 2};
        op_do(&o2, string);
        //printf("[%s]\n", string);
        assert (0 == memcmp(string, result, strlen(result)));
    }
    {
        char *string = strdup("abcdefghij"); // !!is r/o .. not freed
        char *result =        "defghijabc";
        struct op o2 = {1, 0, 2, 7};
        op_do(&o2, string);
        //printf("[%s]\n", string);
        assert (0 == memcmp(string, result, strlen(result)));
    }
    {
        char *string = strdup("pauznucwppjrzqwfasbytbmmwufeuwskxplmjnibfrsgiomkinlcqxomrwtmulytcjfmypndjhkrxwdglokblaofwjttwrmz");
        char *result =        "pauznucwppjrzqfwjttwrmzwfasbytbmmwufeuwskxplmjnibfrsgiomkinlcqxomrwtmulytcjfmypndjhkrxwdglokblao";
        struct op o2 = {1, 87, 96, 14};
        op_do(&o2, string);
        //printf("[%s]\n", string);
        assert (0 == memcmp(string, result, strlen(result)));
    }

    printf("done testing..\n");
    exit(0);
#endif

    char *sequence = strdup(startSequence);

    int step, this_op;
    int best_score = 98999;
    int max_tries = 150000;
    int ops_order[] = { 5, 2, 1 };

    char tmp[strlen(sequence)];
    for (step = 0; step<T; step++) {
        int better_score = 0;
        int tmp_score;
        struct op best_op = {0, 0, 0, 0}, o;

        for (i=0; i<3; i++) {
            this_op = ops_order[i];

            tmp_score = brute(this_op, best_score, ms_split[this_op], sequence, &o);
            /// got better ?
            if (tmp_score < best_score) {
#if 0
                char *c = op2str(&o);
                printf("(%d)new best score[+%d]: %d -> %d[%s]\n", this_op, best_score - tmp_score, best_score, tmp_score, c);
                free(c);
#endif
                best_score = tmp_score;
                memcpy(&best_op, &o, sizeof(o));
                better_score = 1;
            }

        }

        if (0 == better_score) {
            // could no do better ?
            //printf("[%d]:(\n", best_score);
            // .. ignore
            //continue;
        } else {
            best_ops[best_op.cmd]++;
            //char *c = op2str(&best_op);
            //printf("add %s", c);
            op_push(&best_op);
            //printf("OP %d %d %d", best_op.cmd, best_op.p1, best_op.p2);
            op_do(&best_op, sequence);
        }

    } /* for step */

#if 0
    int final_score = calc_score(N, sequence, targetSequence, charDifference);
    printf(" start: %s(%d)\n", startSequence, (int)strlen(startSequence));
    printf("   end: %s(%d)\n", sequence, (int)strlen(sequence));
    printf("target: %s(%d)\n", targetSequence, (int)strlen(targetSequence));
    printf("final score %d\n", final_score);
    printf("total_ops: %d %d %d %d %d\n", total_ops[1], total_ops[2], total_ops[3], total_ops[4], total_ops[5]);
    printf("best_ops: %d %d %d %d %d\n", best_ops[1], best_ops[2], best_ops[3], best_ops[4], best_ops[5]);
#endif

    FILE *of;
    of = fopen("fixdna.out", "w");
    fprintf(of, "%d\n", ops_count);
    char *c;
    for (i=0; i<ops_count; i++) {
        c =  op2str(&ops_array[i]);
        fprintf(of, "%s", c);
        free(c);
    }
    fclose(of);
    //log_die("end..", 0);
    //printf("total elapsed: %d\n", elapsed_ms);
    exit(0);