#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>
#include <string.h>
#include <wctype.h>
#include <wchar.h>
#include <locale.h>
#include <math.h>
#include <ctype.h>

struct Elem
{
    struct Elem *next;
    char *str;
};

char *stringcopywithpointer( const char *source) {
    int len = strlen(source);
    char *copy = malloc(len+1);
    strcpy(copy, source);
    return copy;
}

struct Elem *process_3(struct Elem * root, char *str, int precount) {
    struct Elem* tmp = root;
    if (!root) return root;
    if (!str) return root;
    int cmpres = strcmp(root->str, str);
    if (cmpres == 0) {
        return root;
    }
    if (cmpres > 0) {
        struct Elem* begin = malloc(sizeof(struct Elem));
        begin->str = stringcopywithpointer(str);
        begin->next = root;
        return begin;
    }
    while (tmp->next != NULL && strcmp(tmp->next->str, str) < 0) tmp = tmp->next;
    if (tmp->next && strcmp(tmp->next->str, str) == 0) return root;
    struct Elem* nxt = tmp->next;
    tmp->next = malloc(sizeof(struct Elem));
    tmp->next->str = stringcopywithpointer(str);
    tmp->next->next = nxt;
    if (precount <= 0)
        return root;
    struct Elem* from = root;
    int met = 0;
    struct Elem* to = root;
    for (int i = 0; i < precount; i++) {
        if (to == tmp) {
            met = 1;
            to = to->next;
            break;
        }
        to = to->next;
    }
    struct Elem* res = (met ? tmp->next : root);
    int strt = met;
    while (!met) {
        if (to == tmp) {
            met = 1;
            to = to->next;
            from = from->next;
            break;
        }
        to = to->next;
        from = from->next;
    }
    if (!strt) {
        struct Elem* tmpfrom = root;
        while (tmpfrom->next != from) {
            tmpfrom = tmpfrom->next;
        }
        tmpfrom->next    = tmp->next;
    }
    while (from != to) {
        free(from->str);
        struct Elem* tmpn = from->next;
        free(from);
        from = tmpn;
    }
    return res;
}

int main() {
    struct Elem* root = malloc(sizeof(struct Elem));
    root->str = malloc(3);
    root->str[0] = 'a';
    root->str[1] = 'a';
    root->str[2] = 0;
    struct Elem* tmp = root;
    for (int i = 0; i < 5; i++) {
        root->next  = malloc(sizeof(struct Elem));
        root = root->next;
        root->str = malloc(3);
        root->str[0] = 'a';
        root->str[1] = 'a' + 2 * (i + 1);
        root->str[2] = 0;
    }
    root = tmp;
    while(tmp != NULL) {
        printf("%s\n", tmp->str);
        tmp = tmp->next;
    }
    printf("\n");
    char* a = malloc(3);
    a[0] = 'a';
    a[1] = 'd';
    a[2] = 0;
    tmp = process_3(root, a, 3);
    free(a);
    while(tmp != NULL) {
        printf("%s\n", tmp->str);
        fflush(stdout);
        tmp = tmp->next;
    }
    return 0;
}