// SNIPPET read
pub trait Readable {
    type Output;
    fn words_count() -> usize;
    fn read_words(words: &[&str]) -> Result<Self::Output, String>;
}
#[macro_export]
macro_rules! readable {
    ( $t:ty, $words_count:expr, |$words:ident| $read_words:expr ) => {
        impl Readable for $t {
            type Output = $t;
            fn words_count() -> usize { $words_count }
            fn read_words($words: &[&str]) -> Result<$t, String> {
                Ok($read_words)
            }
        }
    };
}
readable!((), 1, |_ss| ());
readable!(String, 1, |ss| ss[0].to_string());
impl Readable for char {
    type Output = char;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<char, String> {
        let chars: Vec<char> = words[0].chars().collect();
        if chars.len() == 1 {
            Ok(chars[0])
        } else {
            Err(format!("cannot parse `{}` as a char", words[0]))
        }
    }
}
pub struct Chars();
impl Readable for Chars {
    type Output = Vec<char>;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Vec<char>, String> {
        Ok(words[0].chars().collect())
    }
}
impl Readable for i8 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<i8, String> {
        use std::str::FromStr;
        i8::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(i8))
        })
    }
}
impl Readable for u8 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<u8, String> {
        use std::str::FromStr;
        u8::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(u8))
        })
    }
}
impl Readable for i16 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<i16, String> {
        use std::str::FromStr;
        i16::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(i16))
        })
    }
}
impl Readable for u16 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<u16, String> {
        use std::str::FromStr;
        u16::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(u16))
        })
    }
}
impl Readable for i32 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<i32, String> {
        use std::str::FromStr;
        i32::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(i32))
        })
    }
}
impl Readable for u32 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<u32, String> {
        use std::str::FromStr;
        u32::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(u32))
        })
    }
}
impl Readable for i64 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<i64, String> {
        use std::str::FromStr;
        i64::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(i64))
        })
    }
}
impl Readable for u64 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<u64, String> {
        use std::str::FromStr;
        u64::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(u64))
        })
    }
}
impl Readable for isize {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<isize, String> {
        use std::str::FromStr;
        <isize>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(isize))
        })
    }
}
impl Readable for usize {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<usize, String> {
        use std::str::FromStr;
        <usize>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(usize))
        })
    }
}
impl Readable for f32 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<f32, String> {
        use std::str::FromStr;
        f32::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(usize))
        })
    }
}
impl Readable for f64 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<f64, String> {
        use std::str::FromStr;
        f64::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(usize))
        })
    }
}
#[allow(non_camel_case_types)]
pub struct u8_;
impl Readable for u8_ {
    type Output = u8;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        u8::read_words(words).map(|n| n-1)
    }
}
#[allow(non_camel_case_types)]
pub struct u16_;
impl Readable for u16_ {
    type Output = u16;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        u16::read_words(words).map(|n| n-1)
    }
}
#[allow(non_camel_case_types)]
pub struct u32_;
impl Readable for u32_ {
    type Output = u32;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        u32::read_words(words).map(|n| n-1)
    }
}
#[allow(non_camel_case_types)]
pub struct u64_;
impl Readable for u64_ {
    type Output = u64;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        u64::read_words(words).map(|n| n-1)
    }
}
#[allow(non_camel_case_types)]
pub struct usize_;
impl Readable for usize_ {
    type Output = usize;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        <usize>::read_words(words).map(|n| n-1)
    }
}
impl<T1: Readable, T2: Readable> Readable for (T1, T2) {
    type Output = (T1::Output, T2::Output);
    fn words_count() -> usize {
        T1::words_count() + T2::words_count()
    }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        assert_eq!(words.len(), Self::words_count());
        let mut start = 0;
        let count1 = T1::words_count();
        let val1 = T1::read_words(&words[start .. start+count1])?;
        start += count1;
        let val2 = T2::read_words(&words[start..])?;
        Ok((val1, val2))
    }
}
impl<T1: Readable, T2: Readable, T3: Readable> Readable for (T1, T2, T3) {
    type Output = (T1::Output, T2::Output, T3::Output);
    fn words_count() -> usize {
        T1::words_count() + T2::words_count() + T3::words_count()
    }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        assert_eq!(words.len(), Self::words_count());
        let mut start = 0;
        let count1 = T1::words_count();
        let val1 = T1::read_words(&words[start .. start+count1])?;
        start += count1;
        let count2 = T2::words_count();
        let val2 = T2::read_words(&words[start .. start+count2])?;
        start += count2;
        let val3 = T3::read_words(&words[start..])?;
        Ok((val1, val2, val3))
    }
}
impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable> Readable for (T1, T2, T3, T4) {
    type Output = (T1::Output, T2::Output, T3::Output, T4::Output);
    fn words_count() -> usize {
        T1::words_count() + T2::words_count() + T3::words_count() + T4::words_count()
    }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        assert_eq!(words.len(), Self::words_count());
        let mut start = 0;
        let count1 = T1::words_count();
        let val1 = T1::read_words(&words[start .. start+count1])?;
        start += count1;
        let count2 = T2::words_count();
        let val2 = T2::read_words(&words[start .. start+count2])?;
        start += count2;
        let count3 = T3::words_count();
        let val3 = T3::read_words(&words[start .. start+count3])?;
        start += count3;
        let val4 = T4::read_words(&words[start..])?;
        Ok((val1, val2, val3, val4))
    }
}
impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable, T5: Readable> Readable for (T1, T2, T3, T4, T5) {
    type Output = (T1::Output, T2::Output, T3::Output, T4::Output, T5::Output);
    fn words_count() -> usize {
        T1::words_count() + T2::words_count() + T3::words_count() + T4::words_count() + T5::words_count()
    }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        assert_eq!(words.len(), Self::words_count());
        let mut start = 0;
        let count1 = T1::words_count();
        let val1 = T1::read_words(&words[start .. start+count1])?;
        start += count1;
        let count2 = T2::words_count();
        let val2 = T2::read_words(&words[start .. start+count2])?;
        start += count2;
        let count3 = T3::words_count();
        let val3 = T3::read_words(&words[start .. start+count3])?;
        start += count3;
        let count4 = T4::words_count();
        let val4 = T4::read_words(&words[start .. start+count4])?;
        start += count4;
        let val5 = T5::read_words(&words[start..])?;
        Ok((val1, val2, val3, val4, val5))
    }
}
impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable, T5: Readable, T6: Readable> Readable for (T1, T2, T3, T4, T5, T6) {
    type Output = (T1::Output, T2::Output, T3::Output, T4::Output, T5::Output, T6::Output);
    fn words_count() -> usize {
        T1::words_count() + T2::words_count() + T3::words_count() + T4::words_count() + T5::words_count() + T6::words_count()
    }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        assert_eq!(words.len(), Self::words_count());
        let mut start = 0;
        let count1 = T1::words_count();
        let val1 = T1::read_words(&words[start .. start+count1])?;
        start += count1;
        let count2 = T2::words_count();
        let val2 = T2::read_words(&words[start .. start+count2])?;
        start += count2;
        let count3 = T3::words_count();
        let val3 = T3::read_words(&words[start .. start+count3])?;
        start += count3;
        let count4 = T4::words_count();
        let val4 = T4::read_words(&words[start .. start+count4])?;
        start += count4;
        let count5 = T5::words_count();
        let val5 = T5::read_words(&words[start .. start+count5])?;
        start += count5;
        let val6 = T6::read_words(&words[start..])?;
        Ok((val1, val2, val3, val4, val5, val6))
    }
}
pub trait ReadableFromLine {
    type Output;
    fn read_line(line: &str) -> Result<Self::Output, String>;
}
fn split_into_words(line: &str) -> Vec<&str> {
    #[allow(deprecated)]
    line.trim_right_matches('\n').split_whitespace().collect()
}
impl<T: Readable> ReadableFromLine for T {
    type Output = T::Output;
    fn read_line(line: &str) -> Result<T::Output, String> {
        let words = split_into_words(line);
        if words.len() != T::words_count() {
            return Err(format!("line `{}` has {} words, expected {}",
                               line, words.len(), T::words_count()));
        }
        T::read_words(&words)
    }
}
fn read_words_into_vec<T: Readable>(words: &[&str], line: &str) -> Result<Vec<T::Output>, String> {
    let n = T::words_count();
    assert_eq!(words.len() % n, 0);
    let mut result = Vec::new();
    for chunk in words.chunks(n) {
        match T::read_words(chunk) {
            Ok(v) => result.push(v),
            Err(msg) => {
                let fragment_msg = if n == 1 {
                    format!("word {}", result.len())
                } else {
                    let l = result.len();
                    format!("words {}-{}", n*l + 1, (n+1) * l)
                };
                return Err(format!(
                    "{} of line `{}`: {}", fragment_msg, line, msg
                ));
            }
        }
    }
    Ok(result)
}
fn split_into_words_for_collection<T: Readable>(
    line: &str, prefix_words_count: usize
) -> Result<Vec<&str>, String> {
    let n = T::words_count();
    let words = split_into_words(line);
    if words.len() < prefix_words_count {
        return Err(
            format!("line `{}` has {} words, expected at least {}",
                    line, words.len(), prefix_words_count)
        );
    }
    if (words.len() - prefix_words_count) % T::words_count() != 0 {
        return Err(
            format!("line `{}` has {} words, expected {} + {}n",
                    line, words.len(), prefix_words_count, n)
        );
    }
    Ok(words)
}
#[macro_export]
macro_rules! readable_collection {
    ($u:ident => $collection_in:ty, $collection_out:ty) => {
        readable_collection!($u: [] => $collection_in, $collection_out);
    };
    ($u:ident : [ $( $bound:path ),* ] => $collection_in:ty, $collection_out:ty) => {
        impl<$u: Readable> ReadableFromLine for $collection_in
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = $collection_out;
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let words = split_into_words_for_collection::<$u>(line, 0)?;
                Ok(read_words_into_vec::<$u>(&words, line)?.into_iter().collect())
            }
        }
        impl<T1: Readable, $u: Readable> ReadableFromLine for (T1, $collection_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = (T1::Output, $collection_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let prefix_len = T1::words_count();
                let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
                let val1 = T1::read_words(&words[..prefix_len])?;
                let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
                Ok((val1, rest.into_iter().collect()))
            }
        }
        impl<T1: Readable, T2: Readable, $u: Readable> ReadableFromLine for (T1, T2, $collection_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = (T1::Output, T2::Output, $collection_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let prefix_len = <(T1, T2)>::words_count();
                let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
                let mut start = 0;
                let count1 = T1::words_count();
                let val1 = T1::read_words(&words[start .. start+count1])?;
                start += count1;
                let count2 = T2::words_count();
                let val2 = T2::read_words(&words[start .. start+count2])?;
                let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
                Ok((val1, val2, rest.into_iter().collect()))
            }
        }
        impl<T1: Readable, T2: Readable, T3: Readable, $u: Readable> ReadableFromLine for (T1, T2, T3, $collection_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = (T1::Output, T2::Output, T3::Output, $collection_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let prefix_len = <(T1, T2, T3)>::words_count();
                let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
                let mut start = 0;
                let count1 = T1::words_count();
                let val1 = T1::read_words(&words[start .. start+count1])?;
                start += count1;
                let count2 = T2::words_count();
                let val2 = T2::read_words(&words[start .. start+count2])?;
                start += count2;
                let count3 = T3::words_count();
                let val3 = T3::read_words(&words[start .. start+count3])?;
                let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
                Ok((val1, val2, val3, rest.into_iter().collect()))
            }
        }
        impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable, $u: Readable> ReadableFromLine for (T1, T2, T3, T4, $collection_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = (T1::Output, T2::Output, T3::Output, T4::Output, $collection_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let prefix_len = <(T1, T2, T3, T4)>::words_count();
                let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
                let mut start = 0;
                let count1 = T1::words_count();
                let val1 = T1::read_words(&words[start .. start+count1])?;
                start += count1;
                let count2 = T2::words_count();
                let val2 = T2::read_words(&words[start .. start+count2])?;
                start += count2;
                let count3 = T3::words_count();
                let val3 = T3::read_words(&words[start .. start+count3])?;
                start += count3;
                let count4 = T4::words_count();
                let val4 = T4::read_words(&words[start .. start+count4])?;
                let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
                Ok((val1, val2, val3, val4, rest.into_iter().collect()))
            }
        }
    };
}
readable_collection!(U => Vec<U>, Vec<U::Output>);
pub fn read<T: ReadableFromLine>() -> T::Output {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    T::read_line(&line).unwrap()
}
#[macro_export]
macro_rules! read {
    () => {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
    };
    ( $pat:pat = $t:ty ) => {
        let $pat = read::<$t>();
    };
    ( $( $pat:pat = $t:ty ),+ ) => {
        read!(($($pat),*) = ($($t),*));
    };
}
#[macro_export]
macro_rules! readls {
    ( $( $pat:pat = $t:ty ),+ ) => {
        $(
            read!($pat = $t);
        )*
    };
}
pub fn readx<T: ReadableFromLine>() -> Vec<T::Output> {
    use std::io::{self, BufRead};
    let stdin = io::stdin();
    let result = stdin.lock().lines().map(|line_result| {
        let line = line_result.expect("read from stdin failed");
        T::read_line(&line).unwrap()
    }).collect();
    result
}
#[macro_export]
macro_rules! readx_loop {
    ( |$pat:pat = $t:ty| $body:expr ) => {
        {
            use std::io::BufRead;
            let stdin = std::io::stdin();
            for line in stdin.lock().lines() {
                let line = line.expect("read from stdin failed");
                let $pat = <$t>::read_line(&line).unwrap();
                $body
            }
        }
    };
    ( |$($pat:pat = $t:ty),*| $body:expr ) => {
        readx_loop!(|($($pat),*) = ($($t),*)| $body);
    };
}
pub fn readn<T: ReadableFromLine>(n: usize) -> Vec<T::Output> {
    use std::io::{self, BufRead};
    let stdin = io::stdin();
    let result: Vec<T::Output> = stdin.lock().lines().take(n).map(|line_result| {
        let line = line_result.expect("read from stdin failed");
        T::read_line(&line).unwrap()
    }).collect();
    if result.len() < n {
        panic!("expected reading {} lines, but only {} lines are read",
               n, result.len());
    }
    result
}
#[macro_export]
macro_rules! readn_loop {
    ( $n:expr, |$pat:pat = $t:ty| $body:expr ) => {
        {
            use std::io::BufRead;
            let stdin = std::io::stdin();
            let mut lock = stdin.lock();
            for _ in 0..$n {
                let mut line = String::new();
                lock.read_line(&mut line).expect("read from stdin failed");
                let $pat = <$t>::read_line(&line).unwrap();
                $body
            }
        }
    };
    ( $n:expr, |$($pat:pat = $t:ty),*| $body:expr ) => {
        readn_loop!($n, |($($pat),*) = ($($t),*)| $body);
    };
}
pub trait Words {
    fn read<T: Readable>(&self) -> T::Output;
}
impl<'a> Words for [&'a str] {
    fn read<T: Readable>(&self) -> T::Output {
        T::read_words(self).unwrap()
    }
}
impl<'a> Words for &'a str {
    fn read<T: Readable>(&self) -> T::Output {
        T::read_words(&[self]).unwrap()
    }
}

// SNIPPET vec
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Vec2<T> {
    pub x: T,
    pub y: T
}
impl<T> Vec2<T> {
    pub fn new(x: T, y: T) -> Vec2<T> {
        Vec2 { x: x, y: y }
    }
    pub fn inner(self, other: Vec2<T>) -> T
    where
        T: std::ops::Add<T, Output=T> + std::ops::Mul<T, Output=T>
    {
        self.x * other.x + self.y * other.y
    }
}
impl<T: std::fmt::Display> std::fmt::Display for Vec2<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{} {}", self.x, self.y)
    }
}
impl<S, T: std::ops::Add<S>> std::ops::Add<Vec2<S>> for Vec2<T> {
    type Output = Vec2<T::Output>;
    fn add(self, rhs: Vec2<S>) -> Self::Output {
        Vec2::new(self.x + rhs.x, self.y + rhs.y)
    }
}
impl<S, T: std::ops::AddAssign<S>> std::ops::AddAssign<Vec2<S>> for Vec2<T> {
    fn add_assign(&mut self, rhs: Vec2<S>) {
        self.x += rhs.x;
        self.y += rhs.y;
    }
}
impl<S, T: std::ops::Sub<S>> std::ops::Sub<Vec2<S>> for Vec2<T> {
    type Output = Vec2<T::Output>;
    fn sub(self, rhs: Vec2<S>) -> Self::Output {
        Vec2::new(self.x - rhs.x, self.y - rhs.y)
    }
}
impl<S, T: std::ops::SubAssign<S>> std::ops::SubAssign<Vec2<S>> for Vec2<T> {
    fn sub_assign(&mut self, rhs: Vec2<S>) {
        self.x -= rhs.x;
        self.y -= rhs.y;
    }
}
impl<T: std::ops::Neg> std::ops::Neg for Vec2<T> {
    type Output = Vec2<T::Output>;
    fn neg(self) -> Self::Output {
        Vec2::new(-self.x, -self.y)
    }
}
macro_rules! impl_mul_vec2 {
    ( $($t: ty)* ) => { $(
        impl std::ops::Mul<Vec2<$t>> for $t {
            type Output = Vec2<<$t as std::ops::Mul>::Output>;
            fn mul(self, rhs: Vec2<$t>) -> Self::Output {
                Vec2::new(self * rhs.x, self * rhs.y)
            }
        }
    )* }
}
impl_mul_vec2!(i8 u8 i16 u16 i32 u32 i64 u64 f32 f64);
impl<S: Copy, T: std::ops::Mul<S>> std::ops::Mul<S> for Vec2<T> {
    type Output = Vec2<T::Output>;
    fn mul(self, rhs: S) -> Self::Output {
        Vec2::new(self.x * rhs, self.y * rhs)
    }
}
impl<S: Copy, T: std::ops::MulAssign<S>> std::ops::MulAssign<S> for Vec2<T> {
    fn mul_assign(&mut self, rhs: S) {
        self.x *= rhs;
        self.y *= rhs;
    }
}
impl<S: Copy, T: std::ops::Div<S>> std::ops::Div<S> for Vec2<T> {
    type Output = Vec2<T::Output>;
   fn div(self, rhs: S) -> Self::Output {
        Vec2::new(self.x / rhs, self.y / rhs)
    }
}
impl<S: Copy, T: std::ops::DivAssign<S>> std::ops::DivAssign<S> for Vec2<T> {
    fn div_assign(&mut self, rhs: S) {
        self.x /= rhs;
        self.y /= rhs;
    }
}
impl<T: Readable> Readable for Vec2<T> {
    type Output = Vec2<T::Output>;
    fn words_count() -> usize {
        T::words_count() * 2
    }
    fn read_words(words: &[&str]) -> Result<Vec2<T::Output>, String> {
        let n = T::words_count();
        Ok(Vec2::new(T::read_words(&words[..n])?,
                     T::read_words(&words[n..])?))
    }
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Vec3<T> {
    pub x: T,
    pub y: T,
    pub z: T
}
impl<T> Vec3<T> {
    pub fn new(x: T, y: T, z: T) -> Vec3<T> {
        Vec3 { x: x, y: y , z: z }
    }
    pub fn inner(self, other: Vec3<T>) -> T
    where
        T: std::ops::Add<T, Output=T> + std::ops::Mul<T, Output=T>
    {
        self.x * other.x + self.y * other.y + self.z * other.z
    }
}
impl<T: std::fmt::Display> std::fmt::Display for Vec3<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{} {} {}", self.x, self.y, self.z)
    }
}
impl<S, T: std::ops::Add<S>> std::ops::Add<Vec3<S>> for Vec3<T> {
    type Output = Vec3<T::Output>;
    fn add(self, rhs: Vec3<S>) -> Self::Output {
        Vec3::new(self.x + rhs.x, self.y + rhs.y, self.z + rhs.z)
    }
}
impl<S, T: std::ops::AddAssign<S>> std::ops::AddAssign<Vec3<S>> for Vec3<T> {
    fn add_assign(&mut self, rhs: Vec3<S>) {
        self.x += rhs.x;
        self.y += rhs.y;
        self.z += rhs.z;
    }
}
impl<S, T: std::ops::Sub<S>> std::ops::Sub<Vec3<S>> for Vec3<T> {
    type Output = Vec3<T::Output>;
    fn sub(self, rhs: Vec3<S>) -> Self::Output {
        Vec3::new(self.x - rhs.x, self.y - rhs.y, self.z - rhs.z)
    }
}
impl<S, T: std::ops::SubAssign<S>> std::ops::SubAssign<Vec3<S>> for Vec3<T> {
    fn sub_assign(&mut self, rhs: Vec3<S>) {
        self.x -= rhs.x;
        self.y -= rhs.y;
        self.z -= rhs.z;
    }
}
impl<T: std::ops::Neg> std::ops::Neg for Vec3<T> {
    type Output = Vec3<T::Output>;
    fn neg(self) -> Self::Output {
        Vec3::new(-self.x, -self.y, -self.z)
    }
}
macro_rules! impl_mul_vec3 {
    ( $($t: ty)* ) => { $(
        impl std::ops::Mul<Vec3<$t>> for $t {
            type Output = Vec3<<$t as std::ops::Mul>::Output>;
            fn mul(self, rhs: Vec3<$t>) -> Self::Output {
                Vec3::new(self * rhs.x, self * rhs.y, self * rhs.z)
            }
        }
    )* }
}
impl_mul_vec3!(i8 u8 i16 u16 i32 u32 i64 u64 f32 f64);
impl<S: Copy, T: std::ops::Mul<S>> std::ops::Mul<S> for Vec3<T> {
    type Output = Vec3<T::Output>;
    fn mul(self, rhs: S) -> Self::Output {
        Vec3::new(self.x * rhs, self.y * rhs, self.z * rhs)
    }
}
impl<S: Copy, T: std::ops::MulAssign<S>> std::ops::MulAssign<S> for Vec3<T> {
    fn mul_assign(&mut self, rhs: S) {
        self.x *= rhs;
        self.y *= rhs;
        self.z *= rhs;
    }
}
impl<S: Copy, T: std::ops::Div<S>> std::ops::Div<S> for Vec3<T> {
    type Output = Vec3<T::Output>;
   fn div(self, rhs: S) -> Self::Output {
        Vec3::new(self.x / rhs, self.y / rhs, self.z / rhs)
    }
}
impl<S: Copy, T: std::ops::DivAssign<S>> std::ops::DivAssign<S> for Vec3<T> {
    fn div_assign(&mut self, rhs: S) {
        self.x /= rhs;
        self.y /= rhs;
        self.z /= rhs;
    }
}
impl<T: Readable> Readable for Vec3<T> {
    type Output = Vec3<T::Output>;
    fn words_count() -> usize {
        T::words_count() * 3
    }
    fn read_words(words: &[&str]) -> Result<Vec3<T::Output>, String> {
        let n = T::words_count();
        Ok(Vec3::new(T::read_words(&words[..n])?,
                     T::read_words(&words[n..2*n])?,
                     T::read_words(&words[2*n..])?))
    }
}

// SNIPPET dbg
#[macro_export]
#[cfg(local)]
macro_rules! dbg {
    () => {
        {
            use std::io::{self, Write};
            writeln!(io::stderr(), "{}: dbg", line!()).unwrap();
        }
    };
    ($e: expr) => {
        {
            use std::io::{self, Write};
            let result = $e;
            writeln!(io::stderr(), "{}: {} = {:?}",
                     line!(), stringify!($e), result)
                .unwrap();
            result
        }
    }
}
#[macro_export]
#[cfg(not(local))]
macro_rules! dbg {
    () => {};
    ($e: expr) => {
        { $e }
    }
}

// SNIPPET cmp
use std::cmp::{Ord, Ordering};
pub fn minmax<T: Ord>(a: T, b: T) -> (T, T) {
    if a <= b { (a, b) } else { (b, a) }
}
#[macro_export]
macro_rules! chmin {
    ($place: expr, $expr: expr) => {
        let value = $expr;
        if value < $place {
            $place = value;
        }
    }
}
#[macro_export]
macro_rules! chmax {
    ($place: expr, $expr: expr) => {
        let value = $expr;
        if value > $place {
            $place = value;
        }
    }
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default, Hash)]
pub struct Reverse<T: Ord>(pub T);
impl<T: Ord> PartialOrd for Reverse<T> {
    fn partial_cmp(&self, other: &Reverse<T>) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}
impl<T: Ord> Ord for Reverse<T> {
    fn cmp(&self, other: &Reverse<T>) -> Ordering {
        other.0.cmp(&self.0)
    }
}
pub trait SortDesc<T> {
    fn sort_desc(&mut self) where T: Ord;
    fn sort_desc_by_key<K: Ord, F: FnMut(&T) -> K>(&mut self, f: F);
}
impl<T> SortDesc<T> for [T] {
    fn sort_desc(&mut self) where T: Ord {
        self.sort();
        self.reverse();
    }
    fn sort_desc_by_key<K: Ord, F: FnMut(&T) -> K>(&mut self, mut f: F) {
        self.sort_by_key(|x| Reverse(f(x)));
    }
}
#[derive(Clone, Copy, PartialEq, PartialOrd, Debug, Default, Hash)]
pub struct Total<T: PartialOrd + PartialEq>(pub T);
impl<T: PartialOrd + PartialEq> Eq for Total<T> {}
impl<T: PartialOrd + PartialEq> Ord for Total<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}
pub trait IteratorMinmax: Iterator {
    fn minmax(self) -> Option<(Self::Item, Self::Item)>;
    fn minmax_by_key<K, F>(self, key_fn: F) -> Option<(Self::Item, Self::Item)>
    where
        K: Ord,
        F: FnMut(&Self::Item) -> K;
    fn minmax_by<F>(self, compare: F) -> Option<(Self::Item, Self::Item)>
    where
        F: FnMut(&Self::Item, &Self::Item) -> Ordering;
}
impl<T: Ord + Clone, I: Iterator<Item=T>> IteratorMinmax for I {
    fn minmax(self) -> Option<(Self::Item, Self::Item)> {
        self.minmax_by(|a, b| a.cmp(b))
    }
    fn minmax_by_key<K, F>(self, mut key_fn: F) -> Option<(Self::Item, Self::Item)>
    where
        K: Ord,
        F: FnMut(&Self::Item) -> K
    {
        self.minmax_by(|a, b| key_fn(a).cmp(&key_fn(b)))
    }
    fn minmax_by<F>(mut self, mut compare: F) -> Option<(Self::Item, Self::Item)>
    where
        F: FnMut(&Self::Item, &Self::Item) -> Ordering
    {
        let first = match self.next() {
            Some(x) => x,
            None => return None
        };
        let second = match self.next() {
            Some(x) => x,
            None => return Some((first.clone(), first))
        };
        let mut result = minmax(first, second);
        while let Some(x) = self.next() {
            let (min, max) = result;
            result = if compare(&x, &min) == Ordering::Less {
                (x, max)
            } else if compare(&max, &x) == Ordering::Less {
                (min, x)
            } else {
                (min, max)
            };
        }
        Some(result)
    }
}

// END SNIPPETS

use std::collections::BinaryHeap;

type V = Vec2<f64>;

fn dist(p1: V, p2: V) -> f64 {
    f64::sqrt((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y))
}

#[derive(PartialEq)]
struct Node {
    v: usize,
    d: f64
}

impl Eq for Node {}

impl Ord for Node {
    fn cmp(&self, other: &Node) -> Ordering {
        other.d.partial_cmp(&self.d).unwrap()
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Node) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn dijkstra(graph: &[Vec<f64>]) -> f64 {
    let mut dist = vec![None; graph.len()];
    dist[graph.len() - 2] = Some(0.0);
    let mut queue = BinaryHeap::new();
    queue.push(Node { v: graph.len()-2, d: 0.0 });

    while let Some(node) = queue.pop() {
        if node.v == graph.len() - 1 {
            break;
        }
        if dist[node.v].map_or(false, |d| d < node.d) {
            continue;
        }

        for (v, cost) in graph[node.v].iter().cloned().enumerate() {
            if dist[v].map_or(false, |d| d <= node.d + cost) {
                continue;
            }
            dist[v] = Some(node.d + cost);
            queue.push(Node { v: v, d: node.d + cost });
        }
    }

    dist.last().unwrap().unwrap()
}

fn main() {
    read!(s = V, t = V);
    read!(n = usize);
    let barriers = readx::<(V, f64)>();
    let mut graph = vec![vec![0.0; n+2]; n+2];
    graph[n][n+1] = dist(s, t);
    graph[n+1][n] = dist(s, t);
    for i in 0..n {
        let d1 = dist(s, barriers[i].0);
        let d1 = if d1-barriers[i].1 > 0.0 { d1-barriers[i].1 } else { 0.0 };
        graph[i][n] = d1;
        graph[n][i] = d1;
        let d2 = dist(t, barriers[i].0);
        let d2 = if d2-barriers[i].1 > 0.0 { d2-barriers[i].1 } else { 0.0 };
        graph[i][n+1] = d2;
        graph[n+1][i] = d2;
    }
    for i in 0..n-1 {
        for j in i+1..n {
            let (p1, r1) = barriers[i];
            let (p2, r2) = barriers[j];
            let d = dist(p1, p2);
            let d = if d-(r1+r2) > 0.0 { d-(r1+r2) } else { 0.0 };
            graph[i][j] = d;
            graph[j][i] = d;
        }
    }
    println!("{}", dijkstra(&graph));
}


Measured memory_bytes: 17656