use std::collections::HashMap;
pub use __cargo_equip::prelude::*;
#[allow(unused_imports)]
use proconio::fastout;
use proconio::input;
// #[fastout]
fn solve() {
// write your solution here!
}
fn main() {
input! {
t: usize
}
for _ in 0..t {
solve();
}
}
// The following code was expanded by `cargo-equip`.
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod __algo_0_1_0 {pub use crate::__cargo_equip::macros::__algo_0_1_0::*;pub mod math{pub mod primes{use super::Integer;pub trait PrimeExt:Integer{fn is_prime(&self)->bool{if*self<Self::ZERO{panic!("failed to check whether integer '{:?}' is a prime number, because it is smaller than zero for which this function is undefined",self);}if*self==Self::ZERO||*self==Self::ONE{return false;}let mut cur=Self::from_i64(2);while cur*cur<=*self{if*self%cur==Self::ZERO{return false;}cur=cur+Self::ONE;}true}fn factorize(&self)->Vec<Self>{if*self<Self::ZERO{panic!("failed to find prime factors of the integer '{:?}', because it is smaller than zero for which this function is undefined",self);}let mut result=vec![];let mut k=Self::from_i64(2);let mut n=*self;while k*k<=*self{while n%k==Self::ZERO{result.push(k);n=n/k;}k=k+Self::ONE;}if n>Self::ONE{result.push(n);}result}}impl<T:Integer>PrimeExt for T{}}pub mod integer{use std::{ops::{Mul,Div,Rem,Add,Sub},fmt::{Display,Debug}};pub trait Integer:Sized+Mul<Self,Output=Self>+Div<Self,Output=Self>+Rem<Self,Output=Self>+Add<Self,Output=Self>+Sub<Self,Output=Self>+PartialEq+Eq+Ord+PartialOrd+Copy+Clone+Display+Debug{const ONE:Self;const ZERO:Self;fn from_i64(val:i64)->Self;}macro_rules!impl_integer{($t:ty)=>{impl Integer for$t{const ONE:Self=1;const ZERO:Self=0;fn from_i64(val:i64)->Self{val as$t}}};}impl_integer!(usize);impl_integer!(isize);impl_integer!(i32);impl_integer!(i64);impl_integer!(u32);impl_integer!(u64);}pub use integer::Integer;pub mod modular{use std::{ops::{Add,Mul,Sub,Div,AddAssign,MulAssign,SubAssign,DivAssign},fmt::Display};#[derive(Copy,Clone,Default,Debug,PartialEq,PartialOrd,Eq,Ord)]pub struct MInt<const MODULUS:u64>{pub value:u64}impl<const M:u64>Display for MInt<M>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.value)}}impl<const MODULUS:u64>MInt<MODULUS>{pub fn one()->Self{Self{value:1}}pub fn zero()->Self{Self{value:0}}pub fn new(value:u64)->Self{Self{value:value%MODULUS}}pub fn pow(self,n:u64)->MInt<MODULUS>{let mut result=Self::one();let mut base=self;let mut exponent=n;while exponent>0{if exponent%2==1{result=result*base;}base=base*base;exponent/=2;}result}fn extended_gcd(a:i64,b:i64)->(i64,i64,i64){if a==0{(b,0,1)}else{let(g,x,y)=Self::extended_gcd(b%a,a);(g,y-(b/a)*x,x)}}pub fn inv(self)->Self{let(_,x,_)=Self::extended_gcd(self.value as i64,MODULUS as i64);Self::new((x+MODULUS as i64)as u64)}}impl<const T:u64>Add<MInt<T>>for MInt<T>{type Output=MInt<T>;fn add(self,rhs:MInt<T>)->Self::Output{let mut value=self.value+rhs.value;if value>=T{value-=T;}Self{value}}}impl<const T:u64>AddAssign<MInt<T>>for MInt<T>{fn add_assign(&mut self,rhs:MInt<T>){*self=*self+rhs;}}impl<const T:u64>Mul<MInt<T>>for MInt<T>{type Output=MInt<T>;fn mul(self,rhs:MInt<T>)->Self::Output{Self{value:(self.value*rhs.value)%T}}}impl<const T:u64>MulAssign<MInt<T>>for MInt<T>{fn mul_assign(&mut self,rhs:MInt<T>){self.value=(self.value*rhs.value)%T;}}impl<const T:u64>Sub<MInt<T>>for MInt<T>{type Output=MInt<T>;fn sub(self,rhs:MInt<T>)->Self::Output{let mut value=self.value+T-rhs.value;if value>=T{value-=T;}Self{value}}}impl<const T:u64>SubAssign<MInt<T>>for MInt<T>{fn sub_assign(&mut self,rhs:MInt<T>){*self=*self-rhs;}}impl<const T:u64>Div<MInt<T>>for MInt<T>{type Output=MInt<T>;fn div(self,rhs:MInt<T>)->Self::Output{self*rhs.inv()}}impl<const T:u64>DivAssign<MInt<T>>for MInt<T>{fn div_assign(&mut self,rhs:MInt<T>){*self=*self/rhs;}}impl<const T:u64>Into<MInt<T>>for u64{fn into(self)->MInt<T>{MInt::new(self)}}}pub fn gcd<T:Integer>(mut a:T,mut b:T)->T{if a>b{std::mem::swap(&mut a,&mut b);}while a!=T::ZERO{b=b%a;std::mem::swap(&mut a,&mut b);}b}pub fn lcm<T:Integer>(a:T,b:T)->T{a/gcd(a,b)*b}}pub mod collections{pub mod segment_tree{use std::ops::{Range,RangeBounds};pub struct SegmentTree<T,F>{n:usize,data:Vec<T>,neutral:T,f:F,}impl<T,F>SegmentTree<T,F>where T:Clone,F:Fn(&T,&T)->T,{pub fn new(n:usize,neutral:T,f:F)->Self{let mut size=1;while size<n{size*=2;}Self{n:size,data:vec![neutral.clone();2*size],neutral,f,}}pub fn new_from_iter<I>(iter:I,neutral:T,f:F)->Self where I:IntoIterator<Item=T>,{let v:Vec<_> =iter.into_iter().collect();let mut size=1;while size<v.len(){size<<=1;}let mut data=vec![neutral.clone();size<<1];for i in 0..v.len(){data[size+i]=v[i].clone();}for i in(1..size).rev(){data[i]=(f)(&data[i<<1],&data[(i<<1)+1]);}Self{n:size,data,neutral,f,}}pub fn update(&mut self,i:usize,value:T){let mut i=i+self.n;self.data[i]=value;while i>1{i>>=1;self.data[i]=(self.f)(&self.data[i<<1],&self.data[(i<<1)+1]);}}pub fn get(&self,i:usize)->&T{&self.data[i+self.n]}pub fn query(&self,range:impl RangeBounds<usize>)->T{self.query_inner(range,1,..)}fn to_range(&self,range:impl RangeBounds<usize>)->Range<usize>{let start=match range.start_bound(){std::ops::Bound::Included(&p)=>p,std::ops::Bound::Excluded(&p)=>p+1,std::ops::Bound::Unbounded=>0,};let end=match range.end_bound(){std::ops::Bound::Included(&p)=>p+1,std::ops::Bound::Excluded(&p)=>p,std::ops::Bound::Unbounded=>self.n,};start..end}fn query_inner(&self,range:impl RangeBounds<usize>,i:usize,inner_range:impl RangeBounds<usize>)->T{let range=self.to_range(range);let inner_range=self.to_range(inner_range);if range.start>=range.end{return self.neutral.clone();}if range.start==inner_range.start&&range.end==inner_range.end{return self.data[i].clone();}let mid=(inner_range.start+inner_range.end)>>1;let left=self.query_inner(range.start..mid.min(range.end),i<<1,inner_range.start..mid);let right=self.query_inner(mid.max(range.start)..range.end,(i<<1)+1,mid..inner_range.end);(self.f)(&left,&right)}pub fn data(&self)->&[T]{&self.data[self.n..]}}pub struct SegmentTreeRU<T,F,G,H>{n:usize,data:Vec<T>,lazy:Vec<Option<T>>,neutral:T,f:F,g:G,h:H}impl<T,F,G,H>SegmentTreeRU<T,F,G,H>where T:Clone+Copy,F:Fn(&T,&T)->T,G:Fn(&T,&T,usize)->T,H:Fn(&T,&T)->T{pub fn new(n:usize,neutral:T,f:F,g:G,h:H)->Self{let mut size=1;while size<n{size*=2;}Self{n:size,data:vec![neutral.clone();size*2],lazy:vec![None;size*2],neutral,f,g,h}}pub fn new_from_iter<I>(iter:I,neutral:T,f:F,g:G,h:H)->Self where I:IntoIterator<Item=T>{let v:Vec<_> =iter.into_iter().collect();let mut size=1;while size<v.len(){size*=2;}let mut data=vec![neutral.clone();2*size];for(i,val)in v.into_iter().enumerate(){data[size+i]=val;}for i in(1..size).rev(){data[i]=(f)(&data[2*i],&data[2*i+1]);}Self{n:size,data,lazy:vec![None;2*size],neutral,f,g,h,}}pub fn query(&mut self,range:impl RangeBounds<usize>)->T{self.query_inner(self.to_range(range),1,self.to_range(..))}fn propagate(&mut self,i:usize,inner_range:Range<usize>){let Some(lazy)=self.lazy[i].clone()else{return;};self.data[i]=(self.g)(&self.data[i],&lazy,inner_range.end-inner_range.start);if inner_range.end-inner_range.start!=1{if let Some(child_lazy)=&self.lazy[i*2]{self.lazy[i*2]=Some((self.h)(child_lazy,&lazy));}else{self.lazy[i*2]=Some(lazy.clone());}if let Some(child_lazy)=&self.lazy[i*2+1]{self.lazy[i*2+1]=Some((self.h)(child_lazy,&lazy));}else{self.lazy[i*2+1]=Some(lazy.clone());}}self.lazy[i]=None;}fn query_inner(&mut self,range:Range<usize>,i:usize,inner_range:Range<usize>)->T{self.propagate(i,inner_range.clone());if range.start>=inner_range.end||inner_range.start>=range.end{return self.neutral.clone();}if range.start<=inner_range.start&&inner_range.end<=range.end{return self.data[i];}let mid=(inner_range.start+inner_range.end)/2;let left=self.query_inner(range.clone(),i*2,inner_range.start..mid);let right=self.query_inner(range,i*2+1,mid..inner_range.end);(self.f)(&left,&right)}pub fn update(&mut self,range:impl RangeBounds<usize>,val:T){self.update_inner(self.to_range(range),val,1,self.to_range(..));}fn update_inner(&mut self,range:Range<usize>,val:T,i:usize,inner_range:Range<usize>){self.propagate(i,inner_range.clone());if range.end<=inner_range.start||inner_range.end<=range.start{return;}if range.start<=inner_range.start&&inner_range.end<=range.end{self.lazy[i]=Some(val.clone());self.propagate(i,inner_range);return;}let mid=(inner_range.start+inner_range.end)/2;self.update_inner(range.clone(),val,i*2,inner_range.start..mid);self.update_inner(range,val,i*2+1,mid..inner_range.end);self.data[i]=(self.f)(&self.data[i*2],&self.data[i*2+1]);}fn to_range(&self,range:impl RangeBounds<usize>)->Range<usize>{let start=match range.start_bound(){std::ops::Bound::Included(&p)=>p,std::ops::Bound::Excluded(&p)=>p+1,std::ops::Bound::Unbounded=>0,};let end=match range.end_bound(){std::ops::Bound::Included(&p)=>p+1,std::ops::Bound::Excluded(&p)=>p,std::ops::Bound::Unbounded=>self.n,};start..end}}}pub mod treap{use std::mem;use super::super::misc::random::rand_u64;pub enum TreapNodeCont<T:PartialOrd>{Some(Box<TreapNode<T>>),Empty}impl<T:PartialOrd>Default for TreapNodeCont<T>{fn default()->Self{TreapNodeCont::Empty}}pub struct Treap<T:PartialOrd>{root:TreapNodeCont<T>,}impl<T:Clone+PartialOrd>Treap<T>{pub fn new()->Self{Self{root:TreapNodeCont::Empty,}}pub fn from_root(root:TreapNodeCont<T>)->Self{Self{root,}}pub fn split(self,x:T)->(Treap<T>,Treap<T>){let(left_root,right_root)=self.root.split(x);(Treap::from_root(left_root),Treap::from_root(right_root))}pub fn insert(&mut self,key:T){let root=mem::take(&mut self.root);self.root=root.insert(TreapNode::from_key(key));}pub fn merge(self,other:Treap<T>)->Treap<T>{let new_root=self.root.merge(other.root);Self{root:new_root}}pub fn erase(&mut self,key:&T){let root=mem::take(&mut self.root);self.root=root.erase(key);}pub fn contains(&self,key:&T)->bool{self.root.contains(key)}pub fn len(&self)->usize{self.root.len()}}pub struct TreapNode<T:PartialOrd>{key:T,left:TreapNodeCont<T>,right:TreapNodeCont<T>,priority:u64,len:usize}impl<T:PartialOrd+Clone>TreapNode<T>{pub fn from_key(key:T)->Self{Self{key,left:TreapNodeCont::Empty,right:TreapNodeCont::Empty,priority:rand_u64(),len:1}}fn recompute(&mut self){self.len=self.left.len()+self.right.len()+1;}}impl<T:PartialOrd+Clone>TreapNodeCont<T>{fn len(&self)->usize{if let TreapNodeCont::Some(root)=self{root.len}else{0}}fn split(self,x:T)->(TreapNodeCont<T>,TreapNodeCont<T>){let Self::Some(mut root)=self else{return(Self::Empty,Self::Empty);};let(left_res,right_res);if root.key>x{(left_res,root.left)=root.left.split(x);root.len=root.left.len()+root.right.len();root.recompute();right_res=TreapNodeCont::Some(root);}else{(root.right,right_res)=root.right.split(x);root.recompute();left_res=TreapNodeCont::Some(root);}(left_res,right_res)}fn insert(self,mut single_node:TreapNode<T>)->TreapNodeCont<T>{let TreapNodeCont::Some(mut root)=self else{return TreapNodeCont::Some(Box::new(single_node));};if single_node.priority>=root.priority{(single_node.left,single_node.right)=TreapNodeCont::Some(root).split(single_node.key.clone());single_node.recompute();TreapNodeCont::Some(Box::new(single_node))}else{if single_node.key<=root.key{root.left=root.left.insert(single_node);}else{root.right=root.right.insert(single_node);}root.recompute();TreapNodeCont::Some(root)}}fn contains(&self,key:&T)->bool{let TreapNodeCont::Some(root)=self else{return false;};match key.partial_cmp(&root.key).unwrap(){std::cmp::Ordering::Less=>{root.left.contains(key)},std::cmp::Ordering::Greater=>{root.right.contains(key)},std::cmp::Ordering::Equal=>{true},}}fn erase(self,key:&T)->TreapNodeCont<T>{let TreapNodeCont::Some(mut root)=self else{return TreapNodeCont::Empty;};match key.partial_cmp(&root.key).unwrap(){std::cmp::Ordering::Less=>{root.left=root.left.erase(key);root.recompute();TreapNodeCont::Some(root)},std::cmp::Ordering::Greater=>{root.right=root.right.erase(key);root.recompute();TreapNodeCont::Some(root)},std::cmp::Ordering::Equal=>{let left_subtree=mem::take(&mut root.left);let right_subtree=mem::take(&mut root.right);left_subtree.merge(right_subtree)},}}fn merge(self,other:TreapNodeCont<T>)->TreapNodeCont<T>{let TreapNodeCont::Some(mut left_root)=self else{return other;};let TreapNodeCont::Some(mut right_root)=other else{return TreapNodeCont::Some(left_root);};if left_root.priority>=right_root.priority{let(left_child,right_child)=(mem::take(&mut left_root.left),mem::take(&mut left_root.right));left_root.left=left_child.merge(right_child);left_root.right=TreapNodeCont::Some(right_root);left_root.recompute();TreapNodeCont::Some(left_root)}else{let(left_child,right_child)=(mem::take(&mut right_root.left),mem::take(&mut right_root.right));right_root.right=left_child.merge(right_child);right_root.left=TreapNodeCont::Some(left_root);right_root.recompute();TreapNodeCont::Some(right_root)}}}}pub mod disjoint_set{pub struct DisjointSet{data:Vec<usize>,size:Vec<usize>}impl DisjointSet{pub fn new(n:usize)->Self{Self{data:(0..n).collect(),size:vec![1;n]}}pub fn find(&mut self,mut x:usize)->usize{if self.data[x]!=x{x=self.find(self.data[x]);self.data[x]=x;}x}pub fn join(&mut self,mut x:usize,mut y:usize)->bool{x=self.find(x);y=self.find(y);if x==y{return false;}if self.size[x]<self.size[y]{std::mem::swap(&mut x,&mut y);}self.size[x]+=self.size[y];self.data[y]=x;true}pub fn size(&mut self,x:usize)->usize{let x=self.find(x);self.size[x]}pub fn len(&self)->usize{self.data.len()}}}}pub mod misc{pub mod random{use std::time::SystemTime;pub static mut RNG:Option<XorShift> =None;pub fn rand_u64()->u64{let rng=unsafe{RNG.get_or_insert(XorShift::new((SystemTime::UNIX_EPOCH.elapsed().unwrap().as_nanos()&0xFFFFFFFFFFFFFFFF)as u64))};rng.next()}pub struct XorShift{x:u64,y:u64,z:u64,w:u64,}impl XorShift{pub fn new(seed:u64)->Self{XorShift{x:9018237498,y:1982731389,z:1894712904,w:seed,}}pub fn next(&mut self)->u64{let t=self.x^(self.x<<11);self.x=self.y;self.y=self.z;self.z=self.w;self.w=self.w^(self.w>>19)^t^(t>>8);self.w}}}pub mod stdout{#[macro_export]macro_rules!__cargo_equip_macro_def___algo_0_1_0_println_iter{($iter:expr)=>{for val in$iter{print!("{} ",val);}println!();};}macro_rules!println_iter{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___algo_0_1_0_println_iter!{$($tt)*})}}pub mod mim{#[macro_export]macro_rules!__cargo_equip_macro_def___algo_0_1_0_maxim{($a:expr,$b:expr)=>{if$b>$a{$a=$b;}};}macro_rules!maxim{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___algo_0_1_0_maxim!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def___algo_0_1_0_minim{($a:expr,$b:expr)=>{if$b<$a{$a=$b;}};}macro_rules!minim{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___algo_0_1_0_minim!{$($tt)*})}}}}
pub mod codeforces {}
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(crate) mod macros {
pub mod __algo_0_1_0 {pub use crate::{__cargo_equip_macro_def___algo_0_1_0_maxim as maxim,__cargo_equip_macro_def___algo_0_1_0_minim as minim,__cargo_equip_macro_def___algo_0_1_0_println_iter as println_iter};}
pub mod codeforces {}
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(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod __algo_0_1_0 {}
pub mod codeforces {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__algo_0_1_0 as algo,proconio};}
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 {}
}
}
