#include <bits/stdc++.h>
using namespace std;

void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans){


    priority_queue<pair<int , int>> pq;
    for(int i = 2; i<=n; i++){
        pq.push({w[i] , i});
    }

    int i1 , i2, p1 , p2;
    int res = 0;
//    i1 = pq.top().first;
//    p1 = pq.top().second;
//    pq.pop();
//    i2 = pq.top().first;
//    p2 = pq.top().second;
//    pq.pop();
//    res = i1 + i2 + pq.top().first;
//    pq.push({i1 , p1});
//    pq.push({i2 , p2});
//    ans[1] = res;

    for(int i = 1; i<=q; i++){
        res = 0;
        w[s[i]] = k[i];
        pq.push({k[i] , s[i]});

        while(!pq.empty() && w[pq.top().second] != pq.top().first){
            pq.pop();

        }
        i1 = pq.top().first;
        p1 = pq.top().second;
        pq.pop();
        while(!pq.empty() && w[pq.top().second] != pq.top().first){
            pq.pop();

        }
        i2 = pq.top().first;
        p2 = pq.top().second;
        pq.pop();
        while(!pq.empty() && w[pq.top().second] != pq.top().first){
            pq.pop();

        }
        res = i1 + i2 + pq.top().first;
        pq.push({i1 , p1});
        pq.push({i2 , p2});
        ans[i] = (long long)res;
    }
}