import java.io.*;
import java.util.*;

// 動的木の簡略バージョン
// 木の連結と切断、頂点の重み設定、パス上の最大重み頂点クエリに、償却実行時間O(logN)で答える。
// 基本的な戦略は、実際に扱いたい木(本物の木)をいくつかのパスの集合に分割し、別の木(仮想木)の形で保持することで、平衡を保てるようにする。
public class DTree {
    // 親、左の子、右の子へのリンク。
    // (1) parent == null のとき、thisは仮想木全体の根。
    // (2) parent.left == this のとき、thisは実線部分木における左の子。
    // (3) parent.right == this のとき、thisは実線部分木における右の子。
    // (4) それ以外のとき、thisは点線で繋がれた子。
    // 実線部分木は、本物の木における下から上へのパスに対応している。
    // 実線部分木は二分探索木と同等の順序が定まっており、本物の木における下から上の順番が、実線部分木における左から右の順番である。
    // 点線は実線部分木同士を繋ぐものである。
    // 仮想木上でvの点線の親がpのとき、本物の木では、vを含む実線部分木の右端の頂点の親がpである。
    // 同時に、仮想機全体の根を含む実線部分木の右端の頂点が、本物の木における根である。
    // このため、本物の木における構造を変えないまま、以下の操作ができる。
    // (1) 実線部分木における木の回転。(rotate)またそれを使ったスプレー。(splay)
    // (2) 点線の子を、新たな左の子として設定する。(splice)
    // なお、後述するreversedフラグがtrueのときは、leftとrightは逆のものとして扱われる。
    private DTree parent, left, right;

    // 頂点に設定されるコスト。 (実際の動的木では、さらに複雑な処理を扱うため、dcostとdminが用いられる。)
    private int cost;

    // 実線部分木上でのthisの子孫のなかで、最も重いもの。
    private DTree maxchild;

    // reversedフラグを表すための変数。
    // (1) parentが実線部分木における親のとき、 dreversed == reversed ^ parent.reversed
    // (2) それ以外のとき、dreversed == reversed
    // ある頂点のdreversedフラグを反転すると、実線部分木上でその頂点の子孫全体の左右が逆転する。
    // これは本物の木における根の変更(evert)クエリのために使われる。
    private boolean dreversed;

    // 普通のコンストラクタ。
    public DTree(int cost) {
        this.cost = cost;
        this.maxchild = this;
    }

    // 実線部分木において根でないならばtrue。
    private boolean isSolidChild() {
        return parent != null && (parent.left == this || parent.right == this);
    }

    // この処理は仮想木の構造を変化させない。
    // reversedがtrueのときに呼び出すと、leftとrightを逆にして、reversedをfalseにする。
    // これによってleftとrightを正しい順序に戻すことができる。
    private void reverse() {
        DTree t=left; left=right; right=t;
        dreversed ^= true;
        if(left != null) left.dreversed ^= true;
        if(right != null) right.dreversed ^= true;
    }

    // 左右の子を更新したときに呼び出す。maxchildを更新するだけ。
    // 親への更新の伝播は行わないので、それに注意して呼び出すこと。
    private void refreshMax() {
        maxchild = this;
        if(left != null && maxchild.cost < left.maxchild.cost) maxchild=left.maxchild;
        if(right != null && maxchild.cost < right.maxchild.cost) maxchild=right.maxchild;
    }

    // 実線部分木において、木を左方向に回転させる。
    // parent.right == this のときだけ呼び出すこと。
    private void rotateLeft() {
        DTree p = parent;
        parent = p.parent; p.parent = this;
        p.right = left; left = p;
        if(p.right != null) p.right.parent = p;
        if(parent != null && parent.left == p) parent.left = this;
        if(parent != null && parent.right == p) parent.right = this;
        p.refreshMax(); refreshMax();
    }

    // 実線部分木において、木を右方向に回転させる。
    // parent.left == this のときだけ呼び出すこと。
    private void rotateRight() {
        DTree p = parent;
        parent = p.parent; p.parent = this;
        p.left = right; right = p;
        if(p.left != null) p.left.parent = p;
        if(parent != null && parent.left == p) parent.left = this;
        if(parent != null && parent.right == p) parent.right = this;
        p.refreshMax(); refreshMax();
    }

    // 実線部分木内でスプレー操作を行い、thisを実線部分木内の根に持ってくる。
    // thisから現在の実線部分木内の根へのパス上の頂点のreversedを全てfalseにしてから行うこと。
    private void splaySolid() {
        while(isSolidChild()) {
            DTree p = parent;
            if(p.left == this) {
                if(!p.isSolidChild()) {
                    rotateRight(); //zig
                } else if(p.parent.left == p) {
                    p.rotateRight(); rotateRight(); //zig-zig
                } else {
                    rotateRight(); rotateLeft(); //zig-zag
                }
            } else {
                if(!p.isSolidChild()) {
                    rotateLeft(); //zig
                } else if(p.parent.left != p) {
                    p.rotateLeft(); rotateLeft(); //zig-zig
                } else {
                    rotateLeft(); rotateRight(); //zig-zag
                }
            }
        }

    }
    // 仮想木全体でスプレー操作を行い、thisを仮想木内の根にする。
    private void splay() {
        // 1段階め。
        // まず、thisから現在の仮想木内の根までの経路上にある頂点のreversedを全てfalseにする。
        // 次に、thisから現在の仮想木内の根までの経路上にある実線部分木上でsplaySolidを行い、
        // thisから現在の仮想木内の根までの経路上に実線の辺がないようにする。
        for(DTree w = this; w != null ; w = w.parent) {
            // normalize reversed state
            boolean reversed = false;
            for(DTree x = w; ; x=x.parent) {
                reversed ^= x.dreversed;
                if(!x.isSolidChild()) break;
            }
            for(DTree x = w; ; x=x.parent) {
                if(reversed) {
                    reversed ^= x.dreversed;
                    x.reverse();
                } else {
                    reversed ^= x.dreversed;
                }
                if(!x.isSolidChild()) break;
            }
            w.splaySolid();
        }
        // 2段階め。
        // thisから現在の仮想木内の根までの経路上でsplice(実線部分木の繋ぎ替え)を行い、
        // thisと現在の根が同じ実線部分木内にあるようにする。
        for(DTree w = this; w.parent != null; w=w.parent) {
            w.parent.left = w;
            w.parent.refreshMax();
        }
        // 3段階め。splaySolidを行い、thisを仮想木内の根にする。
        splaySolid();
    }

    // thisを本物の木における新しい根とする。
    // thisをsplayして、左の子を実線から点線にすると、実線部分木がちょうどthisから本物の木における古い根までの経路になるので
    // この向きを反転すればよい。
    private void evert() {
        splay();
        left = null;
        refreshMax();
        dreversed ^= true;
    }

    // 本物の木における根までの経路上の最大値を求める。
    private DTree maxToRoot() {
        splay();
        left = null;
        refreshMax();
        return maxchild;
    }

    // thisから根に行く経路上の最初の辺を削除することで、木を2つに分割する。
    private void cutToRoot() {
        splay();
        if(right != null) right.parent = null;
        right = null;
        refreshMax();
    }

    // thisからvまでの経路上の最大値。
    public DTree maxTo(DTree v) {
        v.evert();
        return maxToRoot();
    }

    // thisとvを結ぶ辺を作ることで、木を連結する。
    // ここでは根の同一性検査はしていないので、絶対に同じ木に属する頂点をlinkしようとしないこと。
    public void linkTo(DTree v) {
        evert();
        parent = v;
    }

    // thisからvにいく経路上の最初の辺を削除することで、木を2つに分割する。
    public void cutTo(DTree v) {
        v.evert(); cutToRoot();
    }

    // 頂点のコストを再設定する。
    public void setCost(int newcost) {
        splay();
        cost = newcost;
        refreshMax();
    }

    // 頂点のコストを設定する。
    public int getCost() { return cost; }

}