// Arup Guha
// 4/9/2026
// COP 3502 Example Hash Table Code (Linear Chaining Hashing Technique)
// Solution to Kattis Problem: Shiritori
// https://open.kattis.com/problems/shiritori

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

#define MAXSIZE 1000003
#define MAXSTRSIZE 121

typedef struct node {
    char* word;
    struct node* next;
} node;

typedef struct hashtable {
    node** list;
    int size;
} hashtable;

int hashfunction1(char* word, int tablesize);
int hashfunction2(char* word, int tablesize);
void insert(hashtable* ptrTable, char* word);
int search(hashtable* ptrTable, char* word);
hashtable* getNewTable(int realsize);
void freemem(hashtable* ptr);
int searchList(node* list, char* item);
node* insertFront(node* list, char* item);
void freelist(node* ptr);

int main() {

    // Get # of moves.
    int n;
    scanf("%d", &n);

    // Generate table.
    hashtable* mine = getNewTable(MAXSIZE);
    int loser = -1;
    char prev = 'a';

    // Go through the game turns.
    for (int i=0; i<n; i++) {

        char tmp[MAXSTRSIZE];
        scanf("%s", tmp);

        // Covers both ways to lose.
        if  ((i != 0 && tmp[0] != prev) || (search(mine, tmp)) ) {

            // Easier this way for me.
            if (i%2 == 0)   loser = 1;
            else            loser = 2;

            break;
        }

        // Add to table and update last letter of previous word.
        insert(mine, tmp);
        prev = tmp[strlen(tmp)-1];
    }

    // Ta da!
    if (loser == -1)
        printf("Fair Game\n");
    else
        printf("Player %d lost\n", loser);

    freemem(mine);

    return 0;
}

// word[0]*27^(n-1) + word[1]*27^(n-2)+...word[strlen(word)-1]
// where word[i] is the 1-26 value of the letter.
int hashfunction1(char* word, int tablesize) {

    int len = strlen(word);

    int res = 0;
    for (int i=0; i<len; i++) {
        res = (27*res + word[i]-'a'+1)%tablesize;
    }
    return res;
}

// Works other way around (first letter is 27^0, second is 27^1, etc.)
int hashfunction2(char* word, int tablesize) {

    int len = strlen(word);

    // Will always equal 27 to the i power when used in the for loop.
    int pow27 = 1;

    // Stores hash value.
    int res = 0;

    // Build up answer.
    for (int i=0; i<len; i++) {

        // Add in hash value for this letter.
        res = (res + pow27*(word[i]-'a'+1))%tablesize;

        // Update power of 27 for next loop iteration.
        pow27 = (pow27*27)%tablesize;
    }
}

// Returns a pointer to a newly created empty hashtable with array size realsize.
hashtable* getNewTable(int realsize) {

    // Allocate pointer and array.
    hashtable* ptr = malloc(sizeof(hashtable));
    ptr->list = calloc(realsize, sizeof(node*));

    // Set all lists to NULL.
    for (int i=0; i<realsize; i++)
        ptr->list[i] = NULL;

    // Set size.
    ptr->size = realsize;

    // Return ptr to struct.
    return ptr;
}

// Frees memory for table.
void freemem(hashtable* ptr) {
    for (int i=0; i<ptr->size; i++)
        if (ptr->list[i] != NULL)
            freelist(ptr->list[i]);
    free(ptr);
}

// Frees all the memory associated with the linked list pointed to by ptr.
void freelist(node* ptr) {
    if (ptr == NULL) return;
    freelist(ptr->next);
    free(ptr);
}

// Inserts word into the table pointed to by ptrTable.
void insert(hashtable* ptrTable, char* word) {

    // Find where to put this string.
    int idx = hashfunction1(word, ptrTable->size);

    // Insert string into the appropriate linked list.
    ptrTable->list[idx] = insertFront(ptrTable->list[idx], word);
}

// Inserts a new node storing item to the front of the linked list pointed to by list.
node* insertFront(node* list, char* item) {

    // Make a new node, allocate space for string, copy it.
    node* newFront = malloc(sizeof(node));
    newFront->word = calloc(strlen(item)+1, sizeof(char));
    strcpy(newFront->word, item);

    // Link to rest of list and return new front.
    newFront->next = list;
    return newFront;
}

// Returns 1 iff word is stored in the table pointed to by ptrTable.
int search(hashtable* ptrTable, char* word) {

    // Find which list we need to look in.
    int idx = hashfunction1(word, ptrTable->size);

    // Go look for it.
    return searchList(ptrTable->list[idx], word);
}

// Returns 1 iff item is in the linked list pointed to by list.
int searchList(node* list, char* item) {

    // Just doing a regular linear iterative search.
    while (list != NULL) {
        if (!strcmp(list->word, item))
            return 1;
        list = list->next;
    }

    // Never found it.
    return 0;
}