import java.util.Scanner;

public class TrominoTiling {
    private static String[][] board;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Please enter size of board (need to be 2^n and 0 to quit):");
        int boardSize = scanner.nextInt();

        if (boardSize == 0) {
            System.out.println("Quitting…");
            return;
        }

        if ((boardSize & (boardSize - 1)) != 0) {
            System.out.println("Invalid board size. The size must be a power of 2.");
            return;
        }

        board = new String[boardSize][boardSize];

        System.out.println("Please enter coordinates of missing square (separated by a space):");
        int x_missing = scanner.nextInt();
        int y_missing = scanner.nextInt();

        // Initialize the board
        for (int i = 0; i < boardSize; i++) {
            for (int j = 0; j < boardSize; j++) {
                board[i][j] = "UR"; // Default fill
            }
        }

        // Mark the initial missing square
        board[y_missing][x_missing] = "MS";

        // Fill the board with trominoes
        fillBoard(0, 0, boardSize, x_missing, y_missing);

        // Print the tiled board
        for (String[] row : board) {
            for (String cell : row) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
    }

    private static void fillBoard(int row, int col, int size, int missingRow, int missingCol) {
        if (size == 2) {
            // Fill in the 2x2 section
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    if (board[row + i][col + j].equals("UR")) { // Replace default fill except for the missing square
                        if (row + i != missingRow || col + j != missingCol) {
                            board[row + i][col + j] = size == 2 ? "UR" : "MS"; // Fill with UR for the smallest section
                        }
                    }
                }
            }
            return;
        }

        int halfSize = size / 2;
        int centerX = col + halfSize;
        int centerY = row + halfSize;

        // Determine which section has the missing square
        int newMissingRow = missingRow < centerY ? row : centerY;
        int newMissingCol = missingCol < centerX ? col : centerX;

        if (missingRow < centerY && missingCol < centerX) { // Top-left
            fillBoard(row, col, halfSize, missingRow, missingCol); // Actual missing square
        } else {
            board[centerY - 1][centerX - 1] = "MS"; // Virtual missing square
            fillBoard(row, col, halfSize, centerY - 1, centerX - 1);
        }

        if (missingRow < centerY && missingCol >= centerX) { // Top-right
            fillBoard(row, centerX, halfSize, missingRow, missingCol); // Actual missing square
        } else {
            board[centerY - 1][centerX] = "MS"; // Virtual missing square
            fillBoard(row, centerX, halfSize, centerY - 1, centerX);
        }

        if (missingRow >= centerY && missingCol < centerX) { // Bottom-left
            fillBoard(centerY, col, halfSize, missingRow, missingCol); // Actual missing square
        } else {
            board[centerY][centerX - 1] = "MS"; // Virtual missing square
            fillBoard(centerY, col, halfSize, centerY, centerX - 1);
        }

        if (missingRow >= centerY && missingCol >= centerX) { // Bottom-right
            fillBoard(centerY, centerX, halfSize, missingRow, missingCol); // Actual missing square
        } else {
            board[centerY][centerX] = "MS"; // Virtual missing square
            fillBoard(centerY, centerX, halfSize, centerY, centerX);
        }

        // Post fill adjustments if needed for UR, LL, LR etc.
        // This could include additional logic to convert the virtual "MS" markers into actual tromino labels
        // depending on the exact requirements for visually distinguishing the trominos beyond just the "UR" label.
    }

} the output that i got is Please enter size of board (need to be 2^n and 0 to quit):
2
Please enter coordinates of missing square (separated by a space):
0 0
MS UR
UR UR
 
Please enter size of board (need to be 2^n and 0 to quit):
4
Please enter coordinates of missing square (separated by a space):
1 3
UR UR UR UR
UR MS UR UR
UR MS MS UR
UR MS UR UR . The expected output is Please enter size of board (need to be 2^n and 0 to quit): 2
Please enter coordinates of missing square (seperated by a space): 0 0
UR UR 
MS UR 
Please enter size of board (need to be 2^n and 0 to quit): 4
Please enter coordinates of missing square (seperated by a space): 1 3
LL MS UR UR 
LL LL LR UR 
LL LR LR LR 
LL LL LR LR Make the necessary changes to the code to get the expected output