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

typedef struct Node {
    char song[101];
    struct Node* next;
    struct Node* prev;
} Node;

Node* head = NULL;
Node* tail = NULL;

// Utility: Check if a string contains only letters
int isValidString(const char* str) {
    for (int i = 0; str[i]; i++) {
        if (!isalpha(str[i])) {
            return 0;
        }
    }
    return 1;
}

// Insert song into the playlist
void insertSong(char* song) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode->song, song);
    newNode->next = NULL;
    newNode->prev = tail;

    if (tail) {
        tail->next = newNode;
    }
    tail = newNode;

    if (!head) {
        head = newNode;
    }
}

// Print songs starting with the prefix, return 1 if any printed, else 0
int printSongsWithPrefix(const char* prefix) {
    int len = strlen(prefix);
    Node* curr = head;
    int found = 0;

    while (curr) {
        if (strncmp(curr->song, prefix, len) == 0) {
            printf("%s\n", curr->song);
            found = 1;
        }
        curr = curr->next;
    }
    return found;
}

int main() {
    int n;
    scanf("%d", &n);
    getchar(); // consume newline after number input

    char song[101];
    for (int i = 0; i < n; i++) {
        fgets(song, sizeof(song), stdin);
        // Remove trailing newline if exists
        size_t len = strlen(song);
        if (len > 0 && song[len - 1] == '\n') {
            song[len - 1] = '\0';
        }

        if (!isValidString(song)) {
            printf("Invalid input\n");
            return 0;
        }
        insertSong(song);
    }

    char prefix[101];
    fgets(prefix, sizeof(prefix), stdin);
    size_t len = strlen(prefix);
    if (len > 0 && prefix[len - 1] == '\n') {
        prefix[len - 1] = '\0';
    }

    if (!isValidString(prefix)) {
        printf("Invalid input\n");
        return 0;
    }

    if (!printSongsWithPrefix(prefix)) {
        printf("No song found\n");
    }

    // Free memory
    Node* current = head;
    while (current) {
        Node* next = current*