Enunț

Cu ocazia sărbătoririi marii victorii de la ONI2017, cei 10 Bistrițeni au pornit la drum cu scopul de a-și întemeia o țară. După multe dezbateri, aceștia s-au hotărât să o numească Zoomba. Și au mers ei ce au mers, până au ajuns într-un ținut pustiu, iar atunci, marele Zoli a spus: “Și aici să fie întemeiată Zoomba!” (La început, Zoomba nu are niciun oraș). Iulia are sarcina de a construi orașele, iar Maria va construi drumurile ce vor conecta orașele. Astfel, se disting următoarele evenimente:

• 1: Iulia construiește un nou oraș. Dacă ultimul oraș construit este orașul x, atunci noul oraș va fi x + 1 (Dacă nu există niciun oraș în acel moment, atunci noul oraș construit va fi 1).
• 2 x y c: Maria propune construcția unui drum bidirecțional ce leagă orașul x de orașul y de cost c.
• 3 x: Zoli se întreabă care este costul minim pentru a lega un număr maxim de orașe (folosind drumurile propuse de Maria) cu scopul construirii unui județ (un județ este o grupare de orașe în care se poate ajunge din orice oraș în orice alt oraș) ce conține orașul x.

Cerința

Scrieți un program care procesează M evenimente de tipurile precizate mai sus, și afișează în fișierul de ieșire rezultatele evenimentelor de tipul 3.

Date de intrare

Fișierul de intrare episodul1.in conține pe prima linie numărul M, iar pe fiecare linie din cele M, se va afla câte un eveniment, cu formatul specificat mai sus.

Date de ieșire

Fișierul de ieșire episodul1.out va conține pe fiecare linie câte un număr, reprezentând răspunsurile operațiilor de tip 3, în ordiea în care acestea apar în fișierul de intrare.

Restricții și precizări

• 1 ≤ M ≤ 1.000.000
• Pentru orice operație de tip 2, C este maxim până în punctul respectiv.
• Costul unui drum nu depășește 100.000.000
• InParser
• OutParser

Exemplu

episodul1.in

14
1
1
3 1
3 2
2 1 2 1
3 2
1
2 1 3 1
3 1
1
1
2 3 4 3
3 4
3 5

episodul1.out

0
0
1
2
5
0

#include <bits/stdc++.h>
#include <stdio.h>
#include <ctype.h>

using namespace std;

class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

class OutParser {
private:
    FILE *fout;
    char *buff;
    int sp;

    void write_ch(char ch) {
        if (sp == 50000) {
            fwrite(buff, 1, 50000, fout);
            sp = 0;
            buff[sp++] = ch;
        } else {
            buff[sp++] = ch;
        }
    }


public:
    OutParser(const char* name) {
        fout = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout);
        fclose(fout);
    }

    OutParser& operator << (int vu32) {
        if (vu32 <= 9) {
            write_ch(vu32 + '0');
        } else {
            (*this) << (vu32 / 10);
            write_ch(vu32 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (long long vu64) {
        if (vu64 <= 9) {
            write_ch(vu64 + '0');
        } else {
            (*this) << (vu64 / 10);
            write_ch(vu64 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (char ch) {
        write_ch(ch);
        return *this;
    }
    OutParser& operator << (const char *ch) {
        while (*ch) {
            write_ch(*ch);
            ++ch;
        }
        return *this;
    }
};

InParser cin("episodul1.in");
OutParser cout("episodul1.out");

struct muchie
{
    int i , j , c;
};
int T[1000001] , n , cer , m , t;
long long C[1000001];

void leaga(int a , int b , int c)
{
    if(T[a] > T[b]) T[a] = T[b] , C[b] = C[a] + C[b] +  c;
    else T[b] = T[a] , C[a] = C[a] + C[b] + c;
}

int radacina(int a)
{
    if(a == T[a]) return a;
    else return T[a] = radacina(T[a]);
}
int main()
{
    cin >> m;
    int x , y , c;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> cer;
        if(cer == 1) n++ , T[n] = n;
        else if(cer == 2)
        {
            cin >> x >> y >> c;
            int r1 , r2;
            r1 = radacina(x);
            r2 = radacina(y);
            if(r1 != r2)
            {
                t += c;
                leaga(r1 , r2 , c);
            }
        }
        else
        {
            cin >> x;
            cout << C[radacina(x)] << '\n';
        }
    }
}