pirates!

use std::io;
use std::collections::{HashSet, HashMap};

macro_rules! print_err {
    ($($arg:tt)*) => (
        {
            use std::io::Write;
            writeln!(&mut ::std::io::stderr(), $($arg)*).ok();
        }
    )
}

macro_rules! parse_input {
    ($x:expr, $t:ident) => ($x.trim().parse::<$t>().unwrap())
}

macro_rules! impl_pos {
    ($struct_name:ident) => {
        impl Pos for $struct_name {
            fn get_x(&self) -> i32 { self.x }
            fn get_y(&self) -> i32 { self.y }
        }
    }
}

trait Pos {
    fn get_x(&self) -> i32;
    fn get_y(&self) -> i32;
}

struct Ship {
    x: i32,
    y: i32,
    direction: i32,
    speed: i32,
    target: Option<Barrel>,
    road: Vec<(i32, i32)>,
}

impl Ship {
    fn new(x: i32, y: i32, direction: i32, speed: i32) -> Ship {
        Ship {
            x: x,
            y: y,
            direction: direction,
            speed: speed,
            target: None,
            road: Vec::new(),
        }
    }

    fn update(&mut self, x: i32, y: i32, direction: i32, speed: i32) {
        self.x = x;
        self.y = y;
        self.direction = direction;
        self.speed = speed;
    }
    
    fn need_x_turn(&self) -> bool {
        ((self.direction == 0 || self.direction == 1 || self.direction == 5) && self.x > 20) ||
        ((self.direction == 2 || self.direction == 3 || self.direction == 4) && self.x < 3)
    }
    
    fn need_y_turn(&self) -> bool {
        ((self.direction == 2 || self.direction == 1) && self.y < 3) ||
        ((self.direction == 4 || self.direction == 5) && self.y > 18) ||
        self.y < 3
    }
    
    fn set_target(&mut self, target: Option<(Barrel, Vec<(i32, i32)>)>) {
        if let Some((target, road)) = target {
            self.target = Some(target);
            self.road = road;
        } else {
            self.target = None;
        }
    }
    
    fn get_next_step(&mut self) -> Option<(i32, i32)> {
        self.road.pop()
    }
}

#[derive(Clone, Copy, PartialEq, Debug)]
struct Barrel {
    x: i32,
    y: i32,
}

impl Barrel {
    fn new(x: i32, y: i32) -> Barrel {
        Barrel {
            x: x,
            y: y,
        }
    }
}


#[derive(Clone, Copy, PartialEq)]
struct Mine {
    x: i32,
    y: i32,
}

impl Mine {
    fn new(x: i32, y: i32) -> Mine {
        Mine {
            x: x,
            y: y,
        }
    }
}

impl_pos!(Ship);
impl_pos!(Barrel);
impl_pos!(Mine);

impl Pos for (i32, i32) {
    fn get_x(&self) -> i32 { self.0 }
    fn get_y(&self) -> i32 { self.1 }
}

fn compute_distance<T: Pos, U: Pos>(t: &T, u: &U) -> i32 {
    ((t.get_x() - u.get_x()).pow(2) as f32 + (t.get_y() - u.get_y()).pow(2) as f32).sqrt() as i32
}

const MAX_TURN: u32 = 15;
const MINE_DETECTION_DISTANCE: i32 = 5;

const directions: [(i32, i32); 6] = [
   ( 1, 0), (1, -1), (0, -1),
   (-1, 0), (1,  1), (0,  1)
];

fn hex_direction(direction: i32) -> (i32, i32) {
    directions[direction as usize]
}

fn is_neighbor(a: (i32, i32), b: (i32, i32)) -> bool {
    //print_err!("is_neighbor: {:?} / {:?}", a, b);
    for i in 0..6 {
        let dir = hex_direction(i);
        if a.0 + dir.0 == b.0 && a.1 + dir.1 == b.1 {
            return true;
        }
    }
    false
}

fn neighbor(hex: &(i32, i32), direction: i32) -> (i32, i32) {
    let dir = hex_direction(direction);
    (hex.0 + dir.0, hex.1 + dir.1)
}

fn blocked<T: Pos>(pos: &(i32, i32), entities: &[T]) -> bool {
    if pos.0 > 22 || pos.0 < 0 || pos.1 > 20 || pos.1 < 0 {
        return false;
    }
    for entity in entities {
        if pos.0 == entity.get_x() && pos.1 == entity.get_y() {
            return true;
        }
    }
    false
}

fn get_road(positions: &[Vec<(i32, i32)>], end: (i32, i32), ret: (i32, i32)) -> Option<Vec<(i32, i32)>> {
    if positions.is_empty() {
        return None;
    }
    let mut res: Option<Vec<(i32, i32)>> = None;
    let mut pos: Option<usize> = None;
    for y in 0..positions[0].len() - 1 {
        if is_neighbor(positions[0][y], ret) {
            //print_err!("end: {:?} / current: {:?}", end, positions[0][y]);
            if positions[0][y].0 == end.0 && positions[0][y].1 == end.1 {
                return Some(vec![positions[0][y]]);
            } else {
                let c = positions[0][y];
                if let Some(tmp) = get_road(&positions[1..], end, c) {
                    if match res {
                        None => true,
                        Some(ref v) => v.len() > tmp.len(),
                    } {
                        res = Some(tmp);
                        pos = Some(y);
                    }
                }
            }
        }
    }
    if let Some(ref mut res) = res {
        res.push(positions[0][pos.unwrap()]);
    }
    res
}
    
fn create_road<T: Pos, U: Pos>(ship: &Ship, entities: &[T], target: &U) -> Option<Vec<(i32, i32)>> {
    let mut visited: HashSet<(i32, i32)> = HashSet::new();
    visited.insert((ship.x, ship.y));
    let mut fringes: Vec<Vec<(i32, i32)>> = Vec::new();
    fringes.push(vec![(ship.x, ship.y)]);

    let mut current = 1;
    let mut limit = 40;
    'main: while limit > 0 {
        fringes.push(Vec::new());
        for pos in 0..fringes[current - 1].len() {
            //print_err!("new: {:?} {:?}", (ship.x, ship.y), (target.get_x(), target.get_y()));
            for dir in 0..6 {
                let neighbor = neighbor(&fringes[current - 1][pos], dir);
                //print_err!("neighbor: {:?} {:?}", fringes[current - 1][pos], neighbor);
                if !visited.contains(&neighbor) && !blocked(&neighbor, entities) {
                    //print_err!("accepted: {:?}", neighbor);
                    fringes[current].push(neighbor);
                    visited.insert(neighbor);
                    if neighbor.0 == target.get_x() && neighbor.1 == target.get_y() {
                        break 'main
                    }
                }
            }
        }
        let empty = fringes[current].is_empty();
        if empty {
            fringes.pop();
            current -= 1;
        }
        current += 1;
        limit -= 1;
    }
    if limit == 0 {
        return None;
    }
    print_err!("limit: {} {:?}", limit, fringes);
    get_road(&fringes[1..], (target.get_x(), target.get_y()), (ship.get_x(), ship.get_y()))
}

fn get_best_target<T: Pos>(entities: &[Barrel], bad: &[T], ship: &Ship) -> Option<(Barrel, Vec<(i32, i32)>)> {
    //print_err!("nb barrels: {}", entities.len());
    if entities.is_empty() {
        None
    } else if entities.len() == 1 {
        let barrel = *entities.get(0).unwrap();
        if let Some(road) = create_road(ship, bad, &(barrel.get_x(), barrel.get_y())) {
            Some((*entities.get(0).unwrap(), road))
        } else {
            None
        }
    } else {
        let mut three_best: Vec<(i32, Barrel)> = Vec::new();
        for entity in entities {
            let distance = compute_distance(ship, entity);
            if three_best.len() < 3 {
                three_best.push((distance, *entity));
                three_best.sort_by(|x, y| x.0.cmp(&y.0));
            } else {
                if three_best[2].0 > distance {
                    three_best[2] = (distance, *entity);
                    three_best.sort_by(|x, y| x.0.cmp(&y.0));
                }
            }
        }
        let mut best: Option<(Barrel, Vec<(i32, i32)>)> = None;
        
        for besty in three_best {
            if let Some(road) = create_road(ship, bad, &besty.1) {
                if match best {
                    None => true,
                    Some(ref inner) => inner.1.len() > road.len(),
                } {
                    best = Some((besty.1, road))
                }
            }
        }
        best
    }
}

fn main() {
    let mut ships = HashMap::new();
    let mut turn_count = MAX_TURN;
    // game loop
    loop {
        let add_ships = ships.is_empty();
        if turn_count > 0 {
            turn_count -= 1;
        }

        let mut input_line = String::new();
        io::stdin().read_line(&mut input_line).unwrap();
        let my_ship_count = parse_input!(input_line, i32); // the number of remaining ships
        let mut input_line = String::new();
        io::stdin().read_line(&mut input_line).unwrap();
        let entity_count = parse_input!(input_line, usize); // the number of entities (e.g. ships, mines or cannonballs)

        let mut entities = Vec::with_capacity(entity_count);
        let mut mines = Vec::with_capacity(entity_count);

        for i in 0..entity_count as usize {
            let mut input_line = String::new();
            io::stdin().read_line(&mut input_line).unwrap();
            let inputs = input_line.split(" ").collect::<Vec<_>>();
            let entity_id = parse_input!(inputs[0], i32);
            let entity_type = inputs[1].trim().to_string();
            let x = parse_input!(inputs[2], i32);
            let y = parse_input!(inputs[3], i32);
            if entity_type == "SHIP" {
                let arg_1 = parse_input!(inputs[4], i32);
                let arg_2 = parse_input!(inputs[5], i32);
                let arg_3 = parse_input!(inputs[6], i32);
                let arg_4 = parse_input!(inputs[7], i32);
                if add_ships && arg_4 == 1 {
                    ships.insert(entity_id, Ship::new(x, y, arg_1, arg_2));
                } else if arg_4 == 1 {
                    ships.get_mut(&entity_id).unwrap().update(x, y, arg_1, arg_2);
                }
            } else if entity_type == "BARREL" {
                entities.push(Barrel::new(x, y));
            } else if entity_type == "MINE" {
                mines.push(Mine::new(x, y));
            }
        }
        for (_, ship) in &mut ships {
            if if let Some(ref target) = ship.target {
                entities.iter().find(|&x| x == target).is_none()
            } else { false } {
                ship.target = None
            }
            if ship.target.is_none() {
                let target = get_best_target(&entities, &mines, ship);
                ship.set_target(target);
            }
            if ship.target.is_none() {
                let need_x_turn = ship.need_x_turn();
                let need_y_turn = ship.need_y_turn();
                if need_x_turn || need_y_turn || ship.speed < 2 {
                    println!("MOVE {} {}",
                             if need_x_turn {
                                 if ship.x > 20 { 0 } else { 22 }
                             } else {
                                 if ship.direction == 0 || ship.direction == 1 || ship.direction == 5 {
                                     22
                                 } else {
                                     0
                                 }
                             },
                             if need_y_turn {
                                 if ship.y > 18 { 0 } else { 20 }
                             } else {
                                 if ship.direction == 2 || ship.direction == 1 {
                                     20
                                 } else {
                                     0
                                 }
                             });
                } else {
                    println!("WAIT");
                }
            } else {
                print_err!("target: {:?}", ship.target);
                if let Some((x, y)) = ship.get_next_step() {
                    println!("MOVE {} {}", x, y);
                } else {
                    println!("WAIT");
                }
            }
        }
    }
}