結果

問題 No.1625 三角形の質問
ユーザー CoCo_Japan_panCoCo_Japan_pan
提出日時 2024-04-03 19:27:28
言語 Rust
(1.77.0)
結果
AC  
実行時間 1,945 ms / 6,000 ms
コード長 31,441 bytes
コンパイル時間 3,660 ms
コンパイル使用メモリ 219,520 KB
実行使用メモリ 155,144 KB
最終ジャッジ日時 2024-04-03 19:28:01
合計ジャッジ時間 29,240 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,676 KB
testcase_01 AC 60 ms
11,796 KB
testcase_02 AC 578 ms
52,748 KB
testcase_03 AC 732 ms
64,896 KB
testcase_04 AC 438 ms
44,368 KB
testcase_05 AC 1,120 ms
91,016 KB
testcase_06 AC 1,862 ms
131,264 KB
testcase_07 AC 1,845 ms
131,336 KB
testcase_08 AC 1,866 ms
129,560 KB
testcase_09 AC 1,918 ms
132,872 KB
testcase_10 AC 1,835 ms
128,532 KB
testcase_11 AC 1,945 ms
131,752 KB
testcase_12 AC 1,856 ms
131,364 KB
testcase_13 AC 1,824 ms
131,064 KB
testcase_14 AC 1,899 ms
130,932 KB
testcase_15 AC 1,856 ms
129,072 KB
testcase_16 AC 204 ms
52,088 KB
testcase_17 AC 515 ms
126,380 KB
testcase_18 AC 55 ms
15,660 KB
testcase_19 AC 651 ms
155,144 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

pub use __cargo_equip::prelude::*;

use algebra::Monoid;
#[allow(unused_imports)]
use proconio::fastout;
use proconio::input;
use segtree_2d_compressed::SegTree2DCompressed;

#[derive(Clone, Copy, Debug)]
enum Query {
    Add(i64, i64, i64),
    Get(i64, i64),
}

#[derive(Clone, Copy, Debug)]
enum MaxMonoid {}
impl Monoid for MaxMonoid {
    type Target = i64;
    fn binary_operation(a: &Self::Target, b: &Self::Target) -> Self::Target {
        *a.max(b)
    }
    fn id_element() -> Self::Target {
        -1
    }
}

/*#[fastout]
fn main() {
    input! {
        n: usize,
        q: usize,
        a_b_c_d_e_f: [(i64, i64, i64, i64, i64, i64); n],
    }
    let mut queries = a_b_c_d_e_f.into_iter().map(l_r_area).collect::<Vec<_>>();
    for _ in 0..q {
        input! {
            query_type: i64,
        }
        if query_type == 1 {
            input! {
                add: (i64, i64, i64, i64, i64, i64)
            }
            queries.push(l_r_area(add));
        } else {
            input! {
                l: i64,
                r: i64,
            }
            queries.push(Query::Get(l, r));
        }
    }
    let queries = queries;
    let update_queries = queries
        .iter()
        .filter_map(|query| match query {
            Query::Add(l, r, _) => Some((*l, *r)),
            _ => None,
        })
        .collect::<Vec<_>>();
    let mut segtree = SegTree2DCompressed::<MaxMonoid, i64>::new(&update_queries);
    for query in queries {
        match query {
            Query::Add(l, r, area) => segtree.set(l, r, area),
            Query::Get(l, r) => println!("{}", segtree.prod(l..=r, l..=r)),
        }
    }
}*/
fn main() {
    let __proconio_stdout = ::std::io::stdout();
    let mut __proconio_stdout = ::std::io::BufWriter::new(__proconio_stdout.lock());
    #[allow(unused_macros)]
    macro_rules ! print { ($ ($ tt : tt) *) => { { use std :: io :: Write as _ ; :: std :: write ! (__proconio_stdout , $ ($ tt) *) . unwrap () ; } } ; }
    #[allow(unused_macros)]
    macro_rules ! println { ($ ($ tt : tt) *) => { { use std :: io :: Write as _ ; :: std :: writeln ! (__proconio_stdout , $ ($ tt) *) . unwrap () ; } } ; }
    let __proconio_res = {
        input! { n : usize , q : usize , a_b_c_d_e_f : [(i64 , i64 , i64 , i64 , i64 , i64) ; n] , }
        let mut queries = a_b_c_d_e_f.into_iter().map(l_r_area).collect::<Vec<_>>();
        for _ in 0..q {
            input! { query_type : i64 , }
            if query_type == 1 {
                input! { add : (i64 , i64 , i64 , i64 , i64 , i64) }
                queries.push(l_r_area(add));
            } else {
                input! { l : i64 , r : i64 , }
                queries.push(Query::Get(l, r));
            }
        }
        let queries = queries;
        let update_queries = queries
            .iter()
            .filter_map(|query| match query {
                Query::Add(l, r, _) => Some((*l, *r)),
                _ => None,
            })
            .collect::<Vec<_>>();
        let mut segtree = SegTree2DCompressed::<MaxMonoid, i64>::new(&update_queries);
        for query in queries {
            match query {
                Query::Add(l, r, area) => segtree.set(l, r, area),
                Query::Get(l, r) => println!("{}", segtree.prod(l..=r, l..=r)),
            }
        }
    };
    <::std::io::BufWriter<::std::io::StdoutLock> as ::std::io::Write>::flush(
        &mut __proconio_stdout,
    )
    .unwrap();
    return __proconio_res;
}

fn l_r_area(x: (i64, i64, i64, i64, i64, i64)) -> Query {
    let x_list = [x.0, x.2, x.4];
    let left = *x_list.iter().min().unwrap();
    let right = *x_list.iter().max().unwrap();
    let y_list = [x.1, x.3, x.5];
    let x_list_parralel = x_list
        .into_iter()
        .map(|x| x - x_list[0])
        .collect::<Vec<_>>();
    let y_list_parralel = y_list
        .into_iter()
        .map(|y| y - y_list[0])
        .collect::<Vec<_>>();
    let area =
        (x_list_parralel[1] * y_list_parralel[2] - x_list_parralel[2] * y_list_parralel[1]).abs();
    Query::Add(left, right, area)
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `algebra 0.1.0 (path+████████████████████████████████████████████████████)`                                            published in ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::algebra`
///  - `internal_type_traits 0.1.0 (path+███████████████████████████████████████████████████████████████████████████)`        published in **missing**                                           licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::__internal_type_traits_0_1_0`
///  - `proconio 0.4.5 (registry+https://github.com/rust-lang/crates.io-index)`                                                                                                                  licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip::crates::proconio`
///  - `segtree 0.1.0 (path+███████████████████████████████████████████████████████████████████)`                             published in ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::__segtree_0_1_0`
///  - `segtree_2d_compressed 0.1.0 (path+█████████████████████████████████████████████████████████████████████████████████)` published in ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::segtree_2d_compressed`
/// 
///  # Procedural macros
/// 
///  - `proconio-derive 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0`
/// 
///  # License and Copyright Notices
/// 
///  - `proconio 0.4.5 (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 algebra {use std::fmt::Debug;pub trait Map:Clone{type Target:Clone;fn id_map()->Self;fn composition(&mut self,rhs:&Self);fn mapping(&self,target:&mut Self::Target);}pub trait CommutativeMap:Map{}pub trait NonCommutativeMap:Map{}pub trait Monoid{type Target:Debug+Clone;fn id_element()->Self::Target;fn binary_operation(a:&Self::Target,b:&Self::Target)->Self::Target;}pub trait MapMonoid{type Monoid:Monoid;type Map:Map<Target=<Self::Monoid as Monoid>::Target>;fn id_element()-><Self::Monoid as Monoid>::Target{Self::Monoid::id_element()}fn binary_operation(a:&<Self::Monoid as Monoid>::Target,b:&<Self::Monoid as Monoid>::Target,)-><Self::Monoid as Monoid>::Target{Self::Monoid::binary_operation(a,b)}fn id_map()->Self::Map{Self::Map::id_map()}fn composition(f:&mut Self::Map,g:&Self::Map){f.composition(g)}fn mapping(x:&mut<Self::Monoid as Monoid>::Target,f:&Self::Map){f.mapping(x)}}pub trait CommutativeMapMonoid:MapMonoid{}pub trait NonCommutativeMapMonoid:MapMonoid{}pub trait IdempotentMonoid:Monoid{}}
        pub mod __internal_type_traits_0_1_0 {use std::ops::{Add,AddAssign,Sub,SubAssign};pub trait Integral:Copy+Add<Output=Self>+AddAssign+Sub<Output=Self>+SubAssign+Ord+Zero+One+BoundedBelow+BoundedAbove{}pub trait Zero{fn zero()->Self;}pub trait One{fn one()->Self;}pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::MIN}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::MAX}}impl Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}
        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::*;use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::io::BufRead;pub enum Chars{}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()}}pub enum Bytes{}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()}}pub enum Usize1{}impl Readable for Usize1{type Output=usize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->usize{usize::read(source).checked_sub(1).expect("attempted to read the value 0 as a Usize1")}}pub enum Isize1{}impl Readable for Isize1{type Output=isize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->isize{isize::read(source).checked_sub(1).unwrap_or_else(||{panic!(concat!("attempted to read the value {} as a Isize1:"," the value is isize::MIN and cannot be decremented"),std::isize::MIN,)})}}}pub mod source{use crate::__cargo_equip::preludes::proconio::*;use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;pub mod line{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use crate::__cargo_equip::crates::proconio::source::tokens::Tokens;use std::io::BufRead;pub struct LineSource<R:BufRead>{tokens:Tokens,reader:R,}impl<R:BufRead>LineSource<R>{pub fn new(reader:R)->LineSource<R>{LineSource{tokens:"".to_owned().into(),reader,}}fn prepare(&mut self){while self.tokens.is_empty(){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.tokens=line.into();}}}impl<R:BufRead>Source<R>for LineSource<R>{fn next_token(&mut self)->Option<&str>{self.prepare();self.tokens.next_token()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.is_empty()}}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 crate::__cargo_equip::crates::proconio::source::tokens::Tokens;use std::io::BufRead;use std::marker::PhantomData;pub struct OnceSource<R:BufRead>{tokens:Tokens,_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.");OnceSource{tokens:context.into(),_read:PhantomData,}}}impl<R:BufRead>Source<R>for OnceSource<R>{fn next_token(&mut self)->Option<&str>{self.tokens.next_token()}fn is_empty(&mut self)->bool{self.tokens.is_empty()}}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()))}}}mod tokens{use crate::__cargo_equip::preludes::proconio::*;use std::{iter::Peekable,ptr::NonNull,str::SplitWhitespace};pub(super)struct Tokens{tokens:Peekable<SplitWhitespace<'static>>,_current_context:CurrentContext,}impl Tokens{pub(super)fn next_token(&mut self)->Option<&str>{self.tokens.next()}pub(super)fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}impl From<String>for Tokens{fn from(current_context:String)->Self{let current_context=CurrentContext::from(current_context);unsafe{let tokens=current_context.0.as_ref().split_whitespace().peekable();Self{tokens,_current_context:current_context,}}}}unsafe impl Send for Tokens{}unsafe impl Sync for Tokens{}struct CurrentContext(NonNull<str>);impl From<String>for CurrentContext{fn from(s:String)->Self{let s=s.into_boxed_str();Self(NonNull::new(Box::leak(s)).unwrap())}}impl Drop for CurrentContext{fn drop(&mut self){unsafe{Box::from_raw(self.0.as_mut())};}}}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>;#[allow(clippy::wrong_self_convention)]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;}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,),}}}}use crate::__cargo_equip::crates::proconio::source::{auto::AutoSource,line::LineSource};use std::io::{BufReader,Stdin};use std::sync::OnceLock;use std::{io::{self,BufRead},sync::Mutex,};pub use crate::__cargo_equip::crates::proconio::source::Readable as __Readable;pub enum StdinSource<R:BufRead>{Normal(AutoSource<R>),Interactive(LineSource<R>),Unknown(LineSource<R>),}impl<R:BufRead>source::Source<R>for StdinSource<R>{fn next_token(&mut self)->Option<&str>{match self{StdinSource::Normal(source)=>source.next_token(),StdinSource::Interactive(source)=>source.next_token(),StdinSource::Unknown(source)=>source.next_token(),}}fn is_empty(&mut self)->bool{match self{StdinSource::Normal(source)=>source.is_empty(),StdinSource::Interactive(source)=>source.is_empty(),StdinSource::Unknown(source)=>source.is_empty(),}}}pub static STDIN_SOURCE:OnceLock<Mutex<StdinSource<BufReader<Stdin>>>> =OnceLock::new();#[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.get_or_init(||{std::sync::Mutex::new($crate::__cargo_equip::crates::proconio::StdinSource::Normal($crate::__cargo_equip::crates::proconio::source::auto::AutoSource::new(std::io::BufReader::new(std::io::stdin())),))}).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_input_interactive{($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.get_or_init(||{std::sync::Mutex::new($crate::__cargo_equip::crates::proconio::StdinSource::Interactive($crate::__cargo_equip::crates::proconio::source::line::LineSource::new(std::io::BufReader::new(std::io::stdin())),))}).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)*}drop(locked_stdin);};}macro_rules!input_interactive{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_input_interactive!{$($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::__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::__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 source::Source;let mut lock=STDIN_SOURCE.get_or_init(||{Mutex::new(StdinSource::Unknown(LineSource::new(BufReader::new(io::stdin(),))))}).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_2_1 {pub use crate::__cargo_equip::macros::__proconio_derive_0_2_1::*;#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_2_1_derive_readable{($(_:tt)*)=>(::std::compile_error!("`derive_readable` from `proconio-derive 0.2.1` should have been expanded");)}#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_2_1_fastout{($(_:tt)*)=>(::std::compile_error!("`fastout` from `proconio-derive 0.2.1` should have been expanded");)}}
        pub mod __segtree_0_1_0 {use crate::__cargo_equip::preludes::__segtree_0_1_0::*;use algebra::Monoid;use std::ops::RangeBounds;#[derive(Debug,Clone,PartialEq,Eq)]pub struct SegTree<M:Monoid>{range_size:usize,leaf_size:usize,log:usize,data:Vec<M::Target>,}impl<M:Monoid>From<&Vec<M::Target>>for SegTree<M>{fn from(v:&Vec<M::Target>)->Self{let range_size=v.len();let log=(32-(range_size as u32).saturating_sub(1).leading_zeros())as usize;let leaf_size=1<<log;let mut data=vec![M::id_element();leaf_size*2];data[leaf_size..leaf_size+range_size].clone_from_slice(v);let mut seg_tree=SegTree{range_size,leaf_size,log,data,};for i in(1..leaf_size).rev(){seg_tree.update(i);}seg_tree}}impl<M:Monoid>SegTree<M>{pub fn new(n:usize)->Self{(&vec![M::id_element();n]).into()}pub fn set(&mut self,mut p:usize,x:M::Target){assert!(p<self.range_size);p+=self.leaf_size;self.data[p]=x;for i in 1..=self.log{self.update(p>>i);}}pub fn get(&self,p:usize)->M::Target{assert!(p<self.range_size);self.data[p+self.leaf_size].clone()}pub fn prod<R:RangeBounds<usize>>(&self,range:R)->M::Target{let mut l=match range.start_bound(){std::ops::Bound::Included(&l)=>l,std::ops::Bound::Excluded(&l)=>l+1,std::ops::Bound::Unbounded=>0,};let mut r=match range.end_bound(){std::ops::Bound::Included(&r)=>r+1,std::ops::Bound::Excluded(&r)=>r,std::ops::Bound::Unbounded=>self.range_size,};assert!(l<=r&&r<=self.range_size);if l==0&&r==self.range_size{return self.all_prod();}l+=self.leaf_size;r+=self.leaf_size;let mut sml=M::id_element();let mut smr=M::id_element();while l<r{if l&1!=0{sml=M::binary_operation(&sml,&self.data[l]);l+=1;}if r&1!=0{r-=1;smr=M::binary_operation(&self.data[r],&smr);}l>>=1;r>>=1;}M::binary_operation(&sml,&smr)}pub fn all_prod(&self)->M::Target{self.data[1].clone()}pub fn max_right<F>(&self,mut l:usize,f:F)->usize where F:Fn(&M::Target)->bool,{assert!(l<=self.range_size);assert!(f(&M::id_element()));if l==self.range_size{return self.range_size;}l+=self.leaf_size;let mut sm=M::id_element();while{while l%2==0{l>>=1;}if!f(&M::binary_operation(&sm,&self.data[l])){while l<self.leaf_size{l>>=1;let res=M::binary_operation(&sm,&self.data[l]);if f(&res){sm=res;l+=1;}}return l-self.leaf_size;}sm=M::binary_operation(&sm,&self.data[l]);l+=1;{let l=l as isize;(l&-l)!=l}}{}self.range_size}pub fn min_left<F>(&self,mut r:usize,f:F)->usize where F:Fn(&M::Target)->bool,{assert!(r<=self.range_size);assert!(f(&M::id_element()));if r==0{return 0;}r+=self.leaf_size;let mut sm=M::id_element();while{r-=1;while r>1&&r%2!=0{r>>=1;}if!f(&M::binary_operation(&self.data[r],&sm)){while r<self.leaf_size{r=2*r+1;let res=M::binary_operation(&self.data[r],&sm);if f(&res){sm=res;r-=1;}}return r+1-self.leaf_size;}sm=M::binary_operation(&self.data[r],&sm);{let r=r as isize;(r&-r)!=r}}{}0}}impl<M:Monoid>SegTree<M>{fn update(&mut self,k:usize){self.data[k]=M::binary_operation(&self.data[k*2],&self.data[k*2+1]);}}}
        pub mod segtree_2d_compressed {use crate::__cargo_equip::preludes::segtree_2d_compressed::*;use algebra::Monoid;use segtree::SegTree;use std::ops::{Range,RangeBounds};use internal_type_traits::Integral;#[derive(Debug)]pub struct SegTree2DCompressed<M:Monoid,T:Integral>{height_compressed:Vec<T>,width_compressed:Vec<Vec<T>>,data:Vec<SegTree<M>>,}impl<M:Monoid,T:Integral>SegTree2DCompressed<M,T>{pub fn new(update_queries:&[(T,T)])->Self{let height_compressed={let mut tmp=update_queries.iter().map(|&(h,_)|h).collect::<Vec<_>>();tmp.sort();tmp.dedup();tmp};let width_compressed={let mut tmp=vec![vec![];height_compressed.len()*2];for&(h,w)in update_queries.iter(){let h=height_compressed.binary_search(&h).unwrap()+height_compressed.len();tmp[h].push(w);}for v in tmp.iter_mut(){v.sort();v.dedup();}for h in(1..height_compressed.len()).rev(){let child_left=tmp[h*2].clone();let child_right=tmp[h*2+1].clone();tmp[h]=child_left.into_iter().chain(child_right).collect();tmp[h].sort();tmp[h].dedup();}tmp};let data=(0..height_compressed.len()*2).map(|i|SegTree::<M>::new(width_compressed[i].len())).collect();Self{height_compressed,width_compressed,data,}}pub fn get(&self,h:T,w:T)->M::Target{if let Ok(h)=self.height_compressed.binary_search(&h){if let Ok(w)=self.width_compressed[h].binary_search(&w){return self.data[h].get(w);}}M::id_element()}pub fn set(&mut self,h:T,w:T,val:M::Target){let mut h=self.height_compressed.binary_search(&h).expect("h is not in update_queries");h+=self.height_compressed.len();while h>0{let w=self.width_compressed[h].binary_search(&w).expect("w is not in update_queries");self.data[h].set(w,val.clone());h>>=1;}}pub fn prod<R1:RangeBounds<T>,R2:RangeBounds<T>>(&self,height_range:R1,width_range:R2,)->M::Target{let height_left=match height_range.start_bound(){std::ops::Bound::Included(&l)=>l,std::ops::Bound::Excluded(&l)=>l+T::one(),std::ops::Bound::Unbounded=>T::min_value(),};let height_right=match height_range.end_bound(){std::ops::Bound::Included(&r)=>r+T::one(),std::ops::Bound::Excluded(&r)=>r,std::ops::Bound::Unbounded=>T::max_value(),};assert!(height_left<=height_right);let mut height_left=self.height_compressed.partition_point(|&h|h<height_left);let mut height_right=self.height_compressed.partition_point(|&h|h<height_right);height_left+=self.height_compressed.len();height_right+=self.height_compressed.len();let mut ret=M::id_element();while height_left<height_right{if height_left&1!=0{let w_range=self.calc_row_range(height_left,&width_range);ret=M::binary_operation(&ret,&self.data[height_left].prod(w_range));height_left+=1;}if height_right&1!=0{height_right-=1;let w_range=self.calc_row_range(height_right,&width_range);ret=M::binary_operation(&ret,&self.data[height_right].prod(w_range));}height_left>>=1;height_right>>=1;}ret}fn calc_row_range<R1:RangeBounds<T>>(&self,h:usize,width_range:&R1)->Range<usize>{let w_left=match width_range.start_bound(){std::ops::Bound::Included(&l)=>l,std::ops::Bound::Excluded(&l)=>l+T::one(),std::ops::Bound::Unbounded=>T::min_value(),};let w_right=match width_range.end_bound(){std::ops::Bound::Included(&r)=>r+T::one(),std::ops::Bound::Excluded(&r)=>r,std::ops::Bound::Unbounded=>T::max_value(),};let w_left=self.width_compressed[h].partition_point(|&w|w<w_left);let w_right=self.width_compressed[h].partition_point(|&w|w<w_right);w_left..w_right}}}
    }

    pub(crate) mod macros {
        pub mod algebra {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_input_interactive as input_interactive,__cargo_equip_macro_def_proconio_read_value as read_value};}
        pub mod __proconio_derive_0_2_1 {pub use crate::{__cargo_equip_macro_def___proconio_derive_0_2_1_derive_readable as derive_readable,__cargo_equip_macro_def___proconio_derive_0_2_1_fastout as fastout};}
        pub mod __segtree_0_1_0 {}
        pub mod segtree_2d_compressed {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod algebra {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__proconio_derive_0_2_1 as proconio_derive;}
        pub mod __proconio_derive_0_2_1 {}
        pub mod __segtree_0_1_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebra;}
        pub mod segtree_2d_compressed {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{algebra,__internal_type_traits_0_1_0 as internal_type_traits,__segtree_0_1_0 as segtree};}
    }
}
0