
trait ArcisIterator {
    type Item;
    fn len(&self) -> usize;
    fn __next(&mut self) -> Self::Item;
    fn __next_back(&mut self) -> Self::Item;
}

impl<T: ArcisIterator> T {

    fn count(self) -> usize {
        self.len()
    }
    fn rev(self) -> ArcisRevIterator<Self> {
        ArcisRevIterator::new(self)
    }
    fn enumerate(self) -> ArcisEnumerate<Self> {
        ArcisEnumerate::new(self)
    }
    fn chain(self, other: impl IntoIterator) -> ArcisChainIterator<Self, impl ArcisIterator> {
        ArcisChainIterator::new(self, other.into_iter())
    }
    fn skip(self, n: usize) -> ArcisSkipIterator<Self> {
        ArcisSkipIterator::new(self, n)
    }
    fn take(self, n: usize) -> ArcisTakeIterator<Self> {
        ArcisTakeIterator::new(self, n)
    }
    fn zip(self, other: impl IntoIterator) -> ArcisZipIterator<Self, impl ArcisIterator> {
        ArcisZipIterator::new(self, other.into_iter())
    }
    fn step_by(self, n: usize) -> ArcisStepByIterator<Self> {
        ArcisStepByIterator::new(self, n)
    }
    fn cloned(self) -> ArcisClonedIterator<Self> {
        ArcisClonedIterator::new(self)
    }
    fn copied(self) -> ArcisCopiedIterator<Self> {
        ArcisCopiedIterator::new(self)
    }
    fn for_each<F>(self, mut f: F) {
        for item in self {
            f(item);
        }
    }
    fn map<B, F>(self, func: fn(Self::Item) -> B) -> ArcisMapIterator<Self, B> {
        ArcisMapIterator::new(self, func)
    }
    fn fold<B, F>(self, init: B, mut f: fn(B, Self::Item) -> B) -> B {
        let mut res = init;
        for item in self {
            res = f(res, item);
        }
        res
    }
    fn sum(self) -> Self::Item {
        self.fold( 0 as Self::Item, |a, b| a + b)
    }
    fn product(self) -> Self::Item {
        let mut prod = 1 as Self::Item;
        for val in self {
            prod *= val;
        }
        prod
    }

}

struct ArcisRevIterator<I: ArcisIterator> {
    iter: I,
}
impl<I: ArcisIterator> ArcisRevIterator<I> {
    fn new(iter: I) -> Self {
        ArcisRevIterator { iter }
    }
}

impl<I: ArcisIterator> ArcisIterator for ArcisRevIterator<I> {
    type Item = I::Item;

    fn len(&self) -> usize {
        self.iter.len()
    }
    fn __next(&mut self) -> Self::Item {
        self.iter.__next_back()
    }
    fn __next_back(&mut self) -> Self::Item {
        self.iter.__next()
    }
}
struct ArcisEnumerate<I: ArcisIterator> {
    iter: I,
    counter: usize,
}

impl<I: ArcisIterator> ArcisEnumerate<I> {
    fn new(iter: I) -> Self {
        let counter = 0;
        ArcisEnumerate {
            iter,
            counter,
        }
    }
}

impl<I: ArcisIterator> ArcisIterator for ArcisEnumerate<I> {
    type Item = (usize, I::Item);
    fn len(&self) -> usize {
        self.iter.len()
    }
    fn __next(&mut self) -> (usize, I::Item) {
        let count = self.counter;
        self.counter += 1;
        (count, self.iter.__next())
    }
    fn __next_back(&mut self) -> (usize, I::Item) {
        let count = self.iter.len() + self.counter - 1;
        (count, self.iter.__next_back())
    }
}

struct ArcisChainIterator<I: ArcisIterator, J: ArcisIterator> {
    iter_a: I,
    iter_b: J,
}

impl<I: ArcisIterator, J: ArcisIterator> ArcisChainIterator<I, J> {
    fn new(iter_a: I, iter_b: J) -> Self {
        ArcisChainIterator { iter_a, iter_b }
    }
}

impl<I: ArcisIterator, J: ArcisIterator> ArcisIterator for ArcisChainIterator<I, J> {
    type Item = I::Item;
    fn len(&self) -> usize {
        self.iter_a.len() + self.iter_b.len()
    }
    fn __next(&mut self) -> Self::Item {
        if self.iter_a.len() == 0 {
            self.iter_b.__next()
        } else {
            self.iter_a.__next()
        }
    }
    fn __next_back(&mut self) -> Self::Item {
        if self.iter_b.len() == 0 {
            self.iter_a.__next_back()
        } else {
            self.iter_b.__next_back()
        }
    }
}

struct ArcisSkipIterator<I: ArcisIterator> {
    iter: I,
    n_skips: usize,
}

impl<I: ArcisIterator> ArcisSkipIterator<I> {
    fn new(iter: I, n_skips: usize) -> Self {
        ArcisSkipIterator { iter, n_skips }
    }
}

impl<I: ArcisIterator> ArcisIterator for ArcisSkipIterator<I> {
    type Item = I::Item;
    fn len(&self) -> usize {
        self.iter.len().max(self.n_skips) - self.n_skips
    }
    fn __next(&mut self) -> Self::Item {
        for _ in 0..self.n_skips {
            self.iter.__next();
        }
        self.n_skips = 0;
        self.iter.__next()
    }
    fn __next_back(&mut self) -> Self::Item {
        self.iter.__next_back()
    }
}

struct ArcisTakeIterator<I: ArcisIterator> {
    iter: I,
    n_back_skips: usize,
}

impl<I: ArcisIterator> ArcisTakeIterator<I> {
    fn new(iter: I, n_takes: usize) -> Self {
        let n_back_skips = iter.len() - n_takes;
        ArcisTakeIterator { iter, n_back_skips }
    }
}

impl<I: ArcisIterator> ArcisIterator for ArcisTakeIterator<I> {
    type Item = I::Item;
    fn len(&self) -> usize {
        self.iter.len().max(self.n_back_skips) - self.n_back_skips
    }
    fn __next(&mut self) -> Self::Item {
        self.iter.__next()
    }
    fn __next_back(&mut self) -> Self::Item {
        for _ in 0..self.n_back_skips {
            self.iter.__next_back();
        }
        self.n_back_skips = 0;
        self.iter.__next_back()
    }
}

struct ArcisZipIterator<I: ArcisIterator, J: ArcisIterator> {
    iter_l: I,
    iter_r: J,
}

impl<I: ArcisIterator, J: ArcisIterator> ArcisZipIterator<I, J> {
    fn new(iter_l: I, iter_r: J) -> Self {
        ArcisZipIterator { iter_l, iter_r }
    }
}

impl<I: ArcisIterator, J: ArcisIterator> ArcisIterator for ArcisZipIterator<I, J> {
    type Item = (I::Item, J::Item);
    fn len(&self) -> usize {
        self.iter_l.len().min(self.iter_r.len())
    }
    fn __next(&mut self) -> Self::Item {
        (self.iter_l.__next(), self.iter_r.__next())
    }
    fn __next_back(&mut self) -> Self::Item {
        if self.iter_l.len() > self.iter_r.len() {
            for _ in self.iter_r.len()..self.iter_l.len() {
                self.iter_l.__next_back();
            }
        }
        if self.iter_r.len() > self.iter_l.len() {
            for _ in self.iter_l.len()..self.iter_r.len() {
                self.iter_r.__next_back();
            }
        }
        (self.iter_l.__next_back(), self.iter_r.__next_back())
    }
}

struct ArcisStepByIterator<I: ArcisIterator> {
    iter: I,
    step: usize,
}
impl<I: ArcisIterator> ArcisStepByIterator<I> {
    fn new(iter: I, step: usize) -> Self {
        ArcisStepByIterator { iter, step }
    }
}
impl<I: ArcisIterator> ArcisIterator for ArcisStepByIterator<I> {
    type Item = I::Item;
    fn len(&self) -> usize {
        (self.iter.len() + self.step - 1) / self.step
    }
    fn __next(&mut self) -> Self::Item {
        let res = self.iter.__next();
        for _ in 0..(self.step - 1) {
            if self.iter.len() > 0 {
                self.iter.__next();
            }
        }
        res
    }
    fn __next_back(&mut self) -> Self::Item {
        for _ in 0..((self.iter.len() - 1) % self.step) {
            self.iter.__next_back();
        }
        self.iter.__next_back()
    }
}

struct ArcisCopiedIterator<I: ArcisIterator> {
    iter: I,
}

impl<I: ArcisIterator> ArcisCopiedIterator<I> {
    fn new(iter: I) -> Self {
        ArcisCopiedIterator { iter }
    }
}

impl<T, I: ArcisIterator> ArcisIterator for ArcisCopiedIterator<I> {
    type Item = T;
    fn len(&self) -> usize {
        self.iter.len()
    }
    fn __next(&mut self) -> Self::Item {
        *self.iter.__next()
    }
    fn __next_back(&mut self) -> Self::Item {
        *self.iter.__next_back()
    }
}
struct ArcisClonedIterator<I: ArcisIterator> {
    iter: I,
}

impl<I: ArcisIterator> ArcisClonedIterator<I> {
    fn new(iter: I) -> Self {
        ArcisClonedIterator { iter }
    }
}

impl<T, I: ArcisIterator> ArcisIterator for ArcisClonedIterator<I> {
    type Item = T;
    fn len(&self) -> usize {
        self.iter.len()
    }
    fn __next(&mut self) -> Self::Item {
        self.iter.__next().clone()
    }
    fn __next_back(&mut self) -> Self::Item {
        self.iter.__next_back().clone()
    }
}
struct ArcisArrayIterator<T> {
    arr: [T],
    left_skip: usize,
    right_skip: usize,
}

impl<T> ArcisArrayIterator<T> {
    fn new(arr: [T]) -> Self {
        Self { arr, left_skip: 0, right_skip: 0 }
    }
}

impl<T> ArcisIterator for ArcisArrayIterator<T> {
    type Item = T;
    fn len(&self) -> usize {
        self.arr.len() - self.left_skip - self.right_skip
    }

    fn __next(&mut self) -> Self::Item {
        let res = self.arr[self.left_skip];
        self.left_skip += 1;
        res
    }

    fn __next_back(&mut self) -> Self::Item {
        let res = self.arr[self.arr.len() - 1 - self.right_skip];
        self.right_skip += 1;
        res
    }
}

struct InclusiveRangeIterator<T> {
    start: T,
    end: T,
}

impl<T> InclusiveRangeIterator<T> {
    fn new(start: T, end: T) -> Self {
        InclusiveRangeIterator { start, end }
    }
}

impl<T> ArcisIterator for InclusiveRangeIterator<T> {
    type Item = T;
    fn len(&self) -> usize {
        (self.end - self.start + 1).max(0)
    }

    fn __next(&mut self) -> Self::Item {
        let res = self.start;
        self.start += 1;
        res
    }

    fn __next_back(&mut self) -> Self::Item {
        let res = self.end;
        self.end -= 1;
        res
    }
}

struct ArcisMapIterator<Iter: ArcisIterator, O> {
    iter: Iter,
    func: fn(Iter::Item) -> O,
}

impl<Iter: ArcisIterator, O> ArcisMapIterator<Iter, O> {
    fn new(iter: Iter, func: fn(Iter::Item) -> O) -> Self {
        ArcisMapIterator { iter, func }
    }
}

impl<Iter: ArcisIterator, O> ArcisIterator for ArcisMapIterator<Iter, O> {
    type Item = O;

    fn len(&self) -> usize {
        self.iter.len()
    }
    fn __next(&mut self) -> Self::Item {
        (self.func)(self.iter.__next())
    }
    fn __next_back(&mut self) -> Self::Item {
        (self.func)(self.iter.__next_back())
    }
}

impl (integer, integer) {
    fn __to_inclusive_range(self) -> InclusiveRangeIterator {
        InclusiveRangeIterator::new(self.0, self.1)
    }
    fn __to_exclusive_range(self) -> InclusiveRangeIterator {
        InclusiveRangeIterator::new(self.0, self.1-1)
    }
}
