// Arup Guha
// 4/9/2026
// COP 3502 Example Hash Table Code (Linear Probing 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 hashtable {
    char** table;
    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 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 struct, array.
    hashtable* ptr = malloc(sizeof(hashtable));
    ptr->table = calloc(realsize, sizeof(char*));

    // Set pointers to null.
    for (int i=0; i<realsize; i++)
        ptr->table[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->table[i] != NULL)
            free(ptr->table[i]);
    free(ptr);
}

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

    int idx = hashfunction1(word, ptrTable->size);

    // This is linear probing.
    while (ptrTable->table[idx] != NULL)
        idx = (idx+1)%ptrTable->size;

    // Copy in the string to the right place.
    ptrTable->table[idx] = calloc(strlen(word)+1, sizeof(char));
    strcpy(ptrTable->table[idx], word);
}

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

    int idx = hashfunction1(word, ptrTable->size);

    // Keep looking until a blank.
    while (ptrTable->table[idx] != NULL) {

        // Woo hoo! Found it!
        if (!strcmp(ptrTable->table[idx], word))
            return 1;

        // Go to next.
        idx = (idx+1)%ptrTable->size;
    }

    // If we get here, it's not in the table.
    return 0;
}