import random

def create_hard_maze(size=40):
    """
    Creates a highly difficult 40x40 maze.
    
    The maze includes:
    - 'S' for the start point
    - 'G' for the goal point
    - '#' for walls (obstacles)
    - 'I' for an item
    - 'T' for a trap
    
    The difficulty is maximized by creating a large number of walls, 
    making the path from 'S' to 'G' extremely narrow and complex.
    """
    # Initialize a 40x40 grid with open paths
    maze = [[' ' for _ in range(size)] for _ in range(size)]
    
    # Place 'S' (Start) at a random position near the top-left
    start_pos = (random.randint(1, 5), random.randint(1, 5))
    maze[start_pos[0]][start_pos[1]] = 'S'
    
    # Place 'G' (Goal) at a random position near the bottom-right
    goal_pos = (random.randint(size - 6, size - 2), random.randint(size - 6, size - 2))
    maze[goal_pos[0]][goal_pos[1]] = 'G'
    
    # Ensure 'S' and 'G' are not the same position
    while start_pos == goal_pos:
        goal_pos = (random.randint(size - 6, size - 2), random.randint(size - 6, size - 2))
        maze[goal_pos[0]][goal_pos[1]] = 'G'
        
    # Create a large number of walls (obstacles)
    # Filling ~60% of the maze with walls to maximize difficulty
    num_walls = int(size * size * 0.6) 
    
    for _ in range(num_walls):
        r, c = random.randint(0, size - 1), random.randint(0, size - 1)
        # Make sure not to place a wall on 'S' or 'G'
        if maze[r][c] == ' ':
            maze[r][c] = '#'
            
    # Place 'I' (Item) and 'T' (Trap)
    num_items = 2 # You can adjust the number of items/traps
    num_traps = 2
    
    for _ in range(num_items):
        r, c = random.randint(0, size - 1), random.randint(0, size - 1)
        if maze[r][c] == ' ':
            maze[r][c] = 'I'
            
    for _ in range(num_traps):
        r, c = random.randint(0, size - 1), random.randint(0, size - 1)
        if maze[r][c] == ' ':
            maze[r][c] = 'T'
            
    # Add a border of walls around the entire maze for containment
    for i in range(size):
        maze[0][i] = '#'
        maze[size - 1][i] = '#'
        maze[i][0] = '#'
        maze[i][size - 1] = '#'
        
    return maze

# Generate the highly difficult 40x40 maze
hard_maze = create_hard_maze()

# Print the maze to see the result
for row in hard_maze:
    print(' '.join(row))