import sys

# Function to check if a cell is within the grid boundaries
def within_bounds(r, c, R, C):
    return r >= 0 and r < R and c >= 0 and c < C

# Function to simulate the car movement
def simulate_car(grid, start, finish):
    # List to keep track of the drivable pairs
    drivable_pairs = []

    # Loop over all possible start and finish pairs
    for i in range(len(start)):
        for j in range(len(finish)):
            # If the start and finish cells are the same, skip this pair
            if start[i] == finish[j]:
                continue

            # Initialize the probabilities for each cell to 0
            prob = [[0.0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
            prob[start[i][0]][start[i][1]] = 1.0

            # Loop over all possible movements
            for _ in range(200):
                # Initialize the new probability matrix
                new_prob = [[0.0 for _ in range(len(grid[0]))] for _ in range(len(grid))]

                # Loop over all cells in the grid
                for r in range(len(grid)):
                    for c in range(len(grid[0])):
                        # Skip cells that are walls or hazards
                        if grid[r][c] == '#' or grid[r][c] == '*':
                            new_prob[r][c] = prob[r][c]
                            continue

                        # Initialize the new probability for the current cell to 0
                        p = 0.0

                        # Calculate the probability of moving to the cell north of the current cell
                        if within_bounds(r-1, c, len(grid), len(grid[0])) and grid[r-1][c] != '#':
                            p += prob[r-1][c] * 0.5
                            if grid[r-1][c] == finish[j]:
                                drivable_pairs.append((start[i], finish[j]))

                        # Calculate the probability of moving to the cell south of the current cell
                        if within_bounds(r+1, c, len(grid), len(grid[0])) and grid[r+1][c] != '#':
                            p += prob[r+1][c] * 0.5
                            if grid[r+1][c] == finish[j]:
                                drivable_pairs.append((start[i], finish[j]))

                        # Calculate the probability of moving to the cell east of the current cell
                        if within_bounds(r, c+1, len(grid), len(grid[0])) and grid[r][c+1] != '#':
                            p += prob[r][c+1] * 0.5
                            if grid[r][c+1] == finish[j]:
                                drivable_pairs.append((start[i], finish[j]))

                        # Calculate the probability of moving to the cell west of the current cell
                        if within_bounds(r, c-1, len(grid), len(grid[0])) and grid[r][c-1] != '#':
                            p += prob[r][c-1] * 0.5
                            if grid[r][c-1] == finish[j]:
                                drivable_pairs.append((start[i], finish[j]))

                        # Update the new probability matrix for the current cell
                        new_prob[r][c] = p

                # Update the probability matrix for the next iteration
                prob = new_prob

    # Return the list of drivable pairs
    if len(drivable_pairs) == 0:
        return "NONE"
    else:
        drivable_pairs.sort()