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

#define ll long long

int main(){
    ll n , q;
    cin>>n>>q;

    vector<ll> vec(n);
    multiset<ll> st;
    ll sum = 0 , s = 0;
    for(int i=0;i<n;i++){
        cin>>vec[i];
        st.insert(vec[i]);
        sum += vec[i];
    }

    while(q--){
        ll t;
        cin>>t;

        if(t == 1){
            ll y;
            cin>>y;
            s += y;
        }
        else if(t == 2){
            ll y;
            cin>>y;
            st.insert(y + s);
            sum += y + s;
        }
        else{
            ll ans = sum , s1 = 0 , c = 0;
            vector<ll> v;
            for(auto x : st){
                if(x > s) break;
                v.push_back(x) , s1 += x , c++;
            }
            ll sz = st.size();
            for(int i=0;i<v.size();i++){
                st.erase(v[i]);
                sum -= v[i];
            }
            ans -= s1;
            ans -= (sz - c) * s;
            cout << ans << endl;
        }
    }
return 0;
}