#![allow(dead_code)]
#![allow(non_upper_case_globals)]
#![allow(unused_imports)]
use grid::{Coord, Map2d, DC};
use std::cmp::*;
use std::collections::*;
use std::io::stdin;

use self::rnd::shuffle;

const TIME_LIMIT: f64 = 2.7;
const N: usize = 50;
const N2: usize = N * N;
const M: usize = 20;

pub fn main() {
    get_time();
    let input = read_input();
    let output = solve(&input);
    output.print_ans();
    eprintln!("Time = {}", get_time());
}

fn solve(input: &Input) -> Output {
    let state = loop {
        let mut state = State::new(input);
        state.calc_score_2(input);
        if state.score < usize::MAX / 3 {
            break state;
        }
    };
    annealing(input, TIME_LIMIT - get_time(), state).to_output_2(input)
}

#[derive(Clone)]
struct State {
    score: usize,
    use_bomb: Map2d<Vec<bool>>,
    cnt_use: Map2d<usize>,
    jun: Vec<(Coord, usize)>,
}

impl State {
    fn new(input: &Input) -> Self {
        let score = !0;
        let mut use_bomb = Map2d::new(vec![vec![false; M]; N2], N);
        let mut cnt_use = Map2d::new(vec![0; N2], N);
        let mut jun = vec![];
        let mut pvec = vec![];
        let mut pvec2 = vec![];
        for x in 0..N {
            for y in 0..N {
                if 5 < x && x < N - 5 && 5 < y && y < N - 5 {
                    pvec.push(Coord::new(x, y));
                } else {
                    pvec2.push(Coord::new(x, y));
                }
            }
        }
        rnd::shuffle(&mut pvec);
        rnd::shuffle(&mut pvec2);
        pvec.extend(pvec2);
        for p in pvec {
            if input.map[p] == Square::Empty || cnt_use[p] > 0 {
                continue;
            }
            if let Some(&(bp, bid)) = input.can_hakai_rev[p]
                .iter()
                .find(|&&bp| 5 < bp.0.x && bp.0.x < N - 5 && 5 < bp.0.y && bp.0.y < N - 5)
            {
                use_bomb[bp][bid] = true;
                for &np in input.can_hakai[bp][bid].iter() {
                    cnt_use[np] += 1;
                }
                jun.push((bp, bid));
            } else {
                let (bp, bid) = input.can_hakai_rev[p][rnd::next() % input.can_hakai_rev[p].len()];
                use_bomb[bp][bid] = true;
                for &np in input.can_hakai[bp][bid].iter() {
                    cnt_use[np] += 1;
                }
                jun.push((bp, bid));
            }
        }
        Self {
            score,
            use_bomb,
            cnt_use,
            jun,
        }
    }

    fn calc_score(&mut self, input: &Input) {
        let mut score = 0;
        let sz = self.jun.len();
        // uso dp
        let mut dp = 0;
        let mut rui = 0;
        let mut mae = Coord::new(0, 0);
        let mut bombed = Map2d::new(vec![false; N2], N);
        for i in 0..sz {
            score += input.bomb_cost[self.jun[i].1];
            let ue = if i == 0 {
                (!0, !0)
            } else {
                (
                    dp + rui + self.jun[i].0.dist(&mae),
                    1 * (rui + self.jun[i].0.dist(&mae)),
                )
            };
            let sita = if let Some(&near) = input.near_shop[self.jun[i].0]
                .iter()
                .find(|&&np| !bombed[np])
            {
                (
                    dp + mae.dist(&near) + self.jun[i].0.dist(&near),
                    1 * (self.jun[i].0.dist(&near)),
                )
            } else {
                (!0, !0)
            };
            if ue.0 < sita.0 {
                dp = ue.0;
                rui = ue.1;
            } else {
                dp = sita.0;
                rui = sita.1;
            }
            mae = self.jun[i].0;
            for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
                bombed[np] = true;
            }
        }

        self.score = score + dp;
    }

    fn calc_score_2(&mut self, input: &Input) {
        let mut score = 0;
        let sz = self.jun.len();
        // uso dp
        // 前から
        let max_size = 3;
        let mut dp = vec![vec![usize::MAX; max_size]; sz + 1];
        dp[0][0] = 0;
        let mut bombed = Map2d::new(vec![false; N2], N);
        for i in 0..sz {
            score += 5 * input.bomb_cost[self.jun[i].1];
            // 購入する場合0->j
            if dp[i][0] != usize::MAX {
                if let Some(&near) = input.near_shop[self.jun[i].0]
                    .iter()
                    .find(|&&np| !bombed[np])
                {
                    for j in 0..max_size {
                        let cost = if i == 0 {
                            dp[i][0]
                                + 1 * Coord::new(0, 0).dist(&near)
                                + 1 * (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
                        } else {
                            dp[i][0]
                                + 1 * self.jun[i - 1].0.dist(&near)
                                + 1 * (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
                        };
                        dp[i + 1][j] = dp[i + 1][j].min(cost);
                    }
                }
            }
            // 購入しない場合
            for j in 1..max_size {
                if dp[i][j] == usize::MAX {
                    continue;
                }
                let cost =
                    dp[i][j] + 1 * (j + 1) * (j + 1) * self.jun[i - 1].0.dist(&self.jun[i].0);
                dp[i + 1][j - 1] = dp[i + 1][j - 1].min(cost);
            }

            for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
                bombed[np] = true;
            }
        }
        if dp[sz][0] == usize::MAX {
            self.score = usize::MAX / 2;
        } else {
            self.score = score + dp[sz][0];
        }
    }

    fn calc_score_3(&mut self, input: &Input) {
        // バグっている
        let mut score = 0;
        let sz = self.jun.len();
        // uso dp
        // 前から
        let max_size = 3;
        let mut dp = vec![vec![usize::MAX; max_size]; 2];
        dp[0][0] = 0;
        let mut bombed = Map2d::new(vec![false; N2], N);
        for i in 0..sz {
            score += 5 * input.bomb_cost[self.jun[i].1];
            // 購入する場合0->j
            if dp[i % 2][0] != usize::MAX {
                if let Some(&near) = input.near_shop[self.jun[i].0]
                    .iter()
                    .find(|&&np| !bombed[np])
                {
                    for j in 0..max_size {
                        let cost = if i == 0 {
                            dp[i % 2][0]
                                + 1 * Coord::new(0, 0).dist(&near)
                                + 1 * (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
                        } else {
                            dp[i % 2][0]
                                + 1 * self.jun[i - 1].0.dist(&near)
                                + 1 * (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
                        };
                        dp[(i + 1) % 2][j] = dp[(i + 1) % 2][j].min(cost);
                    }
                }
            }
            // 購入しない場合
            for j in 1..max_size {
                if dp[i % 2][j] == usize::MAX {
                    continue;
                }
                let cost =
                    dp[i % 2][j] + 1 * (j + 1) * (j + 1) * self.jun[i - 1].0.dist(&self.jun[i].0);
                dp[(i + 1) % 2][j - 1] = dp[(i + 1) % 2][j - 1].min(cost);
            }

            for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
                bombed[np] = true;
            }
        }
        if dp[(sz + 1) % 2][0] == usize::MAX {
            self.score = usize::MAX / 2;
        } else {
            self.score = score + dp[(sz + 1) % 2][0];
        }
    }

    fn to_output(&self, input: &Input) -> Output {
        let mut actions = vec![];
        let sz = self.jun.len();

        let mut dp = 0;
        let mut rui = 0;
        let mut mae = Coord::new(0, 0);
        let mut bombed = Map2d::new(vec![false; N2], N);
        let mut buyvec = vec![];

        for i in 0..sz {
            let ue = if i == 0 {
                (!0, !0)
            } else {
                (
                    dp + rui + self.jun[i].0.dist(&mae),
                    rui + self.jun[i].0.dist(&mae),
                )
            };
            let sita = if let Some(&near) = input.near_shop[self.jun[i].0]
                .iter()
                .find(|&&np| !bombed[np])
            {
                (
                    dp + mae.dist(&near) + self.jun[i].0.dist(&near),
                    self.jun[i].0.dist(&near),
                )
            } else {
                (!0, !0)
            };
            if ue.0 < sita.0 {
                dp = ue.0;
                rui = ue.1;
                actions.extend(moves_dijkstra(mae, self.jun[i].0, &bombed, input));
            } else {
                dp = sita.0;
                rui = sita.1;
                let near = *input.near_shop[self.jun[i].0]
                    .iter()
                    .find(|&&np| !bombed[np])
                    .unwrap();
                //actions.extend(moves(mae, near));
                actions.extend(moves_dijkstra(mae, near, &bombed, input));
                // ここに購入を計算 todo // あとでここに入れる
                buyvec.push(vec![]);
                actions.push((2, !0));
                //
                //actions.extend(moves(near, self.jun[i].0));
                actions.extend(moves_dijkstra(near, self.jun[i].0, &bombed, input));
            }
            // use
            actions.push((3, self.jun[i].1 + 1));
            let lll = buyvec.len() - 1;
            buyvec[lll].push((2, self.jun[i].1 + 1));
            //
            mae = self.jun[i].0;
            for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
                bombed[np] = true;
            }
        }
        let mut ret_actions = vec![];
        let mut buyidx = 0;
        for &(tp, dd) in actions.iter() {
            if tp != 2 {
                ret_actions.push((tp, dd));
            } else {
                for &t in buyvec[buyidx].iter() {
                    ret_actions.push(t);
                }
                buyidx += 1;
            }
        }
        Output {
            score: self.score,
            actions: ret_actions,
        }
    }

    fn to_output_2(&self, input: &Input) -> Output {
        let mut actions = vec![];
        let sz = self.jun.len();

        let max_size = sz + 1;
        let mut dp = vec![vec![(usize::MAX, usize::MAX); max_size]; sz + 1];
        dp[0][0] = (0, !0);
        let mut bombed = Map2d::new(vec![false; N2], N);
        for i in 0..sz {
            // 購入する場合0->j
            if dp[i][0].0 != usize::MAX {
                if let Some(&near) = input.near_shop[self.jun[i].0]
                    .iter()
                    .find(|&&np| !bombed[np])
                {
                    for j in 0..max_size {
                        let cost = if i == 0 {
                            dp[i][0].0
                                + Coord::new(0, 0).dist(&near)
                                + (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
                        } else {
                            dp[i][0].0
                                + self.jun[i - 1].0.dist(&near)
                                + (j + 2) * (j + 2) * near.dist(&self.jun[i].0)
                        };
                        dp[i + 1][j] = dp[i + 1][j].min((cost, 0));
                    }
                }
            }
            // 購入しない場合
            for j in 1..max_size {
                if dp[i][j].0 == usize::MAX {
                    continue;
                }
                let cost = dp[i][j].0 + (j + 1) * (j + 1) * self.jun[i - 1].0.dist(&self.jun[i].0);
                dp[i + 1][j - 1] = dp[i + 1][j - 1].min((cost, j));
            }

            for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
                bombed[np] = true;
            }
        }
        // 復元
        let mut rireki = vec![];
        let mut nowj = 0;
        for i in (1..sz + 1).rev() {
            // use
            rireki.push((3, !0));
            let nextnowj = dp[i][nowj].1;
            assert!(nextnowj != usize::MAX);
            assert!(nowj + 1 >= nextnowj);
            if nowj >= nextnowj {
                // buy
                rireki.push((2, nowj - nextnowj + 1));
            }
            nowj = nextnowj;
            if nowj == usize::MAX {
                eprintln!("AAA {} {} {} {}", i, sz, dp[sz][0].0, dp[sz][0].1);
            }
        }
        rireki.reverse();
        let mut bombed = Map2d::new(vec![false; N2], N);
        let mut mae = Coord::new(0, 0);
        let mut idx = 0;
        for (tp, d) in rireki {
            if tp == 2 {
                // buy
                let near = *input.near_shop[self.jun[idx].0]
                    .iter()
                    .find(|&&np| !bombed[np])
                    .unwrap();
                assert!(input.map[near] == Square::Shop && !bombed[near]);
                actions.extend(moves_dijkstra(mae, near, &bombed, input));
                for j in 0..d {
                    actions.push((2, self.jun[idx + j].1 + 1));
                }
                mae = near;
            } else {
                // use
                actions.extend(moves_dijkstra(mae, self.jun[idx].0, &bombed, input));
                mae = self.jun[idx].0;

                actions.push((3, self.jun[idx].1 + 1));
                for &np in input.can_hakai[self.jun[idx].0][self.jun[idx].1].iter() {
                    bombed[np] = true;
                }
                idx += 1;
            }
        }
        Output {
            score: self.score,
            actions,
        }
    }

    fn add_bomb(&mut self, input: &Input, bp: Coord, bid: usize) {
        for &np in input.can_hakai[bp][bid].iter() {
            self.cnt_use[np] += 1;
        }
    }

    fn swap_jun(&mut self, pos: (usize, usize)) {
        let a = self.jun[pos.0];
        self.jun[pos.0] = self.jun[pos.1];
        self.jun[pos.1] = a;
    }

    fn swap_off(&mut self, input: &Input) -> bool {
        let idx = rnd::next() % self.jun.len();
        let bp = self.jun[idx].0;
        let bid = self.jun[idx].1;
        let mut added = vec![];
        for &np in input.can_hakai[bp][bid].iter() {
            self.cnt_use[np] -= 1;
            if self.cnt_use[np] == 0 {
                let mut revclone = input.can_hakai_rev[np].clone();
                rnd::shuffle(&mut revclone);
                if let Some(&nb) = revclone.iter().find(|&&ip| !self.use_bomb[ip.0][ip.1]) {
                    self.add_bomb(input, nb.0, nb.1);
                    added.push(nb);
                    self.use_bomb[nb.0][nb.1] = true;
                } else {
                    return false;
                }
            }
        }

        self.use_bomb[bp][bid] = false;
        self.jun.remove(idx);
        for nb in added {
            let mut min_cost = !0;
            let mut best_idx = !0;
            for i in 0..self.jun.len() {
                let dist = if i == 0 {
                    Coord::new(0, 0).dist(&nb.0) + nb.0.dist(&self.jun[i].0)
                } else {
                    self.jun[i - 1].0.dist(&nb.0) + nb.0.dist(&self.jun[i].0)
                };
                if min_cost > dist {
                    min_cost = dist;
                    best_idx = i;
                }
            }
            self.jun.insert(best_idx, nb);
        }
        true
    }

    fn insert_jun(&mut self) {
        let bb = rnd::next() % self.jun.len();
        let b = self.jun[bb];
        self.jun.remove(bb);
        let mut min_cost = !0;
        let mut best_idx = !0;
        for i in 0..self.jun.len() {
            let dist = if i == 0 {
                Coord::new(0, 0).dist(&b.0) + b.0.dist(&self.jun[i].0)
            } else {
                self.jun[i - 1].0.dist(&b.0) + b.0.dist(&self.jun[i].0)
            };
            if min_cost > dist {
                min_cost = dist;
                best_idx = i;
            }
        }
        self.jun.insert(best_idx, b);
    }
}

fn annealing(input: &Input, duration: f64, mut state: State) -> State {
    let start_time = get_time();
    let duration_inv = 1.0 / duration;
    const START_TEMP: f64 = 1000.0;
    const END_TEMP: f64 = 1.1;
    const DIFF_TEMP: f64 = END_TEMP / START_TEMP;
    let mut temp = START_TEMP;
    let update_temp = || {
        // 非線形
        return START_TEMP * DIFF_TEMP.powf((get_time() - start_time) * duration_inv);
        // 線形
        //return START_TEMP + (END_TEMP - START_TEMP) * (get_time() - start_time) * duration_inv;
    };

    let loglis = (0..0x10000)
        .map(|i| (i as f64 / 0xffff as f64).ln())
        .collect::<Vec<_>>();
    fn is_accepted(now_score: usize, next_score: usize, temp: f64, loglis: &Vec<f64>) -> bool {
        // 最大化する場合。最小化時は -(next_score - now_score)
        -(next_score as f64 - now_score as f64) >= temp * loglis[rnd::next() & 0xffff]
    }

    let mut best_state = state.clone();
    let mut iter_sa = 0;
    let mut cnt_kousin = 0;
    let mut cnt_kousin_best = 0;
    loop {
        if iter_sa & 255 == 0 {
            if get_time() - start_time > duration {
                break;
            }
            // kick! if mae_kousin > 100 {}
            temp = update_temp();
        }
        iter_sa += 1;

        let op = rnd::next() % 100;
        if op < 60 {
            let now_score = state.score;
            let pos = select_2(state.jun.len());
            state.swap_jun(pos);
            state.calc_score_2(input);
            let next_score = state.score;

            if is_accepted(now_score, next_score, temp, &loglis) {
                cnt_kousin += 1;
            } else {
                state.swap_jun(pos);
                state.score = now_score;
            }
        } else if op < 1 {
            let now_score = state.score;
            let mut next_state = state.clone();
            next_state.insert_jun();
            next_state.calc_score_2(input);
            let next_score = next_state.score;

            if is_accepted(now_score, next_score, temp, &loglis) {
                cnt_kousin += 1;
                state = next_state;
            } else {
                //
            }
        } else {
            let now_score = state.score;
            let mut next_state = state.clone();
            let ss = next_state.swap_off(input);
            if !ss {
                continue;
            }
            next_state.calc_score_2(input);
            let next_score = next_state.score;

            if is_accepted(now_score, next_score, temp, &loglis) {
                cnt_kousin += 1;
                state = next_state;
            } else {
                //
            }
        }
        if best_state.score > state.score {
            best_state = state.clone();
            cnt_kousin_best += 1;
        }
    }
    crate::print_data!(iter_sa);
    crate::print_data!(cnt_kousin);
    crate::print_data!(cnt_kousin_best);
    best_state
}

fn moves(a: Coord, b: Coord) -> Vec<(usize, usize)> {
    let mut ret = vec![];
    let mut p = a;
    while p != b {
        if p.y > b.y {
            p.y -= 1;
            ret.push((1, 0));
        } else if p.x > b.x {
            p.x -= 1;
            ret.push((1, 1));
        } else if p.y < b.y {
            p.y += 1;
            ret.push((1, 2));
        } else if p.x < b.x {
            p.x += 1;
            ret.push((1, 3));
        };
    }
    ret
}

fn moves_dijkstra(a: Coord, b: Coord, bombed: &Map2d<bool>, input: &Input) -> Vec<(usize, usize)> {
    let mut ret = vec![];
    if a == b {
        return ret;
    }
    let mut dp = Map2d::new(vec![(!0usize, !0); N2], N);
    dp[a] = (0, !0);
    let mut que = BinaryHeap::new();
    que.push((Reverse(0), a));
    while let Some((Reverse(dist), p)) = que.pop() {
        if que.len() > 10000 {
            assert!(1 == 0);
        }
        if p == b {
            break;
        }
        for dir in 0..4 {
            let np = p.next(dir);
            if !np.in_map(N) {
                continue;
            }
            let ncost = if input.map[np] == Square::Empty || bombed[np] {
                dist + 1
            } else {
                dist + 2
            };

            if ncost < dp[np].0 {
                dp[np] = (ncost, dir);
                que.push((Reverse(ncost), np));
            }
        }
    }
    assert!(dp[b].1 != !0);
    let mut p = b;
    while p != a {
        ret.push((1, dp[p].1));
        p = p.next((2 + dp[p].1) % 4);
    }
    ret.reverse();
    ret
}

fn calc_dist_dijkstra(a: Coord, b: Coord, bombed: &Map2d<bool>, input: &Input) -> usize {
    let mut dp = Map2d::new(vec![!0usize; N2], N);
    dp[a] = 0;
    let mut que = BinaryHeap::new();
    que.push((Reverse(0), a));
    while let Some((Reverse(dist), p)) = que.pop() {
        if p == b {
            return dist;
        }
        if dist > dp[p] {
            continue;
        }
        for dir in 0..4 {
            let np = p.next(dir);
            if !np.in_map(N) {
                continue;
            }
            let ncost = if input.map[np] == Square::Empty || bombed[np] {
                dist + 1
            } else {
                dist + 2
            };

            if ncost < dp[np] {
                dp[np] = ncost;
                que.push((Reverse(ncost), np));
            }
        }
    }
    unreachable!()
}

#[derive(PartialEq, Eq, Clone, Copy)]
enum Square {
    Empty,
    House,
    Shop,
}

struct Input {
    map: Map2d<Square>,
    bomb_cost: Vec<usize>,
    near_shop: Map2d<Vec<Coord>>,
    can_hakai: Map2d<Vec<Vec<Coord>>>, // そのマスで爆弾iを使って破壊できるもの
    can_hakai_rev: Map2d<Vec<(Coord, usize)>>, // そのマスを破壊することができるマスと爆弾の種類
}

fn read_input() -> Input {
    let _nm = input_vecusize();
    let mut map_ = vec![];
    for _i in 0..N {
        let a = input_string();
        map_.push(a.chars().collect::<Vec<_>>());
    }
    let mut map = vec![];
    for x in 0..N {
        for y in 0..N {
            let c = match map_[x][y] {
                '.' => Square::Empty,
                '#' => Square::House,
                '@' => Square::Shop,
                _ => unreachable!(),
            };
            map.push(c);
        }
    }
    let map = Map2d::new(map, N);
    let mut can_hakai = Map2d::new(vec![vec![vec![]; M]; N2], N);
    let mut bomb_cost = vec![];
    let mut can_hakai_rev = Map2d::new(vec![vec![]; N2], N);
    for bombid in 0..M {
        let cl = input_vecusize();
        let c = cl[0];
        let l = cl[1];
        bomb_cost.push(c);
        for _ in 0..l {
            let dxdy = input_veci32();
            let dx = dxdy[0];
            let dy = dxdy[1];
            for x in 0..N as i32 {
                for y in 0..N as i32 {
                    let nx = x + dx;
                    let ny = y + dy;
                    let p = Coord::new(x as usize, y as usize);
                    let np = Coord::new(nx as usize, ny as usize);
                    if 0 <= nx
                        && nx < N as i32
                        && 0 <= ny
                        && ny < N as i32
                        && map[np] != Square::Empty
                    {
                        can_hakai[p][bombid].push(np);
                        can_hakai_rev[np].push((p, bombid));
                    }
                }
            }
        }
    }
    let mut near_shop = Map2d::new(vec![vec![]; N2], N);
    let mut shops = vec![];
    for x in 0..N {
        for y in 0..N {
            let p = Coord::new(x, y);
            if map[p] == Square::Shop {
                shops.push(p);
            }
        }
    }
    for x in 0..N {
        for y in 0..N {
            let p = Coord::new(x, y);
            near_shop[p] = shops.clone();
            near_shop[p].sort_by(|a, b| p.dist(a).cmp(&p.dist(b)));
        }
    }

    Input {
        map,
        bomb_cost,
        near_shop,
        can_hakai,
        can_hakai_rev,
    }
}

struct Output {
    score: usize,
    actions: Vec<(usize, usize)>,
}

impl Output {
    fn print_ans(&self) {
        //let cost = self.score;
        //crate::print_data!(cost);
        //let score = 1000000000000usize / (10000 + cost);
        //crate::print_data!(score);
        let q = self.actions.len();
        println!("{}", q);
        for i in 0..q {
            if self.actions[i].0 == 1 {
                println!("{} {}", self.actions[i].0, DC[self.actions[i].1]);
            } else {
                println!("{} {}", self.actions[i].0, self.actions[i].1);
            }
        }
    }
}

// ここからライブラリ
#[macro_export]
macro_rules! print_data {
    ( $($x:expr),* ) => {{
        $(eprintln!("[DATA] {} = {:?}", stringify!($x), $x);)*
    }}
}

pub fn get_time() -> f64 {
    static mut START: f64 = -1.0;
    let end = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap()
        .as_secs_f64();
    unsafe {
        if START < 0.0 {
            START = end;
        }
        end - START
    }
}

#[allow(unused)]
mod rnd {
    static mut S: usize = 88172645463325252;

    pub fn next() -> usize {
        unsafe {
            S ^= S << 7;
            S ^= S >> 9;
            S
        }
    }

    pub fn nextf() -> f64 {
        f64::from_bits((0x3ff0000000000000 | next() & 0xfffffffffffff) as u64) - 1.
    }

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

    pub fn exu(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 {
        (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));
        }
    }
}

#[allow(dead_code)]
mod grid {
    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct Coord {
        pub x: usize,
        pub y: usize,
    }

    impl Coord {
        pub const fn new(x: usize, y: usize) -> Self {
            Self { x, y }
        }

        pub const fn new2(p: usize, width: usize) -> Self {
            Self {
                x: p / width,
                y: p % width,
            }
        }

        pub fn in_map(&self, size: usize) -> bool {
            self.x < size && self.y < size
        }

        pub const fn idx(&self, size: usize) -> usize {
            self.x * size + self.y
        }

        pub fn next(self, dir: usize) -> Self {
            self + DXY[dir]
        }

        pub const fn dist(&self, other: &Self) -> usize {
            Self::dist_1d(self.x, other.x) + Self::dist_1d(self.y, other.y)
        }

        const fn dist_1d(x0: usize, x1: usize) -> usize {
            x0.abs_diff(x1)
        }
    }

    impl std::ops::Add for Coord {
        type Output = Self;

        fn add(self, other: Self) -> Self {
            Self {
                x: self.x + other.x,
                y: self.y + other.y,
            }
        }
    }

    pub const DXY: [Coord; 4] = [
        Coord::new(0, !0),
        Coord::new(!0, 0),
        Coord::new(0, 1),
        Coord::new(1, 0),
    ];

    pub const DC: [char; 4] = ['L', 'U', 'R', 'D'];

    #[derive(Debug, Clone)]
    pub struct Map2d<T> {
        pub height: usize,
        pub width: usize,
        map: Vec<T>,
    }

    impl<T: Clone> Map2d<T> {
        pub fn new(map: Vec<T>, width: usize) -> Self {
            let height = map.len() / width;
            debug_assert!(width * height == map.len());
            Self { height, width, map }
        }

        pub fn fill(&mut self, value: T) {
            self.map.fill(value);
        }
    }

    impl<T> std::ops::Index<Coord> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coord: Coord) -> &Self::Output {
            unsafe { self.map.get_unchecked(coord.x * self.width + coord.y) }
        }
    }

    impl<T> std::ops::IndexMut<Coord> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coord: Coord) -> &mut Self::Output {
            unsafe { self.map.get_unchecked_mut(coord.x * self.width + coord.y) }
        }
    }

    impl<T> std::ops::Index<&Coord> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coord: &Coord) -> &Self::Output {
            &self.map[coord.x * self.width + coord.y]
        }
    }

    impl<T> std::ops::IndexMut<&Coord> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coord: &Coord) -> &mut Self::Output {
            &mut self.map[coord.x * self.width + coord.y]
        }
    }

    impl<T> std::ops::Index<usize> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, p: usize) -> &Self::Output {
            &self.map[p]
        }
    }

    impl<T> std::ops::IndexMut<usize> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, p: usize) -> &mut Self::Output {
            &mut self.map[p]
        }
    }
}

fn input_vecusize() -> Vec<usize> {
    let mut a = String::new();
    stdin().read_line(&mut a).unwrap();
    return a
        .trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect();
}
fn input_veci32() -> Vec<i32> {
    let mut a = String::new();
    stdin().read_line(&mut a).unwrap();
    return a
        .trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect();
}

fn input_string() -> String {
    let mut a = String::new();
    stdin().read_line(&mut a).unwrap();
    return a.trim().parse().unwrap();
}

fn select_2(r: usize) -> (usize, usize) {
    let a = rnd::next() % r;
    let b = rnd::exu(0, r, a);
    (a, b)
}