import java.util.*;
import java.util.concurrent.TimeUnit;

 class RectangleGridPermutations {
    private static List<String[][]> possiblePositioningStates = new ArrayList<>();
    private static Rectangle[] rectangles;
    private static String[][] grid;
    private static int gridWidth, gridHeight;
    private static int totalArea;

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        rectangles = new Rectangle[]{
                new Rectangle(2, 1, "A"),
                new Rectangle(2, 1, "B"),
                new Rectangle(3, 1, "C"),
                new Rectangle(3, 5, "D"),
                new Rectangle(4, 3, "E"),
                new Rectangle(4, 2, "F"),
                new Rectangle(7, 1, "G"),
                new Rectangle(7, 1, "H"),
                new Rectangle(1, 8, "I"),
                new Rectangle(8, 2, "J"),
                new Rectangle(3, 2, "K"),
//                new Rectangle(5, 2, "L"),
//                new Rectangle(8, 1, "M"),
        };

        Arrays.sort(rectangles, (r1, r2) -> Integer.compare(r2.space, r1.space));
        totalArea = calculateTotalArea(rectangles);
        gridWidth = rectangles[0].width;
        gridHeight = totalArea / gridWidth;
        grid = new String[gridHeight][gridWidth];

        List<Rectangle[]> permutations = generatePermutations(rectangles);
        for (Rectangle[] perm : permutations) {
            if (tryPermutation(perm)&(!possiblePositioningStates.contains(cloneGrid(grid)))) {
                possiblePositioningStates.add(cloneGrid(grid));
            }
        }

        if (possiblePositioningStates.isEmpty()) {
            System.out.println("No possible positioning states.");
        } else {
            System.out.println("Possible positioning states number: " + possiblePositioningStates.size());
//                        for (String[][] state : possiblePositioningStates) {
//                printGrid(state);
//                System.out.println();}
        }

        long endTime = System.nanoTime();
        System.out.println("Elapsed time: " + TimeUnit.NANOSECONDS.toMillis(endTime - startTime) / 1000 + "."
                + (TimeUnit.NANOSECONDS.toMillis(endTime - startTime) % 1000) + " seconds");
    }

    private static List<Rectangle[]> generatePermutations(Rectangle[] rectangles) {
        List<Rectangle[]> permutations = new ArrayList<>();
        permute(rectangles, 0, permutations);
        return permutations;
    }

    private static void permute(Rectangle[] arr, int k, List<Rectangle[]> result) {
        if (k == arr.length) {
            result.add(arr.clone());
        } else {
            for (int i = k; i < arr.length; i++) {
                swap(arr, i, k);
                permute(arr, k + 1, result);
                swap(arr, k, i);
            }
        }
    }

    private static void swap(Rectangle[] arr, int i, int j) {
        Rectangle temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static boolean tryPermutation(Rectangle[] rectangles) {
        grid = new String[gridHeight][gridWidth];
        for (Rectangle rect : rectangles) {
            boolean placed = false;
            for (int row = 0; row <= gridHeight - rect.height; row++) {
                for (int col = 0; col <= gridWidth - rect.width; col++) {
                    if (canPlaceRectangle(row, col, rect)) {
                        placeRectangle(row, col, rect);
                        placed = true;
                        break;
                    }
                }
                if (placed) break;
            }
            if (!placed) return false;
        }
        return true;
    }

    public static boolean canPlaceRectangle(int row, int col, Rectangle rectangle) {
        if (row + rectangle.height > gridHeight || col + rectangle.width > gridWidth) {
            return false;
        }

        for (int i = row; i < row + rectangle.height; i++) {
            for (int j = col; j < col + rectangle.width; j++) {
                if (grid[i][j] != null) {
                    return false;
                }
            }
        }

        return true;
    }

    public static void placeRectangle(int row, int col, Rectangle rectangle) {
        for (int i = row; i < row + rectangle.height; i++) {
            for (int j = col; j < col + rectangle.width; j++) {
                grid[i][j] = rectangle.name;
            }
        }
    }

    public static int calculateTotalArea(Rectangle[] rectangles) {
        int total = 0;
        for (Rectangle rect : rectangles) {
            total += rect.space;
        }
        return total;
    }
     public static void printGrid(String[][] grid) {
         for (int i = 0; i < grid.length; i++) {
             for (int j = 0; j < grid[0].length; j++) {
                 System.out.print((grid[i][j] != null ? grid[i][j] : " ") + " ");
             }
             System.out.println();
         }
     }
    private static String[][] cloneGrid(String[][] original) {
        String[][] clone = new String[original.length][];
        for (int i = 0; i < original.length; i++) {
            clone[i] = original[i].clone();
        }
        return clone;
    }

    static class Rectangle {
        int width;
        int height;
        String name;
        int space;

        public Rectangle(int width, int height, String name) {
            this.width = width;
            this.height = height;
            this.name = name;
            this.space = width * height;
        }
    }} make this code as fast as ypu can