// The main code is at the very bottom. #[allow(unused_imports)] #[macro_use] pub mod spella { pub mod byte { pub use self::byte_char::*; pub use self::byte_str::*; pub use self::byte_string::*; pub use self::from_byte_str::*; mod byte_char { use std::fmt::{self, Debug, Display, Formatter}; #[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)] pub struct ByteChar(u8); impl ByteChar { pub fn new(c: u8) -> Self { ByteChar(c) } pub fn into_byte(self) -> u8 { self.0 } } impl Debug for ByteChar { fn fmt(&self, f: &mut Formatter) -> fmt::Result { write!(f, "b'{}'", self.0 as char) } } impl Display for ByteChar { fn fmt(&self, f: &mut Formatter) -> fmt::Result { write!(f, "{}", self.0 as char) } } } mod byte_str { use spella::byte::{ByteChar, ByteString}; use std::fmt::{self, Debug, Display, Formatter}; use std::ops::{Deref, DerefMut}; #[derive(PartialEq, Eq, PartialOrd, Ord, Hash)] pub struct ByteStr([ByteChar]); macro_rules! cast { (mut $x:expr, $($T:ty)=>*) => { unsafe { &mut *($x $(as *mut $T)*) } }; ($x:expr, $($T:ty)=>*) => { unsafe { &*($x $(as *const $T)*) } }; } impl ByteStr { pub fn from_bytes(s: &[u8]) -> &Self { cast!(s, [u8] => [ByteChar] => ByteStr) } pub fn from_bytes_mut(s: &mut [u8]) -> &mut Self { cast!(mut s, [u8] => [ByteChar] => ByteStr) } pub fn from_byte_chars(s: &[ByteChar]) -> &Self { cast!(s, [ByteChar] => ByteStr) } pub fn from_byte_chars_mut(s: &mut [ByteChar]) -> &mut Self { cast!(mut s, [ByteChar] => ByteStr) } pub fn as_bytes(&self) -> &[u8] { cast!(self, ByteStr => [ByteChar] => [u8]) } pub fn as_bytes_mut(&mut self) -> &mut [u8] { cast!(mut self, ByteStr => [ByteChar] => [u8]) } } impl ToOwned for ByteStr { type Owned = ByteString; fn to_owned(&self) -> ByteString { ByteString::from(self.0.to_owned()) } } impl Debug for ByteStr { fn fmt(&self, f: &mut Formatter) -> fmt::Result { write!(f, "b\"")?; for &c in &self.0 { write!(f, "{}", c)?; } write!(f, "\"") } } impl Display for ByteStr { fn fmt(&self, f: &mut Formatter) -> fmt::Result { for &c in &self.0 { write!(f, "{}", c)?; } Ok(()) } } impl Deref for ByteStr { type Target = [ByteChar]; fn deref(&self) -> &[ByteChar] { &self.0 } } impl DerefMut for ByteStr { fn deref_mut(&mut self) -> &mut [ByteChar] { &mut self.0 } } } mod byte_string { use spella::byte::{ByteChar, ByteStr}; use std::borrow::{Borrow, BorrowMut}; use std::fmt::{self, Debug, Display, Formatter}; use std::ops::{Deref, DerefMut}; #[derive(Clone, Default, PartialEq, Eq, PartialOrd, Ord, Hash)] pub struct ByteString(Vec); impl ByteString { pub fn into_byte_chars(self) -> Vec { self.0 } pub fn as_byte_str(&self) -> &ByteStr { ByteStr::from_byte_chars(&self.0) } pub fn as_mut_byte_str(&mut self) -> &mut ByteStr { ByteStr::from_byte_chars_mut(&mut self.0) } } impl From> for ByteString { fn from(s: Vec) -> ByteString { ByteString(s) } } impl Borrow for ByteString { fn borrow(&self) -> &ByteStr { self.as_byte_str() } } impl BorrowMut for ByteString { fn borrow_mut(&mut self) -> &mut ByteStr { self.as_mut_byte_str() } } impl Debug for ByteString { fn fmt(&self, f: &mut Formatter) -> fmt::Result { Debug::fmt(self.as_byte_str(), f) } } impl Display for ByteString { fn fmt(&self, f: &mut Formatter) -> fmt::Result { Display::fmt(self.as_byte_str(), f) } } impl Deref for ByteString { type Target = ByteStr; fn deref(&self) -> &ByteStr { ByteStr::from_byte_chars(&self.0) } } impl DerefMut for ByteString { fn deref_mut(&mut self) -> &mut ByteStr { ByteStr::from_byte_chars_mut(&mut self.0) } } } mod from_byte_str { use spella::byte::{ByteChar, ByteStr, ByteString}; use std::error::Error; use std::fmt::{self, Debug, Display, Formatter}; use std::str::{self, FromStr, Utf8Error}; pub trait FromByteStr: Sized { type Err; fn from_byte_str(s: &ByteStr) -> Result; } macro_rules! fn_description { () => { fn description(&self) -> &str { "description() is deprecated; use Display" } }; } #[derive(Debug)] pub struct ParseByteCharError(ParseByteCharErrorKind); #[derive(Debug)] enum ParseByteCharErrorKind { EmptyByteStr, TooManyByteChars, } impl Display for ParseByteCharError { fn fmt(&self, f: &mut Formatter) -> fmt::Result { use self::ParseByteCharErrorKind::*; f.write_str(match self.0 { EmptyByteStr => "empty `ByteStr`", TooManyByteChars => "too many `ByteChar`s", }) } } impl Error for ParseByteCharError { fn_description! {} } impl FromByteStr for ByteChar { type Err = ParseByteCharError; fn from_byte_str(s: &ByteStr) -> Result { use self::ParseByteCharErrorKind::*; match s.len() { 1 => Ok(unsafe { *s.get_unchecked(0) }), 0 => Err(ParseByteCharError(EmptyByteStr)), _ => Err(ParseByteCharError(TooManyByteChars)), } } } #[derive(Debug)] pub enum ParseByteStringError {} impl Display for ParseByteStringError { fn fmt(&self, _: &mut Formatter) -> fmt::Result { match *self {} } } impl Error for ParseByteStringError { fn_description! {} } impl FromByteStr for ByteString { type Err = ParseByteStringError; fn from_byte_str(s: &ByteStr) -> Result { Ok(ByteString::from(s.to_vec())) } } pub struct ParseFromStrError(ParseFromStrErrorKind); enum ParseFromStrErrorKind { Utf8Error(Utf8Error), FromStrError(T::Err), } impl Debug for ParseFromStrError where T::Err: Debug, { fn fmt(&self, f: &mut Formatter) -> fmt::Result { use self::ParseFromStrErrorKind::*; match self.0 { Utf8Error(ref err) => f.debug_tuple("Utf8Error").field(err).finish(), FromStrError(ref err) => f.debug_tuple("FromStrError").field(err).finish(), } } } impl Display for ParseFromStrError where T::Err: Display, { fn fmt(&self, f: &mut Formatter) -> fmt::Result { use self::ParseFromStrErrorKind::*; match self.0 { Utf8Error(ref err) => write!(f, "{}", err), FromStrError(ref err) => write!(f, "{}", err), } } } impl Error for ParseFromStrError where T::Err: Debug + Display, { fn_description! {} } impl FromByteStr for T { type Err = ParseFromStrError; fn from_byte_str(s: &ByteStr) -> Result { use self::ParseFromStrErrorKind::*; str::from_utf8(s.as_bytes()) .map_err(|e| ParseFromStrError(Utf8Error(e))) .and_then(|s| s.parse().map_err(|e| ParseFromStrError(FromStrError(e)))) } } } } pub mod io { pub use self::scanner::*; mod scanner { use spella::byte::{ByteStr, FromByteStr}; use std::io::{self, BufRead}; #[derive(Debug)] pub struct Scanner { reader: R, buf: Vec, pos: usize, } const INITIAL_CAPACITY: usize = 32; impl Scanner { pub fn new(reader: R) -> Self { Scanner { reader: reader, buf: Vec::with_capacity(INITIAL_CAPACITY), pos: 0, } } pub fn next(&mut self) -> io::Result> { self.next_byte_str().map(T::from_byte_str) } pub fn next_byte_str(&mut self) -> io::Result<&ByteStr> { if self.buf.is_empty() { self.read_line()?; } loop { match self.buf.get(self.pos) { Some(&b' ') => self.pos += 1, Some(&b'\n') => self.read_line()?, Some(_) => break, None => return Err(io::Error::from(io::ErrorKind::UnexpectedEof)), } } let start = self.pos; self.pos += 1; loop { match self.buf.get(self.pos) { Some(&b' ') | Some(&b'\n') | None => break, Some(_) => self.pos += 1, } } Ok(ByteStr::from_bytes(&self.buf[start..self.pos])) } fn read_line(&mut self) -> io::Result<()> { self.buf.clear(); self.pos = 0; self.reader.read_until(b'\n', &mut self.buf)?; Ok(()) } } } } } mod prelude { pub use spella::byte::{ByteChar, ByteStr, ByteString}; pub use std::collections::*; pub use std::io::prelude::*; pub use std::iter::FromIterator; pub use std::marker::PhantomData; pub use std::num::Wrapping; pub use std::ops::{Range, RangeFrom, RangeTo}; pub use std::{cell, cmp, f64, i32, i64, isize, iter, mem, rc, str, time, u32, u64, usize}; } use prelude::*; const CUSTOM_STACK_SIZE_MEBIBYTES: Option = None; fn main() { fn exec_solver() { let stdin = std::io::stdin(); let stdout = std::io::stdout(); #[cfg(not(debug_assertions))] let mut writer = std::io::BufWriter::new(stdout.lock()); #[cfg(debug_assertions)] let mut writer = stdout.lock(); solve(stdin.lock(), &mut writer); writer.flush().unwrap(); } if let Some(stack_size_mebibytes) = CUSTOM_STACK_SIZE_MEBIBYTES { std::thread::Builder::new() .name("exec_solver".to_owned()) .stack_size(stack_size_mebibytes * 1024 * 1024) .spawn(exec_solver) .unwrap() .join() .unwrap(); } else { exec_solver(); } } fn solve(reader: R, mut writer: W) { let mut _scanner = spella::io::Scanner::new(reader); #[allow(unused_macros)] macro_rules! scan { ($T:ty) => { _scanner.next::<$T>().unwrap().unwrap() }; ($($T:ty),+) => { ($(scan!($T)),+) }; ($($T:ty),+; $n:expr $(; $m:expr)*) => {{ (0..$n).map(|_| scan!($($T),+ $(; $m)*)).collect::>() }}; } #[allow(unused_macros)] macro_rules! scan_iter { ($T:ty; $n:expr) => { (0..$n).map(|_| scan!($T)) }; } #[allow(unused_macros)] macro_rules! print { ($fmt:expr) => { write!(writer, $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { write!(writer, $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! println { ($fmt:expr) => { writeln!(writer, $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { writeln!(writer, $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! eprint { ($fmt:expr) => { #[cfg(debug_assertions)] write!(std::io::stderr(), $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { #[cfg(debug_assertions)] write!(std::io::stderr(), $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! eprintln { ($fmt:expr) => { #[cfg(debug_assertions)] writeln!(std::io::stderr(), $fmt).unwrap() }; ($fmt:expr, $($arg:tt)*) => { #[cfg(debug_assertions)] writeln!(std::io::stderr(), $fmt, $($arg)*).unwrap() }; } #[allow(unused_macros)] macro_rules! dbg { ($($x:expr),+) => {{ eprint!("[{}:{}] ", file!(), line!()); eprintln!(concat!($(stringify!($x), " = {:?}; "),+), $($x),+); }}; } println!("Yes"); }