public enum State {
    X, O, EMPTY;
}

public class Player {

    private final String id;
    private final String name;
    private final State move;

    public Player(String name, State move) {
        this.id = UUID.randomUUID().toString();
        this.name = name;
        this.move = move;
    }

    public String getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    public State getMove() {
        return move;
    }
}

public class Cell {
    private final int i;
    private final int j;

    public Cell(int i, int j) {
        this.i = i;
        this.j = j;
    }

    public int getI() {
        return i;
    }

    public int getJ() {
        return j;
    }
}

public class Board {

    private static final int DEFAULT_SIZE = 3;

    private final int size;
    private List<List<State>> matrix;

    public Board(int size) {
        this.size = size;
        this.matrix = new ArrayList<>();
        for(int i=0; i<size; i++) {
            List<State> row = new ArrayList<>();
            for(int j=0; j<size; j++) {
                row.add(State.EMPTY);
            }
            this.matrix.add(row);
        }
    }

    public Board() {
        this(DEFAULT_SIZE);
    }

    public int getSize() {
        return size;
    }

    private boolean isCellEmpty(Cell cell) {
        return State.EMPTY.equals(matrix.get(cell.getI()).get(cell.getJ()));
    }

    public boolean isCellValid(Cell cell) {
        return cell.getI() >= 0 && cell.getJ() >= 0 && cell.getI() < size && cell.getJ() < size && isCellEmpty(cell);
    }

    public boolean isBoardFilled() {
        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) {
                if(State.EMPTY.equals(matrix.get(i).get(j))) {
                    return false;
                }
            }
        }
        return true;
    }

    public void addCell(Cell cell, State move) {
        matrix.get(cell.getI()).set(cell.getJ(), move);
    }

    public boolean checkCellState(Cell cell, State state) {
        return state.equals(matrix.get(cell.getI()).get(cell.getJ()));
    }

    public void print() {
        System.out.println();
        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) {
                String cellValue = State.EMPTY.equals(matrix.get(i).get(j)) ? "_" : matrix.get(i).get(j).name();
                System.out.print(cellValue + " ");
            }
            System.out.println();
        }
    }

}

public class GameService {

    private final Board board;
    private final Queue<Player> players;

    public GameService(Board board, List<Player> playerList) {
        this.board = board;
        this.players = new LinkedList<>();
        players.addAll(playerList);
    }

    public void startGame() {
        Scanner sc = new Scanner(System.in);
        while(!board.isBoardFilled()) {
            board.print();
            Player player = players.peek();
            System.out.println("Player " + player.getName() + ", It's your turn");
            String input = sc.nextLine();
            String[] s = input.split(" ");
            if("EXIT".equalsIgnoreCase(s[0])) {
                break;
            }
            int i = Integer.parseInt(s[0]);
            int j = Integer.parseInt(s[1]);
            Cell cell = new Cell(i-1, j-1);
            if(board.isCellValid(cell)) {
                players.remove();
                board.addCell(cell, player.getMove());
                boolean playerWon = checkIfPlayerWon(player.getMove());
                if(playerWon) {
                    System.out.println(player.getName() + " won the game");
                    break;
                }
                else {
                    players.add(player);
                }
            }
            else {
                System.out.println("Invalid Move");
            }
        }
        if(board.isBoardFilled()) {
            System.out.println("Game Over");
        }
    }

    private boolean checkIfPlayerWon(State move) {
        int size = board.getSize();
        boolean  isMajorDiagonalFilled = true, isMinorDiagonalFilled = true;
        for(int i=0; i<size; i++) {
            boolean isRowFilled = true, isColFilled = true;
            for(int j=0; j<size; j++) {
                if(!board.checkCellState(new Cell(i, j), move)) {
                    isRowFilled = false;
                }
                if(!board.checkCellState(new Cell(j, i), move)) {
                    isColFilled = false;
                }
            }
            if(isRowFilled || isColFilled) {
                return true;
            }
            if(!board.checkCellState(new Cell(i, i), move)) {
                isMajorDiagonalFilled = false;
            }
            if(!board.checkCellState(new Cell(i, size - 1 - i), move)) {
                isMinorDiagonalFilled = false;
            }
        }
        return isMajorDiagonalFilled || isMinorDiagonalFilled;
    }

}

public class TicTacToeApplication {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Player> playerList = new ArrayList<>();

        System.out.println("Enter the name of players");
        for(int i=0; i<2; i++) {
            String input = sc.nextLine();
            String[] s = input.split(" ");
            playerList.add(new Player(s[1], State.valueOf(s[0])));
        }

        Board board = new Board();
        GameService gameService = new GameService(board, playerList);
        gameService.startGame();
    }
}