#![allow(dead_code)]
#![allow(unused)]

// Template by SSDD (https://codeforces.com/profile/ifail)
// Feel free to use it :p
// don't forget to add `local` feature in Cargo.toml
// while compiling pass `--features local` or `--all-features` for it
// to perform file IO from local files

use std::fs::File;
use std::io::{BufReader, BufWriter, Read, Write};


struct Reader<T: Read> {
    reader: T,
    buffer: Vec<String>,
}
macro_rules! wrt { // for actual print
    ($writer:expr, $($value:expr),*) => {
        $(write!($writer, "{}", $value).unwrap();)*
    };
}

#[cfg(feature = "local")]
macro_rules! wrtd { // for debug print
    ($writer:expr, $($value:expr),*) => {
        $(write!($writer, "{:?}\n", $value).unwrap();)*
    };
}


#[cfg(not(feature = "local"))]
macro_rules! wrtd { // debug print won't do anything when ans is submitted
    ($writer:expr, $($value:expr),*) => ();
}

fn yn<T: Write>(writer: &mut T, x: bool) {
    wrt!(writer, if x { "YES\n" } else { "NO\n" });
}

impl<T: std::io::BufRead> Reader<T> {
    fn new(reader: T) -> Reader<T> {
        Self {
            reader,
            buffer: vec![],
        }
    }
    fn next<I: std::str::FromStr>(&mut self) -> I where <I as std::str::FromStr>::Err: std::fmt::Debug {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok()
                    .expect("Failed to parse!");
            }

            let mut input = String::new();
            self.reader.read_line(&mut input)
                .expect("Failed to read!");

            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }

    fn next_usz(&mut self) -> usize {
        self.next()
    }

    fn next_st(&mut self) -> String {
        self.next()
    }

    fn next_int(&mut self) -> i32 {
        self.next()
    }

    fn next_ll(&mut self) -> i64 {
        self.next()
    }

    fn next_ft(&mut self) -> f32 {
        self.next()
    }
    fn next_ft6(&mut self) -> f64 {
        self.next()
    }

    fn next_chars(&mut self) -> Vec<char> {
        self.next::<String>().chars().collect()
    }
}

fn solve<R: std::io::BufRead, W: Write>(reader: &mut Reader<R>, writer: &mut W) {

}

fn main() {
    #[cfg(feature = "local")]
        let stdin = BufReader::new(File::open("in.txt").unwrap());
    #[cfg(not(feature = "local"))]
        let stdin = std::io::stdin().lock();

    #[cfg(feature = "local")]
        let mut stdout = BufWriter::new(File::create("out.txt").unwrap());
    #[cfg(not(feature = "local"))]
        let mut stdout = std::io::stdout().lock();

    // Example to write: `wrt!(writer, ans, "\n");` you can pass several of args
    // use `wrtd!` for debug print, it won't print anything in non-local env

    let mut reader = Reader::new(stdin);

    let t = 1;
    // let t = reader.next_usz();
    for _ in 0..t {
        solve(&mut reader, &mut stdout);
    }
}