#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;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGxsIGxvbmcgbG9uZwoKaW50IG1haW4oKXsKICAgIGxsIG4gLCBxOwogICAgY2luPj5uPj5xOwoKICAgIHZlY3RvcjxsbD4gdmVjKG4pOwogICAgbXVsdGlzZXQ8bGw+IHN0OwogICAgbGwgc3VtID0gMCAsIHMgPSAwOwogICAgZm9yKGludCBpPTA7aTxuO2krKyl7CiAgICAgICAgY2luPj52ZWNbaV07CiAgICAgICAgc3QuaW5zZXJ0KHZlY1tpXSk7CiAgICAgICAgc3VtICs9IHZlY1tpXTsKICAgIH0KCiAgICB3aGlsZShxLS0pewogICAgICAgIGxsIHQ7CiAgICAgICAgY2luPj50OwoKICAgICAgICBpZih0ID09IDEpewogICAgICAgICAgICBsbCB5OwogICAgICAgICAgICBjaW4+Pnk7CiAgICAgICAgICAgIHMgKz0geTsKICAgICAgICB9CiAgICAgICAgZWxzZSBpZih0ID09IDIpewogICAgICAgICAgICBsbCB5OwogICAgICAgICAgICBjaW4+Pnk7CiAgICAgICAgICAgIHN0Lmluc2VydCh5ICsgcyk7CiAgICAgICAgICAgIHN1bSArPSB5ICsgczsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgbGwgYW5zID0gc3VtICwgczEgPSAwICwgYyA9IDA7CiAgICAgICAgICAgIHZlY3RvcjxsbD4gdjsKICAgICAgICAgICAgZm9yKGF1dG8geCA6IHN0KXsKICAgICAgICAgICAgICAgIGlmKHggPiBzKSBicmVhazsKICAgICAgICAgICAgICAgIHYucHVzaF9iYWNrKHgpICwgczEgKz0geCAsIGMrKzsKICAgICAgICAgICAgfQogICAgICAgICAgICBsbCBzeiA9IHN0LnNpemUoKTsKICAgICAgICAgICAgZm9yKGludCBpPTA7aTx2LnNpemUoKTtpKyspewogICAgICAgICAgICAgICAgc3QuZXJhc2UodltpXSk7CiAgICAgICAgICAgICAgICBzdW0gLT0gdltpXTsKICAgICAgICAgICAgfQogICAgICAgICAgICBhbnMgLT0gczE7CiAgICAgICAgICAgIGFucyAtPSAoc3ogLSBjKSAqIHM7CiAgICAgICAgICAgIGNvdXQgPDwgYW5zIDw8IGVuZGw7CiAgICAgICAgfQogICAgfQpyZXR1cm4gMDsKfQ==