stdin

// #![allow(unused)]

mod util {
    // IO handlers and Parsers
    #![allow(dead_code)]
    use std::io::BufRead;
    use std::str::FromStr;

    pub fn generate_input() -> impl FnMut() -> String {
        let mut lock = std::io::stdin().lock();
        move || {
            let mut buf = String::new();
            lock.read_line(&mut buf).unwrap();
            // Option 1. trim every trailing white spaces.
            buf.truncate(buf.trim_end().len());
            // Option 2. trim only line feed characters
            // buf.truncate(buf.trim_end_matches("\r\n").trim_end_matches('\n').len());
            buf
        }
    }

    pub fn split_parse<T: FromStr>(s: &str) -> impl Iterator<Item = T> + '_ {
        s.split(' ').map(|w| w.parse::<T>().ok().unwrap())
    }

    pub fn into_vec<T: FromStr>(s: &str) -> Vec<T> {
        split_parse::<T>(s).collect()
    }

    pub fn isize(s: &str) -> isize {
        s.parse().unwrap()
    }

    pub fn usize(s: &str) -> usize {
        s.parse().unwrap()
    }

    pub fn parse<T: FromStr>(s: &str) -> T {
        s.parse().ok().unwrap()
    }

    pub fn take_two<T: FromStr>(s: &str) -> (T, T) {
        let mut it = split_parse::<T>(s);
        let mut get = move || it.next().unwrap();
        (get(), get())
    }

    pub fn take_three<T: FromStr>(s: &str) -> (T, T, T) {
        let mut it = split_parse::<T>(s);
        let mut get = move || it.next().unwrap();
        (get(), get(), get())
    }
}