std::vector< std::vector<std::pair<int,long>> > g;

std::pair<int, long> deijkstra(int start, int n, int m) {
    const int INF = 1000000000;
	std::vector<long> d(n + m + 1, INF);
	d[start] = 0;
    set < pair<int,int> > q;
	q.insert(make_pair (d[start], start));
    while (!q.empty()) {
		int v = q.begin()->second;
        q.erase(q.begin());
		for (size_t j = 0; j < g[v].size(); ++j) {
			int to = g[v][j].first,
				len = g[v][j].second;
			if (d[v] + len < d[to]) {
                q.erase (make_pair (d[to], to));
				d[to] = d[v] + len;
                p[to] = v;
                q.insert(make_pair (d[to], to));
			}
		}
	}
    int max_id = start;
    long max_val = -1;
    for (int i = 1; i <= n + m; ++i) {
        if (d[i] != INF && d[i] >= max_val) {
            max_val = d[i];
            max_id = i;
        }
    }
    return make_pair(max_id, max_val);
}

// Complete the cyclicalQueries function below.
vector<long> cyclicalQueries(vector<long> w, int m, int n) {
    // Return the list of answers to all queries of type 4. Take the query information from standard input.
    vector<long> res;
    g.resize(n + m + 1);
    for (int i = 1; i <= n; ++i) {
        int f = i, t = i + 1;
        if (f == n) t = 1;
        std::pair<int, long> p1 = std::make_pair(t, w[i-1]);
        g[f].push_back(p1);
    }
    int type, node, weight;
    int max_id = n;
    for (int i = 0; i < m; ++i) {
        cin >> type >> node;
        switch (type) {
            case 1: {
                cin >> weight;
                int good_node = deijkstra(node, n, m).first;
                max_id++;
                std::pair<int, long> p1 = std::make_pair(max_id, weight);
                g[good_node].push_back(p1);
                break;
            }
            case 2: {
                cin >> weight;
                int good_node = node;
                max_id++;
                std::pair<int, long> p1 = std::make_pair(max_id, weight);
                g[good_node].push_back(p1);
                break;
            }
            case 3: {
                int good_node = deijkstra(node, n, m).first;
                g.erase(g.begin() + good_node);
                for (size_t i = 0; i < g.size(); ++i) {
                    size_t to_del = -1;
                    for (size_t j = 0; j < g[i].size(); ++j) {
                        if (g[i][j].first == good_node) to_del = j;
                    }
                    if (to_del != -1) {
                        g[i].erase(g[i].begin() + to_del);
                    }
                }
                break;
            }
            case 4: {
                long res_t = deijkstra(node, n, m).second;
                res.push_back(res_t);
                break;
            }
            default:
                break;
        }
    }
    return res;
}