use std::ptr::NonNull;

pub trait Cluster: Clone + std::fmt::Debug {
    type V: Default + Copy + std::fmt::Debug;
    fn identity() -> Self;
    fn compress(left: Self, right: Self, a: Self::V, b: Self::V, c: Self::V) -> Self;
    fn rake(left: Self, right: Self, a: Self::V, b: Self::V, c: Self::V) -> Self;
    fn reverse(&mut self);
}

pub type Link<N> = Option<N>;

pub struct VertexRaw<T: Cluster> {
    val: T::V,
    handle: Option<CompNode<T>>
}

impl<T: Cluster> VertexRaw<T> {
    pub fn new(val: T::V) -> Self {
        VertexRaw {
            val: val,
            handle: None,
        }
    }
    pub fn dummy() -> Self {
        VertexRaw {
            val: T::V::default(),
            handle: None,
        }
    }
    pub fn handle(&self) -> Option<CompNode<T>> {
        self.handle
    }
    pub fn handle_mut(&mut self) -> &mut Option<CompNode<T>> {
        &mut self.handle
    }
    pub fn value(&self) -> T::V {
        self.val
    }
    pub fn value_set(&mut self, val: T::V) {
        let mut root = expose_raw(self.handle().unwrap());
        self.val = val;
        root.fix();
    }
}

pub struct Vertex<T: Cluster> {
    vertex: NonNull<VertexRaw<T>>,
}

impl<T: Cluster> Vertex<T> {
    pub fn dangling() -> Self {
        Vertex { vertex: NonNull::dangling() }
    }
    pub fn new(val: T::V) -> Self {
        unsafe {
            let v = Vertex { vertex: NonNull::new_unchecked(Box::into_raw(Box::new(VertexRaw::new(val)))) };
            let dummy = Vertex { vertex: NonNull::new_unchecked(Box::into_raw(Box::new(VertexRaw::dummy()))) };
            link(v, dummy, T::identity());
            v
        }
    }
    pub fn handle(&self) -> Option<CompNode<T>> {
        unsafe { self.vertex.as_ref().handle() }
    }
    pub fn handle_mut(&mut self) -> &mut Option<CompNode<T>> {
        unsafe { self.vertex.as_mut().handle_mut() }
    }
    pub fn value(&self) -> T::V {
        unsafe { self.vertex.as_ref().value() }
    }
    pub fn value_set(&mut self, val: T::V) {
        unsafe { self.vertex.as_mut().value_set(val); }
    }
}

impl<T: Cluster> Clone for Vertex<T> {
    fn clone(&self) -> Self {
        Vertex { vertex: self.vertex.clone() }
    }
}
impl<T: Cluster> Copy for Vertex<T> {}
impl<T: Cluster> PartialEq for Vertex<T> {
    fn eq(&self, other: &Self) -> bool {
        self.vertex == other.vertex
    }
}

pub enum CompNode<T: Cluster> {
    Node(NonNull<Compress<T>>),
    Leaf(NonNull<Edge<T>>),
}

pub enum RakeNode<T: Cluster> {
    Node(NonNull<Rake<T>>),
    Leaf(CompNode<T>),
}

pub enum ParentNode<T: Cluster> {
    Compress(NonNull<Compress<T>>),
    Rake(NonNull<Rake<T>>),
}

pub struct Edge<T: Cluster> {
    v: [Vertex<T>; 2],
    par: Link<ParentNode<T>>,
    me: NonNull<Edge<T>>,


    pub val: T,
}

pub struct Compress<T: Cluster> {
    ch: [CompNode<T>; 2],
    v: [Vertex<T>; 2],
    rake: Link<RakeNode<T>>,
    par: Link<ParentNode<T>>,
    me: NonNull<Compress<T>>,
    rev: bool,

    pub guard: bool,


    pub fold: T
}

pub struct Rake<T: Cluster> {
    ch: [RakeNode<T>; 2],
    v: [Vertex<T>; 2],
    par: Link<ParentNode<T>>,

    fold: T,
}

impl<T: Cluster> Edge<T> {
    pub fn new(v: Vertex<T>, u: Vertex<T>, val: T) -> NonNull<Edge<T>> {
        unsafe {
            let mut e = NonNull::new_unchecked(Box::into_raw(Box::new(Edge {
                v: [v, u],
                par: None,
                val: val,
                me: NonNull::dangling(),
            })));
            e.as_mut().me = e;
            e.as_mut().fix();
            e
        }
    }
}

impl<T: Cluster> Compress<T> {
    pub fn new(left: CompNode<T>, right: CompNode<T>) -> NonNull<Compress<T>> {
        unsafe {
            let mut n = NonNull::new_unchecked(Box::into_raw(Box::new(Compress {
                ch: [left, right],
                v: [Vertex::dangling(), Vertex::dangling()],
                rake: None,
                par: None,
                rev: false,
                me: NonNull::dangling(),
                guard: false,
                fold: T::identity(),
            })));
            n.as_mut().me = n;
            n.as_mut().fix();
            n
        }
    }
}

impl<T: Cluster> Rake<T> {
    pub fn new(left: RakeNode<T>, right: RakeNode<T>) -> NonNull<Rake<T>> {
        unsafe {
            let mut r = NonNull::new_unchecked(Box::into_raw(Box::new(Rake {
                ch: [left, right],
                v: [Vertex::dangling(), Vertex::dangling()],
                par: None,
                fold: T::identity()
            })));
            r.as_mut().fix();
            r
        }
    }
}

pub trait TVertex<T: Cluster> {
    fn fix(&mut self);
    fn push(&mut self);
    fn reverse(&mut self);
    fn parent(&self) -> Link<ParentNode<T>>;
    fn parent_mut(&mut self) -> &mut Link<ParentNode<T>>;
}

pub trait Node<T: Cluster>: TVertex<T> {
    type Child: TVertex<T>;
    fn child(&self, dir: usize) -> Self::Child;
    fn child_mut(&mut self, dir: usize) -> &mut Self::Child;
}

impl<T: Cluster> TVertex<T> for Edge<T> {
    fn fix(&mut self) {
        match self.parent() {
            Some(ParentNode::Compress(_)) => {
                if parent_dir_comp(CompNode::Leaf(self.me)).is_none() {
                    *self.v[0].handle_mut() = Some(CompNode::Leaf(self.me));
                }
            }
            Some(ParentNode::Rake(_)) => {
                *self.v[0].handle_mut() = Some(CompNode::Leaf(self.me));
            }
            _ => {
                *self.v[0].handle_mut() = Some(CompNode::Leaf(self.me));
                *self.v[1].handle_mut() = Some(CompNode::Leaf(self.me));
            }
        }
    }
    fn push(&mut self) {}
    fn reverse(&mut self) {
        self.v.swap(0, 1);
        self.val.reverse();
    }
    fn parent(&self) -> Link<ParentNode<T>> { self.par }
    fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> { &mut self.par }
}

impl<T: Cluster> Compress<T> {
    pub fn rake(&self) -> Link<RakeNode<T>> { self.rake }
    pub fn rake_mut(&mut self) -> &mut Link<RakeNode<T>> { &mut self.rake }
}

impl<T: Cluster> TVertex<T> for Compress<T> {
    fn fix(&mut self) {
        self.push();
        self.v[0] = self.ch[0].endpoints(0);
        self.v[1] = self.ch[1].endpoints(1);
        //self.fold = self.ch[0].fold() + self.ch[1].fold();

        self.fold = T::compress(
            match self.rake {
                Some(r) => T::rake(self.ch[0].fold(), r.fold(), self.ch[0].endpoints(0).value(), r.endpoints(0).value(), self.ch[0].endpoints(1).value()),
                None => self.ch[0].fold(),
            },
            self.ch[1].fold(), self.ch[0].endpoints(0).value(), self.ch[1].endpoints(1).value(), self.ch[0].endpoints(1).value()
            );
        *self.ch[0].endpoints(1).handle_mut() = Some(CompNode::Node(self.me));
        /*println!("fix=====");
        for i in 0..2 {
            for j in 0..2 {
                println!("{}, {} = {}", i, j, self.ch[0].endpoints(i) == self.ch[1].endpoints(j));
            }
        }*/
        assert!(self.ch[0].endpoints(1) == self.ch[1].endpoints(0));
        match self.parent() {
            Some(ParentNode::Compress(_)) => {
                if parent_dir_comp(CompNode::Node(self.me)).is_none() {
                    *self.v[0].handle_mut() = Some(CompNode::Node(self.me));
                }
            },
            Some(ParentNode::Rake(_)) => {
                *self.v[0].handle_mut() = Some(CompNode::Node(self.me));
            }
            _ => {
                *self.v[0].handle_mut() = Some(CompNode::Node(self.me));
                *self.v[1].handle_mut() = Some(CompNode::Node(self.me));
            }
        }
    }
    fn push(&mut self) {
        if self.rev {
            self.ch[0].reverse();
            self.ch[1].reverse();
            self.rev = false;
        }
    }
    fn reverse(&mut self) {
        self.ch.swap(0, 1);
        self.v.swap(0, 1);
        self.fold.reverse();
        self.rev ^= true;
        self.push();
    }
    fn parent(&self) -> Link<ParentNode<T>> { self.par }
    fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> { &mut self.par }
}

impl<T: Cluster> Node<T> for Compress<T> {
    type Child = CompNode<T>;
    fn child(&self, dir: usize) -> Self::Child { self.ch[dir] }
    fn child_mut(&mut self, dir: usize) -> &mut Self::Child { &mut self.ch[dir] }
}

impl<T: Cluster> TVertex<T> for Rake<T> {
    fn fix(&mut self) {
        self.push();
        self.v = [self.ch[0].endpoints(0), self.ch[0].endpoints(1)];
        self.fold = T::rake(self.ch[0].fold(), self.ch[1].fold(), self.ch[0].endpoints(0).value(), self.ch[1].endpoints(0).value(), self.ch[0].endpoints(1).value());
    }
    fn push(&mut self) {
    }
    fn reverse(&mut self) {
        self.push();
    }
    fn parent(&self) -> Link<ParentNode<T>> { self.par }
    fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> { &mut self.par }
}

impl<T: Cluster> Node<T> for Rake<T> {
    type Child = RakeNode<T>;
    fn child(&self, dir: usize) -> Self::Child { self.ch[dir] }
    fn child_mut(&mut self, dir: usize) -> &mut Self::Child { &mut self.ch[dir] }
}

impl<T: Cluster> CompNode<T> {
    pub fn endpoints(&self, dir: usize) -> Vertex<T> {
        unsafe {
            match *self {
                CompNode::Node(node) => node.as_ref().v[dir],
                CompNode::Leaf(leaf) => leaf.as_ref().v[dir],
            }
        }
    }
    pub fn fold(&self) -> T {
        unsafe {
            match *self {
                CompNode::Node(node) => node.as_ref().fold.clone(),
                CompNode::Leaf(leaf) => leaf.as_ref().val.clone(),
            }
        }
    }
}

impl<T: Cluster> RakeNode<T> {
    pub fn endpoints(&self, dir: usize) -> Vertex<T> {
        unsafe {
            match *self {
                RakeNode::Node(node) => node.as_ref().v[dir],
                RakeNode::Leaf(leaf) => leaf.endpoints(dir),
            }
        }
    }
    pub fn fold(&self) -> T {
        unsafe {
            match *self {
                RakeNode::Node(node) => node.as_ref().fold.clone(),
                RakeNode::Leaf(leaf) => leaf.fold(),
            }
        }
    }
}

impl<T: Cluster> TVertex<T> for CompNode<T> {
    fn fix(&mut self) {
        unsafe {
            match *self {
                CompNode::Node(mut node) => node.as_mut().fix(),
                CompNode::Leaf(mut leaf) => leaf.as_mut().fix(),
            }
        }
    }
    fn push(&mut self) {
        unsafe {
            match *self {
                CompNode::Node(mut node) => node.as_mut().push(),
                CompNode::Leaf(mut leaf) => leaf.as_mut().push(),
            }
        }
    }
    fn reverse(&mut self) {
        unsafe {
            match *self {
                CompNode::Node(mut node) => node.as_mut().reverse(),
                CompNode::Leaf(mut leaf) => leaf.as_mut().reverse(),
            }
        }
    }
    fn parent(&self) -> Link<ParentNode<T>> {
        unsafe {
            match *self {
                CompNode::Node(node) => node.as_ref().parent(),
                CompNode::Leaf(leaf) => leaf.as_ref().parent(),
            }
        }
    }
    fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> {
        unsafe {
            match self {
                CompNode::Node(ref mut node) => node.as_mut().parent_mut(),
                CompNode::Leaf(ref mut leaf) => leaf.as_mut().parent_mut(),
            }
        }
    }
}

impl<T: Cluster> TVertex<T> for RakeNode<T> {
    fn fix(&mut self) {
        unsafe {
            match *self {
                RakeNode::Node(mut node) => node.as_mut().fix(),
                RakeNode::Leaf(mut leaf) => leaf.fix(),
            }
        }
    }
    fn push(&mut self) {
        unsafe {
            match *self {
                RakeNode::Node(mut node) => node.as_mut().push(),
                RakeNode::Leaf(mut leaf) => leaf.push(),
            }
        }
    }
    fn reverse(&mut self) {
        unsafe {
            match *self {
                RakeNode::Node(mut node) => node.as_mut().reverse(),
                RakeNode::Leaf(mut leaf) => leaf.reverse(),
            }
        }
    }
    fn parent(&self) -> Link<ParentNode<T>> {
        unsafe {
            match *self {
                RakeNode::Node(node) => node.as_ref().parent(),
                RakeNode::Leaf(leaf) => leaf.parent(),
            }
        }
    }
    fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> {
        unsafe {
            match self {
                RakeNode::Node(ref mut node) => node.as_mut().parent_mut(),
                RakeNode::Leaf(ref mut leaf) => leaf.parent_mut(),
            }
        }
    }
}

impl<T: Cluster> TVertex<T> for ParentNode<T> {
    fn fix(&mut self) {
        unsafe {
            match *self {
                ParentNode::Compress(mut node) => node.as_mut().fix(),
                ParentNode::Rake(mut leaf) => leaf.as_mut().fix(),
            }
        }
    }
    fn push(&mut self) {
        unsafe {
            match *self {
                ParentNode::Compress(mut node) => node.as_mut().push(),
                ParentNode::Rake(mut leaf) => leaf.as_mut().push(),
            }
        }
    }
    fn reverse(&mut self) {
        unsafe {
            match *self {
                ParentNode::Compress(mut node) => node.as_mut().reverse(),
                ParentNode::Rake(mut leaf) => leaf.as_mut().reverse(),
            }
        }
    }
    fn parent(&self) -> Link<ParentNode<T>> {
        unsafe {
            match *self {
                ParentNode::Compress(node) => node.as_ref().parent(),
                ParentNode::Rake(leaf) => leaf.as_ref().parent(),
            }
        }
    }
    fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> {
        unsafe {
            match self {
                ParentNode::Compress(ref mut node) => node.as_mut().parent_mut(),
                ParentNode::Rake(ref mut leaf) => leaf.as_mut().parent_mut(),
            }
        }
    }
}

impl<T: Cluster> PartialEq for CompNode<T> {
    fn eq(&self, other: &Self) -> bool {
        match (*self, *other) {
            (CompNode::Node(a), CompNode::Node(b)) => a == b,
            (CompNode::Leaf(a), CompNode::Leaf(b)) => a == b,
            _ => false,
        }
    }
}

impl<T: Cluster> PartialEq for RakeNode<T> {
    fn eq(&self, other: &Self) -> bool {
        match (*self, *other) {
            (RakeNode::Node(a), RakeNode::Node(b)) => a == b,
            (RakeNode::Leaf(a), RakeNode::Leaf(b)) => a == b,
            _ => false,
        }
    }
}


impl<T: Cluster> PartialEq for ParentNode<T> {
    fn eq(&self, other: &Self) -> bool {
        match (*self, *other) {
            (ParentNode::Compress(a), ParentNode::Compress(b)) => a == b,
            (ParentNode::Rake(a), ParentNode::Rake(b)) => a == b,
            _ => false,
        }
    }
}


impl<T: Cluster> Clone for CompNode<T> {
    fn clone(&self) -> Self {
        match *self {
            CompNode::Node(a) => CompNode::Node(a),
            CompNode::Leaf(a) => CompNode::Leaf(a),
        }
    }
}

impl<T: Cluster> Clone for RakeNode<T> {
    fn clone(&self) -> Self {
        match *self {
            RakeNode::Node(a) => RakeNode::Node(a),
            RakeNode::Leaf(a) => RakeNode::Leaf(a),
        }
    }
}

impl<T: Cluster> Clone for ParentNode<T> {
    fn clone(&self) -> Self {
        match *self {
            ParentNode::Compress(a) => ParentNode::Compress(a),
            ParentNode::Rake(a) => ParentNode::Rake(a),
        }
    }
}

impl<T: Cluster> Copy for CompNode<T> {}
impl<T: Cluster> Copy for RakeNode<T> {}
impl<T: Cluster> Copy for ParentNode<T> {}

pub fn parent_dir_comp<T: Cluster>(child: CompNode<T>) -> Option<(usize, NonNull<Compress<T>>)> {
    unsafe {
        match child.parent() {
            Some(ParentNode::Compress(mut p)) => {
                p.as_mut().push();
                if p.as_ref().guard { None }
                else if p.as_ref().child(0) == child { Some((0, p)) }
                else if p.as_ref().child(1) == child { Some((1, p)) }
                else { None }
            }
            _ => None,
        }
    }
}

pub fn parent_dir_comp_guard<T: Cluster>(child: CompNode<T>) -> Option<(usize, NonNull<Compress<T>>)> {
    unsafe {
        match child.parent() {
            Some(ParentNode::Compress(mut p)) => {
                p.as_mut().push();
                if p.as_ref().child(0) == child { Some((0, p)) }
                else if p.as_ref().child(1) == child { Some((1, p)) }
                else { None }
            }
            _ => None,
        }
    }
}


pub fn parent_dir_comp_rake<T: Cluster>(child: CompNode<T>) -> Option<(usize, NonNull<Rake<T>>)> { 
    unsafe { 
        match child.parent() {
            Some(ParentNode::Rake(mut p)) => {
                p.as_mut().push();
                if p.as_ref().child(0) == RakeNode::Leaf(child) { Some((0, p)) }
                else if p.as_ref().child(1) == RakeNode::Leaf(child) { Some((1, p)) }
                else { None }
            }
            _ => None,
        }
    }
}


pub fn parent_dir_rake<T: Cluster>(child: RakeNode<T>) -> Option<(usize, NonNull<Rake<T>>)> {
    unsafe {
        match child.parent() {
            Some(ParentNode::Rake(mut p)) => {
                p.as_mut().push();
                if p.as_ref().child(0) == child { Some((0, p)) }
                else if p.as_ref().child(1) == child { Some((1, p)) }
                else { None }
            }
            _ => None,
        }
    }
}

pub fn rotate_comp<T: Cluster>(mut t: NonNull<Compress<T>>, mut x: NonNull<Compress<T>>, dir: usize) {
    unsafe {
        let y = x.as_ref().parent();
        if let Some(mut yy) = y { 
            yy.push()
        }
        let par = parent_dir_comp_guard(CompNode::Node(x));
        let rake_par = parent_dir_comp_rake(CompNode::Node(x));
        *x.as_mut().child_mut(dir ^ 1) = t.as_ref().child(dir);
        *t.as_ref().child(dir).parent_mut() = Some(ParentNode::Compress(x));
        *t.as_mut().child_mut(dir) = CompNode::Node(x);
        *x.as_mut().parent_mut() = Some(ParentNode::Compress(t));
        x.as_mut().fix();
        t.as_mut().fix();
        *t.as_mut().parent_mut() = y;
        if let Some((xdir, mut yy)) = par {
            *yy.as_mut().child_mut(xdir) = CompNode::Node(t);
            //println!("yy===========================");
            //test_comp_endpoints(CompNode::Node(yy));
            if !yy.as_ref().guard { yy.as_mut().fix(); }
        }
        else if let Some((xdir, mut yy)) = rake_par {
            *yy.as_mut().child_mut(xdir) = RakeNode::Leaf(CompNode::Node(t));
            yy.as_mut().fix();
        }
    }
}

pub fn rotate_rake<T: Cluster>(mut t: NonNull<Rake<T>>, mut x: NonNull<Rake<T>>, dir: usize) {
    unsafe {
        let y = x.as_ref().parent();
        if let Some(mut yy) = y { yy.push() }
        let par = parent_dir_rake(RakeNode::Node(x));
        *x.as_mut().child_mut(dir ^ 1) = t.as_ref().child(dir);
        *t.as_ref().child(dir).parent_mut() = Some(ParentNode::Rake(x));
        *t.as_mut().child_mut(dir) = RakeNode::Node(x);
        *x.as_mut().parent_mut() = Some(ParentNode::Rake(t));
        x.as_mut().fix();
        t.as_mut().fix();
        *t.as_mut().parent_mut() = y;
        if let Some((xdir, mut yy)) = par {
            *yy.as_mut().child_mut(xdir) = RakeNode::Node(t);
            yy.as_mut().fix();
        }
        else if let Some(ParentNode::Compress(mut yy)) = y {
            *yy.as_mut().rake_mut() = Some(RakeNode::Node(t));
            //test_comp_print(CompNode::Node(yy));
            //test_comp_print(yy.as_ref().child(0));
            //test_comp_print(yy.as_ref().child(1));
            if !yy.as_ref().guard { yy.as_mut().fix(); }
        }
    }
}

pub fn splay_comp<T: Cluster>(mut t: NonNull<Compress<T>>) {
    unsafe {
        t.as_mut().push();
        t.as_mut().fix();
        while let Some((_,mut q)) = parent_dir_comp(CompNode::Node(t)) {
            q.as_mut().push();
            if let Some((_, mut r)) = parent_dir_comp(CompNode::Node(q)) {
                r.as_mut().push();
                q.as_mut().push();
                t.as_mut().push();
                let qt_dir = parent_dir_comp(CompNode::Node(t)).unwrap().0;
                let rq_dir = parent_dir_comp(CompNode::Node(q)).unwrap().0;
                if rq_dir == qt_dir {
                    rotate_comp(q, r, rq_dir ^ 1);
                    rotate_comp(t, q, qt_dir ^ 1);
                }
                else {
                    rotate_comp(t, q, qt_dir ^ 1);
                    rotate_comp(t, r, rq_dir ^ 1);
                }
            }
            else {
                let qt_dir = parent_dir_comp(CompNode::Node(t)).unwrap().0;
                t.as_mut().push();
                //println!("t =====================");
                //test_comp_print(CompNode::Node(t));
                //println!("=============");
                //test_comp_endpoints(CompNode::Node(q));
                rotate_comp(t, q, qt_dir ^ 1);
            }
        }
    }
    //println!("====================== end splay =================================");
}

pub fn splay_rake<T: Cluster>(mut t: NonNull<Rake<T>>) {
    unsafe {
        t.as_mut().push();
        t.as_mut().fix();
        while let Some((_, mut q)) = parent_dir_rake(RakeNode::Node(t)) {
            q.as_mut().push();
            if let Some((_, mut r)) = parent_dir_rake(RakeNode::Node(q)) {
                r.as_mut().push();
                q.as_mut().push();
                t.as_mut().push();
                let qt_dir = parent_dir_rake(RakeNode::Node(t)).unwrap().0;
                let rq_dir = parent_dir_rake(RakeNode::Node(q)).unwrap().0;
                if rq_dir == qt_dir {
                    rotate_rake(q, r, rq_dir ^ 1);
                    rotate_rake(t, q, qt_dir ^ 1);
                }
                else {
                    rotate_rake(t, q, qt_dir ^ 1);
                    rotate_rake(t, r, rq_dir ^ 1);
                }
            }
            else {
                let qt_dir = parent_dir_rake(RakeNode::Node(t)).unwrap().0;
                t.as_mut().push();
                rotate_rake(t, q, qt_dir ^ 1);
            }
        }
    }
}
pub fn expose_raw<T: Cluster>(mut node: CompNode<T>) -> CompNode<T> {
    loop {
        //println!("function expose --- node");
        //test_comp_print(node);
        //println!("endpoints ---------------------");
        /*test_comp_endpoints(
            {
                let mut nn = node;
                while let Some((_dir, par)) = parent_dir_comp(nn) {
                    nn = CompNode::Node(par);
                }
                nn
            }
            );*/
        if let CompNode::Node(comp) = node {
            splay_comp(comp);
        }
        let mut n = match node.parent() {
            None => break,
            Some(ParentNode::Rake(mut par)) => {
                unsafe { par.as_mut().push(); }
                splay_rake(par);
                //unsafe { println!("{}", par.as_ref().parent().is_none()); }
                //unsafe { println!("{}", if let Some(ParentNode::Rake(_)) = par.as_ref().parent() { true } else { false }); }
                if let Some(ParentNode::Compress(n)) = unsafe { par.as_ref().parent() } {
                    n
                }
                else { unreachable!() }
            }
            Some(ParentNode::Compress(mut n)) => {
                unsafe { n.as_mut().push(); }
                unsafe {
                    if n.as_ref().guard && parent_dir_comp_guard(node).is_some() { break }
                }
                n
            }
        };
        //println!("splay_comp_n ---------------------");
        //test_comp_endpoints(CompNode::Node(n));
        splay_comp(n);
        //println!("aaa=====");
        //test_comp_endpoints(CompNode::Node(n));
        //println!("node");
        //test_comp_print(node);
        let dir = match parent_dir_comp_guard(CompNode::Node(n)) {
            Some((dir, _)) => dir,
            None => 0,
        };
        if dir == 1 {
            unsafe {
                n.as_ref().child(dir).reverse();
                n.as_ref().child(dir).push();
                node.reverse();
                node.push();
            }
        }
        if let Some((n_dir, mut rake)) = parent_dir_rake(RakeNode::Leaf(node)) {
            unsafe {
                let mut nch = n.as_mut().child(dir);
                *rake.as_mut().child_mut(n_dir) = RakeNode::Leaf(nch);
                *nch.parent_mut() = Some(ParentNode::Rake(rake));
                *n.as_mut().child_mut(dir) = node;
                *node.parent_mut() = Some(ParentNode::Compress(n));
                nch.fix();
                rake.as_mut().fix();
                node.fix();
                n.as_mut().fix();
                splay_rake(rake);
                //println!("=================2===================");
                //test_comp_endpoints(CompNode::Node(n));
            }
        }
        else {
            unsafe {
                let mut nch = n.as_mut().child(dir);
                *n.as_mut().rake_mut() = Some(RakeNode::Leaf(nch));
                *nch.parent_mut() = Some(ParentNode::Compress(n));
                *n.as_mut().child_mut(dir) = node;
                *node.parent_mut() = Some(ParentNode::Compress(n));
                nch.fix();
                node.fix();
                //println!("=================1===================");
                //test_comp_endpoints(CompNode::Node(n));
                n.as_mut().fix();
            }
        }
        if let CompNode::Leaf(_) = node {
            node = CompNode::Node(n);
        }
    }
    node
}

pub fn expose<T: Cluster>(ver: Vertex<T>) -> CompNode<T> {
    expose_raw(ver.handle().unwrap())
}

pub fn soft_expose<T: Cluster>(v: Vertex<T>, u: Vertex<T>) {
    unsafe {
        let mut root = expose(v);
        if v.handle() == u.handle() {
            if root.endpoints(1) == v || root.endpoints(0) == u {
                root.reverse();
                root.push();
            }
            return;
        }

        if root.endpoints(0) == v {
            unreachable!();
            root.reverse();
            root.push();
        }
        if root.endpoints(1) == v {
            unreachable!();
            expose(u);
        }
        else if let CompNode::Node(mut r) = root {
            r.as_mut().guard = true;
            //println!("guard ---------------");
            //test_comp_print(root);
            //test_comp_print(u.as_ref().1.unwrap());
            let soot = expose(u);
            r.as_mut().guard = false;
            r.as_mut().fix();
            if parent_dir_comp(soot).unwrap().0 == 0 {
                root.reverse();
                root.push();
            }
        }
        else {
            unreachable!()
        }
    }
}

pub fn link<T: Cluster>(v: Vertex<T>, u: Vertex<T>, weight: T) -> NonNull<Edge<T>> {
    unsafe {
        if v.handle().is_none() && u.handle().is_none() {
            Edge::new(v, u, weight)
        }
        else {
            let nnu = u.handle();
            let nnv = v.handle();
            let mut e = Edge::new(v, u, weight);
            let mut left = match nnu {
                None => {
                    CompNode::Leaf(e)
                }
                Some(uu) => {
                    let mut uu = expose_raw(uu);
                    uu.push();
                    if uu.endpoints(1) == u {
                        uu.reverse();
                        uu.push();
                    }
                    if uu.endpoints(0) == u {
                        let mut nu = Compress::new(CompNode::Leaf(e), uu);
                        *e.as_mut().parent_mut() = Some(ParentNode::Compress(nu));
                        e.as_mut().fix();
                        *uu.parent_mut() = Some(ParentNode::Compress(nu));
                        uu.fix();
                        nu.as_mut().fix();

                        CompNode::Node(nu)
                    }
                    else {
                        let mut nu = match uu {
                            CompNode::Node(nu) => nu,
                            _ => unreachable!(),
                        };
                        let mut left_ch = nu.as_ref().child(0);
                        *nu.as_mut().child_mut(0) = CompNode::Leaf(e);
                        *e.as_mut().parent_mut() = Some(ParentNode::Compress(nu));
                        e.as_mut().fix();
                        let beta = nu.as_ref().rake();
                        let mut rake = match beta {
                            Some(mut b) => {
                                let rake = Rake::new(b, RakeNode::Leaf(left_ch));
                                *b.parent_mut() = Some(ParentNode::Rake(rake));
                                *left_ch.parent_mut() = Some(ParentNode::Rake(rake));
                                left_ch.fix();
                                b.fix();
                                RakeNode::Node(rake)
                            }
                            None => {
                                RakeNode::Leaf(left_ch)
                            }
                        };
                        rake.fix();
                        *nu.as_mut().rake_mut() = Some(rake);
                        *rake.parent_mut() = Some(ParentNode::Compress(nu));
                        rake.fix();
                        nu.as_mut().fix();

                        CompNode::Node(nu)
                    }
                }
            };
            match nnv {
                None => {}
                Some(vv) => {
                    let mut vv = expose_raw(vv);
                    vv.push();
                    if vv.endpoints(0) == v {
                        vv.reverse();
                        vv.push();
                    }
                    if vv.endpoints(1) == v {
                        let mut top = Compress::new(vv, left);
                        *vv.parent_mut() = Some(ParentNode::Compress(top));
                        vv.fix();
                        *left.parent_mut() = Some(ParentNode::Compress(top));
                        left.fix();
                        top.as_mut().fix();
                    }
                    else {
                        let mut nv = match vv {
                            CompNode::Node(nv) => nv,
                            _ => unreachable!(),
                        };
                        let mut right_ch = nv.as_ref().child(1);
                        right_ch.reverse();
                        right_ch.push();
                        *nv.as_mut().child_mut(1) = left;
                        *left.parent_mut() = Some(ParentNode::Compress(nv));
                        left.fix();
                        let alpha = nv.as_ref().rake();
                        let mut rake = match alpha {
                            Some(mut a) => {
                                let mut rake = Rake::new(a, RakeNode::Leaf(right_ch));
                                *a.parent_mut() = Some(ParentNode::Rake(rake));
                                a.fix();
                                *right_ch.parent_mut() = Some(ParentNode::Rake(rake));
                                right_ch.fix();
                                rake.as_mut().fix();

                                RakeNode::Node(rake)
                            }
                            None => {
                                RakeNode::Leaf(right_ch)
                            }
                        };
                        rake.fix();
                        *nv.as_mut().rake_mut() = Some(rake);
                        *rake.parent_mut() = Some(ParentNode::Compress(nv));
                        rake.fix();
                        //test_comp_print(nv.as_ref().child(0));
                        //test_comp_print(nv.as_ref().child(1));
                        //println!("-------------");
                        nv.as_mut().fix();
                    }
                }
            }
            e
        }
    }
}

fn bring<T: Cluster>(mut root: NonNull<Compress<T>>) {
    unsafe {
        match root.as_ref().rake() {
            None => {
                let mut left = root.as_ref().child(0);
                let _ = Box::from_raw(root.as_ptr());
                *left.parent_mut() = None;
                left.fix();
            }
            Some(RakeNode::Leaf(mut new_right)) => {
                new_right.reverse();
                new_right.push();

                *root.as_mut().child_mut(1) = new_right;
                *new_right.parent_mut() = Some(ParentNode::Compress(root));

                *root.as_mut().rake_mut() = None;

                new_right.fix();
                root.as_mut().fix();
            }
            Some(RakeNode::Node(mut rake)) => {
                rake.as_mut().push();
                while let RakeNode::Node(mut right) = rake.as_ref().child(1) {
                    right.as_mut().push();
                    rake = right;
                }
                root.as_mut().guard = true;
                splay_rake(rake);
                root.as_mut().guard = false;
                let mut new_rake = rake.as_ref().child(0);
                let mut new_right = if let RakeNode::Leaf(right) = rake.as_ref().child(1) {
                    right
                }
                else { unreachable!() };

                let _ = Box::from_raw(rake.as_ptr());
                
                new_right.reverse();
                new_right.push();

                *root.as_mut().child_mut(1) = new_right;
                *new_right.parent_mut() = Some(ParentNode::Compress(root));

                *root.as_mut().rake_mut() = Some(new_rake);
                *new_rake.parent_mut() = Some(ParentNode::Compress(root));

                new_rake.fix();
                new_right.fix();
                root.as_mut().fix();
            }
        }
    }
}

pub fn cut<T: Cluster>(v: Vertex<T>, u: Vertex<T>) {
    unsafe {
        soft_expose(v, u);
        let mut root = v.handle().unwrap();
        root.push();
        if let CompNode::Node(root) = root {
            let mut right = root.as_ref().child(1);
            *right.parent_mut() = None;

            right.reverse();
            right.push();

            if let CompNode::Node(right) = right {
                if let CompNode::Leaf(e) = right.as_ref().child(1) {
                    bring(right);
                    bring(root);
                    let _ = Box::from_raw(e.as_ptr());
                }
                else { unreachable!() }
            }
            else { unreachable!() }
        }
        else { unreachable!() }
    }
}

fn select_rake<T: Cluster, F: Fn(T, T, T::V, T::V, T::V) -> usize>(mut rake: RakeNode<T>, sel: F, right: &mut (T, T::V, T::V)) -> CompNode<T> {
    unsafe {
        rake.push();
        while let RakeNode::Node(r) = rake {

            r.as_ref().child(0).push();
            r.as_ref().child(0).fix();
            r.as_ref().child(1).push();
            r.as_ref().child(1).fix();
            let (rf, r0, _r1) = (T::rake(r.as_ref().child(1).fold(), right.0.clone(), r.as_ref().child(1).endpoints(0).value(), right.1, r.as_ref().child(1).endpoints(1).value()), r.as_ref().child(1).endpoints(0).value(), r.as_ref().child(1).endpoints(1).value());
            let dir = sel(r.as_ref().child(0).fold(), rf, 
                          r.as_ref().child(0).endpoints(0).value(), r0, r.as_ref().child(0).endpoints(1).value());
            rake = r.as_ref().child(dir);
            *right = (T::rake(r.as_ref().child(1 - dir).fold(), right.0.clone(), r.as_ref().child(1 - dir).endpoints(0).value(), right.1, r.as_ref().child(1 - dir).endpoints(1).value()), r.as_ref().child(1 - dir).endpoints(0).value(), r.as_ref().child(1 - dir).endpoints(1).value());
            rake.push();
        }
        if let RakeNode::Leaf(comp) = rake { comp }
        else { unreachable!() }
    }
}

pub fn select<T: Cluster, F: Fn(T, T, T::V, T::V, T::V) -> usize>(v : Vertex<T>, sel: F) -> (Vertex<T>, Vertex<T>) {
    let mut node = expose(v);
    let mut left = None;
    let mut right = None;
    unsafe {
        node.push();
        while let CompNode::Node(n) = node {
            n.as_ref().child(0).push();
            n.as_ref().child(0).fix();
            n.as_ref().child(1).push();
            n.as_ref().child(1).fix();
            if let Some(mut r) = n.as_ref().rake() { r.push(); r.fix(); }
            let a = n.as_ref().child(0);
            let b = n.as_ref().child(1);
            let r = n.as_ref().rake();

            let (af, a0, a1) = match left.clone() {
                Some((lf, l0, l1)) => (T::compress(lf, a.fold(), l0, a.endpoints(1).value(), l1), l0, a.endpoints(1).value()),
                None => (a.fold(), a.endpoints(0).value(), a.endpoints(1).value()),
            };
            
            let (bf, b0, b1) = match right.clone() {
                Some((rf, _r0, r1)) => (T::compress(b.fold(), rf, b.endpoints(0).value(), r1, b.endpoints(1).value()), b.endpoints(0).value(), r1),
                None => (b.fold(), b.endpoints(0).value(), b.endpoints(1).value()),
            };
            let dir = sel(
                match r {
                    Some(r) => T::rake(af.clone(), r.fold(), a0, r.endpoints(0).value(), a1),
                    None => af.clone(),
                },
                bf.clone(),
                a0, b1, a1
            );
            node = if dir == 0 {
                if let Some(_) = r {
                    let mut rbf = bf.clone();
                    rbf.reverse();
                    let rb0 = b1;
                    let _rb1 = b0;
                    let (mut rf, r0, r1) = (T::rake(r.unwrap().fold(), rbf.clone(), r.unwrap().endpoints(0).value(), rb0, r.unwrap().endpoints(1).value()), r.unwrap().endpoints(0).value(), r.unwrap().endpoints(1).value());
                    let dir = sel(af.clone(), rf.clone(), a0, r0, a1);
                    if dir == 0 {
                        rf.reverse();
                        right = Some((rf, r1, r0));
                        n.as_ref().child(0)
                    }
                    else {
                        right = Some((T::rake(af, rbf, a0, rb0, a1), a0, a1));
                        let res = select_rake(n.as_ref().rake().unwrap(), &sel, right.as_mut().unwrap());
                        right = if let Some((mut rf, r0, r1)) = right.take() {
                            rf.reverse();
                            Some((rf, r1, r0))
                        }
                        else { None };
                        res
                    }
                }
                else {
                    right = Some((bf, b0, b1));
                    n.as_ref().child(0)
                }
            }
            else {
                left = match r {
                    Some(r) => Some((T::rake(af.clone(), r.fold(), a0, r.endpoints(0).value(), a1), a0, a1)),
                    None => Some((af, a0, a1)),
                };
                n.as_ref().child(1)
            };
            node.push();
        }
    }
    if let CompNode::Leaf(_) = node {
        (node.endpoints(0), node.endpoints(1))
    }
    else { unreachable!() }
}


pub fn test_comp_endpoints<T: Cluster + std::fmt::Debug>(node: CompNode<T>) where T::V: Copy + std::fmt::Debug {
    unsafe {
        //node.push();
        match node {
            CompNode::Node(n) => {
                println!("NODE {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::<Vec<_>>(), node.fold());
                println!("left");
                test_comp_endpoints(n.as_ref().child(0));
                println!("right");
                test_comp_endpoints(n.as_ref().child(1));
            }
            CompNode::Leaf(_) => {
                println!("LEAF {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::<Vec<_>>(), node.fold());
            }
        }
    }
}

pub fn test_comp_set<T: Cluster + std::fmt::Debug>(mut node: CompNode<T>) where T::V: Copy + std::fmt::Debug {
    unsafe {
        node.push();
        match node {
            CompNode::Node(n) => {
                println!("NODE {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::<Vec<_>>(), node.fold());
                println!("left");
                test_comp_print(n.as_ref().child(0));
                println!("right");
                test_comp_print(n.as_ref().child(1));
            }
            CompNode::Leaf(_) => {
                println!("LEAF {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::<Vec<_>>(), node.fold());
            }
        }
    }
}

pub fn test_comp_print<T: Cluster + std::fmt::Debug>(node: CompNode<T>) where T::V: Copy + std::fmt::Debug {
    match node {
        CompNode::Node(_) => {
            println!("NODE {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::<Vec<_>>(), node.fold());
        }
        CompNode::Leaf(_) => {
            println!("LEAF {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::<Vec<_>>(), node.fold());
        }
    }
}

#[derive(Clone, Debug)]
struct Median {
    inter_weight: usize,
    left_sum: usize,
    right_sum: usize,
    ans: usize,
    length: usize,
}

impl Median {
    fn new(l: usize) -> Self {
        Median {
            inter_weight: 0,
            ans: 0,
            left_sum: 0,
            right_sum: 0,
            length: l,
        }
    }
}

impl Cluster for Median {
    type V = usize;
    fn identity() -> Self {
        Median {
            inter_weight: 0,
            left_sum: 0,
            right_sum: 0,
            ans: 0,
            length: 0,
        }
    }
    fn compress(a: Self, b: Self, av: usize, bv: usize, cv: usize) -> Self {
        Median {
            inter_weight: a.inter_weight + b.inter_weight + cv,
            ans: a.right_sum + b.left_sum + a.length * av + b.length * bv,
            left_sum: a.left_sum + b.left_sum + a.length * (b.inter_weight + cv),
            right_sum: b.right_sum + a.right_sum + b.length * (a.inter_weight + cv),
            length: a.length + b.length,
        }
    }
    fn rake(a: Self, b: Self, _av: usize, bv: usize, _cv: usize) -> Self {
        Median {
            inter_weight: a.inter_weight + b.inter_weight + bv,
            ans: 0,
            left_sum: a.left_sum + b.right_sum + a.length * b.inter_weight + (a.length + b.length) * bv,
            right_sum: a.right_sum + b.right_sum + b.length * bv,
            length: a.length,
        }
    }
    fn reverse(&mut self) {
        std::mem::swap(&mut self.left_sum, &mut self.right_sum);
    }
}

use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let q: usize = iter.next().unwrap().parse().unwrap();
    let mut v: Vec<_> = (0..n).map(|_| Vertex::new(1)).collect();
    let mut sum = 0;
    for _ in 0..q {
        let query: usize = iter.next().unwrap().parse().unwrap();
        if query == 1 {
            let a: usize = iter.next().unwrap().parse().unwrap();
            let b: usize = iter.next().unwrap().parse().unwrap();
            let c: usize = iter.next().unwrap().parse().unwrap();
            let (a, b) = ((a - 1 + sum) % n, (b - 1 + sum) % n);
            //println!("link {} {}", a, b);
            link(v[a], v[b], Median::new(c));
        }
        else if query == 2 {
            let a: usize = iter.next().unwrap().parse().unwrap();
            let b: usize = iter.next().unwrap().parse().unwrap();
            let (a, b) = ((a - 1 + sum) % n, (b - 1 + sum) % n);
            //println!("cut {} {}", a, b);
            cut(v[a], v[b]);
        }
        else if query == 3 {
            let a: usize = iter.next().unwrap().parse().unwrap();
            let a = (a - 1 + sum) % n;
            let val = v[a].value();
            v[a].value_set(1 - val);
            let (x, y) = select(v[a], |a, b, av, bv, cv| {
                if a.inter_weight + av + cv >= b.inter_weight + bv + cv { 0 }
                else { 1 }
            });
            //println!("query 3 = {}", a);
            let ans = std::cmp::min(expose(x).fold().ans, expose(y).fold().ans);
            let ans = (0..n).filter(|i| {
                let root = expose(v[a]);
                expose(v[*i]);
                root.parent().is_some() || *i == a
            }).map(|i| expose(v[i]).fold().ans).min().unwrap();
            sum = (sum + ans % n) % n;
            println!("{}", ans);
        }
    }

}