#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

struct Voyage {
    int id;
    int hrs;
    int mins;
    char dest[21];
};

char *strToUpper(char *s) {
    int i = 0;
    while (*s) {
        *s = toupper(*s);
        s++;
        i++;
    }
    return s - i;
}

int time(int m1, int h1, int m2, int h2) {
    int sum = (m2 - m1) + (h2 - h1) * 60;
    return sum;
}

void read(FILE *fr, struct Voyage *voyages, int N) {
    for (int i = 0; i < N; i++) {
        fscanf(fr, "%d %d:%d %s",
               &voyages[i].id, &voyages[i].hrs, &voyages[i].mins, voyages[i].dest);

        strToUpper(voyages[i].dest);
    }
}

void sort(struct Voyage *voyages, int N) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N - 1 - i; j++) {
            if (voyages[j].hrs > voyages[j + 1].hrs) {
                struct Voyage tmp = voyages[j];
                voyages[j] = voyages[j + 1];
                voyages[j + 1] = tmp;
            } else if (voyages[j].hrs == voyages[j + 1].hrs && \
                    voyages[j].mins > voyages[j + 1].mins) {
                struct Voyage tmp = voyages[j];
                voyages[j] = voyages[j + 1];
                voyages[j + 1] = tmp;
            } else if (voyages[j].hrs == voyages[j + 1].hrs && \
                    voyages[j].mins == voyages[j + 1].mins && \
                    strcmp(voyages[j].dest, voyages[j + 1].dest) > 0) {
                struct Voyage tmp = voyages[j];
                voyages[j] = voyages[j + 1];
                voyages[j + 1] = tmp;
            } else if (voyages[j].hrs == voyages[j + 1].hrs && \
                    voyages[j].mins == voyages[j + 1].mins && \
                    strcmp(voyages[j].dest, voyages[j + 1].dest) == 0 && \
                    voyages[j].id > voyages[j + 1].id) {
                struct Voyage tmp = voyages[j];
                voyages[j] = voyages[j + 1];
                voyages[j + 1] = tmp;
            }
        }
    }
}

void write(FILE *fw, struct Voyage *voyages, int K) {
    for (int i = 0; i < K; i++) {
        fprintf(fw, "%03d %02d:%02d %s %d\n",
                voyages[i].id, voyages[i].hrs, voyages[i].mins, voyages[i].dest, 1);
    }
}

int main() {
    FILE *fr = fopen("D:/Projects/CLionProjects/Lab_6/input.txt", "rt");
    FILE *fw = fopen("D:/Projects/CLionProjects/Lab_6/output.txt", "wt");

    int K, N;
    fscanf(fr, "%d", &K);
    fscanf(fr, "%d", &N);

    struct Voyage *voyages = (struct Voyage *) malloc(N * sizeof(struct Voyage));

    read(fr, voyages, N);
    sort(voyages, N);

    write(fw, voyages, K);

    fclose(fw);
    fclose(fr);
    return 0;
}