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

const int N = 5e3 + 5;
void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans){
    multiset<int> st;
    for (int i = 2; i <= n; ++i)    st.insert(w[i]);
    for (int i = 1; i <= q; ++i) {
        st.erase(st.find(w[s[i]]));
        st.insert(k[i]);
        w[s[i]] = k[i];
        auto it = st.rbegin();
        for (int j = 1; j <= 3; ++j) {
            ans[i] += *it;
            if (j != 3) it++;
        }
    }
    return;
}
/*
4 2
0 1 1 1
0 1 2 3
2 3
10 20
*/