#include <set>
#include <cstdio>

using namespace std;

/* Global Constants */
// gNUMBER_OF_GAMES cannot be bigger than 6
const int gNUMBER_OF_GAMES = 5;
const int gGRID_SIZE = gNUMBER_OF_GAMES * gNUMBER_OF_GAMES;
const int gNUMBER_OF_PLAYERS = 2*gNUMBER_OF_GAMES;
const int gNUMBER_OF_PRIME_PRODUCTS = (gNUMBER_OF_PLAYERS * (gNUMBER_OF_PLAYERS - 1)) / 2;

/* Function prototypes */
void decompose_prime(int num, int primeList[]);
bool check_row(int myRow[]);
bool check_grid(int myGrid[]);
void print_grid(int myGrid[]);
bool fill_grid(int myGrid[],int prodPrimes[]);

int main()
{
    int grid[gGRID_SIZE] = {0};

    const int myPrimes[] = {2,3,5,7,11,13,17,19,23,29,31,37};

    // Create an array of all products of primes.
    int prodPrimes[gNUMBER_OF_PRIME_PRODUCTS];
    int ctr = 0;
    for (int i=0;i<gNUMBER_OF_PLAYERS-1;i++)
    {
        for (int j=i+1;j<gNUMBER_OF_PLAYERS;j++)
        {
            // Fill in the 'ctr' slot with primes[i]*primes[j]
            prodPrimes[ctr++] = myPrimes[i]*myPrimes[j];
        }
    }

    if (fill_grid(grid,prodPrimes))
        print_grid(grid);
    else
        printf("No solution found!\n");

    return 0;
}

/* Sub-function definitions */

void decompose_prime(int num, int primeList[])
{
    /*
    Decompose an int into primes
    This only works in our special case where
    num is the prod of two primes, each <= 37.
    */

    static const int myPrimes[] = {2,3,5,7,11,13,17,19,23,29,31,37};

    if (num == 0)
    {
        primeList[0] = 0;
        primeList[1] = 0;
        return;
    }
    for (int i=0;i<gNUMBER_OF_PLAYERS;i++)
    {
        if (num % myPrimes[i] == 0)
        {
            primeList[0] = myPrimes[i];
            primeList[1] = num/myPrimes[i];
            return;
        }
    }
}

bool check_row(int myRow[])
{
    /*
    Check a row of a grid -- specifically, gNUMBER_OF_GAMES values
    We need to make sure no prime factor is shared.
    */
    static int twoPrimes[2] = {0,0};
    set<int> usedPrimes;
    for (int k=0;k<gNUMBER_OF_GAMES;k++)
    {
        if (myRow[k] == 0)
            continue;
        decompose_prime(myRow[k], twoPrimes);
        // See if the primes are in `usedPrimes`
        for (int j=0;j<2;j++)
        {
            if (usedPrimes.find(twoPrimes[j]) != usedPrimes.end())
                return false;
            else
                usedPrimes.insert(twoPrimes[j]);
        }
    }
    return true;
}

bool check_grid(int myGrid[])
{
    /* Check to make sure a given grid is okay (so far) */

    // First check: no two elements of the grid should be the same.
    set<int> gridElements;
    for (int i=0;i<gGRID_SIZE;i++)
    {
        if (myGrid[i] == 0)
            continue;
        if (gridElements.find(myGrid[i]) != gridElements.end())
            return false;
        else
            gridElements.insert(myGrid[i]);
    }

    // Go through each row
    for (int i=0;i<gNUMBER_OF_GAMES;i++)
    {
        int* p_row = &myGrid[gNUMBER_OF_GAMES*i];
        if (!check_row(p_row))
            return false;
    }

    // Go through each column
    int col[gNUMBER_OF_GAMES] = {0};
    for (int j=0;j<gNUMBER_OF_GAMES;j++)
    {
        for (int i=0;i<gNUMBER_OF_GAMES;i++)
            col[i] = myGrid[gNUMBER_OF_GAMES*i+j];
        if (!check_row(col))
            return false;
    }
    return true;
}

void print_grid(int myGrid[])
{
    static int primeList[2] = {0,0};
    for (int i=0;i<gNUMBER_OF_GAMES;i++)
    {
        for (int j=0;j<gNUMBER_OF_GAMES;j++)
        {
            decompose_prime(myGrid[gNUMBER_OF_GAMES*i+j], primeList);
            printf("[%2i,%2i] ",primeList[0],primeList[1]);
        }
        printf("\n");
    }
    printf("-----\n");
}

bool fill_grid(int myGrid[],int prodPrimes[])
{
    int gridCtr,prodCtr = 0;
    while (gridCtr < gGRID_SIZE && gridCtr >= 0)
    {
        while (prodCtr < gNUMBER_OF_PRIME_PRODUCTS)
        {
            myGrid[gridCtr] = prodPrimes[prodCtr];
            if (check_grid(myGrid))
            {
                // Restart the process with greater gridCtr & prodCtr = 0
                gridCtr++;
                prodCtr = 0;
                break; // break out of the inner while loop
            }
            else
                prodCtr++;
        }
        /*
        If we can't find an acceptable match above, we have to delete the
        last entry and try again from the step before.
        Find the previous prodCtr from myGrid[gridCtr-1]
        */

        // Check that the above while loop gave nothing
        if (prodCtr == gNUMBER_OF_PRIME_PRODUCTS)
        {
            // We need to set myGrid[gridCtr] and myGrid[gridCtr-1] to 0;
            myGrid[gridCtr--] = 0;
            for (int i=0;i<gNUMBER_OF_PRIME_PRODUCTS;i++)
            {
                if (myGrid[gridCtr] == prodPrimes[i])
                {
                    prodCtr = i+1;
                    myGrid[gridCtr] = 0;
                    break; // break out of the for loop
                }
            }
        }
    }
    if (gridCtr == gGRID_SIZE)
        return true;
    return false;
}