#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int main()
{
  int n, k, q;
  cin >> n >> k >> q;  
  multiset<long long> ms, msr;
  for (int i = 0; i < n; ++i)
  {
    long long a;
    cin >> a;
    ms.insert(a);
  }
  while (ms.size() > k)
  {
    auto itr = ms.end();
    --itr;
    msr.insert(*itr);
    ms.erase(itr);
  }
  while (q--)
  {
    int t;
    cin >> t;
    if (t == 1)
    {
      int x;
      cin >> x;
      ms.insert(x);
      if (ms.size() > k)
      {
        auto itr = ms.end();
        --itr;
        long long tmp = *itr;
        ms.erase(itr);
        msr.insert(tmp);
      }
    }
    else if (t == 2)
    {
      int y;
      cin >> y;
      auto itr = ms.end();
      --itr;
      long long tmp = *itr;
      ms.erase(itr);
      if (!msr.empty() && *msr.begin() < tmp + y)
      {
        auto itrr = msr.begin();
        ms.insert(*itrr);
        msr.insert(tmp + y);
        msr.erase(itrr);
      }
      else ms.insert(tmp + y);
    }
    else if (t == 3)
    {
      long long tmp = *(--ms.end());
      cout << tmp << endl;
    }
  }
}