import math
import os
import random
import re
import sys

def codify(n):
    my_str = str(n)
    if n<10:
        my_str = "0" + str(n)
        
    return my_str
		
def get_max_val(my_dict):
    k = ""
    v = -1
    my_max = -1
    for center, size in my_dict.items():
        if size>my_max:
            my_max=size
            k = center
            v = size
    
    return k, v

def get_list(center, size):
    my_list = [center]
    i = int(center[0: 2])
    j = int(center[2:])  
    length = int((size-1)/4)
    for n in range(1, length+1):
        my_list.append(codify(i+n)+codify(j))
    for n in range(1, length+1):
        my_list.append(codify(i-n)+codify(j))
    for n in range(1, length+1):
        my_list.append(codify(i)+codify(j+n))
    for n in range(1, length+1):
        my_list.append(codify(i)+codify(j-n))
        
    return my_list
		
def twoPluses(grid):
    limit = 1
    area_list = []
    while limit<16:
        row_len = len(grid)
        visited = dict()
        for i in range(row_len):
            col_len = len(grid[0])
            for j in range(col_len):
                n=0
                while n<limit:
                    if i+n<row_len and i-n>=0 and j+n<col_len and j-n>=0 and grid[i+n][j]=='G' and grid[i-n][j]=='G' and grid[i][j+n]=='G' and grid[i][j-n]=='G':
                        visited[codify(i)+codify(j)] = n*4 + 1
                        n += 1
                    else:
                        break
        
        perm = []
        for center, size in visited.items():
            visited_copy = visited.copy()
            visited_copy.pop(center)
            list1 = get_list(center, size)
            stop = False
            while not stop:
                k, v = get_max_val(visited_copy)
                visited_copy.pop(k)
                list2 = get_list(k, v)
                overlap = False                  
                for cell in list1:
                    if cell in list2:
                        overlap = True
                        break
                if not overlap:
                    stop = True                      
                    perm.append(size*v)
                    
                if len(visited_copy) == 0:
                    stop = True
        
        
        area_list.append(max(perm))
        limit += 1
        
    return max(area_list) 

def twoPluses(grid):
    # Write your code here
    n_rows = len(grid)
    n_columns = len(grid[0])
    
    lr_grid = [[0] * n_columns for i in range(n_rows)]
    max_jv = 0
    for i in range(n_rows):
        last_bad_j = -1
        for j in range(n_columns+1):
            if j == n_columns or grid[i][j] == "B":
                for x in range(j-1, last_bad_j, -1):
                    new_v = j - x
                    if (new_v < lr_grid[i][x]):
                        lr_grid[i][x] = new_v
                    else:
                        max_jv = max(max_jv, lr_grid[i][x])
                        break
                last_bad_j = j
            else:
                # if grid[i][j] == "G":
                lr_grid[i][j] = j - last_bad_j
            
    ud_grid = [[0] * n_columns for i in range(n_rows)]
    max_iv = 0
    for j in range(n_columns):
        last_bad_i = -1
        for i in range(n_rows+1):
            if i == n_rows or grid[i][j] == "B":
                for y in range(i-1, last_bad_i, -1):
                    new_v = i - y
                    if (new_v < ud_grid[y][j]):
                        ud_grid[y][j] = new_v
                    else:
                        max_iv = max(max_iv, ud_grid[y][j])
                        break
                last_bad_i = i
            else:
                # if grid[i][j] == "G":
                ud_grid[i][j] = i - last_bad_i
            
    max_grid = [[0] * n_columns for i in range(n_rows)]
    cross_list = [[] for i in range(min(max_jv, max_iv) + 1)]
    for i in range(n_rows):
        for j in range(n_columns):
            valid_cross = min(lr_grid[i][j], ud_grid[i][j])
            max_grid[i][j] = valid_cross
            if valid_cross > 0:
                cross_list[valid_cross].append((i, j))
    print(grid)
    print(lr_grid)
    print(ud_grid)
    print(max_grid)
    print(cross_list)
  ... rest of the code - brute forcing the solution
	
	
	
	
	

class Result {
  /**
   * Finds the maximum product of areas of two non-overlapping plus shapes.
   */
  public static int twoPluses(List<String> grid) {
    int rows = grid.size();
    int cols = grid.get(0).length();
    List<Set<Integer>> pluses = new ArrayList<>();
    char[][] matrix = convertToMatrix(grid);
    int maxProduct = 0;

    // Identify all possible pluses
    for (int r = 0; r < rows; r++) {
      for (int c = 0; c < cols; c++) {
        if (matrix[r][c] == 'G') {
          int maxWingLength = findMaxWing(matrix, r, c);
          // Find and save all the pluses that shares the same center as smaller pluses might not overlap while bigger ones do
          for (int i = maxWingLength; i >= 0; i--) {
            pluses.add(getPlusCells(r, c, i, cols));
          }
        }
      }
    }
    // Check every pair of pluses. if they don't overlap, compare the product of them with the max product found up to that point.
    for (int i = 0; i < pluses.size(); i++) {
      for (int j = i + 1; j < pluses.size(); j++) {
        if (!hasOverlap(pluses.get(i), pluses.get(j))) {
          int product = pluses.get(i).size() * pluses.get(j).size();
          maxProduct = Math.max(maxProduct, product);
        }
      }
    }
    return maxProduct;
  }

  /**
   * Determines the maximum wing length of a plus centered at the given cell. Checks each direction.
   */
  private static int findMaxWing(char[][] matrix, int row, int col) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int maxWing = 0;

    while (row - maxWing >= 0 && row + maxWing < rows && col - maxWing >= 0
        && col + maxWing < cols && matrix[row - maxWing][col] == 'G'
        && matrix[row + maxWing][col] == 'G'
        && matrix[row][col - maxWing] == 'G'
        && matrix[row][col + maxWing] == 'G') {
      maxWing++;
    }
    return maxWing - 1;
  }

  /**
   * Converts the grid of strings into a 2D character array.
   */
  private static char[][] convertToMatrix(List<String> grid) {
    int rows = grid.size();
    int cols = grid.get(0).length();
    char[][] matrix = new char[rows][cols];

    for (int r = 0; r < rows; r++) {
      matrix[r] = grid.get(r).toCharArray();
    }
    return matrix;
  }

  /**
   * Returns the set of cell indices covered by a plus with the given center and
   * wing length.
   */
  private static Set<Integer> getPlusCells(
      int row, int col, int wingLength, int cols) {
    Set<Integer> cells = new HashSet<>();
    cells.add(row * cols + col); // Center cell

    for (int i = 1; i <= wingLength; i++) {
      cells.add((row - i) * cols + col); // Up
      cells.add((row + i) * cols + col); // Down
      cells.add(row * cols + (col - i)); // Left
      cells.add(row * cols + (col + i)); // Right
    }
    return cells;
  }

  /**
   * Checks if two pluses overlap.
   */
  private static boolean hasOverlap(Set<Integer> plus1, Set<Integer> plus2) {
    for (int cell : plus1) {
      if (plus2.contains(cell)) {
        return true;
      }
    }
    return false;
  }
}

// grid char const
const GOOD = 'G', BAD = 'B', PLUSED = 'P';

// replace string char by index
function replaceCharAt(str: string, index: number, char: string): string {
    if (index < 0 || index >= str.length) { throw new Error("Index out of range"); }
    return str.substr(0, index) + char + str.substr(index + 1);
}

// select 1 coordinate, let pluses grow, return pluses size and new grid that pluses already growed
function getPluses(grid: string[], startPosition: number[]): [number, string[]][] {
    const y = startPosition[0]
    const x = startPosition[1]

    let plused_grid = [...grid];
    let size = 0;

    plused_grid[y] = replaceCharAt(plused_grid[y], x, PLUSED)

    let result: [number, string[]][] = [[size, [...plused_grid]]]
    while (true) {
        try {
            if (plused_grid[y - (size + 1)][x] != GOOD) break;
            if (plused_grid[y + (size + 1)][x] != GOOD) break;
            if (plused_grid[y][x - (size + 1)] != GOOD) break;
            if (plused_grid[y][x + (size + 1)] != GOOD) break;

            plused_grid[y - (size + 1)] = replaceCharAt(plused_grid[y - (size + 1)], x, PLUSED)
            plused_grid[y] = replaceCharAt(plused_grid[y], x - (size + 1), PLUSED)
            plused_grid[y] = replaceCharAt(plused_grid[y], x + (size + 1), PLUSED)
            plused_grid[y + (size + 1)] = replaceCharAt(plused_grid[y + (size + 1)], x, PLUSED)

            size++;

            result.push([size, [...plused_grid]])
        } catch (e) {
            break;
        }
    }
    return result;
}

function twoPluses(grid: string[]): number {
    // Write your code here

    // store result of this problem
    let maxTotal = 0;

    // loop the grid, find GOOD coordinate, mean it is not in BAD or PLUSED
    for (let y1 = 0; y1 < grid.length; y1++) {
        for (let x1 = 0; x1 < grid[y1].length; x1++) {
            let cell = grid[y1][x1];
            if (cell != GOOD) continue;

            // got 1st pluses, try 2nd loop on a grid that placed 1st pluses
            getPluses(grid, [y1, x1]).forEach(([size_1, grid_1]) => {
                for (let y2 = 0; y2 < grid_1.length; y2++) {
                    for (let x2 = 0; x2 < grid_1[y2].length; x2++) {
                        let cell = grid_1[y2][x2];
                        if (cell != GOOD) continue;

                        // got 2nd pluses, calculate size of 2 pluses, get the larger
                        getPluses(grid_1, [y2, x2]).forEach(([size_2, grid_2]) => {
                            // size is the wing length, so total is: 
                            //      size * 4 (wings) + 1 (intersection point)
                            maxTotal = Math.max((size_1 * 4 + 1) * (size_2 * 4 + 1), maxTotal);
                        })
                    }
                }
            })
        }
    }
    
    // done
    return maxTotal
}