#include <QCoreApplication>  
#include <bits/stdc++.h> 

using namespace std;  

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

// The question is to complete 
// * Class TicTacToe and 
// * Function vector<int> playTicTacToe(TicTacToe& game, vector<vector<int>> moves) 
// * Headers and the int main() code already provided

class TicTacToe {
 public:

  /// \brief MakeMove Interface for the game playing system to add a new move to
  /// the game.
  /// \param player   Player making this move.
  /// \param location The selected location on the board.
  /// \return Result of the move, including the new game status such as Win, Invalid, etc.
  ///
  //Result MakeMove(Player player, Location location);
  
  
  TicTacToe(int boardSize, int numberPlayers) {
      N = boardSize ;
      M = numberPlayers ;
 }

  int get_boardSize(){  return N;   }
  int get_numberPlayers(){  return M;  }

  vector<vector<int>> Init_grid() {
      board.resize(N);
      for(int i = 0; i < N; i++) {
           board[i].resize(N);
           for (int j = 0; j < N; j++) {
              board[i][j] = 0;
            }
      }
      return board;
}

void update_grid(vector<int>move){
      int value = move[0];
      int row = move[1];
      int col = move[2];
      board[row][col] = value;
}

  vector<int> set_players(){
      static vector<int> players(M);
      for(int k=0; k<M; k++){
          players[k] = k+1;
      }
	  return players;
  }

 bool isValid(vector<int> move, int num_player){
      bool result ;
      if(move[0] == num_player && (move[1] <= N) && (move[2] <= N) && (move[1]>=0) && (move[2] >=0))
      {
          result = true;
      }
      else {
          result = false;
      }
      return result;
  }

  bool check_Win(vector<int> move){
      bool win = true;
      int value = move[0]; int row = move[1];  int col = move[2];

// check rows
      for(int i = 0; i<N ; i++){
          if(board[row][i] != move[0]){
               win = false;
               break;
          }
      }

      if(win == true){  return 1;   }
	  
// check cols
      win=true;

      for(int j =0; j<N ; j++){
          if(board[j][col] != move[0]){
                  win = false;
                  break;
          }
      }

      if(win == true){ return 1;  }

      win=true;
 // check left to right diag  && right to left diag
      for(int i=0; i <N ; i++){
          if(board[i][i] != move[0]){
                      win = false ;
                      break;
          }
      }

      if(win == true){ return 1;  }
      win=true;
      for(int i=0; i <N ; i++){
          if(board[i][N-1-i] != move[0]){
                      win = false ;
                      break;
          }
      }

if(win == true)
    return 1;
else {
    return 0;
}
}

 private:
 
 /// Create a representation of the game state and any internal structures to help
  /// determine win conditions. The implementation should easily extend to different
  /// board sizes and run time should scale linearly (or better) with N.
  
  int N, M;
  vector<vector<int>> board;
};


vector<int> playTicTacToe(TicTacToe& game, vector<vector<int>> moves) {
    vector<int> result;

    vector<int> players = game.set_players();
    vector<vector<int>> board = game.Init_grid();
    int board_Size = game.get_boardSize();

    int turn = 0, num_play = 0;
     do{
        while(num_play< players.size()){
            if(game.isValid(moves[turn], players[num_play]))
                 {
                     game.update_grid(moves[turn]);
                     if(game.check_Win(moves[turn])==1)
                     {
                         result.push_back(players[num_play]);
                         return result;
                     }
                     else if((turn == ((board_Size*board_Size) -1)) && game.check_Win(moves[turn])== 0){
                         result.push_back(players[num_play+1]);
                         return result;
                     }
                     else if(game.check_Win(moves[turn])== 0){
                         result.push_back(0);
                         num_play++;
                         turn ++;
                         continue;
                     }
                 }
             else {
                 result.push_back(-1*moves[turn][0]);
                 return result;
             }
        }
        if(num_play >= (players.size()))
            num_play = 0;

       } while(game.check_Win(moves[turn])==0);
    return result ;
}


int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    ofstream fout(getenv("OUTPUT_PATH"));

        string boardSize_temp;
        getline(cin, boardSize_temp);

        int boardSize = stoi(ltrim(rtrim(boardSize_temp)));

        string numberPlayers_temp;
        getline(cin, numberPlayers_temp);

        int numberPlayers = stoi(ltrim(rtrim(numberPlayers_temp)));

        string moves_rows_temp;
        getline(cin, moves_rows_temp);

        int moves_rows = stoi(ltrim(rtrim(moves_rows_temp)));

        string moves_columns_temp;
        getline(cin, moves_columns_temp);

        int moves_columns = stoi(ltrim(rtrim(moves_columns_temp)));

        vector<vector<int>> moves(moves_rows);

        for (int i = 0; i < moves_rows; i++) {
            moves[i].resize(moves_columns);

            string moves_row_temp_temp;
            getline(cin, moves_row_temp_temp);

            vector<string> moves_row_temp = split(rtrim(moves_row_temp_temp));

            for (int j = 0; j < moves_columns; j++) {
                int moves_row_item = stoi(moves_row_temp[j]);

                moves[i][j] = moves_row_item;
            }
        }

        TicTacToe game(boardSize, numberPlayers);

        vector<int> result = playTicTacToe(game, moves);

        cout << "This is the result vector: " << endl;
        for(int n=0; n <result.size(); n++){
            cout << result[n] << " " ;
        }

        system("pause");

            for (int i = 0; i < result.size(); i++) {
                fout << result[i];

                if (i != result.size() - 1) {
                    fout << "\n";
                }
            }

            fout << "\n";

            fout.close();

            return 0;
        }

        string ltrim(const string &str) {
            string s(str);

            s.erase(
                s.begin(),
                find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
            );

            return s;
        }

        string rtrim(const string &str) {
            string s(str);

            s.erase(
                find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
                s.end()
            );

            return s;
        }

        vector<string> split(const string &str) {
            vector<string> tokens;

            string::size_type start = 0;
            string::size_type end = 0;

            while ((end = str.find(" ", start)) != string::npos) {
                tokens.push_back(str.substr(start, end - start));

                start = end + 1;
            }

            tokens.push_back(str.substr(start));

            return tokens;
        }