#![allow(non_snake_case, unused)]

use std::io::*;
use std::{collections::*, fmt::format};
use std::{cmp::*, vec};
use crate::input::{*, marker::*};
use crate::rand::Xoshiro256;

const N: usize = 60;
const H: i64 = 1500;
const INF: i64 = 1_000_000_000;
const TL: f64 = 2.9;
const DIJ: [(usize, usize); 4] = [(!0, 0), (1, 0), (0, !0), (0, 1)];
const DIR: [char; 4] = ['U', 'D', 'L', 'R'];
// Actionは，(行動の種類, 方向)で持つ
type Action = (char, usize);

pub 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;
        }
        // ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 1.5
        }
        #[cfg(not(feature = "local"))]
        {
            (ms - STIME)
        }
    }
}

// コピペで使える proconio もどき
// cunitacさんからお借りしています
// https://gist.github.com/cunitac/b00be62bf68c9fb6055d22eb77c17e14
pub mod input {
    use std::{
        cell::RefCell,
        fmt::Debug,
        io::{stdin, BufRead, BufReader, Stdin},
        str::{FromStr, SplitWhitespace},
    };

    thread_local!(
        pub static STDIN_SOURCE: RefCell<Source> = RefCell::new(Source {
            stdin: BufReader::new(stdin()),
            tokens: "".split_whitespace(),
        });
    );

    pub struct Source {
        stdin: BufReader<Stdin>,
        tokens: SplitWhitespace<'static>,
    }
    impl Source {
        pub fn next_token(&mut self) -> Option<&str> {
            self.tokens.next().or_else(|| {
                let mut input = String::new();
                self.stdin.read_line(&mut input).unwrap();
                self.tokens = Box::leak(input.into_boxed_str()).split_whitespace();
                self.tokens.next()
            })
        }
    }
    #[macro_export]
    macro_rules! read_value {
        (from $s:expr, [$t:tt; $n:expr]) => {
            (0..$n).map(|_| $crate::read_value!(from $s, $t)).collect::<Vec<_>>()
        };
        (from $s:expr, [$t:tt]) => {
            let n = $crate::read_value!(from $s, usize);
            $crate::read_value!(from $s, [$t; n])
        };
        (from $s:expr, $t:ty) => {
            <$t as $crate::input::Readable>::read(&mut $s)
        };
        (from $s:expr, $($t:tt),* $(,)?) => {
            ($($crate::read_value!(from $s, $t)),*)
        };
        ($($r:tt)*) => {
            $crate::input::STDIN_SOURCE.with(|s| {
                let mut s = s.borrow_mut();
                $crate::read_value!(from s, $($r)*)
            })
        }
    }
    #[macro_export]
    macro_rules! input {
        () => {
        };
        ($x:tt: $t:tt, $($r:tt)*) => {
            let $x = $crate::read_value!($t);
            $crate::input!($($r)*);
        };
        (mut $x:tt: $t:tt, $($r:tt)*) => {
            let mut $x = $crate::read_value!($t);
            $crate::input!($($r)*);
        };
        (from $s:expr, $x:tt, $t:tt, $($r:tt)*) => {
            let $x = $crate::read_value!(from $s, $t);
            $crate::input!(from $s, $($r)*);
        };
        (from $s:expr, mut $x:tt, $t:tt, $($r:tt)*) => {
            let mut $x = $crate::read_value!(from $s, $t);
            $crate::input!(from $s, $($r)*);
        };
        ($($r:tt)*) => {
            $crate::input!($($r)*,);
        };
    }
    pub trait Readable {
        type Output;
        fn read(source: &mut Source) -> Self::Output;
    }
    impl<T: FromStr<Err = E>, E: Debug> Readable for T {
        type Output = T;
        fn read(source: &mut Source) -> T {
            source.next_token().unwrap().parse().unwrap()
        }
    }
    pub mod marker {
        macro_rules! impl_readable {
            ($e:ident, $t:ty, $u:ty, $f:expr) => {
                pub enum $e {}
                impl $crate::input::Readable for $e {
                    type Output = $t;
                    fn read(mut source: &mut $crate::input::Source) -> $t {
                        $f($crate::read_value!(from source, $u))
                    }
                }
            };
        }
        impl_readable!(Usize1, usize, usize, |x| x - 1);
        impl_readable!(Isize1, isize, isize, |x| x - 1);
        impl_readable!(Chars, Vec<char>, String, |x: String| x.chars().collect());
        impl_readable!(Bytes, Vec<u8>, String, |x: String| x.bytes().collect());
    }
}

mod rand {
    pub(crate) struct Xoshiro256 {
        s0: u128,
        s1: u128,
        s2: u128,
        s3: u128,
    }

    impl Xoshiro256 {
        pub(crate) fn new(mut seed: u128) -> Self {
            let s0 = split_mix_128(&mut seed);
            let s1 = split_mix_128(&mut seed);
            let s2 = split_mix_128(&mut seed);
            let s3 = split_mix_128(&mut seed);
            Self { s0, s1, s2, s3 }
        }

        fn next(&mut self) -> u128 {
            let result = (self.s1.wrapping_mul(5)).rotate_left(7).wrapping_mul(9);
            let t = self.s1 << 17;

            self.s2 ^= self.s0;
            self.s3 ^= self.s1;
            self.s1 ^= self.s2;
            self.s0 ^= self.s3;
            self.s2 ^= t;
            self.s3 = self.s3.rotate_left(45);

            result
        }

        pub(crate) fn gen_usize(&mut self, lower: usize, upper: usize) -> usize {
            assert!(lower < upper);
            let count = upper - lower;
            (self.next() % count as u128) as usize + lower
        }

        pub(crate) fn gen_i64(&mut self, lower: i64, upper: i64) -> i64 {
            assert!(lower < upper);
            let count = upper - lower;
            (self.next() % count as u128) as i64 + lower
        }

        pub(crate) fn gen_u128(&mut self, lower: u128, upper: u128) -> u128 {
            assert!(lower < upper);
            let count = upper - lower;
            (self.next() % count as u128) as u128 + lower
        }

        pub(crate) fn gen_f64(&mut self) -> f64 {
            const UPPER_MASK: u128 = 0x3ff0000000000000;
            const LOWER_MASK: u128 = 0xfffffffffffff;
            let result = (UPPER_MASK | (self.next() & LOWER_MASK)) as u64;
            let result: f64 = unsafe { std::mem::transmute(result) };
            result - 1.0
        }

        pub(crate) fn gen_bool(&mut self, prob: f64) -> bool {
            self.gen_f64() < prob
        }
    }

    fn split_mix_128(x: &mut u128) -> u128 {
        *x = x.wrapping_add(0x9e3779b97f4a7c15);
        let mut z = *x;
        z = (z ^ z >> 30).wrapping_mul(0xbf58476d1ce4e5b9);
        z = (z ^ z >> 27).wrapping_mul(0x94d049bb133111eb);
        z ^ z >> 31
    }
}

const TRUE: &'static bool = &true;
const FALSE: &'static bool = &false;
#[derive(Clone, Debug)]
/// Efficient bool collection
pub struct BitSet {
    buf: Vec<u64>,
    size: usize,
}
impl BitSet {
    #[allow(dead_code)]
    pub fn new(size: usize) -> BitSet {
        BitSet {
            buf: vec![0; (size + 63) / 64],
            size: size,
        }
    }
    #[allow(dead_code)]
    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));
        }
    }
    #[allow(dead_code)]
    pub fn count_ones(&self) -> usize {
        let sum: u32 = self.buf.iter().map(|x| x.count_ones()).sum();
        sum as usize
    }
    #[allow(dead_code)]
    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;
    fn index(&self, index: usize) -> &bool {
        [FALSE, TRUE][(self.buf[index >> 6] >> (index & 63)) as usize & 1]
    }
}
impl std::ops::ShlAssign<usize> for BitSet {
    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() {
                self.buf[i] = self.buf[i - q];
            }
        } else {
            for i in (q + 1..self.buf.len()).rev() {
                self.buf[i] = (self.buf[i - q] << r) | (self.buf[i - q - 1] >> (64 - r));
            }
            self.buf[q] = self.buf[0] << r;
        }
        for x in &mut self.buf[..q] {
            *x = 0;
        }
        self.chomp();
    }
}
impl std::ops::Shl<usize> for BitSet {
    type Output = Self;
    fn shl(mut self, x: usize) -> Self {
        self <<= x;
        self
    }
}
impl std::ops::ShrAssign<usize> for BitSet {
    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 {
                self.buf[i] = self.buf[i + q];
            }
        } else {
            for i in 0..self.buf.len() - q - 1 {
                self.buf[i] = (self.buf[i + q] >> r) | (self.buf[i + q + 1] << (64 - r));
            }
            let len = self.buf.len();
            self.buf[len - q - 1] = self.buf[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;
    fn shr(mut self, x: usize) -> Self {
        self >>= x;
        self
    }
}
impl<'a> std::ops::BitAndAssign<&'a BitSet> for BitSet {
    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;
    fn bitand(mut self, rhs: &'a Self) -> Self {
        self &= rhs;
        self
    }
}
impl<'a> std::ops::BitOrAssign<&'a BitSet> for BitSet {
    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;
    fn bitor(mut self, rhs: &'a Self) -> Self {
        self |= rhs;
        self
    }
}
impl<'a> std::ops::BitXorAssign<&'a BitSet> for BitSet {
    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;
    fn bitxor(mut self, rhs: &'a Self) -> Self {
        self ^= rhs;
        self
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Position {
    y: i64,
    x: i64,
}

impl Position {
    fn new(y: i64, x: i64) -> Self {
        Self { y, x }
    }
}

#[derive(Clone)]
struct Map {
    N: usize,
    D: i64,
    H: i64,
    S: Vec<Vec<char>>,
    M: usize,
    key: (usize, usize),
    goal: (usize, usize),
    jewelry: Vec<(usize, usize)>,
    gunpowder: Vec<(usize, usize)>,
    wall: Vec<bool>,
    interval_of_probe: Vec<i64>,
}
impl Map {
    fn new() -> Self {
        // 標準入力を受け取る
        input! {
            _N: usize,
            D: i64,
            _H: i64,
        }
        let mut S = vec![];
        for _ in 0..N {
            input! {
                Si: Chars,
            }
            S.push(Si);
        }
        // 鍵，ゴール，宝石，火薬，壁位置を発見しておく
        let mut key = (!0, !0);
        let mut goal = (!0, !0);
        let mut jewelry = vec![];
        let mut gunpowder = vec![];
        let mut wall = vec![false; N*N];
        for y in 0..N {
            for x in 0..N {
                if S[y][x] == '#' {
                    wall[y * N + x] = true;
                } else if S[y][x] == 'K' {
                    key = (y, x);
                } else if S[y][x] == 'G' {
                    goal = (y, x);
                } else if S[y][x] == 'J' {
                    jewelry.push((y, x));
                } else if S[y][x] == 'F' {
                    gunpowder.push((y, x));
                }
            }
        }
        input! {
            M: usize,
        }
        let mut interval_of_probe = vec![0; N*N];
        for _ in 0..M {
            input! {
                y: usize,
                x: usize,
                di: i64,
            }
            interval_of_probe[y * N + x] = di;
        }
        Self { N, D, H, S, M, key, goal, jewelry, gunpowder, wall, interval_of_probe }
    }
}

// 時刻tにおける盤面の状態を保持する構造体
#[derive(Clone)]
struct State<'a> {
    turn: i64,
    is_done: bool,
    evaluated_score: i64, // 評価関数値
    jewelry_map: BitSet, // 宝石位置を表すbitset
    gunpowder_map: BitSet, // 火薬位置を表すbitset
    block_map: BitSet, // ブロック位置を表すbitset
    probe_map: BitSet, // 探知機位置を表すbitset
    pos: (usize, usize), // プレイヤーの現在地の(y, x)
    hp: i64, // プレイヤーの体力
    jewelry: i64, // 宝石の数 (これx10が実際のゲームスコア)
    gunpowder: i64, // 火薬の数
    has_key: bool, // 鍵を持っているかどうか
    search_range: usize, // 次に探しに行く宝石を列挙する数
    search_key_threshold: usize, // 自分から見て鍵のマンハッタン距離がこれ以内なら鍵を優先的に取りに行く
    emergency_hp_threshold_to_key: i64, // 残り体力がこれ以下かつ鍵を持っていなければ鍵へ向かう
    emergency_hp_threshold_to_goal: i64, // 残り体力がこれ以下になったらゴールへ向かう
    output: Vec<(char, char)>, // 出力
    zobrist_hash: u128, // 各マップの状態をなるべく一意に定めるzobrist hash値
    zobrist_hash_map: &'a ZobristHash, // ある座標にプレイヤー･コインがあることを示すハッシュ値を持つ
}
impl<'a> State<'a> {
    fn new(map: &Map, zobrist_hash_map: &'a ZobristHash) -> Self {
        // zobrist_hashを初期化する
        let mut zobrist_hash = 0;
        // 各オブジェクトの位置を表すbitsetを初期化し，位置を記録していく
        let mut jewelry_map = BitSet::new(N * N);
        let mut gunpowder_map = BitSet::new(N * N);
        let mut block_map = BitSet::new(N * N);
        let mut probe_map = BitSet::new(N * N);
        // mapからプレイヤーの初期位置を探す
        let mut pos = (!0, !0);
        for y in 0..N {
            for x in 0..N {
                if map.S[y][x] == 'S' {
                    pos = (y, x);
                    zobrist_hash ^= zobrist_hash_map.player_hash[y][x];
                } else if map.S[y][x] == 'K' {
                    zobrist_hash ^= zobrist_hash_map.key_hash[y][x];
                } else if map.S[y][x] == 'J' {
                    jewelry_map.set(y * N + x, true);
                } else if map.S[y][x] == 'F' {
                    gunpowder_map.set(y * N + x, true);
                } else if map.S[y][x] == 'E' {
                    probe_map.set(y * N + x, true);
                }
            }
        }
        let emergency_hp_threshold_to_key = if map.D == 3 {
            400
        } else if map.D == 4 {
            500
        } else if map.D == 5 {
            600
        } else if map.D == 6 {
            700
        } else {
            800
        };
        let emergency_hp_threshold_to_goal = emergency_hp_threshold_to_key / 2;
        Self {
            turn: 0,
            is_done: false,
            evaluated_score: 0,
            jewelry_map,
            gunpowder_map,
            block_map,
            probe_map,
            jewelry: 0,
            gunpowder: 0,
            has_key: false,
            search_range: 5, // [ToDo] ハードコーディングを辞める
            search_key_threshold: 20, // [ToDo] ハードコーディングを辞める
            emergency_hp_threshold_to_key,
            emergency_hp_threshold_to_goal,
            pos,
            hp: H,
            output: vec![],
            zobrist_hash,
            zobrist_hash_map,
        }
    }
    // 評価関数
    pub fn evaluate_score(&mut self, map: &Map) {
        self.evaluated_score = 0;
        // これまでの獲得宝石数
        self.evaluated_score += self.jewelry;
        // 残りの体力
        self.evaluated_score += self.hp;
        // ターンを無駄にかけることに対してペナルティ
        self.evaluated_score -= self.turn;
        // 鍵の有無やゲームクリアしているかどうかについての評価
        if self.has_key && self.is_done && self.hp >= 0 {
            // 鍵を持っているかつゴールした
            self.evaluated_score += 10000;
        } else if self.has_key && !self.is_done && self.hp >= 0 {
            // 鍵を持っているかつゴールしていない
            self.evaluated_score += 1500;
            // ゴールへの距離が近いほどよいとしたい
            // self.evaluated_score -= self.get_distance_to_destination('G');
            // self.evaluated_score += (500 / self.get_distance_to_destination( 'G'));
            self.evaluated_score -= (self.pos.0.abs_diff(map.goal.0) + self.pos.1.abs_diff(map.goal.1)) as i64;
        } else {
            // それ以外は鍵を持っていないしゴールもしていない
            // 鍵への距離が近いほどよいとしたい
            // self.evaluated_score -= self.get_distance_to_destination('K');
            // self.evaluated_score += (500 / self.get_distance_to_destination('K'));
            self.evaluated_score -= (self.pos.0.abs_diff(map.key.0) + self.pos.1.abs_diff(map.key.1)) as i64;
        }
        // ゴールしてないかつ体力が切れたなら大幅減点
        if !self.is_done && self.hp < 0 {
            self.evaluated_score -= 10000;
            self.is_done = true;
        }
    }
    // 現在地から目的地へのパスをBFSで調べ，経路復元して返す
    pub fn get_path_to_destination(&self, destination: (usize, usize), map: &Map) -> Vec<usize> {
        let mut dist = INF;
        let mut prev = vec![!0; N*N]; // 経路復元
        let mut deque = VecDeque::new();
        let mut visited = vec![vec![false; N]; N];
        deque.push_back((self.pos.0, self.pos.1, 0));
        visited[self.pos.0][self.pos.1] = true;
        while let Some((frm_y, frm_x, dist_frm)) = deque.pop_front() {
            // 目的地なら位置を返す
            if destination.0 ==frm_y && destination.1 == frm_x {
                dist = dist_frm;
                break;
            }
            for d in 0..4 {
                let next_y = frm_y.wrapping_add(DIJ[d].0);
                let next_x = frm_x.wrapping_add(DIJ[d].1);
                // 移動: 範囲内で，訪問済みでも壁でもブロックても探知機でもないなら移動可能
                if next_x < N && next_y < N && !visited[next_y][next_x] && !map.wall[next_y * N + next_x] && !self.block_map[next_y * N + next_x] && !self.probe_map[next_y * N + next_x] {
                    deque.push_back((next_y, next_x, dist_frm + 1));
                    visited[next_y][next_x] = true;
                    prev[next_y * N + next_x] = frm_y * N + frm_x;
                }
            }
        }
        // 経路復元
        let mut path = vec![];
        let mut t = destination.0 * N + destination.1;
        let mut last = (!0, !0);
        while t != !0 {
            if last.0 != !0 && last.1 != !0 {
                // 現在地からlastへ進む方向を取る
                let d = if last.0 > t / N {
                    1
                } else if last.0 < t / N {
                    0
                } else if last.1 > t % N {
                    3
                } else if last.1 < t % N {
                    2
                } else {
                    unreachable!()
                };
                path.push(d);
            }
            last = (t / N, t % N);
            t = prev[t];
        }
        path.reverse();
        path
    }
    // マンハッタン距離の近い宝石の場所上位いくらかとってくる
    // ただし，鍵が近ければ強制的に鍵の場所だけを返す
    pub fn search_target(&self, map: &Map) -> Vec<(usize, usize)> {
        let mut targets = vec![];
        // 鍵が近ければ鍵を返す
        if self.pos.0.abs_diff(map.key.0) + self.pos.1.abs_diff(map.key.1) <= self.search_key_threshold && !self.has_key {
            targets.push((map.key.0, map.key.1));
            return targets;
        }

        // 宝石or火薬
        let mut jewelry_fire = vec![];
        for &(j_y, j_x) in &map.jewelry {
            // 既に取ってるなら飛ばす
            if !self.jewelry_map[j_y * N + j_x] {continue;}
            let d = self.pos.0.abs_diff(j_y) + self.pos.1.abs_diff(j_x);
            jewelry_fire.push((d, (j_y, j_x)));
        }
        for &(g_y, g_x) in &map.gunpowder {
            if !self.gunpowder_map[g_y * N + g_x] {continue;}
            let d = self.pos.0.abs_diff(g_y) + self.pos.1.abs_diff(g_x);
            jewelry_fire.push((d, (g_y, g_x)));
        }
        jewelry_fire.sort();
        for i in 0..self.search_range {
            targets.push((jewelry_fire[i].1));
        }
        targets
    }
    // 1マス進むのをビームサーチの1stepとみなすときの全ての合法手を返す
    pub fn get_legal_actions_of_single_cell(&self, map: &Map) -> Vec<Action> {
        let mut legal_actions = vec![];
        // 上下左右の4方向を調べる
        for d in 0..4 {
            let next_y = self.pos.0.wrapping_add(DIJ[d].0);
            let next_x = self.pos.1.wrapping_add(DIJ[d].1);
            // 移動: 範囲内で，壁でもブロックでも探知機でもないなら移動可能
            if next_x < N && next_y < N && !map.wall[next_y * N + next_x] && !self.block_map[next_y * N + next_x] && !self.probe_map[next_y * N + next_x] {
                // 前回の行動を見て，戻るに相当することをしようとしているなら枝刈りする(LRと動くなど．これはSで代替可能)
                // if self.prev_action.0 == 'M' && (self.prev_action.1 + d) % 4 == 1 {continue;}
                legal_actions.push(('M', d));
            }
            // ブロック生成: 範囲内で，空なら設置可能 (スタート地点も含む)
            if next_x < N && next_y < N && !map.wall[next_y * N + next_x] && !self.block_map[next_y * N + next_x] && !self.probe_map[next_y * N + next_x]
                && !self.jewelry_map[next_y * N + next_x] && !self.gunpowder_map[next_y * N + next_x] && !(next_y == map.goal.0 && next_x == map.goal.1)
                && !(!self.has_key && next_y == map.key.0 && next_x == map.key.1) {
                legal_actions.push(('B', d));
            }
            // ブロック破壊: 範囲内で，ブロックなら破壊可能
            if next_x < N && next_y < N && self.block_map[next_y * N + next_x] {
                legal_actions.push(('B', d));
            }
            // [todo] 火炎放射(=探知機破壊): 範囲内で，火薬があり，上下左右の延長方向に探知機があれば破壊可能
        }
        // 何もしないのは常に合法手
        legal_actions.push(('S', !0));
        legal_actions
    }
    // 宝石or鍵or扉から宝石or鍵or扉へ進むのをビームサーチの1stepとみなすときの全ての合法手を返す
    pub fn get_legal_actions(&self, map: &Map) -> Vec<Vec<Action>> {
        let mut legal_action_list = vec![];
        if self.hp >= self.emergency_hp_threshold_to_key || (self.has_key && self.hp >= self.emergency_hp_threshold_to_goal) {
            // 鍵探索/ゴール到達まで猶予があるなら周囲の宝石を探す
            let targets = self.search_target(map);
            for &(t_y, t_x) in &targets {
                let mut legal_actions = vec![];
                let path = self.get_path_to_destination((t_y, t_x), map);
                for &d in &path {
                    // let next_y = self.pos.0.wrapping_add(DIJ[d].0);
                    // let next_x = self.pos.1.wrapping_add(DIJ[d].1);
                    legal_actions.push(('M', d));
                }
                legal_action_list.push(legal_actions);
            }
        } else if !self.has_key {
            let mut legal_actions = vec![];
            let path = self.get_path_to_destination((map.key.0, map.key.1), map);
            for &d in &path {
                // let next_y = self.pos.0.wrapping_add(DIJ[d].0);
                // let next_x = self.pos.1.wrapping_add(DIJ[d].1);
                legal_actions.push(('M', d));
            }
            legal_action_list.push(legal_actions);
        } else {
            let mut legal_actions = vec![];
            let path = self.get_path_to_destination((map.goal.0, map.goal.1), map);
            for &d in &path {
                // let next_y = self.pos.0.wrapping_add(DIJ[d].0);
                // let next_x = self.pos.1.wrapping_add(DIJ[d].1);
                legal_actions.push(('M', d));
            }
            legal_action_list.push(legal_actions);
        }
        legal_action_list
    }
    // このターンにプレイヤーに当たる探知機の数を見つける
    // [todo] 高速化したい
    fn search_danger_probe(&self, map: &Map) -> i64 {
        let mut num_probe = 0;
        for p in (0..self.pos.0).rev() {
            // 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全
            if map.wall[p * N + self.pos.1] || self.block_map[p * N + self.pos.1] || (self.probe_map[p * N + self.pos.1] && self.turn % map.interval_of_probe[p * N + self.pos.1] != 0) {
                break;
            }
            if self.probe_map[p * N + self.pos.1] && self.turn % map.interval_of_probe[p * N + self.pos.1] == 0 {
                num_probe += 1;
                break;
            }
        }
        for p in self.pos.0+1..N {
            // 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全
            if map.wall[p * N + self.pos.1] || self.block_map[p * N + self.pos.1] || (self.probe_map[p * N + self.pos.1] && self.turn % map.interval_of_probe[p * N + self.pos.1] != 0) {
                break;
            }
            if self.probe_map[p * N + self.pos.1] && self.turn % map.interval_of_probe[p * N + self.pos.1] == 0 {
                num_probe += 1;
                break;
            }
        }
        for p in (0..self.pos.1).rev() {
            // 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全
            if map.wall[self.pos.0 * N + p] || self.block_map[self.pos.0 * N + p] || (self.probe_map[self.pos.0 * N + p] && self.turn % map.interval_of_probe[self.pos.0 * N + p] != 0) {
                break;
            }
            if self.probe_map[self.pos.0 * N + p] && self.turn % map.interval_of_probe[self.pos.0 * N + p] == 0 {
                num_probe += 1;
                break;
            }
        }
        for p in self.pos.1+1..N {
            // 探知機を見つけるまでに先に壁かブロックか作動しない探知機見つかればこのターンは安全
            if map.wall[self.pos.0 * N + p] || self.block_map[self.pos.0 * N + p] || (self.probe_map[self.pos.0 * N + p] && self.turn % map.interval_of_probe[self.pos.0 * N + p] != 0) {
                break;
            }
            if self.probe_map[self.pos.0 * N + p] && self.turn % map.interval_of_probe[self.pos.0 * N + p] == 0 {
                num_probe += 1;
                break;
            }
        }
        num_probe
    }
    // 指定したactionを各マップに施す
    pub fn advance(&mut self, map: &Map, action: Action) {
        // ターン加算
        self.turn += 1;
        // 1ターンで必ず体力を1消耗する
        self.hp -= 1;
        // 行動の種類によって分岐する
        match action.0 {
            'S' => {
                // outputへ入れる
                self.output.push((action.0, 'x'));
            },
            'M' => {
                let d = action.1;
                let next_y = self.pos.0.wrapping_add(DIJ[d].0);
                let next_x = self.pos.1.wrapping_add(DIJ[d].1);
                // 移動前のプレイヤー位置に関して，zobrist hashのxorして消す
                self.zobrist_hash ^= self.zobrist_hash_map.player_hash[self.pos.0][self.pos.1];
                // 移動し，zobrist hashも更新
                self.pos = (next_y, next_x);
                self.zobrist_hash ^= self.zobrist_hash_map.player_hash[next_y][next_x];
                if next_y == map.key.0 && next_x == map.key.1 {
                    // 鍵の取得
                    self.has_key = true;
                    self.zobrist_hash ^= self.zobrist_hash_map.key_hash[next_y][next_x];
                } else if next_y == map.goal.0 && next_x == map.goal.1 && self.has_key {
                    // ゲームクリア
                    self.is_done = true;
                } else if self.jewelry_map[next_y * N + next_x] {
                    // 宝石の取得
                    self.jewelry += 10;
                    self.jewelry_map.set(next_y * N + next_x, false);
                    self.zobrist_hash ^= self.zobrist_hash_map.jewelry_hash[next_y][next_x];
                } else if self.gunpowder_map[next_y * N + next_x] {
                    // 火薬の取得
                    self.gunpowder += 1;
                    self.gunpowder_map.set(next_y * N + next_x, false);
                    self.zobrist_hash ^= self.zobrist_hash_map.gunpowder_hash[next_y][next_x];
                }
                // outputへ入れる
                self.output.push((action.0, DIR[action.1]));
            },
            'B' => {
                let d = action.1;
                let next_y = self.pos.0.wrapping_add(DIJ[d].0);
                let next_x = self.pos.1.wrapping_add(DIJ[d].1);
                // 生成･破壊は隣にあるかないかで分岐
                if self.block_map[next_y * N + next_x] {
                    self.block_map.set(next_y * N + next_x, false);
                    self.zobrist_hash ^= self.zobrist_hash_map.block_hash[next_y][next_x];
                } else {
                    self.block_map.set(next_y * N + next_x, true);
                    self.zobrist_hash ^= self.zobrist_hash_map.block_hash[next_y][next_x];
                }
                // outputへ入れる
                self.output.push((action.0, DIR[action.1]));
            },
            'F' => (),
            _ => unreachable!(),
        }
        // 今いる場所の上下左右の延長線上で，このターンに作動する探知機が存在するかどうか調べる
        if !self.is_done {
            let num_probes = self.search_danger_probe(map);
            self.hp -= num_probes * map.D;
        }
    }
    // 回答を出力する
    pub fn print(&self) {
        for &(action, dir) in &self.output {
            if action == 'S' {
                println!("{}", action);
            } else {
                println!("{} {}", action, dir);
            }
        }
    }
}
// Stateをbinaryheapに入れるとき，評価値の大きい順に取り出すため，partialordを実装する
// impl Ord for State {
impl<'a> Ord for State<'a> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.evaluated_score.cmp(&other.evaluated_score)
    }
}
// impl PartialEq for State {
impl<'a> PartialEq for State<'a> {
    fn eq(&self, other: &Self) -> bool {
        self.evaluated_score == other.evaluated_score
    }
}
// impl Eq for State {} // ここは空でOK
impl<'a> Eq for State<'a> {} // ここは空でOK
// impl PartialOrd for State {
impl<'a> PartialOrd for State<'a> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.evaluated_score.partial_cmp(&other.evaluated_score)
    }
}

// ある座標にプレイヤー，ブロック，探知機，宝石，火薬，鍵が存在することをハッシュに変換する
#[derive(Clone)]
struct ZobristHash {
    player_hash: Vec<Vec<u128>>, // 座標pにプレイヤーが存在することに対応するハッシュ値
    block_hash: Vec<Vec<u128>>, // 座標pにブロックが存在することに対応するハッシュ値
    probe_hash: Vec<Vec<u128>>, // 座標pにブロックが存在することに対応するハッシュ値
    jewelry_hash: Vec<Vec<u128>>, // 座標pにブロックが存在することに対応するハッシュ値
    gunpowder_hash: Vec<Vec<u128>>, // 座標pにブロックが存在することに対応するハッシュ値
    key_hash: Vec<Vec<u128>>, // 座標pにブロックが存在することに対応するハッシュ値
}
impl ZobristHash {
    fn new() -> Self {
        let mut rng = Xoshiro256::new(8192);
        let mut player_hash = vec![vec![0; N]; N];
        let mut block_hash = vec![vec![0; N]; N];
        let mut probe_hash = vec![vec![0; N]; N];
        let mut jewelry_hash = vec![vec![0; N]; N];
        let mut gunpowder_hash = vec![vec![0; N]; N];
        let mut key_hash = vec![vec![0; N]; N];
        for y in 0..N {
            for x in 0..N {
                player_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);
                block_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);
                probe_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);
                jewelry_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);
                gunpowder_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);
                key_hash[y][x] = rng.gen_u128(std::u128::MIN, std::u128::MAX);
            }
        }
        Self { player_hash, block_hash, probe_hash, jewelry_hash, gunpowder_hash, key_hash }
    }
}

// ビームサーチ
fn beam_search<'a>(state: &'a State<'a>, map: &Map, beam_width: usize, beam_depth: usize) -> Option<State<'a>> {
    let mut best_state = state.clone();
    let mut now_beam = BinaryHeap::new();
    now_beam.push(state.clone());
    let mut zobrist_hash_set = HashSet::new();
    for _ in 0..beam_depth {
        let mut next_beam = BinaryHeap::new();
        for _ in 0..beam_width {
            if now_beam.is_empty() {break;}
            let now_state = now_beam.pop().unwrap();
            if now_state.is_done {continue;}
            let legal_action_list = now_state.get_legal_actions(map);
            // eprintln!("legal_actions: {:?}", legal_actions);
            for i in 0..legal_action_list.len() {
                let mut next_state = now_state.clone();
                for &action in &legal_action_list[i] {                    
                    next_state.advance(map, action);
                    next_state.evaluate_score(map);
                    // 宝石から宝石への移動にしたことで，ゲーム上では複数のアクションを一気にやるようになってる
                    // 途中でも終了判定を入れる必要がある
                    if next_state.is_done {break;}
                    // eprintln!("action: {:?}", action);
                    // eprintln!("pos: {:?}", next_state.pos);
                    // eprintln!("jewelry: {}", next_state.jewelry);
                }
                // 同一盤面が評価済みかどうかで評価値を変える
                if zobrist_hash_set.contains(&next_state.zobrist_hash) {
                    continue;
                } else {
                    zobrist_hash_set.insert(next_state.zobrist_hash);
                }
                next_beam.push(next_state);
            }
        }
        if next_beam.is_empty() {
            eprintln!("empty");
            break;
        }
        if best_state.evaluated_score <= next_beam.peek().unwrap().evaluated_score && next_beam.peek().unwrap().is_done {
            best_state = next_beam.peek().unwrap().clone();
        }
        now_beam.clear();
        while now_beam.len() < beam_width {
            if let Some(state) = next_beam.pop() {
                now_beam.push(state);
            } else {
                break;
            }
        }
    }
    Some(best_state)
}

fn main() {
    get_time();
    let map = Map::new();
    let zobrist_hash_map = ZobristHash::new();
    let mut state = State::new(&map, &zobrist_hash_map);

    // ビームサーチを回す
    if let Some(bs_state) = beam_search(&state, &map, 100, H as usize) {
        bs_state.print();
        eprintln!("turn: {}", bs_state.turn);
        eprintln!("evaluated score: {}", bs_state.evaluated_score);
        eprintln!("D: {}", map.D);
        eprintln!("remained HP: {}", bs_state.hp);
        eprintln!("game score: {}", bs_state.jewelry);
        eprintln!("time: {}", get_time());
    } else {
        eprintln!("error");
        eprintln!("time: {}", get_time());
    }
}