use std::fmt;
use std::ops::{Add, AddAssign};
use std::collections::BinaryHeap;

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(feature = "single_testcase")]
        {
            eprint!("[line:{}] ", line!());
            eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
        }
    }
}

fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        ms - STIME
    }
}

//--------------------------------------------------------------------------------
// https://atcoder.jp/contests/intro-heuristics/submissions/14832097

#[allow(dead_code)]
fn readln() -> String {
    let mut line = String::new();
    ::std::io::stdin()
        .read_line(&mut line)
        .unwrap_or_else(|e| panic!("{}", e));
    line
}

#[allow(unused_macros)]
macro_rules! read {
	($($t:tt),*; $n:expr) => {{
		let stdin = ::std::io::stdin();
		let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
			let line = line.unwrap();
			let mut it = line.split_whitespace();
			_read!(it; $($t),*)
		}).collect::<Vec<_>>();
		ret
	}};
	($($t:tt),*) => {{
		let line = readln();
		let mut it = line.split_whitespace();
		_read!(it; $($t),*)
	}};
}

macro_rules! _read {
	($it:ident; [char]) => {
		_read!($it; String).chars().collect::<Vec<_>>()
	};
	($it:ident; [u8]) => {
		Vec::from(_read!($it; String).into_bytes())
	};
	($it:ident; usize1) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
	};
	($it:ident; [usize1]) => {
		$it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
	};
	($it:ident; [$t:ty]) => {
		$it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
	};
	($it:ident; $t:ty) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
	};
	($it:ident; $($t:tt),+) => {
		($(_read!($it; $t)),*)
	};
}

//--------------------------------------------------------------------------------
// https://atcoder.jp/contests/hokudai-hitachi2017-1/submissions/1797182

pub struct XorShift {
    pub x: [u32; 4],
}

impl XorShift {
    pub fn new(mut seed: u32) -> XorShift {
        let mut x = [0; 4];
        for i in 0..4 {
            seed = 1812433253u32
                .wrapping_mul(seed ^ (seed >> 30))
                .wrapping_add(i as u32);
            x[i] = seed;
        }
        XorShift { x: x }
    }
    pub fn next_u32(&mut self) -> u32 {
        let t = self.x[0] ^ (self.x[0] << 11);
        for i in 0..3 {
            self.x[i] = self.x[i + 1]
        }
        self.x[3] = self.x[3] ^ (self.x[3] >> 19) ^ t ^ (t >> 8);
        self.x[3]
    }
    /// [0, n)
    pub fn next(&mut self, n: u32) -> u32 {
        loop {
            let t = self.next_u32();
            let r = t % n;
            if (t - r).checked_add(n).is_some() {
                return r;
            }
        }
    }
    pub fn shuffle<T>(&mut self, a: &mut [T]) {
        for i in 0..a.len() {
            let j = i + self.next((a.len() - i) as u32) as usize;
            a.swap(i, j);
        }
    }
}

//--------------------------------------------------------------------------------
// https://docs.rs/bitset-fixed/0.1.0/src/bitset_fixed/lib.rs.html
const TRUE: &bool = &true;
const FALSE: &bool = &false;

#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
/// Fixed sized bitset
pub struct BitSet {
    buf: Vec<u64>,
    size: usize,
}

impl BitSet {
    /// Construct a new, zero bitset with specified capacity.
    /// This method allocates O(size) bits
    pub fn new(size: usize) -> BitSet {
        BitSet {
            buf: vec![0; (size + 63) / 64],
            size,
        }
    }

    /// Set i-th bit to `b`
    #[inline]
    pub fn set(&mut self, i: usize, b: bool) {
        assert!(i < self.size);
        if b {
            self.buf[i >> 6] |= 1 << (i & 63);
        } else {
            self.buf[i >> 6] &= !(1 << (i & 63));
        }
    }

    /// Get the size of bits
    #[inline]
    pub fn size(&self) -> usize {
        self.size
    }

    /// Get the number of ones
    #[inline]
    pub fn count_ones(&self) -> u32 {
        self.buf.iter().map(|x| x.count_ones()).sum()
    }

    /// Get the number of zeros
    #[inline]
    pub fn count_zeros(&self) -> u32 {
        self.size as u32 - self.count_ones()
    }

    /// Faster left shift and or
    ///
    /// `bitset | (bitset << x)`
    #[inline]
    pub fn shl_or(&mut self, x: usize) {
        let q = x >> 6;
        let r = x & 63;

        if q >= self.buf.len() {
            return;
        }

        if r == 0 {
            for i in (q..self.buf.len()).rev() {
                *unsafe { self.buf.get_unchecked_mut(i) } |=
                    *unsafe { self.buf.get_unchecked(i - q) };
            }
        } else {
            for i in (q + 1..self.buf.len()).rev() {
                *unsafe { self.buf.get_unchecked_mut(i) } |=
                    (unsafe { self.buf.get_unchecked(i - q) } << r)
                        | (unsafe { self.buf.get_unchecked(i - q - 1) } >> (64 - r));
            }
            *unsafe { self.buf.get_unchecked_mut(q) } |= unsafe { self.buf.get_unchecked(0) } << r;
        }

        self.chomp();
    }

    /// Get inner buffer
    #[inline]
    pub fn buffer(&self) -> &[u64] {
        &self.buf
    }

    /// Get inner buffer with mutable reference
    #[inline]
    pub fn buffer_mut(&mut self) -> &mut [u64] {
        &mut self.buf
    }

    /// Set tailing bits in inner buffer whose index are greater than size to `0`
    #[inline]
    pub fn chomp(&mut self) {
        let r = self.size & 63;
        if r != 0 {
            if let Some(x) = self.buf.last_mut() {
                let d = 64 - r;
                *x = (*x << d) >> d;
            }
        }
    }
}

impl std::ops::Index<usize> for BitSet {
    type Output = bool;
    #[inline]
    fn index(&self, index: usize) -> &bool {
        assert!(index < self.size);
        [FALSE, TRUE][(self.buf[index >> 6] >> (index & 63)) as usize & 1]
    }
}

impl std::ops::ShlAssign<usize> for BitSet {
    #[inline]
    fn shl_assign(&mut self, x: usize) {
        let q = x >> 6;
        let r = x & 63;

        if q >= self.buf.len() {
            for x in &mut self.buf {
                *x = 0;
            }
            return;
        }

        if r == 0 {
            for i in (q..self.buf.len()).rev() {
                *unsafe { self.buf.get_unchecked_mut(i) } =
                    *unsafe { self.buf.get_unchecked(i - q) };
            }
        } else {
            for i in (q + 1..self.buf.len()).rev() {
                *unsafe { self.buf.get_unchecked_mut(i) } =
                    (unsafe { self.buf.get_unchecked(i - q) } << r)
                        | (unsafe { self.buf.get_unchecked(i - q - 1) } >> (64 - r));
            }
            *unsafe { self.buf.get_unchecked_mut(q) } = unsafe { self.buf.get_unchecked(0) } << r;
        }

        for x in &mut self.buf[..q] {
            *x = 0;
        }

        self.chomp();
    }
}

impl std::ops::Shl<usize> for BitSet {
    type Output = Self;

    #[inline]
    fn shl(mut self, x: usize) -> Self {
        self <<= x;
        self
    }
}

impl<'a> std::ops::Shl<usize> for &'a BitSet {
    type Output = BitSet;
    #[inline]
    fn shl(self, x: usize) -> Self::Output {
        let mut result = self.clone();
        result <<= x;
        result
    }
}

impl std::ops::ShrAssign<usize> for BitSet {
    #[inline]
    fn shr_assign(&mut self, x: usize) {
        let q = x >> 6;
        let r = x & 63;

        if q >= self.buf.len() {
            for x in &mut self.buf {
                *x = 0;
            }
            return;
        }

        if r == 0 {
            for i in 0..self.buf.len() - q {
                *unsafe { self.buf.get_unchecked_mut(i) } =
                    *unsafe { self.buf.get_unchecked(i + q) };
            }
        } else {
            for i in 0..self.buf.len() - q - 1 {
                *unsafe { self.buf.get_unchecked_mut(i) } =
                    (unsafe { self.buf.get_unchecked(i + q) } >> r)
                        | (unsafe { self.buf.get_unchecked(i + q + 1) } << (64 - r));
            }
            let len = self.buf.len();
            *unsafe { self.buf.get_unchecked_mut(len - q - 1) } =
                unsafe { self.buf.get_unchecked(len - 1) } >> r;
        }

        let len = self.buf.len();
        for x in &mut self.buf[len - q..] {
            *x = 0;
        }
    }
}

impl std::ops::Shr<usize> for BitSet {
    type Output = Self;

    #[inline]
    fn shr(mut self, x: usize) -> Self {
        self >>= x;
        self
    }
}

impl<'a> std::ops::Shr<usize> for &'a BitSet {
    type Output = BitSet;

    #[inline]
    fn shr(self, x: usize) -> Self::Output {
        let mut result = self.clone();
        result >>= x;
        result
    }
}

impl<'a> std::ops::BitAndAssign<&'a BitSet> for BitSet {
    #[inline]
    fn bitand_assign(&mut self, rhs: &'a Self) {
        for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) {
            *a &= *b;
        }
    }
}

impl<'a> std::ops::BitAnd<&'a BitSet> for BitSet {
    type Output = Self;
    #[inline]
    fn bitand(mut self, rhs: &'a Self) -> Self::Output {
        self &= rhs;
        self
    }
}

impl<'a, 'b> std::ops::BitAnd<&'b BitSet> for &'a BitSet {
    type Output = BitSet;
    #[inline]
    fn bitand(self, rhs: &'b BitSet) -> Self::Output {
        let mut result = self.clone();
        result &= rhs;
        result
    }
}

impl<'a> std::ops::BitOrAssign<&'a BitSet> for BitSet {
    #[inline]
    fn bitor_assign(&mut self, rhs: &'a Self) {
        for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) {
            *a |= *b;
        }
        self.chomp();
    }
}

impl<'a> std::ops::BitOr<&'a BitSet> for BitSet {
    type Output = Self;
    #[inline]
    fn bitor(mut self, rhs: &'a Self) -> Self::Output {
        self |= rhs;
        self
    }
}

impl<'a, 'b> std::ops::BitOr<&'b BitSet> for &'a BitSet {
    type Output = BitSet;
    #[inline]
    fn bitor(self, rhs: &'b BitSet) -> Self::Output {
        let mut result = self.clone();
        result |= rhs;
        result
    }
}

impl<'a> std::ops::BitXorAssign<&'a BitSet> for BitSet {
    #[inline]
    fn bitxor_assign(&mut self, rhs: &'a Self) {
        for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) {
            *a ^= *b;
        }
        self.chomp();
    }
}

impl<'a> std::ops::BitXor<&'a BitSet> for BitSet {
    type Output = Self;
    #[inline]
    fn bitxor(mut self, rhs: &'a Self) -> Self {
        self ^= rhs;
        self
    }
}

impl<'a, 'b> std::ops::BitXor<&'b BitSet> for &'a BitSet {
    type Output = BitSet;
    #[inline]
    fn bitxor(self, rhs: &'b BitSet) -> Self::Output {
        let mut result = self.clone();
        result ^= rhs;
        result
    }
}

impl std::ops::Not for BitSet {
    type Output = Self;
    #[inline]
    fn not(mut self) -> Self::Output {
        for x in &mut self.buf {
            *x = !*x;
        }
        self.chomp();
        self
    }
}

impl<'a> std::ops::Not for &'a BitSet {
    type Output = BitSet;
    #[inline]
    fn not(self) -> Self::Output {
        !self.clone()
    }
}

//--------------------------------------------------------------------------------

const SEED: u32 = 890482;
const TIME_LIMIT: f64 = 2.9;

const GRID_SIZE: usize = 50;
const NUM_BOMB: usize = 20;
const SH: usize = 0;
const SW: usize = 0;

const INF: i32 = 1_000_000_000;
const NIL: usize = 1_000_000_000;
const DIRS: [Position; 4] = [
    Position { h: 0, w: !0 },
    Position { h: 0, w: 1 },
    Position { h: !0, w: 0 },
    Position { h: 1, w: 0 },
];
const DIRS_CHAR: [char; 4] = ['L', 'R', 'U', 'D'];
const L: usize = 0;
const R: usize = 1;
const U: usize = 2;
const D: usize = 3;

fn get_opposite(di: usize) -> usize {
    match di {
        L => R,
        R => L,
        U => D,
        D => U,
        _ => unreachable!(),
    }
}

#[derive(Debug, Copy, Clone)]
enum Cell {
    Empty,
    Building,
    Shop,
}

impl Cell {
    fn new(c: char) -> Self {
        match c {
            '.' => Self::Empty,
            '#' => Self::Building,
            '@' => Self::Shop,
            _ => unreachable!(),
        }
    }
}

#[derive(Debug, PartialEq, Copy, Clone, Ord, Eq, PartialOrd)]
struct Position {
    h: usize,
    w: usize,
}

impl Add for Position {
    type Output = Position;
    fn add(self, rhs: Self) -> Self {
        Position {
            h: self.h.wrapping_add(rhs.h),
            w: self.w.wrapping_add(rhs.w),
        }
    }
}

impl AddAssign for Position {
    fn add_assign(&mut self, rhs: Self) {
        *self = Position {
            h: self.h.wrapping_add(rhs.h),
            w: self.w.wrapping_add(rhs.w),
        }
    }
}

impl Position {
    fn read() -> Self {
        let (dh, dw) = read!(isize, isize);
        let h = if dh < 0 {
            ((-dh) as usize).wrapping_neg()
        } else {
            dh as usize
        };
        let w = if dw < 0 {
            ((-dw) as usize).wrapping_neg()
        } else {
            dw as usize
        };
        Self { h, w }
    }
}

#[derive(Debug, Default)]
struct Bomb {
    cost: i32,
    num_position: usize,
    positions: Vec<Position>,
}

impl Bomb {
    fn read() -> Self {
        let (cost, num_position) = read!(i32, usize);
        let mut positions = Vec::with_capacity(num_position);
        for _ in 0..num_position {
            positions.push(Position::read());
        }
        Self {
            cost,
            num_position,
            positions,
        }
    }
}

#[derive(Debug)]
struct Input {
    grid_size: usize, // N
    num_bomb: usize,
    gridss: [[Cell; GRID_SIZE]; GRID_SIZE],
    bombs: [Bomb; NUM_BOMB],
}

impl Input {
    fn read() -> Self {
        let (grid_size, num_bomb) = read!(usize, usize);
        let gridss_char = read!([char]; GRID_SIZE);
        let mut gridss = [[Cell::Empty; GRID_SIZE]; GRID_SIZE];
        for hi in 0..GRID_SIZE {
            for wi in 0..GRID_SIZE {
                gridss[hi][wi] = Cell::new(gridss_char[hi][wi]);
            }
        }
        let mut bombs: [Bomb; NUM_BOMB] = Default::default();
        for i in 0..NUM_BOMB {
            bombs[i] = Bomb::read();
        }
        Self {
            grid_size,
            num_bomb,
            gridss,
            bombs,
        }
    }

    fn in_grid(&self, position: &Position) -> bool {
        position.h < self.grid_size && position.w < self.grid_size
    }

    fn to_index(&self, position: &Position) -> usize {
        position.h * self.grid_size + position.w
    }

    fn gen_initial_building(&self) -> BitSet {
        let mut building = BitSet::new(self.grid_size * self.grid_size);
        for h in 0..self.grid_size {
            for w in 0..self.grid_size {
                match self.gridss[h][w] {
                    Cell::Building | Cell::Shop => {
                        let index = self.to_index(&Position { h, w });
                        building.set(index, true);
                    }
                    _ => (),
                }
            }
        }
        building
    }
}

type Output = Vec<Command>;

#[derive(Debug)]
enum Command {
    Move { di: usize },
    Buy { bi: usize },
    Use { bi: usize },
}

impl fmt::Display for Command {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let s = match self {
            Self::Move { di } => {
                let c = DIRS_CHAR[*di];
                format!("1 {c}")
            }
            Self::Buy { bi } => {
                let bi = bi + 1;
                format!("2 {bi}")
            }
            Self::Use { bi } => {
                let bi = bi + 1;
                format!("3 {bi}")
            }
        };
        write!(f, "{}", s)
    }
}

#[derive(Debug, Clone)]
enum Plan {
    Bomb { bi: usize, position: Position },
    Buy { position: Position },
}

fn djikstra(start: &Position, goal: &Position, building: &BitSet, num_bomb: i32, will_return_commands: bool, environment: &Environment) -> (i32, Vec<Command>) {
    let mut distss = [[INF; GRID_SIZE]; GRID_SIZE];
    let mut prevss = [[NIL; GRID_SIZE]; GRID_SIZE];
    distss[start.h][start.w] = 0;
    let mut hp = BinaryHeap::new();
    hp.push((0, *start));
    while let Some((d, position)) = hp.pop() {
        let d = -d;
        let Position { h, w } = position;
        if d != distss[h][w] {
            continue;
        }
        if position == *goal {
            break;
        }
        for (di, &p_diff) in DIRS.iter().enumerate() {
            let next_position = position + p_diff;
            if !environment.input.in_grid(&next_position) {
                continue;
            }
            let ni = environment.input.to_index(&next_position);
            let d_diff = if building[ni] {
                2 * (num_bomb + 1) * (num_bomb + 1)
            } else {
                (num_bomb + 1) * (num_bomb + 1)
            };
            let nd = d + d_diff;
            let Position { h: nh, w: nw } = next_position;
            if nd < distss[nh][nw] {
                distss[nh][nw] = nd;
                prevss[nh][nw] = di;
                hp.push((-nd, next_position));
            }
        }
    }

    let commands = if will_return_commands {
        let mut commands = vec![];
        let mut position = goal.clone();
        loop {
            let Position { h, w } = position;
            let di = prevss[h][w];
            if di == NIL {
                break;
            }
            commands.push(Command::Move { di });
            position += DIRS[get_opposite(di)];
        }
        commands.reverse();
        commands
    } else {
        vec![]
    };

    let Position { h: gh, w: gw } = goal;
    (distss[*gh][*gw], commands)
}
#[derive(Clone)]
struct AnnealingState {
    plans: Vec<Plan>,
    redo_start_pi: usize,
    redo_end_pi: usize,
    undo_start_pi: usize,
    undo_end_pi: usize,
}

impl AnnealingState {
    fn compute_cost_diff(&self, environment: &Environment, is_redo: bool) -> i32 {
        let (start_pi, end_pi) = if is_redo {
            (self.redo_start_pi, self.redo_end_pi)
        } else {
            (self.undo_start_pi, self.undo_end_pi)
        };
        let mut building = environment.initial_building.clone();
        let mut num_bomb = 0;
        for (pi, plan) in self.plans[..start_pi].iter().enumerate() {
            match plan {
                Plan::Bomb { bi, position } => {
                    let Position { h, w } = position;
                    building &= &!(&environment.bombsss[*h][*w][*bi]);
                    num_bomb -= 1;
                }
                Plan::Buy { position: _ } => {
                    for future_plan in self.plans.iter().skip(pi + 1) {
                        match future_plan {
                            Plan::Bomb { bi: _, position: _ } => {
                                num_bomb += 1;
                            }
                            Plan::Buy { position: _ } => break,
                        }
                    }
                }
            }
        }

        let mut position = if start_pi == 0 {
            Position { h: SH, w: SW }
        } else {
            match self.plans[start_pi - 1] {
                Plan::Buy { position } => position,
                Plan::Bomb { bi: _, position } => position,
            }
        };
        let mut cost_diff = 0;
        for pi in start_pi..end_pi {
            let plan = &self.plans[pi];
            // move
            let next_position = match plan {
                Plan::Bomb { bi: _, position } => position,
                Plan::Buy { position} => position,
            };
            let (ud_di, ud_count) = if position.h > next_position.h {
                (U, position.h - next_position.h)
            } else {
                (D, next_position.h - position.h)
            };
            let (lr_di, lr_count) = if position.w > next_position.w {
                (L, position.w - next_position.w)
            } else {
                (R, next_position.w - position.w)
            };
            let mut di_counts = if ud_count > lr_count {
                [(ud_di, ud_count), (lr_di, lr_count)]
            } else {
                [(lr_di, lr_count), (ud_di, ud_count)]
            };
            while di_counts[0].1 > 0 {
                let next_positions = [position + DIRS[di_counts[0].0], position + DIRS[di_counts[1].0]];
                let indexs = [environment.input.to_index(&next_positions[0]), environment.input.to_index(&next_positions[1])];
                let di = if di_counts[1].1 == 0 || !building[indexs[0]] || building[indexs[0]] && building[indexs[1]] {
                    let di = di_counts[0].0;
                    di_counts[0].1 -= 1;
                    if di_counts[0].1 < di_counts[1].1 {
                        let tmp = di_counts[0];
                        di_counts[0] = di_counts[1];
                        di_counts[1] = tmp;
                    }
                    di
                } else {
                    let di = di_counts[1].0;
                    di_counts[1].1 -= 1;
                    di
                };
                position += DIRS[di];
                cost_diff += if building[environment.input.to_index(&position)] {
                    2 * (num_bomb + 1) * (num_bomb + 1)
                } else {
                    (num_bomb + 1) * (num_bomb + 1)
                }
            }

            // use or buy
            match plan {
                Plan::Bomb { bi, position } => {
                    let Position { h, w } = position;
                    building &= &!(&environment.bombsss[*h][*w][*bi]);
                    num_bomb -= 1;
                }
                Plan::Buy { position: _ } => {
                    for future_plan in self.plans.iter().skip(pi + 1) {
                        match future_plan {
                            Plan::Bomb { bi: _, position: _ } => {
                                // cost_diff += environment.input.bombs[*bi].cost;
                                num_bomb += 1;
                            }
                            Plan::Buy { position: _ } => break,
                        }
                    }
                }
            }
        }

        cost_diff
    }

    fn compute_cost(&self, environment: &Environment) -> i32 {
        let mut cost = 0;
        let mut building = environment.initial_building.clone();
        let mut position = Position { h: SH, w: SW };
        let mut num_bomb = 0;
        for (pi, plan) in self.plans.iter().enumerate() {
            // move
            let next_position = match plan {
                Plan::Bomb { bi: _, position } => position,
                Plan::Buy { position } => position,
            };
            let (ud_di, ud_count) = if position.h > next_position.h {
                (U, position.h - next_position.h)
            } else {
                (D, next_position.h - position.h)
            };
            let (lr_di, lr_count) = if position.w > next_position.w {
                (L, position.w - next_position.w)
            } else {
                (R, next_position.w - position.w)
            };
            let mut di_counts = if ud_count > lr_count {
                [(ud_di, ud_count), (lr_di, lr_count)]
            } else {
                [(lr_di, lr_count), (ud_di, ud_count)]
            };
            while di_counts[0].1 > 0 {
                let next_positions = [position + DIRS[di_counts[0].0], position + DIRS[di_counts[1].0]];
                let indexs = [environment.input.to_index(&next_positions[0]), environment.input.to_index(&next_positions[1])];
                let di = if di_counts[1].1 == 0 || !building[indexs[0]] || building[indexs[0]] && building[indexs[1]] {
                    let di = di_counts[0].0;
                    di_counts[0].1 -= 1;
                    if di_counts[0].1 < di_counts[1].1 {
                        let tmp = di_counts[0];
                        di_counts[0] = di_counts[1];
                        di_counts[1] = tmp;
                    }
                    di
                } else {
                    let di = di_counts[1].0;
                    di_counts[1].1 -= 1;
                    di
                };
                position += DIRS[di];
                cost += if building[environment.input.to_index(&position)] {
                    2 * (num_bomb + 1) * (num_bomb + 1)
                } else {
                    (num_bomb + 1) * (num_bomb + 1)
                }
            }

            // use or buy
            match plan {
                Plan::Bomb { bi, position } => {
                    let Position { h, w } = position;
                    building &= &!(&environment.bombsss[*h][*w][*bi]);
                    num_bomb -= 1;
                }
                Plan::Buy { position: _ } => {
                    for future_plan in self.plans.iter().skip(pi + 1) {
                        match future_plan {
                            Plan::Bomb { bi, position: _ } => {
                                cost += environment.input.bombs[*bi].cost;
                                num_bomb += 1;
                            }
                            Plan::Buy { position: _ } => break,
                        }
                    }
                }
            }
        }

        cost
    }

    fn compute_score(&self, environment: &Environment) -> i32 {
        let cost = self.compute_cost(environment);
        10.max((1e12f64 / (1e4f64 + cost as f64)).floor() as i32)
    }

    fn compute_output(&self, environment: &Environment) -> Output {
        let mut output = vec![];
        let mut building = environment.initial_building.clone();
        let mut position = Position { h: SH, w: SW };
        for (pi, plan) in self.plans.iter().enumerate() {
            // move
            let next_position = match plan {
                Plan::Bomb { bi: _, position } => position,
                Plan::Buy { position } => position,
            };
            let (ud_di, ud_count) = if position.h > next_position.h {
                (U, position.h - next_position.h)
            } else {
                (D, next_position.h - position.h)
            };
            let (lr_di, lr_count) = if position.w > next_position.w {
                (L, position.w - next_position.w)
            } else {
                (R, next_position.w - position.w)
            };
            let mut di_counts = if ud_count > lr_count {
                [(ud_di, ud_count), (lr_di, lr_count)]
            } else {
                [(lr_di, lr_count), (ud_di, ud_count)]
            };
            while di_counts[0].1 > 0 {
                let next_positions = [position + DIRS[di_counts[0].0], position + DIRS[di_counts[1].0]];
                let indexs = [environment.input.to_index(&next_positions[0]), environment.input.to_index(&next_positions[1])];
                let di = if di_counts[1].1 > 0 && building[indexs[0]] && !building[indexs[1]] {
                    let di = di_counts[1].0;
                    di_counts[1].1 -= 1;
                    di
                } else {
                    let di = di_counts[0].0;
                    di_counts[0].1 -= 1;
                    if di_counts[0].1 < di_counts[1].1 {
                        let tmp = di_counts[0];
                        di_counts[0] = di_counts[1];
                        di_counts[1] = tmp;
                    }
                    di
                };
                position += DIRS[di];
                output.push(Command::Move { di });
            }

            // use or buy
            match plan {
                Plan::Bomb { bi, position } => {
                    let Position { h, w } = position;
                    building &= &!(&environment.bombsss[*h][*w][*bi]);
                    output.push(Command::Use { bi: *bi });
                }
                Plan::Buy { position } => {
                    for future_plan in self.plans.iter().skip(pi + 1) {
                        match future_plan {
                            Plan::Bomb { bi, position: _ } => {
                                output.push(Command::Buy { bi: *bi });
                            }
                            Plan::Buy { position: _ } => break,
                        }
                    }
                }
            }
        }
        output
    }

    fn compute_cost_djikstra(&self, environment: &Environment) -> i32 {
        let mut cost = 0;
        let mut building = environment.initial_building.clone();
        let mut position = Position { h: SH, w: SW };
        let mut num_bomb = 0;
        for (pi, plan) in self.plans.iter().enumerate() {
            // move
            let next_position = match plan {
                Plan::Bomb { bi: _, position } => position,
                Plan::Buy { position } => position,
            };
            let (cost_diff, _) = djikstra(&position, next_position, &building, num_bomb, false, environment);
            cost += cost_diff;
            position = *next_position;

            // use or buy
            match plan {
                Plan::Bomb { bi, position } => {
                    let Position { h, w } = position;
                    building &= &!(&environment.bombsss[*h][*w][*bi]);
                    num_bomb -= 1;
                }
                Plan::Buy { position: _ } => {
                    for future_plan in self.plans.iter().skip(pi + 1) {
                        match future_plan {
                            Plan::Bomb { bi, position: _ } => {
                                cost += environment.input.bombs[*bi].cost;
                                num_bomb += 1;
                            }
                            Plan::Buy { position: _ } => break,
                        }
                    }
                }
            }
        }

        cost
    }

    fn compute_score_djikstra(&self, environment: &Environment) -> i32 {
        let cost = self.compute_cost_djikstra(environment);
        10.max((1e12f64 / (1e4f64 + cost as f64)).floor() as i32)
    }

    fn compute_output_djikstra(&self, environment: &Environment) -> Output {
        let mut output = vec![];
        let mut building = environment.initial_building.clone();
        let mut position = Position { h: SH, w: SW };
        let mut num_bomb = 0;
        for (pi, plan) in self.plans.iter().enumerate() {
            // move
            let next_position = match plan {
                Plan::Bomb { bi: _, position } => position,
                Plan::Buy { position } => position,
            };
            let (_, mut commands) = djikstra(&position, next_position, &building, num_bomb, true, environment);
            output.append(&mut commands);
            position = *next_position;

            // use or buy
            match plan {
                Plan::Bomb { bi, position } => {
                    let Position { h, w } = position;
                    building &= &!(&environment.bombsss[*h][*w][*bi]);
                    num_bomb -= 1;
                    output.push(Command::Use { bi: *bi });
                }
                Plan::Buy { position } => {
                    for future_plan in self.plans.iter().skip(pi + 1) {
                        match future_plan {
                            Plan::Bomb { bi, position: _ } => {
                                output.push(Command::Buy { bi: *bi });
                                num_bomb += 1;
                            }
                            Plan::Buy { position: _ } => break,
                        }
                    }
                }
            }
        }
        output
    }
    fn compute_cost_simple(&self, environment: &Environment) -> i32 {
        let mut cost = 0;
        let mut building = environment.initial_building.clone();
        let mut position = Position { h: SH, w: SW };
        let mut num_bomb = 0;
        for (pi, plan) in self.plans.iter().enumerate() {
            // move
            let next_position = match plan {
                Plan::Bomb { bi: _, position } => position,
                Plan::Buy { position } => position,
            };
            let (di, count) = if position.h > next_position.h {
                (U, position.h - next_position.h)
            } else {
                (D, next_position.h - position.h)
            };
            let position_diff = DIRS[di];
            for _ in 0..count {
                position += position_diff;
                let index = environment.input.to_index(&position);
                if building[index] {
                    cost += 2 * (num_bomb + 1) * (num_bomb + 1);
                } else {
                    cost += (num_bomb + 1) * (num_bomb + 1);
                }
            }
            let (di, count) = if position.w > next_position.w {
                (L, position.w - next_position.w)
            } else {
                (R, next_position.w - position.w)
            };
            let position_diff = DIRS[di];
            for _ in 0..count {
                position += position_diff;
                let index = environment.input.to_index(&position);
                if building[index] {
                    cost += 2 * (num_bomb + 1) * (num_bomb + 1);
                } else {
                    cost += (num_bomb + 1) * (num_bomb + 1);
                }
            }

            // use or buy
            match plan {
                Plan::Bomb { bi, position } => {
                    let Position { h, w } = position;
                    building &= &!(&environment.bombsss[*h][*w][*bi]);
                    num_bomb -= 1;
                }
                Plan::Buy { position } => {
                    for future_plan in self.plans.iter().skip(pi + 1) {
                        match future_plan {
                            Plan::Bomb { bi, position } => {
                                cost += environment.input.bombs[*bi].cost;
                                num_bomb += 1;
                            }
                            Plan::Buy { position } => break,
                        }
                    }
                }
            }
        }

        cost
    }
    fn compute_score_simple(&self, environment: &Environment) -> i32 {
        let cost = self.compute_cost_simple(environment);
        10.max((1e12f64 / (1e4f64 + cost as f64)).floor() as i32)
    }

    fn compute_output_simple(&self) -> Output {
        let mut output = vec![];
        let mut now_position = Position { h: SH, w: SW };
        for (pi, plan) in self.plans.iter().enumerate() {
            // move
            let next_position = match plan {
                Plan::Bomb { bi, position } => position,
                Plan::Buy { position } => position,
            };
            let (di, count) = if now_position.h > next_position.h {
                (U, now_position.h - next_position.h)
            } else {
                (D, next_position.h - now_position.h)
            };
            for _ in 0..count {
                output.push(Command::Move { di });
            }
            let (di, count) = if now_position.w > next_position.w {
                (L, now_position.w - next_position.w)
            } else {
                (R, next_position.w - now_position.w)
            };
            for _ in 0..count {
                output.push(Command::Move { di });
            }
            now_position = *next_position;

            // use or buy
            match plan {
                Plan::Bomb { bi, position } => {
                    output.push(Command::Use { bi: *bi });
                }
                Plan::Buy { position } => {
                    for future_plan in self.plans.iter().skip(pi + 1) {
                        match future_plan {
                            Plan::Bomb { bi, position } => {
                                output.push(Command::Buy { bi: *bi });
                            }
                            Plan::Buy { position } => break,
                        }
                    }
                }
            }
        }
        output
    }

    fn compute_building(&self, end_pi: usize, environment: &Environment) -> BitSet {
        let mut building = environment.initial_building.clone();
        for (pi, plan) in self.plans.iter().enumerate() {
            if pi == end_pi {
                break;
            }

            // use or buy
            match plan {
                Plan::Bomb { bi, position } => {
                    let Position { h, w } = position;
                    building &= &!(&environment.bombsss[*h][*w][*bi]);
                }
                Plan::Buy { position } => (),
            }
        }

        building
    }

    fn compute_available_shops(&self, end_pi: usize, environment: &Environment) -> Vec<usize> {
        let mut shops = vec![];
        let building = self.compute_building(end_pi, environment);
        for (si, shop) in environment.shops.iter().enumerate() {
            let index = environment.input.to_index(shop);
            if building[index] {
                shops.push(si);
            }
        }
        shops
    }

    fn compute_shop_pis(&self) -> Vec<usize> {
        let mut shop_pis = vec![];
        for (pi, plan) in self.plans.iter().enumerate() {
            if let Plan::Buy { position: _} = plan {
                shop_pis.push(pi);
            }
        }
        shop_pis
    }

    /// 爆破計画を前倒しした時に寄る予定だった店が爆破されていないかを確認する
    fn check_can_move_bomb(&self, from_pi: usize, to_pi: usize, environment: &Environment) -> bool {
        assert!(from_pi > to_pi);
        let bomb_plan = &self.plans[from_pi];
        match bomb_plan {
            Plan::Bomb { bi, position: bomb_position } => {
                let Position { h, w } = bomb_position;
                let bomb = &environment.bombsss[*h][*w][*bi];
                for plan in self.plans[to_pi..from_pi].iter() {
                    if let Plan::Buy { position } = plan {
                        let index = environment.input.to_index(position);
                        if bomb[index] {
                            return false;
                        }
                    }
                }
            }
            Plan::Buy { position: _ } => unreachable!(),
        }
        true
    }

    /// 買う計画を後ろ倒しした時にその店がすでに爆破されていないかを確認する
    fn check_can_move_shop(&self, from_pi: usize, to_pi: usize, environment: &Environment) -> bool {
        assert!(from_pi < to_pi);
        let buy_plan = &self.plans[from_pi];
        match buy_plan {
            Plan::Buy { position: buy_position} => {
                let index = environment.input.to_index(buy_position);
                for plan in self.plans[from_pi + 1..to_pi+1].iter() {
                    if let Plan::Bomb { bi, position } = plan {
                        let Position { h, w } = position;
                        let bomb = &environment.bombsss[*h][*w][*bi];
                        if bomb[index] {
                            return false;
                        }
                    }
                }
            }
            Plan::Bomb { bi: _, position: _ } => unreachable!(),
        }
        true
    }
}

fn gen_annealing_state(
    xor_shift: &mut XorShift,
    environment: &Environment,
) -> AnnealingState {
    let mut construction_state = ConstructionState::new(environment.input);
    let greedy_action = GreedyAction { };
    loop {
        let ok = greedy_action.apply(&mut construction_state, &environment);
        if !ok {
            break;
        }
    }

    let count = construction_state.building.count_ones();
    if count == 0 {
        let mut plans = construction_state.plans;
        let si = xor_shift.next(environment.shops.len() as u32) as usize;
        plans.insert(
            0,
            Plan::Buy {
                position: environment.shops[si],
            },
        );
        AnnealingState { plans, redo_start_pi: NIL, redo_end_pi: NIL, undo_start_pi: NIL, undo_end_pi: NIL }
    } else {
        unreachable!();
    }
}

struct Environment<'a> {
    bombsss: Vec<Vec<Vec<BitSet>>>,
    shops: Vec<Position>,
    initial_building: BitSet,
    input: &'a Input,
}

impl<'a> Environment<'a> {
    fn new(input: &'a Input) -> Self {
        Self {
            bombsss: gen_bombsss(input),
            shops: gen_shops(input),
            initial_building: input.gen_initial_building(),
            input,
        }
    }
}

#[derive(Debug)]
struct ConstructionState {
    plans: Vec<Plan>,
    building: BitSet,
    bomb_usedsss: [[[bool; NUM_BOMB]; GRID_SIZE]; GRID_SIZE],
}

impl ConstructionState {
    fn new(input: &Input) -> Self {
        Self {
            plans: vec![],
            building: input.gen_initial_building(),
            bomb_usedsss: [[[false; NUM_BOMB]; GRID_SIZE]; GRID_SIZE],
        }
    }

    fn apply_plan(&mut self, plan: Plan, environment: &Environment) {
        if let Plan::Bomb { bi, position } = plan {
            let Position { h, w } = position;
            self.building &= &!(&environment.bombsss[h][w][bi]);
        }
        self.plans.push(plan);
    }
}

trait Action<S, E> {
    fn apply(&self, state: &mut S, environment: &E) -> bool;
}

struct GreedyAction { }

impl<'a> Action<ConstructionState, Environment<'a>> for GreedyAction {
    fn apply(&self, state: &mut ConstructionState, environment: &Environment) -> bool {
        let mut max_efficiency = 0.0;
        let mut max_posision = Position { h: NIL, w: NIL };
        let mut max_bi = NIL;
        for h in 0..environment.input.grid_size {
            for w in 0..environment.input.grid_size {
                for bi in 0..environment.input.num_bomb {
                    if state.bomb_usedsss[h][w][bi] {
                        continue;
                    }
                    let bitset = &state.building & &environment.bombsss[h][w][bi];
                    let count = bitset.count_ones();
                    let cost = environment.input.bombs[bi].cost;
                    let efficiency = count as f64 / cost as f64;
                    if efficiency > max_efficiency {
                        max_efficiency = efficiency;
                        max_posision = Position { h, w };
                        max_bi = bi;
                    }
                }
            }
        }

        if max_bi == NIL {
            false
        } else {
            let Position { h, w } = max_posision;
            state.bomb_usedsss[h][w][max_bi] = true;
            let plan = Plan::Bomb {
                bi: max_bi,
                position: max_posision,
            };
            state.apply_plan(plan, environment);
            true
        }
    }
}

fn gen_bombsss(input: &Input) -> Vec<Vec<Vec<BitSet>>> {
    let mut bitsetsss = vec![];
    for h in 0..input.grid_size {
        let mut bitsetss = vec![];
        for w in 0..input.grid_size {
            let base_position = Position { h, w };
            let mut bitsets = vec![];
            for bomb in input.bombs.iter() {
                let mut bitset = BitSet::new(input.grid_size * input.grid_size);
                for &position in bomb.positions.iter() {
                    let p = base_position + position;
                    if input.in_grid(&p) {
                        let index = input.to_index(&p);
                        bitset.set(index, true);
                    }
                }
                bitsets.push(bitset);
            }
            bitsetss.push(bitsets);
        }
        bitsetsss.push(bitsetss);
    }
    bitsetsss
}

fn gen_shops(input: &Input) -> Vec<Position> {
    let mut shops = vec![];
    for h in 0..input.grid_size {
        for w in 0..input.grid_size {
            match input.gridss[h][w] {
                Cell::Shop => shops.push(Position { h, w }),
                _ => (),
            }
        }
    }
    shops
}

trait Neighbor {
    fn redo(&mut self, environment: &Environment, annealing_state: &mut AnnealingState);
    fn undo(&mut self, environment: &Environment, annealing_state: &mut AnnealingState);
}

struct MoveBombNeighbor {
    from_pi: usize,
    to_pi: usize,
}

impl Neighbor for MoveBombNeighbor {
    fn redo(&mut self, _environment: &Environment, annealing_state: &mut AnnealingState) {
        let plan = annealing_state.plans.remove(self.from_pi);
        match plan {
            Plan::Bomb { bi: _, position: _ } => annealing_state.plans.insert(self.to_pi, plan),
            Plan::Buy { position: _ } => unreachable!(),
        }
        let min_pi = self.from_pi.min(self.to_pi);
        let max_pi = self.from_pi.max(self.to_pi);
        for pi in (0..min_pi).rev() {
            if let Plan::Buy { position } = annealing_state.plans[pi] {
                annealing_state.redo_start_pi = pi;
                break;
            }
        }
        annealing_state.redo_end_pi = annealing_state.plans.len();
        for pi in max_pi + 1..annealing_state.plans.len() {
            if let Plan::Buy { position } = annealing_state.plans[pi] {
                annealing_state.redo_end_pi = pi + 1;
                break;
            }
        }
        annealing_state.undo_start_pi = annealing_state.redo_start_pi;
        annealing_state.undo_end_pi = annealing_state.redo_end_pi;
    }

    fn undo(&mut self, _environment: &Environment, annealing_state: &mut AnnealingState) {
        let plan = annealing_state.plans.remove(self.to_pi);
        match plan {
            Plan::Bomb { bi: _, position: _ } => annealing_state.plans.insert(self.from_pi, plan),
            Plan::Buy { position: _ } => unreachable!(),
        }
    }
}

struct AddShopNeighbor {
    to_pi: usize,
    plan: Plan,
}

impl Neighbor for AddShopNeighbor {
    fn redo(&mut self, environment: &Environment, annealing_state: &mut AnnealingState) {
        match self.plan {
            Plan::Buy { position } => annealing_state.plans.insert(self.to_pi, self.plan.clone()),
            Plan::Bomb { bi: _, position: _ } => unreachable!(),
        }
        for pi in (0..self.to_pi).rev() {
            if let Plan::Buy { position } = annealing_state.plans[pi] {
                annealing_state.redo_start_pi = pi;
                break;
            }
        }
        annealing_state.redo_end_pi = annealing_state.plans.len();
        for pi in self.to_pi + 1..annealing_state.plans.len() {
            if let Plan::Buy { position } = annealing_state.plans[pi] {
                annealing_state.redo_end_pi = pi + 1;
                break;
            }
        }
        annealing_state.undo_start_pi = annealing_state.redo_start_pi;
        annealing_state.undo_end_pi = annealing_state.redo_end_pi - 1;
    }

    fn undo(&mut self, environment: &Environment, annealing_state: &mut AnnealingState) {
        let plan = annealing_state.plans.remove(self.to_pi);
        match plan {
            Plan::Buy { position: _ } => (),
            Plan::Bomb { bi: _, position: _ } => unreachable!(),
        }
    }
}

struct DeleteShopNeighbor {
    from_pi: usize,
    plan: Plan,
}

impl Neighbor for DeleteShopNeighbor {
    fn redo(&mut self, environment: &Environment, annealing_state: &mut AnnealingState) {
        self.plan = annealing_state.plans.remove(self.from_pi);
        match self.plan {
            Plan::Buy { position: _ } => (),
            Plan::Bomb { bi: _, position: _ } => unreachable!(),
        }
        for pi in (0..self.from_pi).rev() {
            if let Plan::Buy { position } = annealing_state.plans[pi] {
                annealing_state.redo_start_pi = pi;
                break;
            }
        }
        annealing_state.redo_end_pi = annealing_state.plans.len();
        for pi in self.from_pi + 1..annealing_state.plans.len() {
            if let Plan::Buy { position } = annealing_state.plans[pi] {
                annealing_state.redo_end_pi = pi + 1;
                break;
            }
        }
        annealing_state.undo_start_pi = annealing_state.redo_start_pi;
        annealing_state.undo_end_pi = annealing_state.redo_end_pi + 1;
    }

    fn undo(&mut self, environment: &Environment, annealing_state: &mut AnnealingState) {
        match self.plan {
            Plan::Buy { position: _ } => (),
            Plan::Bomb { bi: _, position: _ } => unreachable!(),
        }
        annealing_state.plans.insert(self.from_pi, self.plan.clone());
    }
}

struct MoveShopNeighbor {
    from_pi: usize,
    to_pi: usize,
}

impl Neighbor for MoveShopNeighbor {
    fn redo(&mut self, _environment: &Environment, annealing_state: &mut AnnealingState) {
        let plan = annealing_state.plans.remove(self.from_pi);
        match plan {
            Plan::Bomb { bi: _, position: _ } => unreachable!(),
            Plan::Buy { position: _ } => annealing_state.plans.insert(self.to_pi, plan),
        }
        let mut start_pi1 = 0;
        for pi in (0..self.from_pi).rev() {
            if let Plan::Buy { position } = annealing_state.plans[pi] {
                start_pi1 = pi;
                break;
            }
        }
        let mut end_pi1 = annealing_state.plans.len();
        for pi in self.from_pi + 1..annealing_state.plans.len() {
            if let Plan::Buy { position } = annealing_state.plans[pi] {
                end_pi1 = pi + 1;
                break;
            }
        }
        let mut start_pi2 = 0;
        for pi in (0..self.to_pi).rev() {
            if let Plan::Buy { position } = annealing_state.plans[pi] {
                start_pi2 = pi;
                break;
            }
        }
        let mut end_pi2 = annealing_state.plans.len();
        for pi in self.to_pi + 1..annealing_state.plans.len() {
            if let Plan::Buy { position } = annealing_state.plans[pi] {
                end_pi2 = pi + 1;
                break;
            }
        }
        annealing_state.redo_start_pi = start_pi1.min(start_pi2);
        annealing_state.redo_end_pi = end_pi1.max(end_pi2);
        annealing_state.undo_start_pi = annealing_state.redo_start_pi;
        annealing_state.undo_end_pi = annealing_state.redo_end_pi;
    }

    fn undo(&mut self, _environment: &Environment, annealing_state: &mut AnnealingState) {
        let plan = annealing_state.plans.remove(self.to_pi);
        match plan {
            Plan::Bomb { bi: _, position: _ } => unreachable!(),
            Plan::Buy { position: _ } => annealing_state.plans.insert(self.from_pi, plan),
        }
    }
}

struct ChangeShopNeighbor {
    pi: usize,
    from_plan: Plan,
    to_plan: Plan,
}

impl Neighbor for ChangeShopNeighbor {
    fn redo(&mut self, environment: &Environment, annealing_state: &mut AnnealingState) {
        self.from_plan = annealing_state.plans[self.pi].clone();
        match self.from_plan {
            Plan::Buy { position: _ } => (),
            Plan::Bomb { bi: _, position: _ } => unreachable!(),
        }
        annealing_state.plans[self.pi] = self.to_plan.clone();
        annealing_state.redo_start_pi = self.pi;
        annealing_state.redo_end_pi = self.pi + 2;
        annealing_state.undo_start_pi = annealing_state.redo_start_pi;
        annealing_state.undo_end_pi = annealing_state.redo_end_pi;
    }

    fn undo(&mut self, environment: &Environment, annealing_state: &mut AnnealingState) {
        match self.from_plan {
            Plan::Buy { position: _ } => (),
            Plan::Bomb { bi: _, position: _ } => unreachable!(),
        }
        annealing_state.plans[self.pi] = self.from_plan.clone();
    }
}

fn gen_neighbor(
    environment: &Environment,
    annealing_state: &AnnealingState,
    xor_shift: &mut XorShift,
) -> Box<dyn Neighbor> {
    // let probs = [0.6, 0.7, 0.8, 0.9, 1.0];
    let probs = [0.4, 0.55, 0.7, 0.85, 1.0];
    loop {
        let prob = xor_shift.next_u32() as f64 / std::u32::MAX as f64;
        if prob < probs[0] {
            // MoveBombNeighbor
            // eprintln!("MoveBombNeighbor");
            let l = annealing_state.plans.len();
            let mut from_pi;
            loop {
                from_pi = 1 + xor_shift.next(l as u32 - 1) as usize;
                if let Plan::Bomb { bi: _, position: _ } = annealing_state.plans[from_pi] {
                    break;
                }
            }
            let mut to_pi;
            loop {
                to_pi = 1 + xor_shift.next(l as u32 - 1) as usize;
                if to_pi != from_pi {
                    break;
                }
            }
            if from_pi < to_pi || annealing_state.check_can_move_bomb(from_pi, to_pi, environment) {
                return Box::new(MoveBombNeighbor { from_pi, to_pi });
            } else {
                continue;
            }
        } else if prob < probs[1] {
            // AddShopNeighbor
            // eprintln!("AddShopNeighbor");
            let mut to_pi;
            let mut plan;
            loop {
                to_pi = 1 + xor_shift.next(annealing_state.plans.len() as u32 - 2) as usize;
                let available_shops = annealing_state.compute_available_shops(to_pi, environment);
                if !available_shops.is_empty() {
                    let i = xor_shift.next(available_shops.len() as u32) as usize;
                    let si = available_shops[i];
                    plan = Plan::Buy { position: environment.shops[si] };
                    break;
                }
            }
            return Box::new(AddShopNeighbor { to_pi, plan });
        } else if prob < probs[2] {
            // DeleteShopNeighbor
            // eprintln!("DeleteShopNeighbor");
            let shop_pis = annealing_state.compute_shop_pis();
            if shop_pis.len() <= 1 {
                continue;
            }
            let i = 1 + xor_shift.next(shop_pis.len() as u32 - 1) as usize;
            let from_pi = shop_pis[i];
            let plan = Plan::Buy { position: Position { h: NIL, w: NIL } }; // dummy plan
            return Box::new(DeleteShopNeighbor { from_pi, plan });
        } else if prob < probs[3] {
            // MoveShopNeighbor
            // eprintln!("MoveShopNeighbor");
            let shop_pis = annealing_state.compute_shop_pis();
            if shop_pis.len() <= 1 {
                continue;
            }
            let fi = 1 + xor_shift.next(shop_pis.len() as u32 - 1) as usize;
            let from_pi = shop_pis[fi];
            let mut to_pi;
            loop {
                to_pi = 1 + xor_shift.next(annealing_state.plans.len() as u32 - 1) as usize;
                if to_pi != from_pi {
                    break;
                }
            }
            if from_pi > to_pi || annealing_state.check_can_move_shop(from_pi, to_pi, environment) {
                return Box::new(MoveShopNeighbor { from_pi, to_pi });
            } else {
                continue;
            }
        } else if prob < probs[4] {
            // ChangeShopNeighbor
            // eprintln!("ChangeShopNeighbor");
            let shop_pis = annealing_state.compute_shop_pis();
            let i = xor_shift.next(shop_pis.len() as u32) as usize;
            let pi = shop_pis[i];
            let available_shops = annealing_state.compute_available_shops(pi, environment);
            if available_shops.len() <= 1 {
                continue;
            }
            let from_plan = annealing_state.plans[pi].clone();
            match from_plan {
                Plan::Buy { position } => {
                    let mut to_position;
                    loop {
                        let i = xor_shift.next(available_shops.len() as u32) as usize;
                        let si = available_shops[i].clone();
                        to_position = environment.shops[si];
                        if to_position != position {
                            break;
                        }
                    }
                    let to_plan = Plan::Buy { position: to_position };
                    return Box::new(ChangeShopNeighbor { pi, from_plan, to_plan });
                }
                Plan::Bomb { bi: _, position: _ } => unreachable!(),
            }
        } else {
            unreachable!();
        }
    }
}

fn annealing(
    environment: &Environment,
    initial_state: AnnealingState,
    duration: f64,
    temp_start: f64,
    temp_end: f64,
    xor_shift: &mut XorShift,
) -> AnnealingState {
    let mut state = initial_state.clone();
    let mut cost = state.compute_cost(environment);
    let mut best_state = state.clone();
    let mut best_cost = cost;
    let init_cost = cost;

    let mut all_iter = 0;
    let mut valid_iter = 0;
    let mut accepted_count = 0;
    let mut update_count = 0;

    let duration_inv = 1.0 / duration;
    let start_time = get_time();

    let mut temp_inv = 1.0 / temp_start;

    loop {
        all_iter += 1;
        if (all_iter & ((1 << 10) - 1)) == 0 {
            let t = (get_time() - start_time) * duration_inv;
            let temp = temp_start.powf(1.0 - t) * temp_end.powf(t);
            temp_inv = 1.0 / temp;
            if t >= 1.0 {
                break;
            }
        }

        let mut neighbor = gen_neighbor(environment, &state, xor_shift);
        neighbor.redo(environment, &mut state);
        let mut cost_diff = state.compute_cost_diff(environment, true);
        neighbor.undo(environment, &mut state);
        cost_diff -= state.compute_cost_diff(environment, false);

        if cost_diff <= 0
            || xor_shift.next_u32() as f64 / (std::u32::MAX as f64)
                < f64::exp(-cost_diff as f64 * temp_inv)
        {
            neighbor.redo(environment, &mut state);
            cost += cost_diff;
            accepted_count += 1;

            if cost < best_cost {
                best_cost = cost;
                best_state = state.clone();
                update_count += 1;
            }
        }

        valid_iter += 1;
    }

    eprintln!("===== annealing =====");
    eprintln!("init cost  : {}", init_cost);
    eprintln!("cost       : {}", best_cost);
    eprintln!("all iter   : {}", all_iter);
    eprintln!("valid iter : {}", valid_iter);
    eprintln!("accepted   : {}", accepted_count);
    eprintln!("updated    : {}", update_count);
    eprintln!("");

    best_state
}

fn solve(input: &Input) -> Output {
    let mut xor_shift = XorShift::new(SEED);
    let environment = Environment::new(input);
    let annealing_state = gen_annealing_state(&mut xor_shift, &environment);
    let duration = TIME_LIMIT - get_time();
    let temp_start = 5000f64;
    let temp_end = 1f64;
    let annealed_state = annealing(
        &environment,
        annealing_state,
        duration,
        temp_start,
        temp_end,
        &mut xor_shift,
    );
    let score = annealed_state.compute_score_djikstra(&environment);
    debug!(score);
    annealed_state.compute_output_djikstra(&environment)
}

fn print_output(output: &Output) {
    // eprintln!("{}", output.len());
    println!("{}", output.len());
    for e in output.iter() {
        // eprintln!("{}", e);
        println!("{}", e);
    }
}

fn main() {
    get_time();

    let input = Input::read();
    let output = solve(&input);
    print_output(&output);

    eprintln!("time_elapsed: {:.3}", get_time());
}

#[cfg(test)]
mod tests {
    use crate::Position;

    #[test]
    fn position_add() {
        let p1 = Position { h: 10, w: 10 };
        let p2 = Position {
            h: 1usize.wrapping_neg(),
            w: 2usize.wrapping_neg(),
        };
        let p3 = p1 + p2;
        assert_eq!(p3, Position { h: 9, w: 8 });
    }
}