// The main code is at the very bottom.

#[allow(unused_imports)]
#[macro_use]
pub mod spella {
  pub mod algebra {
    pub use self::structures::*;

    mod structures {
      pub use self::associative::Associative;
      pub use self::magma::Magma;
      pub use self::monoid::Monoid;
      pub use self::semigroup::Semigroup;
      pub use self::unital::Unital;

      mod associative {
        use spella::algebra::Magma;

        pub trait Associative: Magma {}
      }

      mod magma {
        pub trait Magma: Clone {
          fn op(&self, rhs: &Self) -> Self;

          fn op_assign_right(&mut self, rhs: &Self) {
            *self = self.op(rhs);
          }

          fn op_assign_left(&mut self, lhs: &Self) {
            *self = lhs.op(self);
          }
        }
      }

      mod monoid {
        use spella::algebra::{Semigroup, Unital};

        pub trait Monoid: Semigroup + Unital {}

        impl<T: Semigroup + Unital> Monoid for T {}
      }

      mod semigroup {
        use spella::algebra::{Associative, Magma};

        pub trait Semigroup: Magma + Associative {}

        impl<T: Magma + Associative> Semigroup for T {}
      }

      mod unital {
        use spella::algebra::Magma;

        pub trait Unital: Magma {
          fn identity() -> Self;
        }
      }
    }
  }

  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<ByteChar>);

      impl ByteString {
        pub fn into_byte_chars(self) -> Vec<ByteChar> {
          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<Vec<ByteChar>> for ByteString {
        fn from(s: Vec<ByteChar>) -> ByteString {
          ByteString(s)
        }
      }

      impl Borrow<ByteStr> for ByteString {
        fn borrow(&self) -> &ByteStr {
          self.as_byte_str()
        }
      }

      impl BorrowMut<ByteStr> 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<Self, Self::Err>;
      }

      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<Self, Self::Err> {
          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<Self, Self::Err> {
          Ok(ByteString::from(s.to_vec()))
        }
      }

      pub struct ParseFromStrError<T: FromStr>(ParseFromStrErrorKind<T>);

      enum ParseFromStrErrorKind<T: FromStr> {
        Utf8Error(Utf8Error),
        FromStrError(T::Err),
      }

      impl<T: FromStr> Debug for ParseFromStrError<T>
      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<T: FromStr> Display for ParseFromStrError<T>
      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<T: FromStr> Error for ParseFromStrError<T>
      where
        T::Err: Debug + Display,
      {
        fn_description! {}
      }

      impl<T: FromStr> FromByteStr for T {
        type Err = ParseFromStrError<T>;

        fn from_byte_str(s: &ByteStr) -> Result<T, Self::Err> {
          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<R> {
        reader: R,
        buf: Vec<u8>,
        pos: usize,
      }

      const INITIAL_CAPACITY: usize = 32;

      impl<R: BufRead> Scanner<R> {
        pub fn new(reader: R) -> Self {
          Scanner {
            reader: reader,
            buf: Vec::with_capacity(INITIAL_CAPACITY),
            pos: 0,
          }
        }

        pub fn next<T: FromByteStr>(&mut self) -> io::Result<Result<T, T::Err>> {
          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(())
        }
      }
    }
  }

  pub mod mem {
    pub mod arena {
      use self::free_list::FreeList;
      pub use self::rc_arena::*;

      mod free_list {
        use std::mem;

        #[derive(Debug)]
        pub struct FreeList<T> {
          entries: Vec<Entry<T>>,
          next: usize,
        }

        #[derive(Debug)]
        enum Entry<T> {
          Vacant { next: usize },
          Occupied { value: T },
        }

        impl<T> FreeList<T> {
          pub fn with_capacity(capacity: usize) -> Self {
            FreeList {
              entries: Vec::with_capacity(capacity),
              next: 0,
            }
          }

          pub fn get(&self, key: usize) -> &T {
            match &self.entries[key] {
              &Entry::Occupied { ref value } => value,
              &Entry::Vacant { .. } => panic!(),
            }
          }

          pub fn insert(&mut self, value: T) -> usize {
            if self.next == self.entries.len() {
              assert!(self.entries.len() < self.entries.capacity());

              self.entries.push(Entry::Occupied { value: value });
              let new_next = self.next + 1;
              mem::replace(&mut self.next, new_next)
            } else {
              match mem::replace(
                &mut self.entries[self.next],
                Entry::Occupied { value: value },
              ) {
                Entry::Vacant { next } => mem::replace(&mut self.next, next),
                Entry::Occupied { .. } => unreachable!(),
              }
            }
          }

          pub fn remove(&mut self, key: usize) -> T {
            match mem::replace(&mut self.entries[key], Entry::Vacant { next: self.next }) {
              Entry::Occupied { value } => {
                self.next = key;
                value
              }
              Entry::Vacant { .. } => panic!(),
            }
          }
        }
      }

      mod rc_arena {
        use super::FreeList;

        use std::cell::{Cell, UnsafeCell};
        use std::fmt::{self, Debug, Formatter};
        use std::ops::Deref;

        pub struct RcArena<T> {
          pool: UnsafeCell<FreeList<RcBox<T>>>,
        }

        impl<T: Debug> Debug for RcArena<T> {
          fn fmt(&self, f: &mut Formatter) -> fmt::Result {
            f.debug_struct("RcArena")
              .field("pool", unsafe { self.pool() })
              .finish()
          }
        }

        impl<T> RcArena<T> {
          pub fn with_capacity(capacity: usize) -> Self {
            RcArena {
              pool: UnsafeCell::new(FreeList::with_capacity(capacity)),
            }
          }

          pub fn alloc(&self, value: T) -> Rc<T> {
            let key = unsafe { self.pool_mut() }.insert(RcBox::new(value));

            Rc::new(self, key)
          }

          unsafe fn pool(&self) -> &FreeList<RcBox<T>> {
            &*self.pool.get()
          }

          unsafe fn pool_mut(&self) -> &mut FreeList<RcBox<T>> {
            &mut *self.pool.get()
          }
        }

        pub struct Rc<'a, T: 'a> {
          arena: &'a RcArena<T>,
          key: usize,
        }

        impl<'a, T> Rc<'a, T> {
          fn new(arena: &'a RcArena<T>, key: usize) -> Self {
            Rc {
              arena: arena,
              key: key,
            }
          }

          unsafe fn rc_box(&self) -> &RcBox<T> {
            self.arena.pool().get(self.key)
          }

          fn ref_count(&self) -> usize {
            unsafe { self.rc_box() }.ref_count.get()
          }

          unsafe fn set_ref_count(&self, ref_count: usize) {
            self.rc_box().ref_count.set(ref_count)
          }

          unsafe fn inc_ref_count(&self) {
            assert!(self.ref_count() < usize::max_value());

            self.set_ref_count(self.ref_count() + 1)
          }

          unsafe fn dec_ref_count(&self) {
            self.set_ref_count(self.ref_count() - 1)
          }
        }

        impl<'a, T> Clone for Rc<'a, T> {
          fn clone(&self) -> Self {
            unsafe {
              self.inc_ref_count();
            }

            Self::new(self.arena, self.key)
          }
        }

        impl<'a, T> Drop for Rc<'a, T> {
          fn drop(&mut self) {
            unsafe {
              self.dec_ref_count();
            }

            if self.ref_count() == 0 {
              drop(unsafe { self.arena.pool_mut() }.remove(self.key));
            }
          }
        }

        impl<'a, T> Deref for Rc<'a, T> {
          type Target = T;

          fn deref(&self) -> &T {
            &unsafe { self.arena.pool() }.get(self.key).value
          }
        }

        impl<'a, T: Debug> Debug for Rc<'a, T> {
          fn fmt(&self, f: &mut Formatter) -> fmt::Result {
            write!(f, "{:?}", self as &T)
          }
        }

        #[derive(Debug)]
        struct RcBox<T> {
          value: T,
          ref_count: Cell<usize>,
        }

        impl<T> RcBox<T> {
          fn new(value: T) -> Self {
            RcBox {
              value: value,
              ref_count: Cell::new(1),
            }
          }
        }
      }
    }
  }

  pub mod sequences {
    pub mod persistent {
      pub use self::avl_tree::{AvlTree, AvlTreeWithArena};

      pub mod avl_tree {
        use spella::algebra::{Monoid, Semigroup};
        use spella::mem::arena;

        use std::borrow::Cow;
        use std::cmp;
        use std::fmt::{self, Debug, Formatter};
        use std::ops::Deref;

        pub struct Arena<'arena, K: 'arena, V: 'arena>(arena::RcArena<Node<'arena, K, V>>);

        impl<'arena, K, V> Arena<'arena, K, V> {
          pub fn with_capacity(capacity: usize) -> Self {
            Arena(arena::RcArena::with_capacity(capacity))
          }

          pub fn box_and_leak<'a>(self) -> &'a mut Self
          where
            Self: 'a,
          {
            let ptr = Box::into_raw(Box::new(self));
            unsafe { &mut *ptr }
          }
        }

        pub struct AvlTree<'arena, K: 'arena, V: 'arena> {
          root: Option<Link<'arena, K, V>>,
        }

        impl<'arena, K, V> Clone for AvlTree<'arena, K, V> {
          fn clone(&self) -> Self {
            AvlTree::with_root(self.root.as_ref().map(Link::clone))
          }
        }

        impl<'arena, K: Debug, V: Debug> Debug for AvlTree<'arena, K, V> {
          fn fmt(&self, f: &mut Formatter) -> fmt::Result {
            let mut list = f.debug_list();

            if let Some(ref root) = self.root {
              root.traverse(&mut |node| {
                if node.height == 1 {
                  list.entry(&(&node.key, &node.value));
                }
              });
            }

            list.finish()
          }
        }

        impl<'arena, K, V> AvlTree<'arena, K, V> {
          fn with_root<T: Into<Option<Link<'arena, K, V>>>>(root: T) -> Self {
            AvlTree { root: root.into() }
          }

          fn root(&self) -> Option<&Link<'arena, K, V>> {
            self.root.as_ref()
          }
        }

        impl<'arena, K, V> AvlTree<'arena, K, V>
        where
          K: Monoid,
          V: Semigroup,
        {
          pub fn new() -> Self {
            AvlTree { root: None }
          }

          pub fn with_arena(
            self,
            arena: &'arena Arena<'arena, K, V>,
          ) -> AvlTreeWithArena<'arena, K, V> {
            AvlTreeWithArena {
              arena: arena,
              inner: self,
            }
          }

          pub fn is_empty(&self) -> bool {
            self.root.is_none()
          }

          pub fn key(&self) -> Cow<K> {
            self
              .root()
              .map(|root| Cow::Borrowed(&root.key))
              .unwrap_or(Cow::Owned(K::identity()))
          }

          pub fn get<Idx>(&self, index: Idx) -> Option<(&K, &V)>
          where
            Idx: FnMut(&K) -> bool,
          {
            self.root().map(|root| root.get(index))
          }

          pub fn fold<StartIdx, EndIdx>(&self, _start_index: StartIdx, _end_index: EndIdx) -> V
          where
            StartIdx: FnMut(&K) -> bool,
            EndIdx: FnMut(&K) -> bool,
          {
            unimplemented!()
          }

          // TODO
          pub fn traverse<F>(&self, mut f: F)
          where
            F: FnMut(&K, &V),
          {
            if let Some(root) = self.root() {
              root.traverse(&mut |node| {
                if node.height == 1 {
                  f(&node.key, &node.value)
                }
              });
            }
          }
        }

        pub struct AvlTreeWithArena<'arena, K: 'arena, V: 'arena> {
          arena: &'arena Arena<'arena, K, V>,
          inner: AvlTree<'arena, K, V>,
        }

        impl<'arena, K, V> Deref for AvlTreeWithArena<'arena, K, V> {
          type Target = AvlTree<'arena, K, V>;

          fn deref(&self) -> &Self::Target {
            &self.inner
          }
        }

        impl<'arena, K, V> AvlTreeWithArena<'arena, K, V> {
          pub fn into_inner(self) -> AvlTree<'arena, K, V> {
            self.inner
          }
        }

        impl<'arena, K, V> AvlTreeWithArena<'arena, K, V>
        where
          K: Monoid,
          V: Semigroup,
        {
          pub fn from_iter<I>(arena: &'arena Arena<'arena, K, V>, iter: I) -> Self
          where
            I: IntoIterator<Item = (K, V)>,
          {
            use std::collections::VecDeque;

            let mut iter = iter
              .into_iter()
              .map(|(key, value)| Node::new_leaf(key, value));

            let mut deque = {
              let (lower, _) = iter.size_hint();
              VecDeque::with_capacity(lower / 2 + lower % 2)
            };

            loop {
              match (iter.next(), iter.next()) {
                (Some(l), Some(r)) => deque.push_back(Node::new_inner(Twin::new::<Forward>(
                  Link::new(arena, l),
                  Link::new(arena, r),
                ))),

                (Some(node), None) => {
                  deque.push_back(node);
                  break;
                }

                (None, _) => break,
              }
            }

            let mut forward = false;

            while deque.len() > 1 {
              let mut len = deque.len();

              if forward {
                while len >= 2 {
                  let parent = Node::new_inner(Twin::new::<Forward>(
                    Link::new(arena, deque.pop_front().unwrap()),
                    Link::new(arena, deque.pop_front().unwrap()),
                  ));

                  deque.push_back(parent);
                  len -= 2;
                }

                if len == 1 {
                  let node = deque.pop_front().unwrap();
                  deque.push_back(node);
                }
              } else {
                while len >= 2 {
                  let parent = Node::new_inner(Twin::new::<Backward>(
                    Link::new(arena, deque.pop_back().unwrap()),
                    Link::new(arena, deque.pop_back().unwrap()),
                  ));

                  deque.push_front(parent);
                  len -= 2;
                }

                if len == 1 {
                  let node = deque.pop_back().unwrap();
                  deque.push_front(node);
                }
              }

              forward = !forward;
            }

            let root = deque.pop_back().map(|node| Link::new(arena, node));
            AvlTree::with_root(root).with_arena(arena)
          }

          pub fn replace<Idx>(&self, index: Idx, key: K, value: V) -> Option<((&K, &V), Self)>
          where
            Idx: FnMut(&K) -> bool,
          {
            self.root().map(|root| {
              let (key_value, root) = root.replace(self.arena, K::identity(), index, key, value);
              let tree = AvlTree::with_root(Link::new(self.arena, root)).with_arena(self.arena);

              (key_value, tree)
            })
          }

          pub fn insert<Idx>(&self, index: Idx, key: K, value: V) -> Self
          where
            Idx: FnMut(&K) -> bool,
          {
            let root = if let Some(root) = self.root() {
              root.insert(self.arena, K::identity(), index, key, value)
            } else {
              Node::new_leaf(key, value)
            };

            AvlTree::with_root(Link::new(self.arena, root)).with_arena(self.arena)
          }

          pub fn remove<Idx>(&self, index: Idx) -> Option<((&K, &V), Self)>
          where
            Idx: FnMut(&K) -> bool,
          {
            self.root().map(|root| {
              let (key_value, root) = root.remove(self.arena, K::identity(), index);
              let tree = AvlTree::with_root(root).with_arena(self.arena);

              (key_value, tree)
            })
          }

          pub fn append(&self, other: &Self) -> Self {
            let root = match (self.root(), other.root()) {
              (Some(l), Some(r)) => Some(Link::new(self.arena, l.append(self.arena, r))),
              (Some(node), None) | (None, Some(node)) => Some(Link::clone(node)),
              (None, None) => None,
            };

            AvlTree::with_root(root).with_arena(self.arena)
          }

          pub fn split<Idx>(&self, index: Idx) -> (Self, Self)
          where
            Idx: FnMut(&K) -> bool,
          {
            let (l, r) = self
              .root()
              .map(|root| {
                root
                  .split(self.arena, K::identity(), index)
                  .into_inner::<Forward>()
              })
              .unwrap_or_default();

            let l = AvlTree::with_root(l).with_arena(self.arena);
            let r = AvlTree::with_root(r).with_arena(self.arena);

            (l, r)
          }
        }

        #[derive(Debug)]
        struct Node<'arena, K: 'arena, V: 'arena> {
          key: K,
          value: V,
          height: usize,
          children: Option<Twin<Link<'arena, K, V>>>,
        }

        impl<'arena, K, V> Node<'arena, K, V> {
          fn traverse<F>(&self, f: &mut F)
          where
            F: FnMut(&Node<'arena, K, V>),
          {
            if let Some(ref children) = self.children {
              children.l.traverse(f);
              f(&self);
              children.r.traverse(f);
            } else {
              f(&self);
            }
          }
        }

        #[derive(Clone, Debug)]
        struct Link<'arena, K: 'arena, V: 'arena>(arena::Rc<'arena, Node<'arena, K, V>>);

        impl<'arena, K, V> Deref for Link<'arena, K, V> {
          type Target = Node<'arena, K, V>;

          fn deref(&self) -> &Node<'arena, K, V> {
            &self.0
          }
        }

        impl<'arena, K, V> Link<'arena, K, V> {
          fn new(arena: &'arena Arena<'arena, K, V>, node: Node<'arena, K, V>) -> Self {
            Link(arena.0.alloc(node))
          }

          fn clone(this: &Self) -> Self {
            Link(arena::Rc::clone(&this.0))
          }
        }

        impl<'arena, K, V> Node<'arena, K, V>
        where
          K: Monoid,
          V: Semigroup,
        {
          fn new_inner(children: Twin<Link<'arena, K, V>>) -> Self {
            Node {
              key: children.l.key.op(&children.r.key),
              value: children.l.value.op(&children.r.value),
              height: cmp::max(children.l.height, children.r.height) + 1,
              children: Some(children),
            }
          }

          fn new_leaf(key: K, value: V) -> Self {
            Node {
              key: key,
              value: value,
              height: 1,
              children: None,
            }
          }

          fn balance_factor(&self) -> isize {
            self.children.as_ref().map_or(0, |children| {
              children.r.height as isize - children.l.height as isize
            })
          }

          fn get<Idx>(&self, mut index: Idx) -> (&K, &V)
          where
            Idx: FnMut(&K) -> bool,
          {
            let mut key_acc = K::identity();
            let mut node = self;

            while let Some(ref children) = node.children {
              if index(&key_acc.op(&children.l.key)) {
                node = &children.l;
              } else {
                key_acc.op_assign_right(&children.l.key);
                node = &children.r;
              }
            }

            (&node.key, &node.value)
          }
        }

        impl<'arena, K, V> Node<'arena, K, V>
        where
          K: Monoid,
          V: Semigroup,
        {
          fn remove<Idx>(
            &self,
            arena: &'arena Arena<'arena, K, V>,
            key_acc: K,
            mut index: Idx,
          ) -> ((&K, &V), Option<Link<'arena, K, V>>)
          where
            Idx: FnMut(&K) -> bool,
          {
            if let Some(ref children) = self.children {
              let next_key_acc = key_acc.op(&children.l.key);

              if index(&next_key_acc) {
                Self::remove_one_side::<L, _>(arena, children, key_acc, index)
              } else {
                Self::remove_one_side::<R, _>(arena, children, next_key_acc, index)
              }
            } else {
              ((&self.key, &self.value), None)
            }
          }

          fn remove_one_side<'a, Side: SideType, Idx>(
            arena: &'arena Arena<'arena, K, V>,
            children: &'a Twin<Link<'arena, K, V>>,
            key_acc: K,
            index: Idx,
          ) -> ((&'a K, &'a V), Option<Link<'arena, K, V>>)
          where
            Idx: FnMut(&K) -> bool,
          {
            let (a, b) = children.inner::<Side>();
            let (key_value, a) = a.remove(arena, key_acc, index);

            let root = if let Some(a) = a {
              Link::new(
                arena,
                Node::new_inner(Twin::new::<Side>(a, Link::clone(b))).adjust::<Side>(arena),
              )
            } else {
              Link::clone(b)
            };

            (key_value, Some(root))
          }

          fn adjust<Side: SideType>(self, arena: &'arena Arena<'arena, K, V>) -> Self {
            Side::select::<fn(_, _) -> _>(Self::adjust_l, Self::adjust_r).0(self, arena)
          }

          fn adjust_l(self, arena: &'arena Arena<'arena, K, V>) -> Self {
            match self.balance_factor() {
              -1...1 => self,

              2 => match self.children.as_ref().unwrap().r.balance_factor() {
                -1 => self.rotate_twice::<L>(arena),

                0...1 => self.rotate_once::<L>(arena),

                _ => unreachable!(),
              },

              _ => unreachable!(),
            }
          }

          fn adjust_r(self, arena: &'arena Arena<'arena, K, V>) -> Self {
            match self.balance_factor() {
              -1...1 => self,

              -2 => match self.children.as_ref().unwrap().l.balance_factor() {
                -1...0 => self.rotate_once::<R>(arena),

                1 => self.rotate_twice::<R>(arena),

                _ => unreachable!(),
              },

              _ => unreachable!(),
            }
          }

          fn rotate_once<Side: SideType>(&self, arena: &'arena Arena<'arena, K, V>) -> Self {
            let a = self;

            let (b, c) = a.children.as_ref().unwrap().inner::<Side>();
            let (d, e) = c.children.as_ref().unwrap().inner::<Side>();

            let a = Node::new_inner(Twin::new::<Side>(Link::clone(b), Link::clone(d)));
            let c = Node::new_inner(Twin::new::<Side>(Link::new(arena, a), Link::clone(e)));

            c
          }

          fn rotate_twice<Side: SideType>(&self, arena: &'arena Arena<'arena, K, V>) -> Self {
            let a = self;

            let (b, c) = a.children.as_ref().unwrap().inner::<Side>();
            let (d, e) = c.children.as_ref().unwrap().inner::<Side>();
            let (f, g) = d.children.as_ref().unwrap().inner::<Side>();

            let a = Node::new_inner(Twin::new::<Side>(Link::clone(b), Link::clone(f)));
            let c = Node::new_inner(Twin::new::<Side>(Link::clone(g), Link::clone(e)));
            let d = Node::new_inner(Twin::new::<Side>(Link::new(arena, a), Link::new(arena, c)));

            d
          }
        }

        impl<'arena, K, V> Link<'arena, K, V>
        where
          K: Monoid,
          V: Semigroup,
        {
          fn replace<Idx>(
            &self,
            arena: &'arena Arena<'arena, K, V>,
            key_acc: K,
            mut index: Idx,
            key: K,
            value: V,
          ) -> ((&K, &V), Node<'arena, K, V>)
          where
            Idx: FnMut(&K) -> bool,
          {
            if let Some(ref children) = self.children {
              let next_key_acc = key_acc.op(&children.l.key);

              if index(&next_key_acc) {
                Self::replace_one_side::<L, _>(arena, children, key_acc, index, key, value)
              } else {
                Self::replace_one_side::<R, _>(arena, children, next_key_acc, index, key, value)
              }
            } else {
              let node = Node::new_leaf(key, value);

              ((&self.key, &self.value), node)
            }
          }

          fn replace_one_side<'a, Side: SideType, Idx>(
            arena: &'arena Arena<'arena, K, V>,
            children: &'a Twin<Link<'arena, K, V>>,
            key_acc: K,
            index: Idx,
            key: K,
            value: V,
          ) -> ((&'a K, &'a V), Node<'arena, K, V>)
          where
            Idx: FnMut(&K) -> bool,
          {
            let (a, b) = children.inner::<Side>();
            let (key_value, a) = a.replace(arena, key_acc, index, key, value);
            let root = Node::new_inner(Twin::new::<Side>(Link::new(arena, a), Link::clone(b)));

            (key_value, root)
          }

          fn insert<Idx>(
            &self,
            arena: &'arena Arena<'arena, K, V>,
            key_acc: K,
            mut index: Idx,
            key: K,
            value: V,
          ) -> Node<'arena, K, V>
          where
            Idx: FnMut(&K) -> bool,
          {
            if let Some(ref children) = self.children {
              let next_key_acc = key_acc.op(&children.l.key);

              if index(&next_key_acc) {
                Self::insert_one_side::<L, _>(arena, children, key_acc, index, key, value)
              } else {
                Self::insert_one_side::<R, _>(arena, children, next_key_acc, index, key, value)
              }
            } else {
              let node = Link::new(arena, Node::new_leaf(key, value));

              Node::new_inner(if index(&key_acc.op(&self.key)) {
                Twin::new::<Forward>(node, Link::clone(self))
              } else {
                Twin::new::<Forward>(Link::clone(self), node)
              })
            }
          }

          fn insert_one_side<Side: SideType, Idx>(
            arena: &'arena Arena<'arena, K, V>,
            children: &Twin<Link<'arena, K, V>>,
            key_acc: K,
            index: Idx,
            key: K,
            value: V,
          ) -> Node<'arena, K, V>
          where
            Idx: FnMut(&K) -> bool,
          {
            let (a, b) = children.inner::<Side>();
            let a = a.insert(arena, key_acc, index, key, value);

            Node::new_inner(Twin::new::<Side>(Link::new(arena, a), Link::clone(b)))
              .adjust::<Side::Opposite>(arena)
          }

          fn split<Idx>(
            &self,
            arena: &'arena Arena<'arena, K, V>,
            key_acc: K,
            mut index: Idx,
          ) -> Twin<Option<Link<'arena, K, V>>>
          where
            Idx: FnMut(&K) -> bool,
          {
            if let Some(ref children) = self.children {
              let next_key_acc = key_acc.op(&children.l.key);

              if index(&next_key_acc) {
                Self::split_one_side::<L, _>(arena, children, key_acc, index)
              } else {
                Self::split_one_side::<R, _>(arena, children, next_key_acc, index)
              }
            } else {
              if index(&key_acc.op(&self.key)) {
                Twin::new::<Forward>(None, Some(Link::clone(self)))
              } else {
                Twin::new::<Forward>(Some(Link::clone(self)), None)
              }
            }
          }

          fn split_one_side<Side: SideType, Idx>(
            arena: &'arena Arena<'arena, K, V>,
            children: &Twin<Link<'arena, K, V>>,
            key_acc: K,
            index: Idx,
          ) -> Twin<Option<Link<'arena, K, V>>>
          where
            Idx: FnMut(&K) -> bool,
          {
            let (a, b) = children.inner::<Side>();
            let (a_a, a_b) = a.split(arena, key_acc, index).into_inner::<Side>();

            let b = if let Some(a_b) = a_b {
              Link::new(
                arena,
                Self::merge(arena, Twin::new::<Side>(a_b, Link::clone(b))),
              )
            } else {
              Link::clone(b)
            };

            Twin::new::<Side>(a_a, Some(b))
          }

          fn merge(
            arena: &'arena Arena<'arena, K, V>,
            children: Twin<Link<'arena, K, V>>,
          ) -> Node<'arena, K, V> {
            children.l.append(arena, &children.r)
          }

          fn append(&self, arena: &'arena Arena<'arena, K, V>, other: &Self) -> Node<'arena, K, V> {
            if self.height > other.height {
              Self::merge_into::<L>(arena, self, other)
            } else {
              Self::merge_into::<R>(arena, other, self)
            }
          }

          fn merge_into<Side: SideType>(
            arena: &'arena Arena<'arena, K, V>,
            dst: &Self,
            src: &Self,
          ) -> Node<'arena, K, V> {
            debug_assert!(src.height <= dst.height);

            if dst.height - src.height > 1 {
              let children = dst.children.as_ref().unwrap();
              let (a, b) = children.inner::<Side>();

              Node::new_inner(Twin::new::<Side>(
                Link::clone(a),
                Link::new(arena, Self::merge_into::<Side>(arena, b, src)),
              ))
              .adjust::<Side>(arena)
            } else {
              Node::new_inner(Twin::new::<Side>(Link::clone(dst), Link::clone(src)))
            }
          }
        }

        #[derive(Clone, Debug)]
        struct Twin<T> {
          l: T,
          r: T,
        }

        impl<T> Twin<T> {
          fn new<Side: SideType>(a: T, b: T) -> Self {
            let (l, r) = Side::select(a, b);
            Twin { l: l, r: r }
          }

          fn inner<Side: SideType>(&self) -> (&T, &T) {
            Side::select(&self.l, &self.r)
          }

          fn into_inner<Side: SideType>(self) -> (T, T) {
            Side::select(self.l, self.r)
          }
        }

        trait SideType {
          type Opposite: SideType;

          fn select<T>(a: T, b: T) -> (T, T);
        }

        enum L {}
        enum R {}

        type Forward = L;
        type Backward = R;

        impl SideType for L {
          type Opposite = R;

          fn select<T>(a: T, b: T) -> (T, T) {
            (a, b)
          }
        }

        impl SideType for R {
          type Opposite = L;

          fn select<T>(a: T, b: T) -> (T, T) {
            (b, a)
          }
        }
      }
    }
  }
}

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<usize> = 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<R: BufRead, W: Write>(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::<Vec<_>>()
    }};
  }

  #[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),+) => {{
      eprintln!(concat!("[{}:{}] ", $(stringify!($x), " = {:?}; "),+), file!(), line!(), $($x),+);
    }};
  }

  use spella::algebra::{Associative, Magma, Unital};
  use spella::sequences::persistent::avl_tree::{Arena, AvlTree, AvlTreeWithArena};
  use std::ops::Deref;

  #[derive(Clone, Copy, Debug)]
  pub struct K(pub usize);

  impl Magma for K {
    fn op(&self, rhs: &Self) -> Self {
      K(self.0 + rhs.0)
    }
  }

  impl Associative for K {}

  impl Unital for K {
    fn identity() -> Self {
      K(0)
    }
  }

  #[derive(Clone, Copy, Debug)]
  struct V(pub u64);

  impl Magma for V {
    fn op(&self, _rhs: &Self) -> Self {
      V(0)
    }
  }

  impl Associative for V {}

  macro_rules! index {
    ($i:expr) => {
      |&K(len)| len > $i
    };
  }

  fn repeat<'arena>(
    arena: &'arena Arena<'arena, K, V>,
    x: u64,
    n: usize,
  ) -> AvlTreeWithArena<'arena, K, V> {
    match n {
      0 => AvlTree::new().with_arena(arena),
      1 => AvlTreeWithArena::from_iter(arena, iter::once((K(1), V(x)))),
      _ => {
        let half = repeat(arena, x, n / 2);
        let mut seq = half.append(&half);
        if n % 2 != 0 {
          seq = seq.insert(index!(0), K(1), V(x));
        }
        seq
      }
    }
  }

  let (n, m) = scan!(usize, usize);

  let mut a = scan!(u64; n);
  a.sort();

  let arena = Arena::with_capacity(1000000).box_and_leak();
  let mut a = AvlTreeWithArena::<K, V>::from_iter(arena, a.into_iter().map(|a_i| (K(1), V(a_i))));
  dbg!(a.deref());

  for _ in 0..m {
    let (b, c) = scan!(usize, u64);

    let r = {
      let mut ok = 0;
      let mut ng = b + 1;

      while ng - ok > 1 {
        let mid = (ok + ng) / 2;

        if (a.get(index!(mid - 1)).unwrap().1).0 < c {
          ok = mid;
        } else {
          ng = mid;
        }
      }

      ok
    };

    dbg!(r, c);

    let (_, tail) = a.split(index!(r));
    dbg!(tail.deref());

    let k = {
      let mut ok = 0;
      let mut ng = tail.key().0 + 1;

      while ng - ok > 1 {
        let mid = (ok + ng) / 2;

        if (tail.get(index!(mid - 1)).unwrap().1).0 < c {
          ok = mid;
        } else {
          ng = mid;
        }
      }

      ok
    };

    let (tail_l, tail_r) = tail.split(index!(k));
    dbg!(tail_l.deref(), tail_r.deref());

    a = tail_l.append(&repeat(arena, c, r)).append(&tail_r);
    dbg!(a.deref());
  }

  let mut sum = 0;
  a.traverse(|_, &V(a_i)| sum += a_i);

  println!("{}", sum);
}


Measured memory_bytes: 24828