#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

    multiset<ll> ms;
    for(int i=2;i<=n;i++)ms.insert(-w[i]);
    for(int i=1;i<=q;i++){
        ms.erase(ms.find(-w[s[i]]));
        ms.insert(-k[i]);
        w[s[i]]=k[i];
        ans[i]=-(*ms.begin()+*next(ms.begin(),1)+*next(ms.begin(),2));
    }

    return;
}