#929590 (Rust) No.5019 Hakai Project

• 問題: No.5019 Hakai Project
• ユーザー: hangry
• 提出日時: 2023-11-19 13:46:33
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 2,967 ms / 3,000 ms
• コード長: 26,762 bytes
• コンパイル時間: 4,045 ms
• コンパイル使用メモリ: 208,924 KB
• 実行使用メモリ: 388,864 KB
• スコア: 2,512,585,834
• 最終ジャッジ日時: 2023-11-19 13:49:14
• 合計ジャッジ時間: 160,135 ms
• ジャッジサーバーID （参考情報）: judge12 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2,949 ms; 341,632 KB
testcase_01	AC	2,945 ms; 328,704 KB
testcase_02	AC	2,955 ms; 388,864 KB
testcase_03	AC	2,946 ms; 248,832 KB
testcase_04	AC	2,957 ms; 329,856 KB
testcase_05	AC	2,946 ms; 291,200 KB
testcase_06	AC	2,940 ms; 243,072 KB
testcase_07	AC	2,951 ms; 338,944 KB
testcase_08	AC	2,945 ms; 295,040 KB
testcase_09	AC	2,945 ms; 316,288 KB
testcase_10	AC	2,939 ms; 226,816 KB
testcase_11	AC	2,948 ms; 298,240 KB
testcase_12	AC	2,947 ms; 292,224 KB
testcase_13	AC	2,947 ms; 283,136 KB
testcase_14	AC	2,948 ms; 301,952 KB
testcase_15	AC	2,939 ms; 232,960 KB
testcase_16	AC	2,950 ms; 296,320 KB
testcase_17	AC	2,949 ms; 312,064 KB
testcase_18	AC	2,944 ms; 281,344 KB
testcase_19	AC	2,945 ms; 292,992 KB
testcase_20	AC	2,946 ms; 304,256 KB
testcase_21	AC	2,953 ms; 316,160 KB
testcase_22	AC	2,943 ms; 274,688 KB
testcase_23	AC	2,955 ms; 302,976 KB
testcase_24	AC	2,952 ms; 383,488 KB
testcase_25	AC	2,954 ms; 293,120 KB
testcase_26	AC	2,945 ms; 322,432 KB
testcase_27	AC	2,952 ms; 343,808 KB
testcase_28	AC	2,941 ms; 265,088 KB
testcase_29	AC	2,944 ms; 264,832 KB
testcase_30	AC	2,967 ms; 262,528 KB
testcase_31	AC	2,941 ms; 235,520 KB
testcase_32	AC	2,946 ms; 263,552 KB
testcase_33	AC	2,949 ms; 343,552 KB
testcase_34	AC	2,945 ms; 299,136 KB
testcase_35	AC	2,943 ms; 278,528 KB
testcase_36	AC	2,940 ms; 264,192 KB
testcase_37	AC	2,939 ms; 233,088 KB
testcase_38	AC	2,933 ms; 197,504 KB
testcase_39	AC	2,951 ms; 373,888 KB
testcase_40	AC	2,944 ms; 319,744 KB
testcase_41	AC	2,950 ms; 354,688 KB
testcase_42	AC	2,943 ms; 268,928 KB
testcase_43	AC	2,954 ms; 367,616 KB
testcase_44	AC	2,953 ms; 288,768 KB
testcase_45	AC	2,940 ms; 247,680 KB
testcase_46	AC	2,958 ms; 312,320 KB
testcase_47	AC	2,944 ms; 307,840 KB
testcase_48	AC	2,946 ms; 284,672 KB
testcase_49	AC	2,949 ms; 326,912 KB

ソースコード

#![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 std::process::id;

const TIME_LIMIT: f64 = 2.9;
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_4(input);
        if state.score < usize::MAX / 3 {
            break state;
        }
    };
    let duration = TIME_LIMIT - get_time();
    annealing(input, duration, 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);
        pvec.reverse();
        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_4(&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;
        static mut bcnt: i32 = -1;
        static mut bombed2: [i32; N2] = [-1; N2];
        unsafe {
            bcnt += 1;

            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| bombed2[np.idx(N)] != bcnt)
                    {
                        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_shop[self.jun[i].0][self.jun[i].1].iter() {
                    bombed2[np.idx(N)] = bcnt;
                }
                for xxxx in 0..max_size {
                    dp[i % 2][xxxx] = usize::MAX;
                }
            }
            if dp[sz % 2][0] == usize::MAX {
                self.score = usize::MAX / 2;
            } else {
                self.score = score + dp[sz % 2][0];
            }
        }
    }

    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.shops
                .iter()
                .find(|&&np| !bombed[np])*/
                let mae = if i == 0 {
                    Coord::new(0, 0)
                } else {
                    self.jun[i - 1].0
                };

                if let Some(&near) =
                    input
                        .shops
                        .iter()
                        .filter(|&&np| !bombed[np])
                        .min_by(|&&a, &&b| {
                            let acost = mae.dist(&a) + 4 * a.dist(&self.jun[i].0);
                            let bcost = mae.dist(&b) + 4 * b.dist(&self.jun[i].0);
                            acost.cmp(&bcost)
                        })
                {
                    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
                    .shops
                    .iter()
                    .filter(|&&np| !bombed[np])
                    .min_by(|&&a, &&b| {
                        let acost = mae.dist(&a) + 4 * a.dist(&self.jun[idx].0);
                        let bcost = mae.dist(&b) + 4 * b.dist(&self.jun[idx].0);
                        acost.cmp(&bcost)
                    })
                    .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_off2(&mut self, input: &Input) -> (bool, usize, (Coord, usize), Vec<(Coord, usize)>) {
        let idx = rnd::next() % self.jun.len();
        let bp = self.jun[idx].0;
        let bid = self.jun[idx].1;
        let mut added = vec![];
        let mut is_ng = false;
        for &np in input.can_hakai[bp][bid].iter() {
            self.cnt_use[np] -= 1;
            if self.cnt_use[np] == 0 && !is_ng {
                let lllen = input.can_hakai_rev[np].len();
                let sidx = rnd::next() % lllen;
                if let Some(lll) = (0..lllen).find(|&iiii| {
                    !self.use_bomb[input.can_hakai_rev[np][(iiii + sidx) % lllen].0]
                        [input.can_hakai_rev[np][(iiii + sidx) % lllen].1]
                }) {
                    let nb = input.can_hakai_rev[np][(lll + sidx) % lllen];
                    self.add_bomb(input, nb.0, nb.1);
                    added.push(nb);
                    self.use_bomb[nb.0][nb.1] = true;
                } else {
                    is_ng = true;
                }
            }
        }
        if is_ng {
            return (false, idx, (bp, bid), added);
        }

        self.use_bomb[bp][bid] = false;
        self.jun.remove(idx);
        for &nb in added.iter() {
            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, idx, (bp, bid), added)
    }

    fn undo_swap_off(
        &mut self,
        input: &Input,
        rireki: (bool, usize, (Coord, usize), Vec<(Coord, usize)>),
    ) {
        self.add_bomb(input, rireki.2 .0, rireki.2 .1);
        if !rireki.0 {
            return;
        }
        for &nb in rireki.3.iter() {
            self.use_bomb[nb.0][nb.1] = false;
            for &np in input.can_hakai[nb.0][nb.1].iter() {
                self.cnt_use[np] -= 1;
            }
        }
        self.jun.retain(|x| !rireki.3.contains(x));
        self.use_bomb[rireki.2 .0][rireki.2 .1] = true;
        self.jun.insert(rireki.1, rireki.2);
    }

    fn insert_jun(&mut self) -> ((Coord, usize), usize, usize) {
        let moto = rnd::next() % self.jun.len();
        let b = self.jun[moto];
        self.jun.remove(moto);
        let tugi = rnd::next() % self.jun.len();
        self.jun.insert(tugi, b);
        (b, moto, tugi)
    }
    fn undo_insert(&mut self, rireki: ((Coord, usize), usize, usize)) {
        self.jun.remove(rireki.2);
        self.jun.insert(rireki.1, rireki.0);
    }
}

fn annealing(input: &Input, duration: f64, mut state: State) -> State {
    let start_time = get_time();
    let duration_inv = 1.0 / duration;
    let start_temp: f64 = state.score as f64 / 30.0;
    let end_temp: f64 = start_temp / 5000.0;
    let 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 < 10 {
            let now_score = state.score;
            let pos = select_2(state.jun.len());
            state.swap_jun(pos);
            state.calc_score_4(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 < 40 {
            let now_score = state.score;
            let rireki = state.insert_jun();
            state.calc_score_4(input);
            let next_score = state.score;
            if is_accepted(now_score, next_score, temp, &loglis) {
                cnt_kousin += 1;
            } else {
                state.undo_insert(rireki);
                state.score = now_score;
            }
        } else {
            let now_score = state.score;
            let rireki = state.swap_off2(input);

            if !rireki.0 {
                state.undo_swap_off(input, rireki);
                continue;
            }
            state.calc_score_4(input);
            let next_score = state.score;

            if is_accepted(now_score, next_score, temp, &loglis) {
                cnt_kousin += 1;
            } else {
                //
                state.undo_swap_off(input, rireki);
                state.score = now_score;
            }
        }
        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>,
    shops: Vec<Coord>,
    can_hakai: Map2d<Vec<Vec<Coord>>>, // そのマスで爆弾iを使って破壊できるもの
    can_hakai_rev: Map2d<Vec<(Coord, usize)>>, // そのマスを破壊することができるマスと爆弾の種類
    can_hakai_shop: Map2d<Vec<Vec<Coord>>>,
    near_shop: Map2d<Vec<Coord>>,
}

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 can_hakai_shop = 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));
                        if map[np] == Square::Shop {
                            can_hakai_shop[p][bombid].push(np);
                        }
                    }
                }
            }
        }
    }
    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);
            }
        }
    }
    let mut near_shop = Map2d::new(vec![vec![]; N2], N);
    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,
        shops,
        can_hakai,
        can_hakai_rev,
        can_hakai_shop,
        near_shop,
    }
}

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)
}