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

struct Node{
    int64_t max1;
    int64_t max2;
    int64_t max3;
};
/*
6 3
0
1
1
1
1
1
0
1
1
1
1
1
6 1 3
2 2 2

6 3
0
5
5
5
1
5
0
1
1
1
1
1
5 1 3
2 2 2
*/
class SegmentTree{
  private:
    vector<Node> tree;
    int64_t s;
    Node NEUTRAL = {INT_MIN, INT_MIN, INT_MIN};
    Node Merge(Node A, Node B){
        vector<int64_t> v = {A.max1, A.max2, A.max3, B.max1, B.max2, B.max3};
        sort(v.begin(), v.end());
        return {v[5], v[4], v[3]};
    }
    void changeHelper(int64_t i, int64_t val, int64_t curL, int64_t curR, int64_t curI){
        if(curL==curR) {
            tree[curI].max1 = val;
            return;
        }
        int64_t mid = (curL + curR)/2;
        if(i<=mid) changeHelper(i, val, curL, mid, curI*2);
        else if(i>mid) changeHelper(i, val, mid+1, curR, curI*2 + 1);
        tree[curI] = Merge(tree[curI*2], tree[curI*2+1]);
    }
  public:
    SegmentTree(vector<int64_t>& v){
        s = pow(2, ceil(log2(v.size())));
        tree = vector<Node>(2*s+5, NEUTRAL);
        for(int64_t i = 0; i<v.size();i++){
            tree[i+s] = {v[i], INT_MIN, INT_MIN};
        }
        for(int64_t i=s-1;i>=1;i--){
            tree[i] = Merge(tree[i*2], tree[i*2+1]);
        }
    }
    void change(int64_t i, int64_t val){
        changeHelper(i, val, 0, s-1, 1);
    }
    long long query(){
        if(tree[1].max3 == INT_MIN) return 10/0;
        return static_cast<long long>(tree[1].max1) + static_cast<long long>(tree[1].max2) + static_cast<long long>(tree[1].max3);
    }
};
void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans){
    int a = 2;
    int b = 3;
    int root = 0;
    if(p[a]==p[b]) root = p[a];
    else{
        if(p[a]==b) root = b;
        else root = a;
    }
    vector<int64_t> tezine(n+1);
    for(int64_t i=1;i<=n;i++){
        if(i==root) tezine[i] = INT_MIN;
        else if(i==1) tezine[i] = tezine[root];
        else tezine[i] = w[i];
    }
    SegmentTree st(tezine);
    for(int64_t i=1;i<=q;i++){
        int64_t ki = s[i];
        if(ki==root && ki!=1) ki = p[ki];
        if(ki!=1)st.change(ki, k[i]);
        ans[i] = st.query();
    }
}