結果

問題 No.274 The Wall
ユーザー あさくち
提出日時 2023-10-07 00:23:14
言語 Rust
(1.83.0 + proconio)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 32,022 bytes
コンパイル時間 12,326 ms
コンパイル使用メモリ 404,044 KB
最終ジャッジ日時 2024-07-26 17:36:06
合計ジャッジ時間 13,242 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
error[E0659]: `proconio` is ambiguous
 --> src/main.rs:3:5
  |
3 | use proconio::input;
  |     ^^^^^^^^ ambiguous name
  |
  = note: ambiguous because of a conflict between a name from a glob import and an outer scope during import or macro resolution
  = note: `proconio` could refer to a crate passed with `--extern`
  = help: use `::proconio` to refer to this crate unambiguously
note: `proconio` could also refer to the module imported here
 --> src/main.rs:1:9
  |
1 | pub use __cargo_equip::prelude::*;
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^
  = help: consider adding an explicit import of `proconio` to disambiguate
  = help: or use `crate::proconio` to refer to this module unambiguously

For more information about this error, try `rustc --explain E0659`.
error: could not compile `main` (bin "main") due to 1 previous error

ソースコード

diff #
プレゼンテーションモードにする

pub use __cargo_equip::prelude::*;
use proconio::input;
fn main() {
    input! {
        n: usize,
        m: usize,
        l_r: [(usize, usize); n],
    }
    let mut sat = TwoSat::new(n);
    // 0, 1, 2, 3, 4, 5
    // nor: (1,3)
    // rev: (6-3 -1, 6-1 -1) = (3, 5)
    fn reverse(l: usize, r: usize, m: usize) -> (usize, usize) {
        (m - r - 1, m - l - 1)
    }
    for i in 0..n {
        for j in i + 1..n {
            let (l_i, r_i) = l_r[i];
            let (l_j, r_j) = l_r[j];
            let (reversed_l_i, reversed_r_i) = reverse(l_i, r_i, m);
            let (reversed_l_j, reversed_r_j) = reverse(l_j, r_j, m);
            // そのままの向き
            if r_i >= l_j && l_i <= r_j {
                sat.add_clause(i, true, j, true);
            }
            // 左を反転
            if reversed_r_i >= l_j && reversed_l_i <= r_j {
                sat.add_clause(i, false, j, true);
            }
            // 右を反転
            if r_i >= reversed_l_j && l_i <= reversed_r_j {
                sat.add_clause(i, true, j, false);
            }
            // 両方反転
            if reversed_r_i >= reversed_l_j && reversed_l_i <= reversed_r_j {
                sat.add_clause(i, false, j, false);
            }
        }
    }
    if sat.satisfiable() {
        println!("YES");
    } else {
        println!("NO");
    }
}
//https://github.com/rust-lang-ja/ac-library-rs
pub mod internal_scc {
    pub use crate::__cargo_equip::prelude::*;
    pub struct Csr<E> {
        start: Vec<usize>,
        elist: Vec<E>,
    }
    impl<E> Csr<E>
    where
        E: Copy,
    {
        pub fn new(n: usize, edges: &[(usize, E)], init: E) -> Self {
            let mut csr = Csr {
                start: vec![0; n + 1],
                elist: vec![init; edges.len()],
            };
            for e in edges.iter() {
                csr.start[e.0 + 1] += 1;
            }
            for i in 1..=n {
                csr.start[i] += csr.start[i - 1];
            }
            let mut counter = csr.start.clone();
            for e in edges.iter() {
                csr.elist[counter[e.0]] = e.1;
                counter[e.0] += 1;
            }
            csr
        }
    }
    #[derive(Copy, Clone)]
    struct _Edge {
        to: usize,
    }
    /// Reference:
    /// R. Tarjan,
    /// Depth-First Search and Linear Graph Algorithms
    pub struct SccGraph {
        n: usize,
        edges: Vec<(usize, _Edge)>,
    }
    impl SccGraph {
        pub fn new(n: usize) -> Self {
            SccGraph { n, edges: vec![] }
        }
        pub fn num_vertices(&self) -> usize {
            self.n
        }
        pub fn add_edge(&mut self, from: usize, to: usize) {
            self.edges.push((from, _Edge { to }));
        }
        /// return pair of (# of scc, scc id)
        pub fn scc_ids(&self) -> (usize, Vec<usize>) {
            // In C++ ac-library, this function is implemented by using recursive lambda functions.
            // Instead, we use fn and struct for capturing environments.
            struct _Env {
                g: Csr<_Edge>,
                now_ord: usize,
                group_num: usize,
                visited: Vec<usize>,
                low: Vec<usize>,
                ord: Vec<Option<usize>>,
                ids: Vec<usize>,
            }
            let mut env = _Env {
                g: Csr::new(self.n, &self.edges, _Edge { to: 0 }),
                now_ord: 0,
                group_num: 0,
                visited: Vec::with_capacity(self.n),
                low: vec![0; self.n],
                ord: vec![None; self.n],
                ids: vec![0; self.n],
            };
            fn dfs(v: usize, n: usize, env: &mut _Env) {
                env.low[v] = env.now_ord;
                env.ord[v] = Some(env.now_ord);
                env.now_ord += 1;
                env.visited.push(v);
                for i in env.g.start[v]..env.g.start[v + 1] {
                    let to = env.g.elist[i].to;
                    if let Some(x) = env.ord[to] {
                        env.low[v] = std::cmp::min(env.low[v], x);
                    } else {
                        dfs(to, n, env);
                        env.low[v] = std::cmp::min(env.low[v], env.low[to]);
                    }
                }
                if env.low[v] == env.ord[v].unwrap() {
                    loop {
                        let u = *env.visited.last().unwrap();
                        env.visited.pop();
                        env.ord[u] = Some(n);
                        env.ids[u] = env.group_num;
                        if u == v {
                            break;
                        }
                    }
                    env.group_num += 1;
                }
            }
            for i in 0..self.n {
                if env.ord[i].is_none() {
                    dfs(i, self.n, &mut env);
                }
            }
            for x in env.ids.iter_mut() {
                *x = env.group_num - 1 - *x;
            }
            (env.group_num, env.ids)
        }
        pub fn scc(&self) -> Vec<Vec<usize>> {
            let ids = self.scc_ids();
            let group_num = ids.0;
            let mut counts = vec![0usize; group_num];
            for &x in ids.1.iter() {
                counts[x] += 1;
            }
            let mut groups: Vec<Vec<usize>> = (0..ids.0).map(|_| vec![]).collect();
            for i in 0..group_num {
                groups[i].reserve(counts[i]);
            }
            for i in 0..self.n {
                groups[ids.1[i]].push(i);
            }
            groups
        }
    }
}
pub mod twosat {
    //! A 2-SAT Solver.
    pub use crate::__cargo_equip::prelude::*;
    use crate::internal_scc;
    /// A 2-SAT Solver.
    ///
    /// For variables $x_0, x_1, \ldots, x_{N - 1}$ and clauses with from
    ///
    /// \\[
    ///   (x_i = f) \lor (x_j = g)
    /// \\]
    ///
    /// it decides whether there is a truth assignment that satisfies all clauses.
    ///
    /// # Example
    ///
    /// ```
    /// #![allow(clippy::many_single_char_names)]
    ///
    /// use ac_library::TwoSat;
    /// use proconio::{input, marker::Bytes, source::once::OnceSource};
    ///
    /// input! {
    ///     from OnceSource::from(
    ///         "3\n\
    ///          3\n\
    ///          a b\n\
    ///          !b c\n\
    ///          !a !a\n",
    ///     ),
    ///     n: usize,
    ///     pqs: [(Bytes, Bytes)],
    /// }
    ///
    /// let mut twosat = TwoSat::new(n);
    ///
    /// for (p, q) in pqs {
    ///     fn parse(s: &[u8]) -> (usize, bool) {
    ///         match *s {
    ///             [c] => ((c - b'a').into(), true),
    ///             [b'!', c] => ((c - b'a').into(), false),
    ///             _ => unreachable!(),
    ///         }
    ///     }
    ///     let ((i, f), (j, g)) = (parse(&p), parse(&q));
    ///     twosat.add_clause(i, f, j, g);
    /// }
    ///
    /// assert!(twosat.satisfiable());
    /// assert_eq!(twosat.answer(), [false, true, true]);
    /// ```
    pub struct TwoSat {
        n: usize,
        scc: internal_scc::SccGraph,
        answer: Vec<bool>,
    }
    impl TwoSat {
        /// Creates a new `TwoSat` of `n` variables and 0 clauses.
        ///
        /// # Constraints
        ///
        /// - $0 \leq n \leq 10^8$
        ///
        /// # Complexity
        ///
        /// - $O(n)$
        pub fn new(n: usize) -> Self {
            TwoSat {
                n,
                answer: vec![false; n],
                scc: internal_scc::SccGraph::new(2 * n),
            }
        }
        /// Adds a clause $(x_i = f) \lor (x_j = g)$.
        ///
        /// # Constraints
        ///
        /// - $0 \leq i < n$
        /// - $0 \leq j < n$
        ///
        /// # Panics
        ///
        /// Panics if the above constraints are not satisfied.
        ///
        /// # Complexity
        ///
        /// - $O(1)$ amortized
        pub fn add_clause(&mut self, i: usize, f: bool, j: usize, g: bool) {
            assert!(i < self.n && j < self.n);
            self.scc.add_edge(2 * i + !f as usize, 2 * j + g as usize);
            self.scc.add_edge(2 * j + !g as usize, 2 * i + f as usize);
        }
        /// Returns whether there is a truth assignment that satisfies all clauses.
        ///
        /// # Complexity
        ///
        /// - $O(n + m)$ where $m$ is the number of added clauses
        pub fn satisfiable(&mut self) -> bool {
            let id = self.scc.scc_ids().1;
            for i in 0..self.n {
                if id[2 * i] == id[2 * i + 1] {
                    return false;
                }
                self.answer[i] = id[2 * i] < id[2 * i + 1];
            }
            true
        }
        /// Returns a truth assignment that satisfies all clauses **of the last call of [`satisfiable`]**.
        ///
        /// # Constraints
        ///
        /// - [`satisfiable`] is called after adding all clauses and it has returned `true`.
        ///
        /// # Complexity
        ///
        /// - $O(n)$
        ///
        /// [`satisfiable`]: #method.satisfiable
        pub fn answer(&self) -> &[bool] {
            &self.answer
        }
    }
    #[cfg(test)]
    mod tests {
        #![allow(clippy::many_single_char_names)]
        pub use crate::__cargo_equip::prelude::*;
        use super::*;
        #[test]
        fn solve_alpc_h_sample1() {
            // https://atcoder.jp/contests/practice2/tasks/practice2_h
            let (n, d) = (3, 2);
            let x = [1, 2, 0i32];
            let y = [4, 5, 6];
            let mut t = TwoSat::new(n);
            for i in 0..n {
                for j in i + 1..n {
                    if (x[i] - x[j]).abs() < d {
                        t.add_clause(i, false, j, false);
                    }
                    if (x[i] - y[j]).abs() < d {
                        t.add_clause(i, false, j, true);
                    }
                    if (y[i] - x[j]).abs() < d {
                        t.add_clause(i, true, j, false);
                    }
                    if (y[i] - y[j]).abs() < d {
                        t.add_clause(i, true, j, true);
                    }
                }
            }
            assert!(t.satisfiable());
            let answer = t.answer();
            let mut res = vec![];
            for (i, &v) in answer.iter().enumerate() {
                if v {
                    res.push(x[i])
                } else {
                    res.push(y[i]);
                }
            }
            //Check the min distance between flags
            res.sort_unstable();
            let mut min_distance = i32::max_value();
            for i in 1..res.len() {
                min_distance = std::cmp::min(min_distance, res[i] - res[i - 1]);
            }
            assert!(min_distance >= d);
        }
        #[test]
        fn solve_alpc_h_sample2() {
            // https://atcoder.jp/contests/practice2/tasks/practice2_h
            let (n, d) = (3, 3);
            let x = [1, 2, 0i32];
            let y = [4, 5, 6];
            let mut t = TwoSat::new(n);
            for i in 0..n {
                for j in i + 1..n {
                    if (x[i] - x[j]).abs() < d {
                        t.add_clause(i, false, j, false);
                    }
                    if (x[i] - y[j]).abs() < d {
                        t.add_clause(i, false, j, true);
                    }
                    if (y[i] - x[j]).abs() < d {
                        t.add_clause(i, true, j, false);
                    }
                    if (y[i] - y[j]).abs() < d {
                        t.add_clause(i, true, j, true);
                    }
                }
            }
            assert!(!t.satisfiable());
        }
    }
}
use twosat::*;
// The following code was expanded by `cargo-equip`.
///  # Bundled libraries
/// 
///  - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT/Apache-2.0`    as `crate::__cargo_equip
    ::crates::__lazy_static_1_4_0`
///  - `proconio 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)`    licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip
    ::crates::proconio`
/// 
///  # Procedural macros
/// 
///  - `proconio-derive 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0`
/// 
///  # License and Copyright Notices
/// 
///  - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)`
/// 
///      ```text
///      Copyright (c) 2010 The Rust Project Developers
/// 
///      Permission is hereby granted, free of charge, to any
///      person obtaining a copy of this software and associated
///      documentation files (the "Software"), to deal in the
///      Software without restriction, including without
///      limitation the rights to use, copy, modify, merge,
///      publish, distribute, sublicense, and/or sell copies of
///      the Software, and to permit persons to whom the Software
///      is furnished to do so, subject to the following
///      conditions:
/// 
///      The above copyright notice and this permission notice
///      shall be included in all copies or substantial portions
///      of the Software.
/// 
///      THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
///      ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
///      TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
///      PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
///      SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
///      CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
///      OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
///      IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
///      DEALINGS IN THE SOFTWARE.
///      ```
/// 
///  - `proconio 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)`
/// 
///      ```text
///      The MIT License
///      Copyright 2019 (C) statiolake <statiolake@gmail.com>
/// 
///      Permission is hereby granted, free of charge, to any person obtaining a copy of
///      this software and associated documentation files (the "Software"), to deal in
///      the Software without restriction, including without limitation the rights to
///      use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
///      the Software, and to permit persons to whom the Software is furnished to do so,
///      subject to the following conditions:
/// 
///      The above copyright notice and this permission notice shall be included in all
///      copies or substantial portions of the Software.
/// 
///      THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
///      IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
///      FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
///      COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
///      IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
///      CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
/// 
///      Copyright for original `input!` macro is held by Hideyuki Tanaka, 2019.  The
///      original macro is licensed under BSD 3-clause license.
/// 
///      Redistribution and use in source and binary forms, with or without
///      modification, are permitted provided that the following conditions are met:
/// 
///      1. Redistributions of source code must retain the above copyright notice, this
///         list of conditions and the following disclaimer.
/// 
///      2. Redistributions in binary form must reproduce the above copyright notice,
///         this list of conditions and the following disclaimer in the documentation
///         and/or other materials provided with the distribution.
/// 
///      3. Neither the name of the copyright holder nor the names of its contributors
///         may be used to endorse or promote products derived from this software
///         without specific prior written permission.
/// 
///      THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
///      ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
///      WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
///      DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
///      FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
///      DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
///      SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
///      CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
///      OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
///      OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
///      ```
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __lazy_static_1_4_0 {#![no_std]use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;pub use crate::__cargo_equip::macros
            ::__lazy_static_1_4_0::*;#[path="inline_lazy.rs"]pub mod lazy{use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;extern crate 
            core;extern crate std;use self::std::prelude::v1::*;use self::std::cell::Cell;use self::std::hint::unreachable_unchecked;use self::std
            ::sync::Once;#[allow(deprecated)]pub use self::std::sync::ONCE_INIT;pub struct Lazy<T:Sync>(Cell<Option<T>>,Once);impl<T:Sync>Lazy<T
            >{#[allow(deprecated)]pub const INIT:Self=Lazy(Cell::new(None),ONCE_INIT);#[inline(always)]pub fn get<F>(&'static self,f:F)->&T where F
            :FnOnce()->T,{self.1.call_once(||{self.0.set(Some(f()));});unsafe{match*self.0.as_ptr(){Some(ref x)=>x,None=>{debug_assert!(false
            ,"attempted to derefence an uninitialized lazy static. This is a bug");unreachable_unchecked()},}}}}unsafe impl<T:Sync>Sync for Lazy<T
            >{}#[macro_export]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create{($NAME:ident,$T:ty)=>{static$NAME:$crate
            ::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy<$T> =$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy::INIT;}
            ;}macro_rules!__lazy_static_create{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create!{$($tt)*})}}pub 
            use core::ops::Deref as __Deref;#[macro_export(local_inner_macros
            )]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal{($(#[$attr:meta])*($($vis:tt)*)static ref$N:ident:$T:ty
            =$e:expr;$($t:tt)*)=>{__lazy_static_internal!(@MAKE TY,$(#[$attr])*,($($vis)*),$N);__lazy_static_internal!(@TAIL,$N:$T=$e);lazy_static!($
            ($t)*);};(@TAIL,$N:ident:$T:ty=$e:expr)=>{impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::__Deref for$N{type Target=$T;fn deref
            (&self)->&$T{#[inline(always)]fn __static_ref_initialize()->$T{$e}#[inline(always)]fn __stability()->&'static$T{__lazy_static_create!
            (LAZY,$T);LAZY.get(__static_ref_initialize)}__stability()}}impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::LazyStatic for$N{fn 
            initialize(lazy:&Self){let _=&**lazy;}}};(@MAKE TY,$(#[$attr:meta])*,($($vis:tt)*),$N:ident)=>{#[allow(missing_copy_implementations
            )]#[allow(non_camel_case_types)]#[allow(dead_code)]$(#[$attr])*$($vis)*struct$N{__private_field:()}#[doc(hidden)]$($vis)*static$N:$N
            =$N{__private_field:()};};()=>()}macro_rules!__lazy_static_internal{($($tt:tt)*)=>(crate
            ::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal!{$($tt)*})}#[macro_export(local_inner_macros
            )]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static{($(#[$attr:meta])*static ref$N:ident:$T:ty=$e:expr;$($t:tt
            )*)=>{__lazy_static_internal!($(#[$attr])*()static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub static ref$N:ident:$T:ty=$e:expr;$($t:tt
            )*)=>{__lazy_static_internal!($(#[$attr])*(pub)static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub($($vis:tt)+)static ref$N:ident:$T:ty=$e
            :expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub($($vis)+))static ref$N:$T=$e;$($t)*);};()=>()}macro_rules!lazy_static{($($tt
            :tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static!{$($tt)*})}pub trait LazyStatic{fn initialize(lazy:&Self);}pub fn 
            initialize<T:LazyStatic>(lazy:&T){LazyStatic::initialize(lazy);}}
        pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]use crate::__cargo_equip::preludes::proconio::*;pub use crate
            ::__cargo_equip::macros::proconio::*;pub use proconio_derive::*;pub mod marker{use crate::__cargo_equip::preludes::proconio::*;pub enum 
            Chars{}pub enum Bytes{}pub enum Usize1{}pub enum Isize1{}}pub mod read{use crate::__cargo_equip::preludes::proconio::*;use crate
            ::__cargo_equip::crates::proconio::marker::{Bytes,Chars,Isize1,Usize1};use crate::__cargo_equip::crates::proconio::source::{Readable
            ,Source};use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;impl<T:FromStr>Readable for T where T
            ::Err:Debug,{type Output=T;fn read<R:BufRead,S:Source<R>>(source:&mut S)->T{let token=source.next_token_unwrap();match token.parse(){Ok(v
            )=>v,Err(e)=>panic!(concat!("failed to parse the input `{input}` ","to the value of type `{ty}`: {err:?}; ","ensure that the input format 
            is collectly specified ","and that the input value must handle specified type.",),input=token,ty=type_name::<T>(),err=e,),}}}impl 
            Readable for Chars{type Output=Vec<char>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<char>{source.next_token_unwrap().chars
            ().collect()}}impl Readable for Bytes{type Output=Vec<u8>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<u8>{source.next_token_unwrap
            ().bytes().collect()}}impl Readable for Usize1{type Output=usize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->usize{usize::read(source
            )-1}}impl Readable for Isize1{type Output=isize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->isize{isize::read(source)-1}}}pub mod 
            source{use crate::__cargo_equip::preludes::proconio::*;use std::io::BufRead;pub mod line{use crate::__cargo_equip::preludes::proconio
            ::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::str::SplitWhitespace;pub struct LineSource<R:BufRead>{tokens
            :Peekable<SplitWhitespace<'static>>,current_context:Box<str>,reader:R,}impl<R:BufRead>LineSource<R>{pub fn new(reader:R)->LineSource<R
            >{LineSource{current_context:"".to_string().into_boxed_str(),tokens:"".split_whitespace().peekable(),reader,}}fn prepare(&mut self){while 
            self.tokens.peek().is_none(){let mut line=String::new();let num_bytes=self.reader.read_line(&mut line).expect("failed to get linel maybe 
            an IO error.");if num_bytes==0{return;}self.current_context=line.into_boxed_str();self.tokens=unsafe{std::mem::transmute::<_,&'static str
            >(&*self.current_context)}.split_whitespace().peekable();}}}impl<R:BufRead>Source<R>for LineSource<R>{fn next_token(&mut self)->Option
            <&str>{self.prepare();self.tokens.next()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.peek().is_none()}}use std::io::BufReader
            ;impl<'a>From<&'a str>for LineSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->LineSource<BufReader<&'a[u8]>>{LineSource::new(BufReader
            ::new(s.as_bytes()))}}}pub mod once{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter
            ::Peekable;use std::marker::PhantomData;use std::str::SplitWhitespace;pub struct OnceSource<R:BufRead>{tokens:Peekable<SplitWhitespace
            <'static>>,context:Box<str>,_read:PhantomData<R>,}impl<R:BufRead>OnceSource<R>{pub fn new(mut source:R)->OnceSource<R>{let mut context
            =String::new();source.read_to_string(&mut context).expect("failed to read from source; maybe an IO error.");let context=context
            .into_boxed_str();let mut res=OnceSource{context,tokens:"".split_whitespace().peekable(),_read:PhantomData,};use std::mem;let context
            :&'static str=unsafe{mem::transmute(&*res.context)};res.tokens=context.split_whitespace().peekable();res}}impl<R:BufRead>Source<R>for 
            OnceSource<R>{fn next_token(&mut self)->Option<&str>{self.tokens.next()}fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}use 
            std::io::BufReader;impl<'a>From<&'a str>for OnceSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->OnceSource<BufReader<&'a[u8]>>{OnceSource
            ::new(BufReader::new(s.as_bytes()))}}}pub mod auto{use crate::__cargo_equip::preludes::proconio::*;#[cfg(debug_assertions)]pub use super
            ::line::LineSource as AutoSource;#[cfg(not(debug_assertions))]pub use super::once::OnceSource as AutoSource;}pub trait Source<R:BufRead
            >{fn next_token(&mut self)->Option<&str>;fn is_empty(&mut self)->bool;fn next_token_unwrap(&mut self)->&str{self.next_token().expect
            (concat!("failed to get the next token; ","maybe reader reached an end of input. ","ensure that arguments for `input!` macro is correctly 
            ","specified to match the problem input."))}}impl<R:BufRead,S:Source<R>>Source<R>for&'_ mut S{fn next_token(&mut self)->Option<&str>{
            (*self).next_token()}fn is_empty(&mut self)->bool{(*self).is_empty()}}pub trait Readable{type Output;fn read<R:BufRead,S:Source<R
            >>(source:&mut S)->Self::Output;}}use crate::__cargo_equip::crates::proconio::source::auto::AutoSource;use lazy_static::lazy_static;use 
            std::io;use std::io::{BufReader,Stdin};use std::sync::Mutex;lazy_static!{#[doc(hidden)]pub static ref STDIN_SOURCE:Mutex<AutoSource
            <BufReader<Stdin>>>=Mutex::new(AutoSource::new(BufReader::new(io::stdin
            ())));}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_input{(@from[$source:expr]@rest)=>{};(@from[$source:expr]@rest mut$
            ($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[mut]@rest$($rest)*}};(@from[$source:expr]@rest$($rest
            :tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt
            )?]@rest$var:tt:$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[$($mut)*]@var$var@kind[]@rest$($rest
            )*}};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest)=>{let$($mut)*$var=$crate::__cargo_equip::crates::proconio
            ::read_value!(@source[$source]@kind[$($kind)*]);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest,$($rest:tt
            )*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*]@rest);$crate::__cargo_equip
            ::crates::proconio::input!(@from[$source]@rest$($rest)*);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest$tt
            :tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*$tt]@rest$($rest
            )*);};(from$source:expr,$($rest:tt)*)=>{#[allow(unused_variables,unused_mut)]let mut s=$source;$crate::__cargo_equip::crates::proconio
            ::input!{@from[&mut s]@rest$($rest)*}};($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.lock
            ().expect(concat!("failed to lock the stdin; please re-run this program.  ","If this issue repeatedly occur, this is a bug in `proconio`. 
             ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));$crate::__cargo_equip::crates::proconio
            ::input!{@from[&mut*locked_stdin]@rest$($rest)*}drop(locked_stdin);};}macro_rules!input{($($tt:tt)*)=>(crate
            ::__cargo_equip_macro_def_proconio_input!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_read_value{
            (@source[$source:expr]@kind[[$($kind:tt)*]])=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[]@rest$
            ($kind)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest)=>{{let len=<usize as$crate::__cargo_equip::crates::proconio::source
            ::Readable>::read($source);$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[[$($kind)*;len]])}}
            ;(@array@source[$source:expr]@kind[$($kind:tt)*]@rest;$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!
            (@array@source[$source]@kind[$($kind)*]@len[$($rest)*])};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate
            ::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*$tt]@rest$($rest)*)};(@array@source[$source
            :expr]@kind[$($kind:tt)*]@len[$($len:tt)*])=>{{let len=$($len)*;(0..len).map(|_|$crate::__cargo_equip::crates::proconio::read_value!
            (@source[$source]@kind[$($kind)*])).collect::<Vec<_>>()}};(@source[$source:expr]@kind[($($kinds:tt)*)])=>{$crate::__cargo_equip::crates
            ::proconio::read_value!(@tuple@source[$source]@kinds[]@current[]@rest$($kinds)*)};(@tuple@source[$source:expr]@kinds[$([$($kind:tt)*]
            )*]@current[]@rest)=>{($($crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]),)*)}
            ;(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest)=>{$crate::__cargo_equip::crates::proconio::read_value!
            (@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr
            :tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr
            )*]]@current[]@rest$($rest)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate
            ::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*]@current[$($curr)*$tt]@rest$($rest)*)}
            ;(@source[$source:expr]@kind[])=>{compile_error!(concat!("Reached unreachable statement while parsing macro input.  ","This is a bug in 
            `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));};(@source[$source
            :expr]@kind[$kind:ty])=>{<$kind as$crate::__cargo_equip::crates::proconio::source::Readable>::read($source)}}macro_rules!read_value{($
            ($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_read_value!{$($tt)*})}pub fn is_stdin_empty()->bool{use crate::__cargo_equip::crates
            ::proconio::source::Source;let mut lock=STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program.  ","If 
            this issue repeatedly occur, this is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs
            /issues>."));lock.is_empty()}}
        pub mod __proconio_derive_0_1_9 {pub use crate::__cargo_equip::macros::__proconio_derive_0_1_9
            ::*;#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_1_9_derive_readable{($(_:tt)*)=>(::std::compile_error!
            ("`derive_readable` from `proconio-derive 0.1.9` should have been expanded"
            );)}#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_1_9_fastout{($(_:tt)*)=>(::std::compile_error!("`fastout` from 
            `proconio-derive 0.1.9` should have been expanded");)}}
    }
    pub(crate) mod macros {
        pub mod __lazy_static_1_4_0 {pub use crate::{__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create as __lazy_static_create
            ,__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal as __lazy_static_internal
            ,__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static as lazy_static};}
        pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_read_value as read_value}
            ;}
        pub mod __proconio_derive_0_1_9 {pub use crate::{__cargo_equip_macro_def___proconio_derive_0_1_9_derive_readable as derive_readable
            ,__cargo_equip_macro_def___proconio_derive_0_1_9_fastout as fastout};}
    }
    pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::__lazy_static_1_4_0::*};}
    mod preludes {
        pub mod __lazy_static_1_4_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;}
        pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;pub(in crate::__cargo_equip)use crate
            ::__cargo_equip::crates::{__lazy_static_1_4_0 as lazy_static,__proconio_derive_0_1_9 as proconio_derive};}
        pub mod __proconio_derive_0_1_9 {}
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0