// Gomoku - Eryk Kopczynski

// Idea strategii:
// ---------------

// Kazde pole na planszy jest elementem (co najwyzej) 20 linii (piatek):
// w kazdym z czterech dostepnych kierunkow mamy 5 mozliwych piatek.
// Przykladowo, na ponizszym rysunku:

// ..........................
// ..........................
// ..........................
// ..........................
// .......XOOOd.......O.O.X..
// ....................XXO...
// ..XXc..............OXeOX..
// ....X...............XOO...
// ....X........ba....O.X.X..
// ............O.............
// ..........................
// ..........................
// ..........................
// ..........................
// (pola a,b,c,d,e sa puste)

// - Pole "a" nalezy do 20 calkowicie pustych linii;
// - Pole "b" nalezy do 16 calkowicie pustych linii i 4 linii z
//   pojedynczym kolkiem;
// - Pole "c" nalezy do 12 pustych linii, 2 linii z pojedynczym X, i 
//   6 linii z podwojnym X;
// - Pole "d" nalezy do 15 pustych linii, po jednej linii z pojedynczym,
//   podwojnym i potrojnym O, 1 linii z pojedynczym X, i 1 linii
//   z trzema O i jednym X;
// - Pole "e" nalezy do 20 linii, na kazdej z nich sa i X, i O.

// Idea jest taka: stawiamy nasz pionek na puste pole majace najwieksza
// wartosc; wartoscia pola jest suma wartosci wszystkich 20 linii
// przechodzacych przez to pole. Wartosc linii zalezy od jej zawartosci.

// Linie zawierajace pionki obu graczy sa bezwartosciowe. Nie ma szans, by
// ktoremus z graczy udalo sie tam utworzyc linie.

// Linie calkowicie puste maja bardzo niska wartosc.

// Linie, na ktorych sa juz 4 nasze pionki, maja dominujaca wartosc.
// Zawsze bedziemy wstawiac tam pionek, jesli jest taka linia.

// Linie, na ktorych sa juz 4 pionki przeciwnika, maja mniejsza wartosc,
// ale rowniez dominujaca w stosunku do pozostalych. Zawsze bedziemy tam
// stawiac pionek, chyba, ze zachodzi poprzednia sytuacja.

// Pozostale pola maja tym wieksza wartosc, im wiecej pionkow tam sie 
// znajduje (i zalezna od tego, czyje sa to pionki).

// W naszym przykladzie:

// Pole "e" ma wartosc zerowa, nie ma po co cos tam stawiac.

// Ruch na pole "b" ma wartosc dosyc niska, ale wyzsza niz ruch na pole
// "a". Oznacza to, ze na poczatku gry gracze beda woleli sie ruszac
// tam, gdzie cos juz sie dzieje w bezposrednim sasiedztwie.

// Ruch na pole "d" ma wprawdzie wysoka wartosc ze wzgledu na obecnosc
// linii z trzema kolkami, ale za to ruch na pole "c" ma az szesc linii
// z dwoma krzyzykami. Lepszym ruchem dla X w tej sytuacji jest ruch na
// pole "c" (jak wiadomo doswiadczonym graczom); wartosc linii XX
// w stosunku do OOO powinna odzwierciedlac ten wybor --- byc wprawdzie
// nizsza, ale na tyle duza, by 5 XX bylo lepsze niz jedno OOO. Gdyby w
// okolicy pola "d" byly natomiast jeszcze jakies inne kolka, byc moze
// ruch wlasnie tam mialby wieksza wartosc. (Jesli by tam byly krzyzyki,
// to tez... ale przypuszczalnie gracz O musialby wowczas zareagowac na
// nowo wytworzone zagrozenia, wiec pole "c" nie zostaloby zepsute).

// Jak dobrac najlepsze wartosci linii? Nie wiadomo... Tutaj zostalo to
// zrobione przy uzyciu algorytmu genetycznego, czyli symulacji doboru
// naturalnego. W skrocie oznacza to, ze programy majace rozne wartosci
// tych parametrow bija sie ze soba, i najlepsze przezywaja do nastepnej
// rundy, przy okazji krzyzujac sie ze soba i mutujac.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

typedef long double ld;

// Pole o wspolrzednych (x,y) jest reprezentowane jako board[(3+x)+23*(3+y)].
// Mozliwe wartosci board[pos] sa nastepujace:

//  0 = puste pole
//  1 = pionek nasz (zazwyczaj)
//  5 = pionek przeciwnika
// 25 = straznik

// Straznicy to elementy tablicy nie odpowiadajace zadnemu polu od (1,1)
// do (15,15); linie wychodzace poza plansze rowniez liczymy, ale maja one
// wartosc 0 --- upraszcza to implementacje.

// Dlaczego nie 0,1,2,3? Zeby z sumy wartosci pol na linii (i z faktu, ze
// co najmniej jedno pole na linii jest puste) mozna bylo jednoznacznie
// wywnioskowac, jakie wartosci sumujemy.

int board[529];

struct player {

  // Parametry okreslajace strategie gracza (genom).
  ld q[7];

  // Wartosc ruchu dla kazdej sumy linii.
  ld delta[125];
  
  // [Algorytm genetyczny] Liczba punktow zdobyta w turnieju.
  int score;
  
  // Ustalanie tablicy delta. 
  void setDelta() {
    for(int k=0; k<125; k++) delta[k] = 0;
    
    delta[4] = 10000;   delta[20] = 1;
    delta[3] = q[0];  delta[15] = q[4];
    delta[2] = delta[3] * q[1];  delta[10] = delta[15] * q[5];
    delta[1] = delta[2] * q[2];  delta[5]  = delta[10] * q[6];
    delta[0] = (delta[1]+delta[5]) * q[3];
    
    // Dla wszystkich pozostalych 0
    }

  // Odwrocenie roli, czyli szukanie najlepszego ruchu dla gracza "5", nie
  // dla gracza "1".
  void revRole() {
    swap(delta[1], delta[5]);
    swap(delta[2], delta[10]);
    swap(delta[3], delta[15]);
    swap(delta[4], delta[20]);
    }
  
  // Suma wartosci delta dla wszystkich linii przechodzacych przez dane pole.
  ld deltaAt(int pos) {
    ld r = 0;
    // Kierunki: 1 = poziomo, 23 = pionowo, 22, 24 = ukosnie
    // (roznica numerow pola na sasiednich polach linii)
    int p[4] = {1,22,23,24};
    // w kazdym kierunku ogladamy 5 linii...
    for(int k=0; k<4; k++) {
      int P = p[k];
      int v = board[pos-4*P] + board[pos-3*P] + board[pos-2*P] + board[pos-P];
      r += delta[v];
      v += board[pos+  P] - board[pos-4*P];
      r += delta[v];
      v += board[pos+2*P] - board[pos-3*P];
      r += delta[v];
      v += board[pos+3*P] - board[pos-2*P];
      r += delta[v];
      v += board[pos+4*P] - board[pos-1*P];
      r += delta[v];
      }
    return r;
    }

  int bm;
  
  ld max() {
    // Wybieramy puste pole z najwieksza wartoscia deltaAt.
    // Jesli kilka pol ma ta sama wartosc, to wybieramy losowo.
    int qbm = 0;
    ld res = -1;
    for(int k=0; k<529; k++) if(board[k] == 0) {
      ld d = deltaAt(k);      
      if(d >= res) {
        if(d > res) {qbm = 0; res = d;}
        qbm++;
        if(rand() % qbm == 0) bm = k;
        }
      }
    return res;
    }

  };

// Poczatkowe czyszczenie planszy.
void clearBoard() {
  for(int y=1; y<=15; y++) for(int x=1; x<=15; x++)
    board[(3+x)+23*(3+y)] = 0;
  }

// "Optymalne" wartosci parametrow gracza (znalezione przy uzyciu algorytmu
// genetycznego).
ld bestq[7] = 
  {0.3355044,0.1991849,0.3135847,0.1029193,0.1890494,0.1967362,0.1022812};

void genetic();

int main() {

  srand(time(NULL));

  // straznicy...
  for(int pos=0; pos<529; pos++) board[pos] = 25;

  clearBoard();

  // odkomentuj, jesli chcesz uruchomic AG
  // genetic(); return 0;

  int first;
  int left;

  player P;
  for(int k=0; k<7; k++) P.q[k] = bestq[k];
  P.setDelta();

  scanf("%d%d", &first, &left);
  if(first) goto move;
  
  // petla gry...
  while(true) {

    int ex, ey;
    scanf("%d%d%d", &ex, &ey, &left);
    board[(3+ex)+23*(3+ey)] = 5;

    move:    
    P.max(); board[P.bm] = 1;
    printf("%d %d\n", (P.bm%23)-3, (P.bm/23)-3);
    fflush(stdout);
    }
  }

// ALGORYTM GENETYCZNY

// (Implementacja i parametry AG uzyte do znalezienia tablicy bestq,
// ktora zostala uzyta na konkursie, zmieniala sie w trakcie jej
// poszukiwania. W rzeczywistosci bylo wiecej pokolen i wielkosc populacji
// byla wieksza. Trudno wiec to nazwac oryginalnym AG z konkursu,
// ale idea jest wlasnie taka.)

#define POOL    10 // wielkosc populacji
#define SURV     5 // ile przezywa, a ile zostaje zastapionych
#define TURNS  100 // liczba pokolen

#define ROUNDS   1 // tyle razy dana para (uporzadkowana) graczy ze soba gra

#define TABELA   0 // czy wypisywac turniej
#define PLANSZA  0 // czy pokazac plansze
#define WYNIKI   1 // czy pisac wyniki kazdego pokolenia
#define WYPPAR   1 // czy wypisywac parametry najlepszego gracza

// populacja
player ppool[POOL];

// przeprowadzenie meczu miedzy ppool[p] a ppool[q]
int play(int p, int q) {
  clearBoard();
  ppool[q].revRole(); // q gra piatkami, nie jedynkami
  int moves = 0;
  int res = 0;
  while(moves < 225) {
    ld sc;
    sc = ppool[p].max();
    board[ppool[p].bm] = 1;
    if(sc >= 5000) {
      res = 1;
      break;
      }
    sc = ppool[q].max();
    board[ppool[q].bm] = 5;
    if(sc >= 5000) {
      res = 2;
      break;
      }
    moves++;
    }

  // dajemy punkty w zaleznosci od wyniku meczu...
  if(res == 0) { 
    ppool[p].score++; ppool[q].score++;
    }
  if(res == 1) { 
    ppool[p].score+=4;
    }
  if(res == 2) { 
    ppool[q].score+=4;
    }
  ppool[q].revRole(); // odwracamy z powrotem
  return res;
  }

// przeprowadzenie turnieju (wyniki => ppool[p].score)
void turniej() {
  for(int r=0; r<ROUNDS; r++)
  for(int p=0; p<POOL; p++) for(int q=0; q<POOL; q++) {
    if(p==q) {
      if(TABELA) printf("\\");
      continue;
      // nie robimy takiego meczu
      }
    int res = play(p, q);
    if(TABELA) printf("%d", res);
    if(TABELA) if(q+1 == POOL) printf("\n");
    
    if(PLANSZA) {
      for(int y=0; y<15; y++) {
        for(int x=0; x<15; x++) {
          printf("%d", board[(4+x)+23*(4+y)]);
          }
        printf("\n");
        }
      }
    }
  }

void genetic() {

  // poczatkowo populacja jest losowa
  for(int p=0; p<POOL; p++) for(int q=0; q<7; q++)
    ppool[p].q[q] = (rand() % 1000000) / 1000000.0;
  
  for(int t=0; t<TURNS; t++) {
    // inicjalizujemy kazdego gracza...
    for(int p=0; p<POOL; p++) ppool[p].setDelta();
    for(int p=0; p<POOL; p++) ppool[p].score = 0;
    
    turniej();

    // wypisanie wynikow
    if(WYNIKI) {
      printf("Turn %d:", t);
      for(int p=0; p<POOL; p++) printf("%4d", ppool[p].score);
      printf("\n");
      }
    
    // sortowanie populacji po wyniku turnieju
    // (czas n^2, ale to bez znaczenia)
    for(int p=0; p<POOL; p++) for(int q=0; q<p; q++) {
      if(ppool[q].score < ppool[p].score) {
        swap(ppool[p].score, ppool[q].score);
        for(int r=0; r<7; r++) swap(ppool[p].q[r], ppool[q].q[r]);
        }
      }

    // wypisanie genomu najlepszego gracza
    if(WYPPAR) {
      printf("%6d", t+1);
      for(int q=0; q<7; q++) printf("%10.7Lf", ppool[0].q[q]);
      printf("\n");
      }
    
    // wszystkich, ktorzy zajeli miejsca dalsze niz SURV, zamieniamy
    // na krzyzowki pozostalych...
    for(int p=SURV; p<POOL; p++) {
      int p0 = rand() % SURV; // ojciec
      int p1 = rand() % SURV; // matka
      for(int q=0; q<7; q++) {
        ppool[p].q[q] = (ppool[p0].q[q] + ppool[p1].q[q]) / 2;
        ppool[p].q[q] += (rand() % 100000) / 1000000.0;
        ppool[p].q[q] -= (rand() % 100000) / 1000000.0;
        }
      }
    
    // no i nastepna kolejka....
    }

  // wypisujemy ostatecznych zwyciezcow
  printf("******");
  for(int q=0; q<7; q++) printf("%10.7Lf", ppool[0].q[q]);
  printf("\n");  
  }