#![allow(non_snake_case)]


// todo: tspで得られた解を自明に有効な近傍のみでlocal_search


fn main(){
    get_time();

    let input=Input::new();
    let ans=solve(&input);

    eprintln!("timer = {}",unsafe{TIME});

    write_output(&ans);
}



fn solve(input:&Input)->Vec<Cmd>{
    let state=State::new(input);
    let mut solver=SA::new(state);
    solver.solve(input,2.5); // todo
    let (ans,score)=solve_tsp(input,solver.state.ans);

    eprintln!("score = {}",score);

    ans
}



fn solve_tsp(input:&Input,a:Vec<usize>)->(Vec<Cmd>,i64){
    let start=a.len();
    let goal=a.len()+1;
    let med=a.len()+2;

    const INF:i64=i64::MAX/32;
    
    let mut dist=vec![vec![0;a.len()+3];a.len()+3];
    for i in 0..a.len(){
        for j in 0..a.len(){
            dist[i][j]=(input.pos[a[i]].0-input.pos[a[j]].0).manh();
        }
    }

    for i in 0..a.len(){
        dist[i][start]=(input.pos[a[i]].0-START).manh();
        dist[start][i]=dist[i][start];
        dist[i][med]=INF;
        dist[med][i]=INF;
    }

    let mut a={
        let route=solve_tsp_greedy(&dist,start);
        let mut route=solve_tsp_ils(&dist,route);

        assert!(&route[..3]==&[start,med,goal] || &route[route.len()-3..]==&[goal,med,start]);
        if &route[..3]==&[start,med,goal]{
            let idx=route.len()-1;
            route[1..idx].reverse();
        }
        
        let mut new=vec![!0;a.len()];
        for (i,&n) in route[1..route.len()-3].iter().enumerate(){
            new[i]=a[n];
        }

        new
    };

    let mut DP=InsertionDP::new(input,&a);
    let mut score=DP.solve(input,a.iter().copied());

    let dist=|a:usize,b:usize|->i64{
        if a&b==!0{
            INF
        } else if a==!0{
            (START-input.pos[b].0).manh()
        } else if b==!0{
            0
        } else{
            (input.pos[a].0-input.pos[b].0).manh()
        }
    };

    while get_time()<=2.9{ // todo
        let (i,j)=(0..10) // todo
            .map(|_|{
                let mut i=rnd::next()%(a.len()+1);
                let mut j;
                loop{
                    j=rnd::range_skip(0,a.len()+1,i);
                    let abs=(i as i64-j as i64).abs();
                    if 1<abs{
                        break;
                    }
                }
                if i>j{
                    (i,j)=(j,i);
                }
                (i,j)
            }).min_by_key(|&(i,j)|{
                let (i0,i1)=(a.get(i-1).copied().unwrap_or(!0),a[i]);
                let (j0,j1)=(a[j-1],a.get(j).copied().unwrap_or(!0));

                dist(i0,j1)+dist(i1,j0)-dist(i0,i1)-dist(j0,j1)
            }).unwrap();

        // todo: 焼きなまし?
        let new=DP.solve(input,a[..i].iter().chain(a[i..j].iter().rev()).chain(a[j..].iter()).copied());
        if score>=new{
            score=new;
            a[i..j].reverse();
        }
    }

    DP.solve(input,a.iter().copied());
    let res=DP.restore();

    let mut route=vec![(START,!0,0,vec![])];

    for i in 0..a.len(){
        if res[i]!=!0{
            route.push((input.shop[res[i]],!0,0,vec![]));
        }
        route.push((input.pos[a[i]].0,a[i],0,vec![]));
    }

    let mut hold=vec![];
    for i in (0..route.len()).rev(){
        route[i].2=(hold.len() as i64+1).pow(2);
        if route[i].1==!0{
            if i==0{
                assert!(hold.is_empty());
            }
            std::mem::swap(&mut hold,&mut route[i].3);
        } else{
            hold.push(input.pos[route[i].1].1);
        }
    }

    let mut dij=Dijkstra::new();
    let mut grid=input.is_block.clone();

    let mut score=a.iter().map(|&n|input.cost[n]).sum::<i64>();
    let mut ret=vec![];

    let mut rest=IndexSet::new(input.shop.len());
    rest.fill();

    assert!(route[0].1==!0 && route[0].3.is_empty());
    
    for w in route.windows(2){
        let (u,v)=(w[0].0,w[1].0);
        let (u,v)=(input.grid.id(u),input.grid.id(v));

        score+=w[0].2*dij.solve(input,&grid,u,v);
        
        if w[1].1!=!0{
            for &n in &input.edge[w[1].1].1{
                grid[input.to_id[n]]=false;
            }

            for &m in &input.shop_edge[w[1].1]{
                if rest.contains(m){
                    rest.del(m);
                }
            }
        }

        let node=dij.restore(v);

        for w in node.windows(2){
            ret.push(Move(get_dir(input.grid.pos(w[0]),input.grid.pos(w[1])) as u8));
        }

        if w[1].1==!0{
            assert!(input.grid[w[1].0]==Shop && grid[input.grid.id(w[1].0)]);
            ret.extend(w[1].3.iter().map(|&n|Buy(n)));
        } else{
            ret.push(Bom(input.pos[w[1].1].1));
        }
    }

    (ret,score)
}



const INF:i64=i64::MAX/4;
const STEP:i64=1518500249; // sqrt(INF)



struct Dijkstra{
    prev:Vec<usize>,
    base:i64,
    dist:Vec<i64>,
    que:(Queue<(usize,i64)>,Queue<(usize,i64)>),
}
impl Dijkstra{
    fn new()->Self{
        let n=(N+1)*(N+1);
        Self{
            prev:vec![!0;n],
            base:INF,
            dist:vec![INF;n],
            que:(Queue::new(),Queue::new()),
        }
    }

    fn restore(&self,mut v:usize)->Vec<usize>{
        let mut route=vec![];
        while v!=!0{
            route.push(v);
            v=self.prev[v];
        }
        route.reverse();
        route
    }

    // todo: 双方向化
    // grid: true->block
    fn solve(&mut self,input:&Input,grid:&[bool],a:usize,b:usize)->i64{
        self.que.0.clear();
        self.que.1.clear();

        self.prev[a]=!0;
        self.base-=STEP;
        self.dist[a]=self.base-STEP;
        self.que.0.push_back((a,self.dist[a]));

        if a==b{
            return 0;
        }

        loop{
            let (v,dist);

            if !self.que.0.is_empty(){
                if !self.que.1.is_empty(){
                    let &(_,dist0)=self.que.0.front().unwrap();
                    let &(_,dist1)=self.que.1.front().unwrap();
                    
                    if dist0>dist1{
                        (v,dist)=self.que.1.pop_front().unwrap();
                    } else{
                        (v,dist)=self.que.0.pop_front().unwrap();
                    }
                } else{
                    (v,dist)=self.que.0.pop_front().unwrap();
                }
            } else if !self.que.1.is_empty(){
                (v,dist)=self.que.1.pop_front().unwrap();
            } else{
                panic!();
            }

            if self.dist[v]!=dist{
                continue;
            }

            for dd in input.grid.dd{
                let nv=v+dd;
                if input.grid.is_wall(nv) || self.dist[nv]<self.base{
                    continue;
                }

                let weight=grid[nv] as i64+1;
                let dist=dist+weight;
                
                self.prev[nv]=v;

                if nv==b{
                    return dist-(self.base-STEP);
                }
                self.dist[nv]=dist;

                if weight==1{
                    self.que.0.push_back((nv,dist));
                } else{
                    self.que.1.push_back((nv,dist));
                }
            }
        }
    }
}




const MAX_HOLD:usize=5; // todo


// 挿入dpではない
// 両方からDPして遅延評価するやつで高速化
struct InsertionDP{
    ratio:Vec<f64>,
    dp:Vec<(f64,usize)>,
    next:Vec<(f64,usize)>,
    rest:IndexSet,
    t:Vec<(i64,i64,usize)>,
    cht:ConvexHallTrick,

    track:Track<usize>,
    last_ans:usize,
}
impl InsertionDP{
    fn new(input:&Input,a:&[usize])->Self{
        // let mut ratio=vec![];
        // let mut r=input.ratio;
        // for _ in 0..=a.len(){
        //     ratio.push(r+1.);
        //     r*=0.3;
        // }
        let ratio=vec![1.;a.len()+1]; // todo: n個終わったときの辺の重み

        Self{
            ratio,
            dp:vec![(0.,!0);MAX_HOLD],
            next:vec![(0.,!0);MAX_HOLD],
            rest:IndexSet::new(input.shop.len()),
            t:vec![],
            cht:ConvexHallTrick::new(),
            track:Track::new(),
            last_ans:!0,
        }
    }
    
    // todo: 復元をしないことで高速化
    fn solve(&mut self,input:&Input,iter:impl Iterator<Item=usize>)->f64{
        self.track.clear();
        
        use std::f64::INFINITY as INF;
        
        self.dp.fill((INF,!0));
        self.dp[0].0=0.;
        self.rest.fill();

        let mut p0=START;

        // todo: 残り個数から自明に不可能なHOLDを見ないようにして高速化
        
        for (i,n) in iter.enumerate(){
            let p1=input.pos[n].0;
            let add=(p0-p1).manh() as f64*self.ratio[i];

            for j in 1..MAX_HOLD{
                let id=self.track.push(self.dp[j].1,!0);
                self.next[j-1]=(self.dp[j].0+add*(j+1) as f64*(j+1) as f64,id);
            }

            self.next[MAX_HOLD-1]=(INF,!0);

            if !self.rest.is_empty(){
                self.t.clear();
                self.t.extend(self.rest.to_slice().iter().map(|&k|((p1-input.shop[k]).manh(),(p0-input.shop[k]).manh(),k)));
                self.t.sort_unstable_by_key(|t|t.0);
                
                self.cht.clear();
                for &(a,b,k) in self.t.iter().rev(){
                    self.cht.add(a,b,k);
                }
    
                for j in 0..MAX_HOLD{
                    // prev-i間で一番近いばくだんやによる
                    let mul=(j as i64+2)*(j as i64+2);
                    let (k,add)=self.cht.get(mul);
                    let new=self.dp[0].0+add as f64*self.ratio[i];

                    if self.next[j].0>new{
                        let id=self.track.push(self.dp[0].1,k);
                        self.next[j]=(new,id);
                    }
                }
            }

            for &m in &input.shop_edge[n]{
                if self.rest.contains(m){
                    self.rest.del(m);
                }
            }

            p0=p1;
            std::mem::swap(&mut self.dp,&mut self.next);
        }

        self.last_ans=self.dp[0].1;

        self.dp[0].0
    }

    fn restore(&self)->Vec<usize>{
        self.track.restore(self.last_ans)
    }
}



#[derive(Clone)]
struct State{
    ans:Vec<usize>,
    used:Vec<bool>,
    cnt:Vec<usize>,
    set:IndexSet,
}
impl State{
    fn new(input:&Input)->State{
        let mut cnt=vec![0;input.cand.len()];
        let mut used=vec![false;input.edge.len()];
        let mut ans=vec![];

        for i in 0..input.cand.len(){
            if cnt[i]!=0{
                continue;
            }
            let new=input.cand[i].choice();
            ans.push(new);
            assert!(!used[new]);
            used[new]=true;

            for &a in &input.edge[new].1{
                cnt[a]+=1;
            }
        }
        assert!(cnt.iter().all(|&n|0<n));

        State{ans,cnt,used,set:IndexSet::new(input.cand.len())}
    }

    fn no(&self)->i64{
        self.set.len() as i64
    }

    fn score(&self,input:&Input)->i64{
        self.ans.iter().map(|&i|input.edge[i].0).sum()
    }

    #[track_caller]
    fn debug(&self,input:&Input){
        let mut used=vec![false;input.edge.len()];
        let mut cnt=vec![0;input.cand.len()];
        for &i in &self.ans{
            used[i]=true;
            for &j in &input.edge[i].1{
                cnt[j]+=1;
            }
        }

        assert!(cnt==self.cnt);
        assert!(used==self.used);
        
        for i in 0..input.cand.len(){
            if cnt[i]==0{
                assert!(self.set.contains(i));
            } else{
                assert!(!self.set.contains(i));
            }
        }
    }

    fn add(&mut self,input:&Input,i:usize){
        for &n in &input.edge[i].1{
            if self.cnt[n]==0{
                self.set.del(n);
            }
            self.cnt[n]+=1;
        }
    }

    fn del(&mut self,input:&Input,i:usize){
        for &n in &input.edge[i].1{
            self.cnt[n]-=1;
            if self.cnt[n]==0{
                self.set.add(n);
            }
        }
    }

    fn try_add(&mut self,input:&Input,i:usize)->i64{
        -input.edge[i].1.iter().map(|&n|(self.cnt[n]==0) as i64).sum::<i64>()
    }

    // todo: これの枝刈り
    fn try_del(&mut self,input:&Input,i:usize)->i64{
        input.edge[i].1.iter().map(|&n|(self.cnt[n]==1) as i64).sum::<i64>()
    }
}


fn trans_del(input:&Input,state:&mut State,add:f64,score:&mut i64,k:f64)->bool{
    let old=*score as f64+state.no() as f64*k;
    
    let idx=rnd::next()%state.ans.len();
    let a=state.ans[idx];
    
    let diff=state.try_del(input,a);
    let new_score=*score-input.edge[a].0;
    let new=new_score as f64+(state.no()+diff) as f64*k;
    let diff=new-old;

    if diff<=add{
        state.del(input,a);
        state.used[a]=false;
        *score=new_score;
        state.ans.swap_remove(idx);
        true
    } else{
        false
    }
}


fn trans_add(input:&Input,state:&mut State,add:f64,score:&mut i64,k:f64)->bool{
    let old=*score as f64+state.no() as f64*k;
    let a=if !state.set.is_empty(){
        input.cand[state.set.rand()].choice()
    } else{
        let mut a=!0;
        for _ in 0..10{
            a=rnd::next()%input.edge.len();
            if !state.used[a]{
                break;
            }
        }
        if a==!0{
            return false;
        }
        a
    };

    let diff=state.try_add(input,a);
    let new_score=*score+input.edge[a].0;
    let new=new_score as f64+(state.no()+diff) as f64*k;
    let diff=new-old;

    if diff<=add{
        state.add(input,a);
        state.used[a]=true;
        *score=new_score;
        state.ans.push(a);
        true
    } else{
        false
    }
}


fn trans_del_add(input:&Input,state:&mut State,add:f64,score:&mut i64,k:f64)->bool{
    let old=*score as f64+state.no() as f64*k;
    
    let idx=rnd::next()%state.ans.len();
    let a=state.ans[idx];
    state.del(input,a);

    if state.set.is_empty(){
        state.ans.swap_remove(idx);
        state.used[a]=false;
        *score-=input.edge[a].0;
        return true;
    }
    
    let mut b=!0;
    for _ in 0..10{
        b=input.cand[state.set.rand()].choice();
        if a!=b{
            break;
        }
    }
    if b==!0{
        return false;
    }

    let diff=state.try_add(input,b);
    let new_score=*score-input.edge[a].0+input.edge[b].0;
    let new=new_score as f64+(state.no()+diff) as f64*k;
    let diff=new-old;

    if diff<=add{
        state.add(input,b);
        state.used[a]=false;
        state.used[b]=true;
        *score=new_score;
        state.ans[idx]=b;
        true
    }  else{
        state.add(input,a);
        false
    }
}


fn trans(input:&Input,state:&mut State,add:f64,score:&mut i64,k:f64)->bool{
    let t=rnd::nextf();
    const C:f64=0.01;

    if !state.ans.is_empty() && t<=C{ // todo
        trans_del(input,state,add,score,k)
    } else if state.ans.is_empty() || t<=C+C{ // todo
        trans_add(input,state,add,score,k)
    } else{
        trans_del_add(input,state,add,score,k)
    }
}



struct SA{
    start:f64,
    tl:f64,
    time:f64,
    heat:f64,
    K:f64,
    table:[f64;65536],
    state:State,
}
impl SA{
    fn new(state:State)->SA{
        let mut table=[0.;65536];
        for i in 0..65536{
            table[i]=((i as f64+0.5)/65536.).ln();
        }
        rnd::shuffle(&mut table);

        SA{
            start:0.,
            tl:0.,
            time:0.,
            heat:0.,
            K:1.,
            table,
            state,
        }
    }
    
    fn update(&mut self)->bool{
        self.time=(get_time()-self.start)/self.tl;
        if self.time>=1.{
            return false;
        }

        // todo
        const T0:f64=10.;
        const T1:f64=0.01;
        self.heat=T0*(T1/T0).powf(self.time.powf(1.5));

        // todo
        const K0:f64=10.;
        const K1:f64=200.;
        self.K=K0+(K1-K0)*self.time;

        true
    }
    
    fn solve(&mut self,input:&Input,tl:f64){
        self.start=get_time();
        assert!(self.start<tl);
        self.tl=tl-self.start;
        
        let mut valid=0;
        let mut score=self.state.score(input);
        let mut best_score=score;
        let mut best=self.state.clone();
        let mut iter=0;

        // let mut cand=self.state.clone();
        // let mut cand_score=INF;
        // let mut stay=0;

        while iter&255!=0 || self.update(){
            iter+=1;
            let add=-self.heat*self.table[iter&65535]; // 最小化
            // let add=0.;
            
            valid+=trans(input,&mut self.state,add,&mut score,self.K) as usize;

            if 0.1<self.time{
                if best_score>score && self.state.set.is_empty(){
                    best_score=score;
                    best=self.state.clone();
                }
                // if cand.set.len() as f64*self.K+cand_score as f64>self.state.set.len() as f64*self.K+score as f64{
                //     stay=0;
                //     cand_score=score;
                //     cand=self.state.clone();
                // } else{
                //     stay+=1;
                //     if stay>=50000{
                //         eprintln!("RollBack");
                //         stay=0;
                //         score=cand_score;
                //         self.state=cand.clone();
                //     }
                // }
            }
        }

        assert!(self.state.score(input)==score);
        self.state.debug(input);
        self.state=best;

        // eprintln!("score = {}",best_score);
        // eprintln!("iter = {}",iter);
        // eprintln!("ratio = {:.3}",valid as f64/iter as f64);
    }
}




const N:usize=50;
const M:usize=20;

const START:P=P(0,0);



#[derive(Clone,Copy,PartialEq,Eq)]
enum Cell{
    Empty,
    Wall,
    Shop,
}
use Cell::*;



#[derive(Clone,Copy,PartialEq,Eq)]
enum Cmd{
    Move(u8),
    Buy(usize),
    Bom(usize),
}
use Cmd::*;


type Grid<T>=grid_type!(T,N,N);



struct Input{
    grid:Grid<Cell>,
    is_block:Vec<bool>,
    shop:Vec<P>,
    edge:Vec<(i64,Vec<usize>)>, // 同じ位置での下位互換は予め除かれる
    cost:Vec<i64>,
    shop_edge:Vec<Vec<usize>>,
    pos:Vec<(P,usize)>,
    cand:Vec<Vec<usize>>,
    to_id:Vec<usize>,
    ratio:f64,
}
impl Input{
    fn new()->Input{
        let mut scan=Scanner::new();
        input!{
            scan,
            n:usize,
            m:usize,
            a:[Chars;n],
            bom:[(i64,[(i64,i64)]);m],
        }
        assert!((n,m)==(N,M));

        let mut grid=vec![vec![Empty;N];N];
        let mut shop=vec![];
        let mut shop_id=vec![vec![!0;N];N];
        for i in 0..N{
            for j in 0..N{
                grid[i][j]=match a[i][j]{
                    '.'=>Empty,
                    '#'=>Wall,
                    '@'=>{
                        shop_id[i][j]=shop.len();
                        shop.push(P::new(i,j));
                        Shop
                    },
                    _=>panic!(),
                };
            }
        }

        let grid=Grid::new(&grid,Empty);

        let mut edge=vec![];
        let mut pos=vec![];

        let mut id=vec![!0;grid.len()];
        let mut to_id=vec![];
        let mut is=0;
        let mut is_block=vec![false;grid.len()];
        let mut cnt=0;
        for i in 0..N{
            for j in 0..N{
                let p=P::new(i,j);
                if grid[p]!=Empty{
                    is_block[grid.id(p)]=true;
                    cnt+=1;
                    id[grid.id(p)]=is;
                    to_id.push(grid.id(p));
                    is+=1;
                }
            }
        }

        let ratio=cnt as f64/(N*N) as f64;

        let mut seen=vec![0;grid.len()];
        let mut at=0;
        let mut cost=vec![];
        
        for i in 0..N{
            for j in 0..N{
                let p=P::new(i,j);
                for i in 0..m{
                    at+=1;
                    let add=bom[i].1.iter().map(|np|p+P(np.0,np.1))
                        .filter(|&p|p.in_range(N,N))
                        .map(|p|{seen[grid.id(p)]=at;id[grid.id(p)]})
                        .filter(|&n|n!=!0)
                        .collect::<Vec<_>>();

                    let mut add_cost=bom[i].0;
                    // todo
                    if let Some(min)=shop.iter().filter(|&&np|seen[grid.id(np)]!=at).map(|&np|(np-p).manh()).min(){
                        add_cost+=(min as f64*4.).round() as i64;
                    }

                    cost.push(bom[i].0);
                    edge.push((add_cost,add));
                    pos.push((p,i));
                }
            }
        }

        let mut shop_edge=vec![vec![];edge.len()];
        for (i,t) in edge.iter().enumerate(){
            for &n in &t.1{
                let id=shop_id[grid.pos(to_id[n])];
                if id!=!0{
                    shop_edge[i].push(id);
                }
            }
        }

        let mut cand=vec![vec![];is];
        for i in 0..edge.len(){
            for &n in &edge[i].1{
                cand[n].push(i);
            }
        }

        let mut t=vec![];
        for i in 0..is{
            t.clear();
            std::mem::swap(&mut t,&mut cand[i]);

            let sum=t.iter().map(|&a|edge[a].1.len() as f64/edge[a].0 as f64).sum::<f64>();
            for &a in &t{
                let ratio=edge[a].1.len() as f64/edge[a].0 as f64/sum;
                for _ in 0..(ratio*t.len() as f64).round() as i64{
                    cand[i].push(a);
                }
            }
        }
        
        assert!(cand.iter().all(|t|!t.is_empty()));

        Input{grid,is_block,shop,edge,cost,shop_edge,pos,cand,to_id,ratio}
    }
}



fn write_output(ans:&[Cmd]){
    println!("{}",ans.len());
    for &c in ans{
        match c{
            Move(dir)=>println!("1 {}",DC[dir as usize]),
            Buy(id)=>println!("2 {}",id+1),
            Bom(id)=>println!("3 {}",id+1),
        }
    }
}



#[allow(unused)]
fn get_time()->f64{
    static mut START:f64=-1.;
    let time=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();
    unsafe{
        if START<0.{
            START=time;
        }

        #[cfg(local)]{
            (time-START)*1.6
        }
        #[cfg(not(local))]{
            time-START
        }
    }
}


#[macro_export]
macro_rules! timer{
    ()=>{
        #[cfg(local)]
        let _timer=Timer(get_time());
    }
}

static mut TIME:f64=0.;
struct Timer(f64);
impl Drop for Timer{
    fn drop(&mut self){
        unsafe{
            TIME+=get_time()-self.0
        }
    }
}


#[allow(unused)]
mod rnd {
    const C:u128=0x2360ED051FC65DA44385DF649FCCF645;
    static mut N:u128=C;

    pub fn set_seed(seed:u128){
        unsafe{
            N^=seed&!1;
        }
    }
    
    pub fn next()->usize{
        unsafe{
            let x=N;
            N*=C;
            (x as usize^(x>>64) as usize).rotate_right((x>>122) as u32)
        }
    }

    pub fn hash()->u64{
        next() as u64
    }

    pub fn nextf()->f64{
        unsafe{
            std::mem::transmute::<u64,f64>(0x3ff0000000000000|(next() as u64)>>12)-1.
        }
    }

    pub fn range(a:usize,b:usize)->usize{
        assert!(a<b);
        next()%(b-a)+a
    }

    pub fn range_skip(a:usize,b:usize,skip:usize)->usize{
        assert!(a<=skip && skip<b);
        let ret=range(a,b-1);
        ret+(skip<=ret) as usize
    }

    pub fn rangei(a:i64,b:i64)->i64{
        assert!(a<b);
        (next()%((b-a) as usize)) as i64+a
    }

    pub fn shuffle<T>(list:&mut [T]){
        for i in (0..list.len()).rev(){
            list.swap(i,next()%(i+1));
        }
    }

    pub fn nextl(n:usize)->usize{
        (next()%n).min(next()%n)
    }

    pub fn nexte(n:usize)->usize{
        (range(1,n+1) as f64*nextf()) as usize
    }
}


trait RandomChoice{
    type Output;
    fn choice(&self)->Self::Output;
}
impl<T:Copy> RandomChoice for [T]{
    type Output=T;
    fn choice(&self)->T{
        self[rnd::next()%self.len()]
    }
}

#[derive(Clone)]
struct StaticGrid<T,const N:usize,const M:usize,const SIZE:usize>{
    wall:[bool;SIZE],
    item:[T;SIZE],
    dd:[usize;4],
    dx:[usize;8],
}
impl<T,const N:usize,const M:usize,const SIZE:usize> StaticGrid<T,N,M,SIZE>{
    // wall:=wallのときのitem
    fn new(grid:&Vec<Vec<T>>,wall:T)->Self where T:Copy{
        assert!(grid.len()==N && grid.iter().all(|t|t.len()==M));
        let mut item=[wall;SIZE];
        let mut wall=[true;SIZE];
        for i in 0..N{
            for j in 0..M{
                item[(i+1)*(M+1)+j+1]=grid[i][j];
                wall[(i+1)*(M+1)+j+1]=false;
            }
        }

        StaticGrid{
            wall,item,
            dd:[!0,!M,1,M+1],
            dx:[!0,!M-1,!M,!M+1,1,M+2,M+1,M],
        }
    }

    const fn len(&self)->usize{
        SIZE
    }

    fn id(&self,p:P)->usize{
        (p.0 as usize+1)*(M+1)+p.1 as usize+1
    }

    fn pos(&self,p:usize)->P{
        P::new(p/(M+1)-1,p%(M+1)-1)
    }

    // 壁でないものから8近傍以内のアクセスであれば正しい値が返ってくる
    fn is_wall(&self,p:usize)->bool{
        self.wall[p]
    }

    fn set_wall(&mut self,p:usize,f:bool){
        self.wall[p]=f;
    }
}
impl<T,const N:usize,const M:usize,const SIZE:usize> Index<usize> for StaticGrid<T,N,M,SIZE>{
    type Output=T;
    fn index(&self,n:usize)->&T{
        &self.item[n]
    }
}
impl<T,const N:usize,const M:usize,const SIZE:usize> IndexMut<usize> for StaticGrid<T,N,M,SIZE>{
    fn index_mut(&mut self,n:usize)->&mut T{
        &mut self.item[n]
    }
}
impl<T,const N:usize,const M:usize,const SIZE:usize> Index<P> for StaticGrid<T,N,M,SIZE>{
    type Output=T;
    fn index(&self,n:P)->&T{
        &self.item[self.id(n)]
    }
}
impl<T,const N:usize,const M:usize,const SIZE:usize> IndexMut<P> for StaticGrid<T,N,M,SIZE>{
    fn index_mut(&mut self,n:P)->&mut T{
        let n=self.id(n);
        &mut self.item[n]
    }
}
impl<T,const N:usize,const M:usize,const SIZE:usize> Index<(usize,usize)> for StaticGrid<T,N,M,SIZE>{
    type Output=T;
    fn index(&self,n:(usize,usize))->&T{
        &self.item[self.id(P::new(n.0,n.1))]
    }
}
impl<T,const N:usize,const M:usize,const SIZE:usize> IndexMut<(usize,usize)> for StaticGrid<T,N,M,SIZE>{
    fn index_mut(&mut self,n:(usize,usize))->&mut T{
        let n=self.id(P::new(n.0,n.1));
        &mut self.item[n]
    }
}


#[macro_export]
macro_rules! grid_type{
    ($t:ident,$n:expr,$m:expr)=>{
        StaticGrid<$t,{$n},{$m},{($m+1)*($n+2)+1}>
    }
}



#[derive(Clone,Copy,PartialEq,Eq,PartialOrd,Ord,Debug,Default,Hash)]
struct P(i64,i64);
impl P{
    fn new(a:usize,b:usize)->P{
        P(a as i64,b as i64)
    }

    fn in_range(self,h:usize,w:usize)->bool{
        h>self.0 as usize && w>self.1 as usize
    }

    fn dot(self,a:P)->i64{
        self.0*a.0+self.1*a.1
    }

    fn det(self,a:P)->i64{
        self.0*a.1-self.1*a.0
    }

    fn manh(self)->i64{
        self.0.abs()+self.1.abs()
    }

    fn abs2(self)->i64{
        self.dot(self)
    }

    // 時計回りに90度
    fn rot90(self)->P{
        P(-self.1,self.0)
    }
}
use std::ops::*;
impl Add for P{
    type Output=P;
    fn add(self,a:P)->P{
        P(self.0+a.0,self.1+a.1)
    }
}
impl Sub for P{
    type Output=P;
    fn sub(self,a:P)->P{
        P(self.0-a.0,self.1-a.1)
    }
}
impl Mul<i64> for P{
    type Output=P;
    fn mul(self,a:i64)->P{
        P(self.0*a,self.1*a)
    }
}
impl Div<i64> for P{
    type Output=P;
    fn div(self,a:i64)->P{
        P(self.0/a,self.1/a)
    }
}
impl Neg for P{
    type Output=P;
    fn neg(self)->P{
        P(-self.0,-self.1)
    }
}
impl AddAssign for P{
    fn add_assign(&mut self,a:P){
        *self=*self+a;
    }
}
impl SubAssign for P{
    fn sub_assign(&mut self,a:P){
        *self=*self-a;
    }
}
impl MulAssign<i64> for P{
    fn mul_assign(&mut self,a:i64){
        *self=*self*a;
    }
}
impl DivAssign<i64> for P{
    fn div_assign(&mut self,a:i64){
        *self=*self/a;
    }
}


impl<T:Index<usize>> Index<P> for [T]{
    type Output=T::Output;
    fn index(&self,idx:P)->&T::Output{
        &self[idx.0 as usize][idx.1 as usize]
    }
}
impl<T:IndexMut<usize>> IndexMut<P> for [T]{
    fn index_mut(&mut self,idx:P)->&mut T::Output{
        &mut self[idx.0 as usize][idx.1 as usize]
    }
}
impl<T:Index<usize>> Index<P> for Vec<T>{
    type Output=T::Output;
    fn index(&self,idx:P)->&T::Output{
        &self[idx.0 as usize][idx.1 as usize]
    }
}
impl<T:IndexMut<usize>> IndexMut<P> for Vec<T>{
    fn index_mut(&mut self,idx:P)->&mut T::Output{
        &mut self[idx.0 as usize][idx.1 as usize]
    }
}

const DD:[P;4]=[P(0,-1),P(-1,0),P(0,1),P(1,0)];
const DC:[char;4]=['L','U','R','D'];


fn get_dir(a:P,b:P)->usize{
    (0..4).find(|&i|DD[i]==b-a).unwrap()
}



struct Scanner{
    stack:std::str::SplitAsciiWhitespace<'static>
}
impl Scanner{
    fn new()->Self{
        use std::io::Read;
        let mut tmp=String::new();
        std::io::stdin().read_to_string(&mut tmp).unwrap();
        Self{stack:Box::leak(tmp.into_boxed_str()).split_ascii_whitespace()}
    }

    fn read<T:std::str::FromStr>(&mut self)->T{
        self.stack.next().unwrap().parse::<T>().unwrap_or_else(|_|panic!("parse error {}",std::any::type_name::<T>()))
    }
}


#[macro_export]
macro_rules! input{
    ($scan:expr $(,)?)=>{};
    ($scan:expr, mut $name:ident:$t:tt $($rest:tt)*)=>{
        let mut $name=read_value!($scan,$t);
        input!{$scan $($rest)*}
    };
    ($scan:expr, $name:ident:$t:tt $($rest:tt)*)=>{
        let $name=read_value!($scan,$t);
        input!{$scan $($rest)*}
    };
}

#[macro_export]
macro_rules! read_value{
    ($scan:expr, ($($t:tt),*))=>{
        ($(read_value!($scan, $t)),*)
    };
    ($scan:expr, [$t:tt;$len:expr])=>{
        (0..$len).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()
    };
    ($scan:expr, [$t:tt])=>{
        (0..$scan.read()).map(|_|read_value!($scan,$t)).collect::<Vec<_>>()
    };
    ($scan:expr, Chars)=>{
        read_value!($scan,String).chars().collect::<Vec<char>>()
    };
    ($scan:expr, Usize1)=>{
        read_value!($scan,usize)-1
    };
    ($scan:expr, $t:ty)=>{
        $scan.read::<$t>()
    };
}



#[derive(Clone)]
struct IndexSet{
    pos:Vec<usize>,
    que:Vec<usize>,
    len:usize
}
impl IndexSet{
    fn new(n:usize)->Self{
        IndexSet{
            pos:(0..n).collect(),
            que:(0..n).collect(),
            len:0
        }
    }

    fn add(&mut self,a:usize){
        let p=self.pos[a];
        assert!(self.len<=p);

        self.que.swap(p,self.len);
        self.pos.swap(a,self.que[p]);
        self.len+=1;
    }

    fn del(&mut self,a:usize){
        let p=self.pos[a];
        assert!(p<self.len);

        self.que.swap(p,self.len-1);
        self.pos.swap(a,self.que[p]);
        self.len-=1;
    }

    fn rand(&self)->usize{
        self.que[rnd::next()%self.len]
    }

    fn to_slice(&self)->&[usize]{
        &self.que[..self.len]
    }

    fn contains(&self,v:usize)->bool{
        self.pos[v]<self.len
    }

    fn is_empty(&self)->bool{
        self.len==0
    }

    fn len(&self)->usize{
        self.len
    }

    fn clear(&mut self){
        self.len=0;
    }

    fn fill(&mut self){
        self.len=self.pos.len();
    }
}

impl std::cmp::PartialEq for IndexSet{
    fn eq(&self,a:&IndexSet)->bool{
        self.pos.len()==a.pos.len() && self.len==a.len
        && self.to_slice().iter().all(|&n|a.contains(n))
    }
}



#[derive(PartialEq,PartialOrd)]
struct O<T:PartialEq+PartialOrd>(T);
impl<T:PartialEq+PartialOrd> Eq for O<T>{} 
impl<T:PartialEq+PartialOrd> Ord for O<T>{
    fn cmp(&self,a:&O<T>)->std::cmp::Ordering{
        self.0.partial_cmp(&a.0).unwrap()
    }
}




struct Queue<T>{
    data:Vec<T>,
    head:usize,
}
impl<T> Queue<T>{
    fn new()->Self{
        Queue{
            data:vec![],
            head:0,
        }
    }

    fn clear(&mut self){
        self.data.clear();
        self.head=0;
    }

    fn is_empty(&self)->bool{
        self.head==self.data.len()
    }

    fn len(&self)->usize{
        self.data.len()-self.head
    }

    fn push_back(&mut self,v:T){
        self.data.push(v);
    }

    fn pop_front(&mut self)->Option<T> where T:Copy{
        if self.head==self.data.len(){
            None
        } else{
            self.head+=1;
            Some(self.data[self.head-1])
        }
    }

    fn front(&self)->Option<&T>{
        if self.is_empty(){
            None
        } else{
            Some(&self.data[self.head])
        }
    }

    fn to_slice(&self)->&[T]{
        &self.data[self.head..]
    }
}
impl<T> Deref for Queue<T>{
    type Target=[T];
    fn deref(&self)->&[T]{
        &self.data[self.head..]
    }
}
impl<T> DerefMut for Queue<T>{
    fn deref_mut(&mut self)->&mut [T]{
        &mut self.data[self.head..]
    }
}
impl<T> Index<usize> for Queue<T>{
    type Output=T;
    fn index(&self,n:usize)->&T{
        let idx=self.head+n;
        assert!(self.head<=idx);
        &self.data[idx]
    }
}
impl<T> IndexMut<usize> for Queue<T>{
    fn index_mut(&mut self,n:usize)->&mut T{
        let idx=self.head+n;
        assert!(self.head<=idx);
        &mut self.data[idx]
    }
}



// https://atcoder.jp/contests/hokudai-hitachi2019-1/submissions/10518254
// kickしてから2-opt,3-optで局所最適にするのを1近傍とした山登り
// 枝刈りをそれなりに入れてる

fn get_score(dist:&Vec<Vec<i64>>,route:&[usize])->i64{
    route.windows(2).map(|w|dist[w[0]][w[1]]).sum()
}

// mv: (i, dir)
fn apply_move<const K:usize>(tour:&mut [usize],idx:&mut [usize],mv:&[(usize,usize);K],BF:&mut Vec<usize>){
    let mut ids=[!0;K];
    let mut it=0..;
    ids.fill_with(||it.next().unwrap());
    ids.sort_unstable_by_key(|&i|mv[i].0);

    let mut order=[0;K];
    for i in 0..K{
        order[ids[i]]=i;
    }
    let mut i=ids[0];
    let mut dir=0;

    BF.clear();

    loop {
        let (j,rev)=if dir==mv[i].1{
            ((i+1)%K,0)
        }
        else{
            ((i+K-1)%K,1)
        };

        if mv[j].1==rev{
            if order[j]==K-1{
                break;
            }
            i=ids[order[j]+1];
            dir=0;
            BF.extend_from_slice(&tour[mv[j].0+1..mv[i].0+1]);
        } 
        else{
            i=ids[order[j]-1];
            dir=1;
            BF.extend(tour[mv[i].0+1..mv[j].0+1].iter().rev().cloned());
        }
    }
    assert_eq!(BF.len(),mv[ids[K-1]].0-mv[ids[0]].0);
    tour[mv[ids[0]].0+1..mv[ids[K-1]].0+1].copy_from_slice(&BF);
    for i in mv[ids[0]].0+1..mv[ids[K-1]].0+1{
        idx[tour[i]]=i;
    }
}
 
const FEASIBLE3:[bool;64]=[false,false,false,true,false,true,true,true,true,true,true,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,true,true,true,true,true,true,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,true,true,true,true,true,true,false,true,false,false,false];

// 一番近いやつを追加していく
fn solve_tsp_greedy(dist:&Vec<Vec<i64>>,start:usize)->Vec<usize>{
    let mut ret=vec![start];
    let mut rest:Vec<_>=(0..dist.len()).filter(|&i|i!=start).collect();
    while !rest.is_empty(){
        let last=*ret.last().unwrap();
        let idx=(0..rest.len()).min_by_key(|&i|O(dist[last][rest[i]])).unwrap();
        ret.push(rest.swap_remove(idx));
    }
    ret.push(start);
    ret
}

// routeは初期解を指定可能
fn solve_tsp_ils(dist:&Vec<Vec<i64>>,mut route:Vec<usize>)->Vec<usize>{
    let n=dist.len();
    assert_eq!(n,route.len()-1);
    let mut f=vec![vec![];n];

    for i in 0..n{
        for j in 0..n{
            if i!=j{
                f[i].push((dist[i][j],j));
            }
        }
        f[i].sort_unstable_by_key(|t|O(t.0));
    }
    let mut idx=vec![!0;n];
    let (mut min_score,mut best)=(get_score(&dist,&route),route.clone());

    let mut BF=vec![];

    for _ in 0..5{ // todo
        let mut cost=get_score(&dist,&route);
        for i in 0..n{
            idx[route[i]]=i;
        }

        loop {
            let mut ok=false;

            for i in 0..n{
                for di in 0..2{
                    'a: for &(ij,vj) in &f[route[i+di]]{
                        if dist[route[i]][route[i+1]]-ij<=0{
                            break;
                        }
                        for dj in 0..2{
                            let j=if idx[vj]==0 && dj==0{
                                n-1
                            } else {
                                idx[vj]-1+dj
                            };

                            let gain=dist[route[i]][route[i+1]]-ij+dist[route[j]][route[j+1]];
                            let diff=gain-dist[route[j+dj]][route[i+1-di]];
                            if di!=dj && diff>0{
                                cost-=diff;
                                apply_move(&mut route,&mut idx,&[(i,di),(j,dj)],&mut BF);
                                ok=true;
                                break 'a;
                            }

                            for &(jk,vk) in &f[route[j+dj]]{
                                if gain-jk<=0{
                                    break;
                                }
                                
                                for dk in 0..2{
                                    let k=if idx[vk]==0 && dk==0{
                                        n-1
                                    } else {
                                        idx[vk]-1+dk
                                    };

                                    if i==k || j==k{
                                        continue;
                                    }
                                    
                                    let diff=gain-jk+dist[route[k]][route[k+1]]-dist[route[k+dk]][route[i+1-di]];
                                    if diff>0{
                                        let mask=((i<j) as usize)<<5 | ((i<k) as usize)<<4 | ((j<k) as usize)<<3 | di<<2 | dj<<1 | dk;

                                        if FEASIBLE3[mask]{
                                            cost-=diff;
                                            apply_move(&mut route,&mut idx,&[(i,di),(j,dj),(k,dk)],&mut BF);
                                            ok=true;
                                            break 'a;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

            if !ok{
                break;
            }
        }

        if min_score>cost{
            min_score=cost;
            best.clear();
            best.extend(&route);
        } else{
            route.clear();
            route.extend(&best);
        }

        if rnd::next()&1==0{
            // double bridge
            let mut is=[!0;4];
            loop{
                is.fill_with(||rnd::next()%n+1);
                is.sort_unstable();
                if is[0]!=is[1] && is[1]!=is[2] && is[2]!=is[3]{
                    break;
                }
            }

            BF.clear();
            let it=route[is[2]..is[3]].iter().chain(&route[is[1]..is[2]]).chain(&route[is[0]..is[1]]);
            BF.extend(it.cloned());
            route[is[0]..is[3]].copy_from_slice(&BF);
        }
        else{
            for _ in 0..6{
                loop{
                    let i=rnd::next()%(n-1);
                    let j=rnd::next()%(n-1);
                    if i<j && j-i<n-2{
                        route[i+1..j].reverse();
                        break;
                    }
                }
            }
        }
    }
    
    best
}



struct ConvexHallTrick(Vec<((i64,i64),usize)>,usize);
impl ConvexHallTrick{
    fn new()->Self{
        Self(vec![],0)
    }

    fn clear(&mut self){
        self.0.clear();
        self.1=0;
    }

    // y=ax+bを追加
    // aが単調減少の必要がある
    fn add(&mut self,a:i64,b:i64,id:usize){
        loop{
            let len=self.0.len();
            if len<2 || !check(self.0[len-2].0,self.0[len-1].0,(a,b)){
                break;
            }
            self.0.pop().unwrap();
        }
        self.0.push(((a,b),id));
    }

    fn f(&self,i:usize,x:i64)->i64{
        self.0[i].0.0*x+self.0[i].0.1
    }

    // f(x)の最小値
    // xは単調増加の必要がある
    fn get(&mut self,x:i64)->(usize,i64){
        while self.0.len()-self.1>=2 && self.f(self.1,x)>=self.f(self.1+1,x){
            self.1+=1;
        }
        (self.0[self.1].1,self.f(self.1,x))
    }
}


fn check(l0:(i64,i64),l1:(i64,i64),l2:(i64,i64))->bool{
    (l1.0-l0.0)*(l2.1-l1.1)>=(l1.1-l0.1)*(l2.0-l1.0)
}



struct Track<T>(Vec<(usize,T)>);
impl<T> Track<T>{
    fn new()->Self{
        Track(vec![])
    }

    fn clear(&mut self){
        self.0.clear();
    }

    fn push(&mut self,prev:usize,v:T)->usize{
        self.0.push((prev,v));
        self.0.len()-1
    }

    fn restore(&self,mut idx:usize)->Vec<T> where T:Clone{
        let mut ret=vec![];
        while idx!=!0{
            let (prev,v)=self.0[idx].clone();
            ret.push(v);
            idx=prev;
        }
        ret.reverse();
        ret
    }
}
impl<T> Index<usize> for Track<T>{
    type Output=T;
    fn index(&self,idx:usize)->&T{
        &self.0[idx].1
    }
}



#[macro_export]#[cfg(not(local))]macro_rules! eprint{($($_:tt)*)=>{}}
#[macro_export]#[cfg(not(local))]macro_rules! eprintln{($($_:tt)*)=>{}}
#[macro_export]#[cfg(not(local))]macro_rules! assert{($($_:tt)*)=>{}}
#[macro_export]#[cfg(not(local))]macro_rules! assert_eq{($($_:tt)*)=>{}}
#[macro_export]#[cfg(not(local))]macro_rules! assert_ne{($($_:tt)*)=>{}}