Untitled

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tt, tc;

const int MAXA = 2e6 + 9;
const int DELTA = 1e6;

bool maxval;
struct Line {
    ll m, c;
    Line() {}
    Line(ll m, ll c) : m(m), c(c) {}
    ll evaluate(ll x) {
        return (m * x + c) * (maxval ? -1 : 1);
    }
};
struct Node {
    Line top;
    int left = -1, right = -1;
    Node() {}
    Node(ll m, ll c) : top(Line(m,c)) {}
    Node (Line curr) : top(curr) {}
    ll evaluate(ll x) {
        return top.evaluate(x);
    }
};
vector<Node> Tree;
const ll INF = 1e18;

vector<vector<pair<int, Line>>> st;


void addline(Line toadd, ll l, ll r, int idx) {
    ll mid = (l+r)/2;
    Line& top = Tree[idx].top;
    if (top.evaluate(mid) > toadd.evaluate(mid)) {
        st.back().emplace_back(idx, top);
        swap(top, toadd);
    }
    if (r-l <= 1) return;
    if (top.evaluate(l) > toadd.evaluate(l)) {
        if (Tree[idx].left == -1) {
            Tree[idx].left = Tree.size();
            Tree.emplace_back(top);
        }
        addline(toadd,l,mid,Tree[idx].left);
    }
    else{
        if (Tree[idx].right == -1) {
            Tree[idx].right = Tree.size();
            Tree.emplace_back(top);
        }
        addline(toadd,mid,r,Tree[idx].right);
    }
}

void addline(ll m,ll c) {
    addline(Line(m,c), 0, MAXA + 1, 0);
}

ll query(ll x,ll l,ll r,int idx) {
    if (idx==-1) return INF;
    if (x<l || x>=r) return Tree[idx].evaluate(x);
    if (r-l <= 1) return Tree[idx].evaluate(x);
    ll mid = (l+r)/2;
    return min({Tree[idx].evaluate(x), query(x,l,mid,Tree[idx].left), query(x,mid,r,Tree[idx].right)});
}

ll query(ll x) {
    return min(Tree[0].evaluate(x), query(x,0,MAXA+1,0)) * (maxval ? -1 : 1);
}

void clear() {
    Tree.clear();
    Tree.emplace_back(0,INF * (maxval ? -1 : 1));
}

void roll_back() {
    auto V = st.back();
    st.pop_back();

    reverse(V.begin(), V.end());
    for (auto& [v, X] : V) {
        swap(Tree[v].top, X);
    }
}

void solve() {
    maxval = 1;
    clear();

	int n = 1;
    int index = 0;
    vector<vector<int>> g(n);
    vector<ll> X(n), Y(n);

    vector<pair<int, ll>> ask; // first is vertex, second is value
    int q;
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            cin >> index;
        } else if (type == 2) {
            ll XX, YY;
            cin >> XX >> YY;
            int new_index;
            cin >> new_index;
            g[index].push_back(new_index);
            X.push_back(XX);
            Y.push_back(YY);
            n++;
            g.push_back(vector<int>());
            index = new_index;
        } else {
            ll V;
            cin >> V;
            ask.emplace_back(index, V);
        }
    }

    vector<vector<int>> queries(n);
    q = ask.size();
    vector<ll> query_ans(q);

    for (int i = 0; i < q; i++) {
        queries[ask[i].first].push_back(i);
    }

    function<void(int)> dfs = [&](int v) {
        st.push_back(vector<pair<int, Line>>());
        addline(X[v], Y[v]);

        for (int quer : queries[v]) query_ans[quer] = query(ask[quer].second);

        for (int u : g[v]) dfs(u);

        roll_back();
    };
    for (ll val : query_ans) cout << val << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	tt = 1, tc = 1;
	// cin >> tt;
	while (tt--) {
		solve();
		tc++;
	}
}