fn main() {
    let mut sc = Scanner::new();
    let n = sc.usize();

    let mut times = vec![];
    let mut xlr = vec![];
    for _ in 0..n {
        let x = sc.input::<String>();
        let l = sc.usize();
        let r = sc.usize();
        xlr.push((x, l, r));
        times.push(l);
        times.push(r);
    }

    let q = sc.usize();
    let mut queries : Vec<(u8, String, usize, usize)> = vec![];
    for _ in 0..q {
        let t = sc.u8();
        match t {
            1 => {
                let x = sc.input::<String>();
                let time = sc.usize();
                queries.push((t, x, time, 0));
                times.push(time);
            }
            2 => {
                let time = sc.usize();
                queries.push((t, "".to_string(), time, 0));
                times.push(time);
            }
            3 => {
                let x = sc.input::<String>();
                let l = sc.usize();
                let r = sc.usize();
                queries.push((t, x, l, r));
                times.push(l);
                times.push(r);
            }
            _ => unreachable!()
        }
    }

    times.sort(); times.dedup();

    def_map_monoid!(M,
        i64,
        i64,
        0,
        |&a:&Self::Type, &b:&Self::Type| a.max(b),
        |&a:&Self::F,&b:&Self::F| a + b,
        |&(a,i):&(Self::Type,usize), &b:&Self::F| a + b
    );

    let mut id = BTreeMap::new();
    let mut now = 0;
    let mut sets = vec![];
    let mut seg = LazySegmentTree::<M>::new(times.len());
    for (x, l, r) in xlr {
        let l = times.binary_search(&l).unwrap();
        let r = times.binary_search(&r).unwrap();
        seg.update(l..=r, 1);
        if !id.contains_key(&x) {
            id.insert(x.clone(), now);
            now += 1;
            sets.push(RangeSet::new(true));
        }
        let id = id[&x];
        sets[id].insert_range(l as i64 ..=r as i64);
    }

    for i in 0..q {
        match queries[i] {
            (1, ref x, time, _) => {
                let time = times.binary_search(&time).unwrap();
                let id = id[x];
                if sets[id].contains(time as i64) {
                    println!("Yes");
                } else {
                    println!("No");
                }
            }
            (2, _, time, _) => {
                let time = times.binary_search(&time).unwrap();
                let ans = seg.fold(time..=time);
                println!("{}", ans);
            }
            (3, ref x, l, r) => {
                let l = times.binary_search(&l).unwrap();
                let r = times.binary_search(&r).unwrap();
                if !id.contains_key(x) {
                    id.insert(x.clone(), now);
                    now += 1;
                    sets.push(RangeSet::new(true));
                }
                let id = id[x];
                seg.update(l..=r, 1);
                sets[id].insert_range(l as i64..r as i64);
            }
            _ => unreachable!()
        }
    }
}

struct RangeSet {
    ranges: std::collections::BTreeSet<(i64, i64)>,
    len: i64,
    merge_adjacent_range_flag: bool
}

#[allow(dead_code)]
impl RangeSet {
    fn new(merge_adjacent_range_flag: bool) -> Self {
        Self { ranges: std::collections::BTreeSet::new(), len:0, merge_adjacent_range_flag }
    }

    fn contains(&self, x:i64) -> bool {
        self.contains_range(x..=x)
    }

    fn contains_range<R:std::ops::RangeBounds<i64>>(&self, range:R) -> bool {
        let left = match range.start_bound() {
            std::ops::Bound::Unbounded => unreachable!(),
            std::ops::Bound::Included(&l) => l,
            _ => unreachable!()
        };
        let right = match range.end_bound() {
            std::ops::Bound::Unbounded => unreachable!(),
            std::ops::Bound::Included(&x) => x + 1,
            std::ops::Bound::Excluded(&x) => x,
        };

        if let Some(&(l2, r2)) = self.ranges.range((left,left)..).next() {
            if l2 <= left && right <= r2 { return true; }
        }

        if let Some(&(l2, r2)) = self.ranges.range(..(left,left)).next_back() {
            if l2 <= left && right <= r2 { return true; }
        }

        false
    }

    fn insert(&mut self, x:i64) -> (i64, i64) {
        self.insert_range(x..=x)
    }

    fn insert_range<R:std::ops::RangeBounds<i64>>(&mut self, range:R) -> (i64, i64) {
        let mut left = match range.start_bound() {
            std::ops::Bound::Unbounded => unreachable!(),
            std::ops::Bound::Included(&l) => l,
            _ => unreachable!()
        };
        let mut right = match range.end_bound() {
            std::ops::Bound::Unbounded => unreachable!(),
            std::ops::Bound::Included(&x) => x + 1,
            std::ops::Bound::Excluded(&x) => x,
        };

        let mut erase = vec![];
        for &(l, r) in self.ranges.range((left,left)..=(right,right)) {
            left = left.min(l);
            right = right.max(r);
            erase.push((l, r));
        }

        if let Some(&prev) = self.ranges.range(..(left,std::i64::MIN)).next_back() {
            if left < prev.1 + if self.merge_adjacent_range_flag {1} else {0} { left = left.min(prev.0); right = right.max(prev.1); erase.push(prev); }
        }

        if let Some(&next) = self.ranges.range((right, std::i64::MIN)..).next() {
            if right > next.0 - if self.merge_adjacent_range_flag {1} else {0} { left = left.min(next.0); right = right.max(next.1); erase.push(next); }
        }

        for e in erase { self.ranges.remove(&e); self.len -= e.1 - e.0 }
        self.ranges.insert((left, right));
        self.len += right - left;
        (left, right)
    }

    fn remove(&mut self, x:i64) -> () {
        self.remove_range(x..=x);
    }

    fn remove_range<R:std::ops::RangeBounds<i64>>(&mut self, range:R) -> () {
        let mut left = match range.start_bound() {
            std::ops::Bound::Unbounded => unreachable!(),
            std::ops::Bound::Included(&l) => l,
            _ => unreachable!()
        };
        let mut right = match range.end_bound() {
            std::ops::Bound::Unbounded => unreachable!(),
            std::ops::Bound::Included(&x) => x + 1,
            std::ops::Bound::Excluded(&x) => x,
        };

        let mut erase = vec![];
        let mut add = vec![];
        for &(l, r) in self.ranges.range((left,left)..=(right,right)) {
            if right < r { add.push((right, r)); }
            if l < left { add.push((l, left)); }
            erase.push((l, r));
        }

        if let Some(&prev) = self.ranges.range(..(left,std::i64::MIN)).next_back() {
            if left < prev.1 + if self.merge_adjacent_range_flag {1} else {0} {
                if prev.0 < left { add.push((prev.0, left)); }
                if right < prev.1 { add.push((right, prev.1)); }
                erase.push(prev);
            }
        }

        if let Some(&next) = self.ranges.range((right, std::i64::MIN)..).next() {
            if right > next.0 - if self.merge_adjacent_range_flag {1} else {0} {
                if next.0 < left { add.push((next.0, left)); }
                if right < next.1 { add.push((right, next.1)); }
                erase.push(next);
            }
        }

        for e in erase { self.ranges.remove(&e); self.len -= e.1 - e.0 }
        for a in add { self.ranges.insert(a); self.len += a.1 - a.0 }
    }



    fn ranges_count(&self) -> usize {
        self.ranges.len()
    }

    fn len(&self) -> i64 {
        self.len
    }

    fn iter(&self) -> std::collections::btree_set::Iter<'_, (i64, i64)> {
        self.ranges.iter()
    }

    fn mex(&self, mut x:i64) -> i64 {
        if let Some(prev) = self.ranges.range(..=(x,std::i64::MAX)).next_back() {
            if x <= prev.0 { x = prev.1 + 1; }
        }
        x
    }
}

#[macro_export]
macro_rules! def_map_monoid {
    ($m:ident, $t1:ty, $t2:ty, $id:expr, $op:expr, $merge:expr, $eval:expr) => {
        pub struct $m;
        impl MapMonoid for $m {
            type Type = $t1;
            type F = $t2;
            fn identity() -> Self::Type { $id }
            fn operator(x:&Self::Type, y:&Self::Type) -> Self::Type { $op(x, y) }
            fn merge(x:&Option<Self::F>, y:&Option<Self::F>) -> Option<Self::F> {
                match (x, y) {
                    (None, None) => None,
                    (Some(x), Some(y)) => Some($merge(x, y)),
                    (&x, None) => x,
                    (None, &y) => y
                }
            }
            fn eval(x:&(Self::Type, usize), y:&Self::F) -> Self::Type {
                $eval(x, y)
            }
        }
    };
}

pub trait MapMonoid {
    type Type: Copy + Clone + std::fmt::Debug;
    type F: Copy + Clone + std::fmt::Debug;
    fn identity() -> Self::Type;
    fn operator(a: &Self::Type, b: &Self::Type) -> Self::Type;
    fn merge(a: &Option<Self::F>, b: &Option<Self::F>) -> Option<Self::F>;
    fn eval(a: &(Self::Type, usize), b: &Self::F) -> Self::Type;
}

struct LazySegmentTree<T: MapMonoid> {
    n: usize,
    seg: Vec<(T::Type, usize)>,
    lazy: Vec<Option<T::F>>,
}

#[allow(unused)]
impl<T: MapMonoid> LazySegmentTree<T> {
    pub fn new(n: usize) -> Self {
        let mut seg = vec![(T::identity(), 1); 2*n+1];
        for i in (1..n).rev() { seg[i].1 = seg[2*i].1 + seg[2*i+1].1; }
        Self { n, seg: seg, lazy: vec![None; 2 * n + 1] }
    }

    pub fn from(s: &[T::Type]) -> Self {
        let n = s.len();
        let mut seg = vec![(T::identity(), 1); 2 * n + 1];
        for (i, &si) in s.iter().enumerate() { seg[i + n].0 = si; }
        for i in (1..n).rev() {
            seg[i].0 = T::operator(&seg[2 * i].0, &seg[2 * i + 1].0);
            seg[i].1 = &seg[2 * i].1 + &seg[2 * i + 1].1;
        }
        LazySegmentTree { n, seg, lazy: vec![None; 2 * n + 1] }
    }

    fn eval(&mut self, i: usize) -> T::Type {
        if let Some(x) = self.lazy[i] {
            T::eval(&self.seg[i], &x)
        } else {
            self.seg[i].0
        }
    }

    fn propagate_at(&mut self, i: usize) {
        self.seg[i] = (self.eval(i), self.seg[i].1);
        self.lazy[i*2] = T::merge(&self.lazy[i * 2], &self.lazy[i]);
        self.lazy[i*2 + 1] = T::merge(&self.lazy[i * 2 + 1], &self.lazy[i]);
        self.lazy[i] = None;
    }

    fn propagate_above(&mut self, i: usize) {
        let height = 63u32.saturating_sub(i.leading_zeros());
        for h in (1..=height).rev() {
            self.propagate_at(i >> h);
        }
    }

    fn recalc_above(&mut self, mut i: usize) {
        while i > 0 {
            i /= 2;
            let left = self.eval(i * 2);
            let right = self.eval(i * 2 + 1);
            self.seg[i].0 = T::operator(&left, &right);
        }
    }

    fn _update(&mut self, mut l: usize, mut r: usize, x: T::F) {
        let l0 = l / (l & l.wrapping_neg());
        let r0 = r / (r & r.wrapping_neg()) - 1;
        self.propagate_above(l0);
        self.propagate_above(r0);

        while l < r {
            if l % 2 == 1 {
                self.lazy[l] = T::merge(&self.lazy[l], &Some(x));
                l += 1;
            }
            if r % 2 == 1 {
                r -= 1;
                self.lazy[r] = T::merge(&self.lazy[r], &Some(x));
            }
            l /= 2;
            r /= 2;
        }

        self.recalc_above(l0);
        self.recalc_above(r0);
    }

    pub fn update<R: std::ops::RangeBounds<usize>>(&mut self, range: R, x: T::F) {
        let l = self.n + match range.start_bound() {
            std::ops::Bound::Unbounded => 0,
            std::ops::Bound::Included(&l) => l,
            _ => unreachable!()
        };
        let r = self.n + match range.end_bound() {
            std::ops::Bound::Unbounded => self.n,
            std::ops::Bound::Included(&x) => x + 1,
            std::ops::Bound::Excluded(&x) => x,
        };
        self._update(l, r, x)
    }

    fn _fold(&mut self, mut l: usize, mut r: usize) -> T::Type {
        let mut left = T::identity();
        let mut right = T::identity();

        self.propagate_above(l / (l & l.wrapping_neg()));
        self.propagate_above(r / (r & r.wrapping_neg()) - 1);

        while l < r {
            if l % 2 == 1 {
                left = T::operator(&left, &self.eval(l));
                l += 1;
            }
            if r % 2 == 1 {
                r -= 1;
                right = T::operator(&self.eval(r), &right);
            }
            l /= 2;
            r /= 2;
        }
        T::operator(&left, &right)
    }

    pub fn fold<R: std::ops::RangeBounds<usize>>(&mut self, range: R) -> T::Type {
        let l = self.n + match range.start_bound() {
            std::ops::Bound::Unbounded => 0,
            std::ops::Bound::Included(&l) => l,
            _ => unreachable!()
        };
        let r = self.n + match range.end_bound() {
            std::ops::Bound::Unbounded => self.n,
            std::ops::Bound::Included(&x) => x + 1,
            std::ops::Bound::Excluded(&x) => x,
        };
        self._fold(l, r)
    }

    pub fn get(&mut self, index: usize) -> T::Type { self.fold(index..=index) }
}



struct Scanner { s : std::collections::VecDeque<String> } #[allow(unused)] impl Scanner { fn new() -> Self { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); Self { s : s.split_whitespace().map(|s| s.to_string()).collect() } } fn reload(&mut self) -> () { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); self.s = s.split_whitespace().map(|s| s.to_string()).collect(); } fn usize(&mut self) -> usize { self.input() } fn usize1(&mut self) -> usize { self.input::<usize>() - 1 } fn isize(&mut self) -> isize { self.input() } fn i32(&mut self) -> i32 { self.input() } fn i64(&mut self) -> i64 { self.input() } fn i128(&mut self) -> i128 { self.input() } fn u8(&mut self) -> u8 { self.input() } fn u32(&mut self) -> u32 { self.input() } fn u64(&mut self) -> u64 { self.input() } fn u128(&mut self) -> u128 { self.input() } fn edge(&mut self) -> (usize, usize) { (self.usize1(), self.usize1()) } fn edges(&mut self, m : usize) -> Vec<(usize, usize)> { let mut e = Vec::with_capacity(m); for _ in 0..m { e.push(self.edge()); } e } fn wedge<T:std::str::FromStr>(&mut self) -> (usize, usize, T) { (self.usize1(), self.usize1(), self.input()) } fn wedges<T:std::str::FromStr>(&mut self, m : usize) -> Vec<(usize, usize, T)> { let mut e = Vec::with_capacity(m); for _ in 0..m { e.push(self.wedge()); } e } fn input<T>(&mut self) -> T where T: std::str::FromStr { if self.s.is_empty() { self.reload(); } if let Some(head) = self.s.pop_front() { head.parse::<T>().ok().unwrap() } else { panic!() } } fn tuple<T, U>(&mut self) -> (T, U) where T: std::str::FromStr, U: std::str::FromStr { (self.input(), self.input()) } fn vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr { if self.s.is_empty() { self.reload(); } self.s.drain(..n).map(|s| s.parse::<T>().ok().unwrap() ).collect::<Vec<T>>() } fn nvec<T>(&mut self) -> Vec<T> where T: std::str::FromStr { let n : usize = self.input(); self.vec(n) } fn chars(&mut self) -> Vec<char> { let s : String = self.input(); s.chars().collect() } fn bytes(&mut self) -> Vec<u8> { let s : String = self.input(); s.bytes().collect() } }


// Copyright 2017 Alkis Evlogimenos
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

use std::cmp::Ordering::{self, Less, Greater};
use std::collections::BTreeMap;

/// Extends [`slice`] with fast operations on ordered slices.
///
/// [`slice`]: https://doc.rust-lang.org/stable/std/primitive.slice.html
pub trait Ext {
    type Item;

    /// Returns the index `i` pointing to the first element in the ordered slice
    /// that is _not less_ than `x`.
    ///
    /// The slice MUST be ordered by the order defined by its elements.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let a = [10, 11, 13, 13, 15];
    /// assert_eq!(a.lower_bound(&9), 0);
    /// assert_eq!(a.lower_bound(&10), 0);
    /// assert_eq!(a.lower_bound(&11), 1);
    /// assert_eq!(a.lower_bound(&12), 2);
    /// assert_eq!(a.lower_bound(&13), 2);
    /// assert_eq!(a.lower_bound(&14), 4);
    /// assert_eq!(a.lower_bound(&15), 4);
    /// assert_eq!(a.lower_bound(&16), 5);
    /// ```
    fn lower_bound(&self, x: &Self::Item) -> usize
        where
            Self::Item: Ord;

    /// Returns the index `i` pointing to the first element in the ordered slice
    /// for which `f(self[i]) != Less`.
    ///
    /// The slice MUST be ordered by the order defined by the comparator
    /// function. The comparator function should take an element and return
    /// `Ordering` that is consistent with the ordering of the slice.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let b = [1, 2, 3, 6, 9, 9];
    /// assert_eq!(b.lower_bound(&3), b.lower_bound_by(|x| x.cmp(&3)));
    /// ```
    fn lower_bound_by<'a, F>(&'a self, f: F) -> usize
        where
            F: FnMut(&'a Self::Item) -> Ordering;

    /// Returns the index `i` pointing to the first element in the ordered slice
    /// for which `f(self[i]) >= k`.
    ///
    /// The slice MUST be ordered by the order defined by the keys of its
    /// elements.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let b = [1, 2, 3, 6, 9, 9];
    /// assert_eq!(b.lower_bound(&3), b.lower_bound_by_key(&6, |x| x * 2));
    /// ```
    fn lower_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize
        where
            F: FnMut(&'a Self::Item) -> K,
            K: Ord;

    /// Returns the index `i` pointing to the first element in the ordered slice
    /// that is _greater_ than `x`.
    ///
    /// The slice MUST be ordered by the order defined by its elements.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let a = [10, 11, 13, 13, 15];
    /// assert_eq!(a.upper_bound(&9), 0);
    /// assert_eq!(a.upper_bound(&10), 1);
    /// assert_eq!(a.upper_bound(&11), 2);
    /// assert_eq!(a.upper_bound(&12), 2);
    /// assert_eq!(a.upper_bound(&13), 4);
    /// assert_eq!(a.upper_bound(&14), 4);
    /// assert_eq!(a.upper_bound(&15), 5);
    /// assert_eq!(a.upper_bound(&16), 5);
    /// ```
    fn upper_bound(&self, x: &Self::Item) -> usize
        where
            Self::Item: Ord;

    /// Returns the index `i` pointing to the first element in the ordered slice
    /// for which `f(self[i]) == Greater`.
    ///
    /// The slice MUST be ordered by the order defined by the comparator
    /// function. The comparator function should take an element and return
    /// `Ordering` that is consistent with the ordering of the slice.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let b = [1, 2, 3, 6, 9, 9];
    /// assert_eq!(b.upper_bound(&3), b.upper_bound_by(|x| x.cmp(&3)));
    /// ```
    fn upper_bound_by<'a, F>(&'a self, f: F) -> usize
        where
            F: FnMut(&'a Self::Item) -> Ordering;

    /// Returns the index `i` pointing to the first element in the ordered slice
    /// for which `f(self[i]) > k`.
    ///
    /// The slice MUST be ordered by the order defined by the keys of its
    /// elements.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let b = [1, 2, 3, 6, 9, 9];
    /// assert_eq!(b.lower_bound(&3), b.lower_bound_by_key(&6, |x| x * 2));
    fn upper_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize
        where
            F: FnMut(&'a Self::Item) -> K,
            K: Ord;

    /// Returns the [`Range`] `a..b` such that all elements in `self[a..b]` are
    /// _equal_ to `x`.
    ///
    /// The slice MUST be ordered by the order defined by its elements.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let b = [10, 11, 13, 13, 15];
    /// for i in 9..17 {
    ///     assert_eq!(b.equal_range(&i), (b.lower_bound(&i)..b.upper_bound(&i)));
    /// }
    /// ```
    /// [`Range`]: https://doc.rust-lang.org/stable/std/ops/struct.Range.html
    fn equal_range(&self, x: &Self::Item) -> std::ops::Range<usize>
        where
            Self::Item: Ord;

    /// Returns the [`Range`] `a..b` such that for all elements `e` in `self[a..b]`
    /// `f(e) == Equal`.
    ///
    /// The slice MUST be ordered by the order defined by the comparator
    /// function. The comparator function should take an element and return
    /// `Ordering` that is consistent with the ordering of the slice.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let b = [10, 11, 13, 13, 15];
    /// for i in 9..17 {
    ///     assert_eq!(b.equal_range(&i), b.equal_range_by(|x| x.cmp(&i)));
    /// }
    /// ```
    /// [`Range`]: https://doc.rust-lang.org/stable/std/ops/struct.Range.html
    fn equal_range_by<'a, F>(&'a self, f: F) -> std::ops::Range<usize>
        where
            F: FnMut(&'a Self::Item) -> Ordering;

    /// Returns the [`Range`] `a..b` such that for all elements `e` in `self[a..b]`
    /// `f(e) == k`.
    ///
    /// The slice MUST be ordered by the order defined by the keys of its
    /// elements.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let b = [10, 11, 13, 13, 15];
    /// for i in 9..17 {
    ///     let i2 = i * 2;
    ///     assert_eq!(b.equal_range(&i), b.equal_range_by_key(&i2, |x| x * 2));
    /// }
    /// ```
    /// [`Range`]: https://doc.rust-lang.org/stable/std/ops/struct.Range.html
    fn equal_range_by_key<'a, K, F>(&'a self, k: &K, f: F) -> std::ops::Range<usize>
        where
            F: FnMut(&'a Self::Item) -> K,
            K: Ord;

    /// Transforms the slice into the next permutation from the set of all
    /// permutations that are lexicographically ordered with respect to the
    /// natural order of T. Returns true if such permutation exists, otherwise
    /// transforms the range into the first permutation and returns false.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let mut b = [2, 1, 3];
    /// let mut v = Vec::new();
    /// for _ in 0..6 {
    ///     let x = b.next_permutation();
    ///     v.push((x, b.to_vec()));
    /// }
    /// assert_eq!(v, &[(true, [2, 3, 1].to_vec()),
    ///                 (true, [3, 1, 2].to_vec()),
    ///                 (true, [3, 2, 1].to_vec()),
    ///                 (false, [1, 2, 3].to_vec()),
    ///                 (true, [1, 3, 2].to_vec()),
    ///                 (true, [2, 1, 3].to_vec())]);
    fn next_permutation(&mut self) -> bool
        where
            Self::Item: Ord;

    /// Transforms the slice into the previous permutation from the set of all
    /// permutations that are lexicographically ordered with respect to the
    /// natural order of T. Returns true if such permutation exists, otherwise
    /// transforms the range into the last permutation and returns false.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let mut b = [2, 1, 3];
    /// let mut v = Vec::new();
    /// for _ in 0..6 {
    ///     let x = b.prev_permutation();
    ///     v.push((x, b.to_vec()));
    /// }
    /// assert_eq!(v, &[(true, [1, 3, 2].to_vec()),
    ///                 (true, [1, 2, 3].to_vec()),
    ///                 (false, [3, 2, 1].to_vec()),
    ///                 (true, [3, 1, 2].to_vec()),
    ///                 (true, [2, 3, 1].to_vec()),
    ///                 (true, [2, 1, 3].to_vec())]);
    fn prev_permutation(&mut self) -> bool
        where
            Self::Item: Ord;

    /// Applies `permutation` to the slice. For each element at index `i` the
    /// following holds:
    ///
    ///   new_self[i] == old_self[permutation[i]]
    ///
    /// The transformation happens in O(N) time and O(1) space. `permutation`
    /// is mutated during the transformation but it is restored to its original
    /// state on return.
    ///
    /// # Panics
    ///
    /// This function panics if `self` and `permutation` do not have the same
    /// length or any value in `permutation` is not in `0..self.len()`.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let mut b = ['d', 'a', 'c', 'b'];
    /// let mut p = [1, 3, 2, 0];
    /// b.apply_permutation(&mut p);
    /// assert_eq!(b, ['a', 'b', 'c', 'd']);
    /// assert_eq!(p, [1, 3, 2, 0]);
    fn apply_permutation(&mut self, permutation: &mut [isize]);

    /// Applies the inverse of `permutation` to the slice. For each element at
    /// index `i` the following holds:
    ///
    ///   new_self[permutation[i]] == old_self[i]
    ///
    /// The transformation happens in O(N) time and O(1) space. `permutation`
    /// is mutated during the transformation but it is restored to its original
    /// state on return.
    ///
    /// # Panics
    ///
    /// This function panics if `self` and `permutation` do not have the same
    /// length or any value in `permutation` is not in `0..self.len()`.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let mut b = ['d', 'a', 'c', 'b'];
    /// let mut p = [3, 0, 2, 1];
    /// b.apply_inverse_permutation(&mut p);
    /// assert_eq!(b, ['a', 'b', 'c', 'd']);
    /// assert_eq!(p, [3, 0, 2, 1]);
    fn apply_inverse_permutation(&mut self, permutation: &mut [isize]);
}

impl<T> Ext for [T] {
    type Item = T;

    fn lower_bound(&self, x: &Self::Item) -> usize
        where
            T: Ord,
    {
        self.lower_bound_by(|y| y.cmp(x))
    }
    fn lower_bound_by<'a, F>(&'a self, mut f: F) -> usize
        where
            F: FnMut(&'a Self::Item) -> Ordering,
    {
        let s = self;
        let mut size = s.len();
        if size == 0 {
            return 0;
        }
        let mut base = 0usize;
        while size > 1 {
            let half = size / 2;
            let mid = base + half;
            let cmp = f(unsafe { s.get_unchecked(mid) });
            base = if cmp == Less { mid } else { base };
            size -= half;
        }
        let cmp = f(unsafe { s.get_unchecked(base) });
        base + (cmp == Less) as usize
    }
    fn lower_bound_by_key<'a, K, F>(&'a self, k: &K, mut f: F) -> usize
        where
            F: FnMut(&'a Self::Item) -> K,
            K: Ord,
    {
        self.lower_bound_by(|e| f(e).cmp(k))
    }

    fn upper_bound(&self, x: &Self::Item) -> usize
        where
            T: Ord,
    {
        self.upper_bound_by(|y| y.cmp(x))
    }

    fn upper_bound_by<'a, F>(&'a self, mut f: F) -> usize
        where
            F: FnMut(&'a Self::Item) -> Ordering,
    {
        let s = self;
        let mut size = s.len();
        if size == 0 {
            return 0;
        }
        let mut base = 0usize;
        while size > 1 {
            let half = size / 2;
            let mid = base + half;
            let cmp = f(unsafe { s.get_unchecked(mid) });
            base = if cmp == Greater { base } else { mid };
            size -= half;
        }
        let cmp = f(unsafe { s.get_unchecked(base) });
        base + (cmp != Greater) as usize
    }
    fn upper_bound_by_key<'a, K, F>(&'a self, k: &K, mut f: F) -> usize
        where
            F: FnMut(&'a Self::Item) -> K,
            K: Ord,
    {
        self.upper_bound_by(|e| f(e).cmp(k))
    }

    fn equal_range(&self, x: &Self::Item) -> std::ops::Range<usize>
        where
            T: Ord,
    {
        self.equal_range_by(|y| y.cmp(x))
    }
    fn equal_range_by<'a, F>(&'a self, mut f: F) -> std::ops::Range<usize>
        where
            F: FnMut(&'a Self::Item) -> Ordering,
    {
        let s = self;
        let mut size = s.len();
        if size == 0 {
            return 0..0;
        }
        let mut base = (0usize, 0usize);
        while size > 1 {
            let half = size / 2;
            let mid = (base.0 + half, base.1 + half);
            let cmp = (
                f(unsafe { s.get_unchecked(mid.0) }),
                f(unsafe { s.get_unchecked(mid.1) }),
            );
            base = (
                if cmp.0 == Less { mid.0 } else { base.0 },
                if cmp.1 == Greater { base.1 } else { mid.1 },
            );
            size -= half;
        }
        let cmp = (
            f(unsafe { s.get_unchecked(base.0) }),
            f(unsafe { s.get_unchecked(base.1) }),
        );
        (base.0 + (cmp.0 == Less) as usize..base.1 + (cmp.1 != Greater) as usize)
    }

    fn equal_range_by_key<'a, K, F>(&'a self, k: &K, mut f: F) -> std::ops::Range<usize>
        where
            F: FnMut(&'a Self::Item) -> K,
            K: Ord,
    {
        self.equal_range_by(|e| f(e).cmp(k))
    }

    fn next_permutation(&mut self) -> bool
        where
            Self::Item: Ord
    {
        // Adapted from http://en.cppreference.com/w/cpp/algorithm/next_permutation.
        if self.len() <= 1 { return false; }
        let last = self.len() - 1;
        let mut a = last;
        loop {
            let mut b = a;
            a -= 1;
            if self[a] < self[b] {
                b = last;
                while self[a] >= self[b] {
                    b -= 1;
                }
                self.swap(a, b);
                self[a+1..].reverse();
                return true;
            }
            if a == 0 {
                self.reverse();
                return false;
            }
        }
    }

    fn prev_permutation(&mut self) -> bool
        where
            Self::Item: Ord
    {
        // Adapted from http://en.cppreference.com/w/cpp/algorithm/prev_permutation.
        if self.len() <= 1 { return false; }
        let last = self.len() - 1;
        let mut a = last;
        loop {
            let mut b = a;
            a -= 1;
            if self[b] < self[a] {
                b = last;
                while self[b] >= self[a] {
                    b -= 1;
                }
                self.swap(a, b);
                self[a+1..].reverse();
                return true;
            }
            if a == 0 {
                self.reverse();
                return false;
            }
        }
    }

    fn apply_permutation(&mut self, perm: &mut [isize]) {
        assert_eq!(self.len(), perm.len());
        assert!(self.len() < isize::max_value() as usize);
        for i in 0..self.len() as isize {
            let mut c = perm[i as usize];
            if c < 0 {
                perm[i as usize] = !c;
            } else if i != c {
                loop {
                    let n = perm[c as usize];
                    self.swap(c as usize, n as usize);
                    perm[c as usize] = !n;
                    c = n;
                    if i == c { break; }
                }
            }
        }
    }

    fn apply_inverse_permutation(&mut self, perm: &mut [isize]) {
        assert_eq!(self.len(), perm.len());
        assert!(self.len() < isize::max_value() as usize);
        for i in 0..self.len() as isize {
            let mut c = perm[i as usize];
            if c < 0 {
                perm[i as usize] = !c;
            } else if i != c {
                loop {
                    self.swap(c as usize, i as usize);
                    let n = perm[c as usize];
                    perm[c as usize] = !n;
                    c = n;
                    if i == c { break; }
                }
            }
        }
    }
}

pub trait Ext2 {
    /// Transforms the slice in the inverse permutation.
    ///
    /// # Panics
    ///
    /// This function panics if any value in `self` is not in `0..self.len()`.
    ///
    /// # Example:
    ///
    /// ```
    /// # use superslice::*;
    /// let mut p = [1, 3, 2, 0];
    /// p.invert_permutation();
    /// assert_eq!(p, [3, 0, 2, 1]);
    fn invert_permutation(&mut self);
}

impl Ext2 for [isize] {
    fn invert_permutation(&mut self) {
        assert!(self.len() < isize::max_value() as usize);
        for i in 0..self.len() as isize {
            let mut c = self[i as usize];
            if c < 0 {
                self[i as usize] = !c;
            } else if i != c {
                let mut n = i;
                loop {
                    let t = self[c as usize];
                    self[c as usize] = !n;
                    n = c;
                    c = t;
                    if c == i {
                        self[i as usize] = n;
                        break;
                    }
                }
            }
        }
    }
}