/*
左偏树构成的森林实现
        支持如下操作：

1. 用一个数值构建一个新的左偏树堆 make_new_heap(val), 返回新建节点的id号
2. 合并id1元素所在的左偏树和id2元素所在的左偏树 merge(id1, id2)，返回新的左偏树的根的id号
3. 将新数值val放入编号为id的数值存在的左偏树 put(id, val)，返回数值是val的新节点的id号
4. 查询id号元素所在堆的堆顶元素的数值 get_top_val(id), 返回堆顶元素(id, val)二元组
5. 将id号所在的堆的堆顶元素从堆上删除，pop_top_val(id), 返回堆顶元素(id, val)二元组
6. 直接通过节点的id号获取数值 get_val(id)

注意：
所有id都由左偏树数据结构自己内部生成，外部只能获取，不能自己任意创建id号
0号节点表示无效的含义，所有有效节点的id号都大于等于1
        id = 0的节点所在的堆代表空堆

代码模板以 2714. 左偏树 题目为蓝本

输入数据格式

1 a，在集合中插入一个新堆，堆中只包含一个数 a。
2 x y，将第 x 个插入的数和第 y 个插入的数所在的小根堆合并。数据保证两个数均未被删除。若两数已在同一堆中，则忽略此操作。
3 x，输出第 x 个插入的数所在小根堆的最小值。数据保证该数未被删除。
4 x，删除第 x 个插入的数所在小根堆的最小值（若最小值不唯一，则优先删除先插入的数）。数据保证该数未被删除。

*/


#include <stdio.h>
#include <algorithm>
using namespace std;

const int MAX_NODE_NUN = 200100;


int ll[MAX_NODE_NUN];       // 左指针
int rr[MAX_NODE_NUN];       // 右指针
int val[MAX_NODE_NUN];      // 实际问题里面节点数值不一定就是int类型，实际使用的时候根据具体情况做修改, 和模板参数T对应即可，需要T类型实现小于运算符
int dis[MAX_NODE_NUN];      // 节点的距离
int pp[MAX_NODE_NUN];       // 并查集数组
int __buffer[MAX_NODE_NUN]; // 缓存，并查集操作时候使用
int __pool_pos = 1;         // 当前对象池的末尾


template<typename T>
class LeftistHeapForest {
    // 获取并查集中的root id
    int __get_union_find_root(int node) {
        int pos = 0;
        int p = node;
        while (p != pp[p]) {
            __buffer[pos++] = p;
            p = pp[p];
        }

        for (int i = 0; i < pos; i++) {
            pp[__buffer[i]] = p;
        }
        return p;
    }

    // 是否在同一个并查集中
    bool __in_same_union_find(int id1, int id2) {
        return __get_union_find_root(id1) == __get_union_find_root(id2);
    }

    // 并查集合并
    void __merge_union_find(int id1, int id2) {
        pp[__get_union_find_root(id1)] = __get_union_find_root(id2);
    }

    // 并查集修改根id
    void __change_union_find_root_id(int id) {
        pp[__get_union_find_root(id)] = id;
        pp[id] = id;
    }

    // 合并根是id1和根是id2的两个堆, 返回新堆的堆顶节点的id号
    int __merge(int id1, int id2) {
        if (id1 == 0 || id2 == 0) {
            return id1 + id2;
        }

        T val1 = val[id1], val2 = val[id2];
        if (val2 < val1 || (val1 == val2 && id2 < id1)) {
            id1 = id1 ^ id2, id2 = id1 ^ id2, id1 = id1 ^ id2;
        }

        int new_root_id = __merge(rr[id1], id2);
        rr[id1] = new_root_id;
        dis[id1] = dis[new_root_id] + 1;

        int l_id = ll[id1], r_id = rr[id1];
        if (dis[r_id] > dis[l_id]) {
            ll[id1] = r_id, rr[id1] = l_id;
        }

        return id1;
    }

public:

    // 用数值v创建新堆, 返回新创建的节点的id
    int make_new_heap(T v) {
        int id = __pool_pos++;
        ll[id] = rr[id] = dis[id] = 0;
        val[id] = v;
        pp[id] = id;
        return id;
    }

    // 合并id1所在的堆和id2所在的堆, 返回新的堆的堆顶元素的id
    int merge(int id1, int id2) {
        if (id1 == 0 || id2 == 0) {
            return __get_union_find_root(id1 + id2);
        }

        if (__in_same_union_find(id1, id2)) {
            return __get_union_find_root(id1);
        }

        int new_root_id = __merge(__get_union_find_root(id1), __get_union_find_root(id2));
        __merge_union_find(id1, id2);                   // 两棵树在并查集里面合并在一起
        __change_union_find_root_id(new_root_id);       // 新的根所在的并查集的根换成这个新根自己

        return new_root_id;
    }

    // 将新数值val放入编号为id的节点存在的左偏树, 返回新节点id号
    int put(int id, T val) {
        int new_id = make_new_heap(val);
        merge(new_id, id);
        return new_id;
    }

    // 获取编号是id的节点所在堆的堆顶的元素(堆顶id, 堆顶val)
    pair<int, T> get_top_val(int id) {
        int top_id = __get_union_find_root(id);
        return pair<int, T>{top_id, val[top_id]};
    }

    // 将id号所在的堆的堆顶元素从堆上删除, 返回堆顶的元素(堆顶id, 堆顶val)
    pair<int, T> pop_top_val(int id) {
        int top_id = __get_union_find_root(id);
        int new_root_id = __merge(ll[top_id], rr[top_id]);
        __change_union_find_root_id(new_root_id);
        return pair<int, T>{top_id, val[top_id]};
    }
};

int main() {
    //freopen("/Users/grh/Programming/CLionProjects/SimpleTest/input.txt", "r", stdin);

    LeftistHeapForest<int> algo;

    int n, op;
    int a, b;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &op);
        switch(op) {
            case 1:
                scanf("%d", &a);
                algo.make_new_heap(a);
                break;
            case 2:
                scanf("%d %d", &a, &b);
                algo.merge(a, b);
                break;
            case 3:
                scanf("%d", &a);
                printf("%d\n", algo.get_top_val(a).second);
                break;
            case 4:
                scanf("%d", &a);
                algo.pop_top_val(a);
                break;

            default:
                break;
        }
    }

    return 0;
}