UTG_2025

from __future__ import annotations
from typing import List, Set, Tuple, Dict, Any
from dataclasses import dataclass
from enum import Enum
import numpy as np
from collections import deque
import sys
import time
 
class State(Enum):
    SEARCH_A = 'SEARCH_A'
    SEARCH_B = 'SEARCH_B'
    SEARCH_C = 'SEARCH_C'
    SEARCH_D = 'SEARCH_D'
    AGGRESSIVE_GROWTH = 'AGGRESSIVE_GROWTH'
    AGGRESSIVE_GROWTH_BIS = 'AGGRESSIVE_GROWTH_BIS'
    PASSIVE_GROWTH = 'PASSIVE_GROWTH'
    PASSIVE_GROWTH_BIS = 'PASSIVE_GROWTH_BIS'

    def __str__(self):
        # Return just the value of the enum member
        return self.value

class EntityType(Enum):
    EMPTY = "EMPTY"
    WALL = "WALL"
    ROOT = "ROOT"
    BASIC = "BASIC"
    TENTACLE = "TENTACLE"
    HARVESTER = "HARVESTER"
    SPORER = "SPORER"
    A = "A"
    B = "B"
    C = "C"
    D = "D"

    def __str__(self):
        # Return just the value of the enum member
        return self.value


class EntityOwner(Enum):
    ME = 1
    OP = 0
    NOONE = -1
 
class OrganDir(Enum):
    NORTH = 'N'
    SOUTH = 'S'
    EAST = 'E'
    WEST = 'W'
    NONE = 'X'

    def __str__(self):
        # Return just the value of the enum member
        return self.value

PROT_TYPES = [
    EntityType.A,
    EntityType.B,
    EntityType.C,
    EntityType.D
]

PROT_TO_SEARCH = {
    EntityType.A : State.SEARCH_A,
    EntityType.B : State.SEARCH_B,
    EntityType.C : State.SEARCH_C,
    EntityType.D : State.SEARCH_D,
}

SEARCH_TO_PROT = {
    State.SEARCH_A : EntityType.A,
    State.SEARCH_B : EntityType.B,
    State.SEARCH_C : EntityType.C,
    State.SEARCH_D : EntityType.D
}

def organ_dir_from_pos(srce, dest):
    if dest[0] - srce[0] == 1:
        return OrganDir.EAST
    elif dest[0] - srce[0] == -1:
        return OrganDir.WEST
    elif dest[1] - srce[1] == -1:
        return OrganDir.NORTH
    elif dest[1] - srce[1] == 1:
        return OrganDir.SOUTH
    else:
        assert False, "Invalid direction between positions"

def filter_grid_pos(grid, filter):
    grid_positions = set()
 
    for x in range(grid.shape[0]):
        for y in range(grid.shape[1]):
            if filter(grid[x, y]):
                grid_positions.add((x, y))
   
    return grid_positions
 
@dataclass
class Organism:
    owner: EntityOwner
    root_id: int

    def __eq__(self, other):
        # Ensure comparison is done correctly by checking the same fields
        if not isinstance(other, Organism):
            return NotImplemented
        return (self.owner == other.owner) and (self.root_id == other.root_id)

    def __hash__(self):
        # Use a tuple of the fields for a consistent hash
        return hash((self.owner, self.root_id))

 
def make_path(
    walls: Set[Tuple[int, int]],
    starts: Set[Tuple[int, int]],
    ends: Set[Tuple[int, int]]
) -> List[Tuple[int, int]]:
    # Define possible movements in 4 directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
   
    # Initialize the queue for BFS and visited set
    queue = deque()
    visited = set()
   
    # Initialize the queue with all start points
    for start in starts:
        if start not in walls:  # Only start from points that are not walls
            queue.append((start, [start]))
            visited.add(start)
 
    # Perform BFS
    while queue:
        current_position, path = queue.popleft()
 
        # Check if the current position is one of the end points
        if current_position in ends:
            return path  # Return the path to the first reached end point
 
        # Explore all possible directions
        for direction in directions:
            new_x, new_y = current_position[0] + direction[0], current_position[1] + direction[1]
            new_position = (new_x, new_y)
 
            # Check if the new position is within bounds and not a wall or visited
            if (0 <= new_x < width and 0 <= new_y < height and
                    new_position not in walls and new_position not in visited):
                visited.add(new_position)
                queue.append((new_position, path + [new_position]))
 
    # If no path was found, return an empty list
    return []


def find_unreachable_positions(
    walls: Set[Tuple[int, int]],
    starts: Set[Tuple[int, int]]
) -> Set[Tuple[int, int]]:
    # Directions for moving in 4 directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    # Set to track all reachable positions
    reachable = set()
 
    # Initialize queue for BFS with all start points
    queue = deque(starts)
 
    # Perform BFS from all starting points
    while queue:
        current_position = queue.popleft()
        # Skip if current position is a wall or already visited
        if current_position in walls or current_position in reachable:
            continue
 
        # Mark current position as reachable
        reachable.add(current_position)
 
        # Explore all possible directions
        for direction in directions:
            new_x, new_y = current_position[0] + direction[0], current_position[1] + direction[1]
            new_position = (new_x, new_y)
 
            # Check if the new position is within bounds and not yet visited
            if (0 <= new_x < width and 0 <= new_y < height and new_position not in reachable and new_position not in walls):
                queue.append(new_position)
 
    # Calculate all positions in the grid and subtract reachable positions to find unreachable ones
    all_positions = {(x, y) for x in range(width) for y in range(height)}
    unreachable = all_positions - reachable
 
    return unreachable    

def make_harvested_prots_and_tentacles_front(owner : EntityOwner) -> Tuple[Set[Tuple[int, int]], \
                                                                           Set[Tuple[int, int]]]:
    tentacles   = filter_grid_pos(grid_type     , lambda entity_type  : entity_type  == EntityType.TENTACLE)
    harvesters  = filter_grid_pos(grid_type     , lambda entity_type  : entity_type  == EntityType.HARVESTER)
    own         = filter_grid_pos(grid_owner    , lambda entity_owner : entity_owner == owner)
    organ_dir_s = filter_grid_pos(grid_organ_dir, lambda organ_dir    : organ_dir    == OrganDir.SOUTH)
    organ_dir_n = filter_grid_pos(grid_organ_dir, lambda organ_dir    : organ_dir    == OrganDir.NORTH)
    organ_dir_w = filter_grid_pos(grid_organ_dir, lambda organ_dir    : organ_dir    == OrganDir.WEST)
    organ_dir_e = filter_grid_pos(grid_organ_dir, lambda organ_dir    : organ_dir    == OrganDir.EAST)

    harvested_prots = set()
    tentacles_front = set()

    own_harvesters = harvesters & own
    own_tentacles  = tentacles  & own
    
    harvested_prots |= set([(pos[0] + 0, pos[1] + 1) for pos in own_harvesters & organ_dir_s])
    harvested_prots |= set([(pos[0] + 0, pos[1] - 1) for pos in own_harvesters & organ_dir_n])
    harvested_prots |= set([(pos[0] + 1, pos[1] + 0) for pos in own_harvesters & organ_dir_w])
    harvested_prots |= set([(pos[0] - 1, pos[1] + 0) for pos in own_harvesters & organ_dir_e])

    tentacles_front |= set([(pos[0] + 0, pos[1] + 1) for pos in own_tentacles & organ_dir_s])
    tentacles_front |= set([(pos[0] + 0, pos[1] - 1) for pos in own_tentacles & organ_dir_n])
    tentacles_front |= set([(pos[0] + 1, pos[1] + 0) for pos in own_tentacles & organ_dir_w])
    tentacles_front |= set([(pos[0] - 1, pos[1] + 0) for pos in own_tentacles & organ_dir_e])

    return harvested_prots, tentacles_front

def make_grow_entity(me_harvested_stock : Dict[EntityType, int],
                     me_harvested_flux  : Dict[EntityType, int]) -> EntityType:
    if me_harvested_flux[EntityType.B] > 0 and me_harvested_flux[EntityType.C] > 0:
        return EntityType.TENTACLE
    if me_harvested_flux[EntityType.A] > 0:
        return EntityType.BASIC
    if me_harvested_stock[EntityType.A] > 0:
        return EntityType.BASIC
    if me_harvested_stock[EntityType.B] > 0 and me_harvested_stock[EntityType.C] > 0:
        return EntityType.TENTACLE
    if me_harvested_stock[EntityType.B] > 0 and me_harvested_stock[EntityType.D] > 0:
        return EntityType.SPORER
    if me_harvested_stock[EntityType.C] > 0 and me_harvested_stock[EntityType.D] > 0:
        return EntityType.HARVESTER
    
    # All hope is lost
    return EntityType.BASIC

def make_state(me_harvested_stock : Dict[EntityType, int],
               me_harvested_flux : Dict[EntityType, int],
               me_paths_by_type : Dict[EntityType, List[Tuple[int, int]]]) -> State:

    len_a = len(me_paths_by_type[EntityType.A])
    len_b = len(me_paths_by_type[EntityType.B])
    len_c = len(me_paths_by_type[EntityType.C])

    def safe_search(state : State) -> State:

        if me_harvested_stock [EntityType.C] == 0 and \
           me_harvested_flux  [EntityType.C] == 0:
            return State.SEARCH_C

        if me_harvested_stock [EntityType.D] == 0 and \
           me_harvested_flux  [EntityType.D] == 0:
            return State.SEARCH_D
        
        return state

    if me_harvested_flux[EntityType.A] == 0:
        if (me_harvested_flux[EntityType.B] == 0 and \
            me_harvested_flux[EntityType.C] == 0):
            if len_b < len_c:
                if 2 * len_b < len_a:
                    return safe_search(State.SEARCH_B)
                return safe_search(State.SEARCH_A)
            else:
                if 2 * len_c < len_a:
                    return safe_search(State.SEARCH_C)
                return safe_search(State.SEARCH_A)
        if me_harvested_flux[EntityType.B] == 0:
            if len_b < len_a:
                return safe_search(State.SEARCH_B)
            return safe_search(State.SEARCH_A)
        if me_harvested_flux[EntityType.C] == 0:
            if len_c < len_a:
                return safe_search(State.SEARCH_C)
        return safe_search(State.SEARCH_A)

    if (me_harvested_flux[EntityType.B] == 0 and \
        me_harvested_flux[EntityType.C] == 0):
        if len_b < len_c:
            return safe_search(State.SEARCH_B)
        return safe_search(State.SEARCH_C)

    if me_harvested_flux[EntityType.B] == 0:
        return safe_search(State.SEARCH_B)

    if me_harvested_flux[EntityType.C] == 0:
        return safe_search(State.SEARCH_C)

    return State.AGGRESSIVE_GROWTH 

def make_grow(grid_organ_id, me_prots, me_harvested_flux, path):

    print(f'Targeting {path[-1]} from {path[0]}', file=sys.stderr)

    grow_entity = make_grow_entity(me_prots, me_harvested_flux)

    if grow_entity not in (EntityType.HARVESTER, EntityType.SPORER):
        return print(f'GROW {grid_organ_id[path[0]]} {path[1][0]} {path[1][1]} {grow_entity}')
    
    organ_dir = organ_dir_from_pos(path[1], path[0])
    print(f'GROW {grid_organ_id[path[0]]} {path[1][0]} {path[1][1]} {grow_entity} {organ_dir}')

def make_move(context : Dict[str, Any], state : State | None, me_organism : Organism):

    # Unpack context
    grid_type            = context['grid_type'            ]
    grid_owner           = context['grid_owner'           ]
    grid_organ_id        = context['grid_organ_id'        ]
    grid_organ_dir       = context['grid_organ_dir'       ]
    grid_organ_parent_id = context['grid_organ_parent_id' ]
    grid_organ_root_id   = context['grid_organ_root_id'   ]
    me_prots             = context['me_prots'             ]
    op_prots             = context['op_prots'             ]
    me_organisms         = context['me_organisms'         ]
    op_organisms         = context['op_organisms'         ]
    me_harvested_prots   = context['me_harvested_prots'   ]
    op_harvested_prots   = context['op_harvested_prots'   ]
    me_tentacles_front   = context['me_tentacles_front'   ]
    op_tentacles_front   = context['op_tentacles_front'   ]
    op_root_ids          = context['op_root_ids'          ] 
    op_organs            = context['op_organs'            ] 
    me_organs            = context['me_organs'            ] 
    walls                = context['walls'                ] 
    empties              = context['empties'              ] 
    prots_by_type        = context['prots_by_type'        ] 
    me_paths_by_type     = context['me_paths_by_type'     ]
    me_harvested_flux    = context['me_harvested_flux'] 

    if not state:
        state = make_state(me_prots, me_harvested_flux, me_paths_by_type)

    # Logic starts here
    print(f'STATE: {state}', file=sys.stderr, flush=True)

    if state in SEARCH_TO_PROT.keys():
        path = me_paths_by_type[SEARCH_TO_PROT[state]]

        if not path:
            return make_move(context, State.AGGRESSIVE_GROWTH, me_organism)

        # Build the harvester
        if len(path) == 3:
            return print(f'GROW {grid_organ_id[path[0]]} {path[1][0]} {path[1][1]} {EntityType.HARVESTER} {organ_dir_from_pos(path[-2], path[-1])}')

        # Build the path to the prot
        make_grow(grid_organ_id, me_prots, me_harvested_flux, path)

    elif state == State.AGGRESSIVE_GROWTH:
        me_unreach = find_unreachable_positions(walls | op_organs, me_organs)
        op_path_to_nearest_prot = make_path(walls | me_organs | (me_unreach - op_organs), op_organs, prots - me_harvested_prots)

        if not op_path_to_nearest_prot:
            return make_move(context, State.AGGRESSIVE_GROWTH_BIS, me_organism)

        me_path_to_nearest_op_prot = make_path(walls | me_harvested_prots | op_organs | op_tentacles_front, me_organs, set([op_path_to_nearest_prot[-1]]))

        if not me_path_to_nearest_op_prot:
            return make_move(context, State.AGGRESSIVE_GROWTH_BIS, me_organism)
        
        make_grow(grid_organ_id, me_prots, me_harvested_flux, me_path_to_nearest_op_prot)

    elif state == State.AGGRESSIVE_GROWTH_BIS:
        me_path_to_nearest_op_organ = make_path(walls | me_harvested_prots | op_tentacles_front, me_organs, op_organs)
            
        if not me_path_to_nearest_op_organ:
            return make_move(context, State.PASSIVE_GROWTH, me_organism)
        
        make_grow(grid_organ_id, me_prots, me_harvested_flux, me_path_to_nearest_op_organ)

    elif state == State.PASSIVE_GROWTH:
        path = make_path(walls | me_harvested_prots | op_tentacles_front, me_organs, empties | (prots - me_harvested_prots))

        if not path:
            return make_move(context, State.PASSIVE_GROWTH_BIS, me_organism)

        make_grow(grid_organ_id, me_prots, me_harvested_flux, path)

    elif state == State.PASSIVE_GROWTH_BIS:
        path = make_path(walls | op_tentacles_front, me_organs, empties | prots)

        if not path:
            return print('WAIT')

        make_grow(grid_organ_id, me_prots, me_harvested_flux, path)

    else:
        print('WAIT')

####################
# GLOBAL VARIABLES #
####################

width, height = [int(i) for i in input().split()]
 
grid_type            = np.full  ((width, height), EntityType.EMPTY)
grid_owner           = np.full  ((width, height), EntityOwner.NOONE)
grid_organ_id        = np.zeros ((width, height), dtype=int)
grid_organ_dir       = np.full  ((width, height), OrganDir.NONE)
grid_organ_parent_id = np.zeros ((width, height), dtype=int)
grid_organ_root_id   = np.zeros ((width, height), dtype=int)

#############
# GAME LOOP #
#############
while True:
 
    start_time = time.time() # START TIMER

    grid_type  = np.full((width, height), EntityType.EMPTY)
    grid_owner = np.full((width, height), EntityOwner.NOONE)
    grid_organ_id = np.zeros((width, height), dtype=int)
    grid_organ_dir = np.full((width, height), OrganDir.NONE)
    grid_organ_parent_id = np.zeros((width, height), dtype=int)
    grid_organ_root_id   = np.zeros((width, height), dtype=int)
 
    organisms = set()
 
    entity_count = int(input())
    for i in range(entity_count):
        inputs = input().split()
        x = int(inputs[0])
        y = int(inputs[1])
        grid_type            [x, y] = EntityType(inputs[2])
        grid_owner           [x, y] = EntityOwner(int(inputs[3]))
        grid_organ_id        [x, y] = int(inputs[4])
        grid_organ_dir       [x, y] = OrganDir(inputs[5])
        grid_organ_parent_id [x, y] = int(inputs[6])
        grid_organ_root_id   [x, y] = int(inputs[7])
 
        organisms.add(Organism(grid_owner[x, y], grid_organ_root_id[x, y]))
 
    me_a, me_b, me_c, me_d = [int(i) for i in input().split()]
    op_a, op_b, op_c, op_d = [int(i) for i in input().split()]
    
    required_actions_count = int(input())  # your number of organisms, output an action for each one in any order

    me_harvested_prots, me_tentacles_front = make_harvested_prots_and_tentacles_front(EntityOwner.ME)
    op_harvested_prots, op_tentacles_front = make_harvested_prots_and_tentacles_front(EntityOwner.OP)
 
    context = {
        'grid_type'            : grid_type,
        'grid_owner'           : grid_owner,
        'grid_organ_id'        : grid_organ_id,
        'grid_organ_dir'       : grid_organ_dir,
        'grid_organ_parent_id' : grid_organ_parent_id,
        'grid_organ_root_id'   : grid_organ_root_id,
        'me_prots'             : { EntityType.A : me_a, EntityType.B : me_b, EntityType.C : me_c, EntityType.D : me_d },
        'op_prots'             : { EntityType.A : op_a, EntityType.B : op_b, EntityType.C : op_c, EntityType.D : op_d },
        'me_organisms'         : [organism for organism in organisms if organism.owner == EntityOwner.ME],
        'op_organisms'         : [organism for organism in organisms if organism.owner == EntityOwner.OP],
        'me_harvested_prots'   : me_harvested_prots,
        'op_harvested_prots'   : op_harvested_prots,
        'me_tentacles_front'   : me_tentacles_front,
        'op_tentacles_front'   : op_tentacles_front,
    }

    # Computed from context
    op_root_ids = set([op_organism.root_id for op_organism in context['op_organisms']])
    op_organs = filter_grid_pos(grid_organ_root_id, lambda organ_root_id: organ_root_id in op_root_ids)

    walls   = filter_grid_pos(grid_type, lambda entity_type: entity_type == EntityType.WALL)
    empties = filter_grid_pos(grid_type, lambda entity_type: entity_type == EntityType.EMPTY)

    prots_by_type = {
        EntityType.A : filter_grid_pos(grid_type, lambda entity_type: entity_type == EntityType.A),
        EntityType.B : filter_grid_pos(grid_type, lambda entity_type: entity_type == EntityType.B),
        EntityType.C : filter_grid_pos(grid_type, lambda entity_type: entity_type == EntityType.C),
        EntityType.D : filter_grid_pos(grid_type, lambda entity_type: entity_type == EntityType.D)
    }

    prots = set.union(*prots_by_type.values())
    me_harvested_flux = {prot_type : len(me_harvested_prots & prots_by_type[prot_type]) for prot_type in PROT_TYPES}

    context['op_root_ids'       ] = op_root_ids
    context['op_organs'         ] = op_organs
    context['walls'             ] = walls
    context['empties'           ] = empties
    context['prots_by_type'     ] = prots_by_type
    context['prots'             ] = prots
    context['me_harvested_flux' ] = me_harvested_flux

    for me_organism in context['me_organisms']:
        me_organs = filter_grid_pos(grid_organ_root_id, lambda organ_root_id: organ_root_id == me_organism.root_id)

        me_paths_by_type = {
            prot_type : make_path(walls | me_harvested_prots, me_organs, prots_by_type[prot_type] - me_harvested_prots) \
            for prot_type in PROT_TYPES
        }

        context['me_organs'        ] = me_organs
        context['me_paths_by_type' ] = me_paths_by_type

        make_move(context, None, me_organism)
    
    end_time = time.time() 
    elapsed_time_ms = (end_time - start_time) * 1000
    print(f"Elapsed time: {elapsed_time_ms:.2f} ms", file=sys.stderr)


# def is_protein(entity_type: EntityType) -> bool:
#     """Returns True if the entity type is A, B, C, or D (protein types)."""
#     return entity_type in {EntityType.A, EntityType.B, EntityType.C, EntityType.D}


# def is_pos_next_to_prot(pos : Tuple[int, int]) -> OrganDir:
#     NEIGHB_0 = grid_type[(pos[0] + 1, pos[1] + 0)] if pos[0] + 1 < height else EntityType.WALL
#     NEIGHB_1 = grid_type[(pos[0] - 1, pos[1] + 0)] if pos[0] - 1 >= 0     else EntityType.WALL
#     NEIGHB_2 = grid_type[(pos[0] + 0, pos[1] + 1)] if pos[1] + 1 < width  else EntityType.WALL
#     NEIGHB_3 = grid_type[(pos[0] + 0, pos[1] - 1)] if pos[1] - 1 >= 0     else EntityType.WALL

#     if is_protein(NEIGHB_0):
#         return OrganDir.EAST
#     if is_protein(NEIGHB_1):
#         return OrganDir.WEST
#     if is_protein(NEIGHB_2):
#         return OrganDir.SOUTH
#     if is_protein(NEIGHB_3):
#         return OrganDir.NORTH