#include <iostream>
#include <queue>
#include <random>
#pragma region // inclusion and optimization
#ifdef IS_TEST
const bool IS_TEST_ENVIROMENT = true;
#else
const bool IS_TEST_ENVIROMENT = false;
#endif
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma endregion // inclusion and optimization

#include <bits/stdc++.h>
#pragma region // comavius::competitive library

namespace comavius::competitive { // typedefs

#pragma region // long long
typedef long long ll;
typedef std::vector<ll> vll;
typedef std::vector<vll> vvll;
typedef std::vector<vvll> vvvll;
typedef std::map<ll, ll> mll;
typedef std::map<ll, mll> mmll;
typedef std::pair<ll, ll> pll;
typedef std::vector<pll> vpll;
#pragma endregion // long long

#pragma region // long double
typedef long double ld;
typedef std::vector<ld> vld;
typedef std::vector<vld> vvld;
typedef std::vector<vvld> vvvld;
#pragma endregion // long double

#pragma region // std::string
typedef std::string str;
typedef std::vector<str> vstr;
typedef std::vector<vstr> vvstr;
typedef std::vector<vvstr> vvvstr;
#pragma endregion // std::string

#pragma region // bool
typedef std::vector<bool> vb;
typedef std::vector<vb> vvb;
typedef std::vector<vvb> vvvb;
#pragma endregion // bool

#pragma region // char
typedef std::vector<char> vc;
typedef std::vector<vc> vvc;
typedef std::vector<vvc> vvvc;
#pragma endregion // char

#pragma region // container of std
#pragma region // std::vector
template <typename T> using vec = std::vector<T>;
template <typename T> using vec2 = std::vector<std::vector<T>>;
template <typename T> using vec3 = std::vector<std::vector<std::vector<T>>>;
template <typename T>
using vec4 = std::vector<std::vector<std::vector<std::vector<T>>>>;
template <typename T>
using vec5 = std::vector<std::vector<std::vector<std::vector<std::vector<T>>>>>;
template <typename T>
using vec6 = std::vector<
    std::vector<std::vector<std::vector<std::vector<std::vector<T>>>>>>;
template <typename T>
using vec7 = std::vector<std::vector<
    std::vector<std::vector<std::vector<std::vector<std::vector<T>>>>>>>;
#pragma endregion // std::vector
#pragma endregion // container of std

} // namespace comavius::competitive

namespace comavius::competitive { // UnionFind

class UnionFind {
  std::vector<long long> parent;
  std::vector<long long> rank;
  std::vector<long long> size;
  std::vector<long long> edge_count;

public:
  UnionFind(long long num_nodes) {
    parent.resize(num_nodes, -1);
    rank.resize(num_nodes, 0);
    size.resize(num_nodes, 1);
    edge_count.resize(num_nodes, 0);
  }

  long long root_of(long long x) {
    if (parent[x] == -1) {
      return x;
    } else {
      return parent[x] = root_of(parent[x]);
    }
  }

  void unite(long long x, long long y) {
    long long rx = root_of(x);
    long long ry = root_of(y);
    if (rx == ry) {
      edge_count[rx]++;
      return;
    } else if (rank[rx] < rank[ry]) {
      parent[rx] = ry;
      size[ry] += size[rx];
      edge_count[ry] += edge_count[rx] + 1;
    } else {
      parent[ry] = rx;
      size[rx] += size[ry];
      if (rank[rx] == rank[ry])
        rank[rx]++;
      edge_count[rx] += edge_count[ry] + 1;
    }
    return;
  }

  bool is_same(long long x, long long y) { return root_of(x) == root_of(y); }

  long long size_of(long long x) { return size[root_of(x)]; }
  bool is_cycle(long long x) {
    return edge_count[root_of(x)] >= size[root_of(x)];
  }
};
} // namespace comavius::competitive

namespace comavius::competitive { // get_primes

std::vector<long long> get_primes(long long n) {
  std::vector<bool> is_prime(n + 1, true);
  std::vector<long long> primes;
  is_prime[0] = false;
  is_prime[1] = false;
  for (long long i = 2; i <= n; i++) {
    if (is_prime[i]) {
      primes.push_back(i);
      for (long long j = 2 * i; j <= n; j += i) {
        is_prime[j] = false;
      }
    }
  }
  return primes;
}
} // namespace comavius::competitive

namespace comavius::competitive { // fast pow (repeated squaring)

template <typename T> T fast_pow(T base, T neutral, long long exponent) {
  T ans = neutral;
  while (exponent > 0) {
    if (exponent % 2 == 1) {
      ans = ans * base;
    }
    base = base * base;
    exponent /= 2;
  }
  return ans;
}
} // namespace comavius::competitive

namespace comavius::competitive { // chmax/chmin

template <typename T> void chmax(T &a, T b) { a = std::max(a, b); }

template <typename T> void chmin(T &a, T b) { a = std::min(a, b); }

} // namespace comavius::competitive

namespace comavius::competitive { // Print(stdout, stderr)
template <typename T>
concept natively_printable = requires(T t) {
  { std::cout << t } -> std::same_as<std::ostream &>;
};
template <typename IteratableT, typename ElementT>
concept iteratable = requires(IteratableT t) {
  { t.begin() } -> std::same_as<typename IteratableT::iterator>;
  { t.end() } -> std::same_as<typename IteratableT::iterator>;
  { *t.begin() } -> std::same_as<ElementT>;
};
template <natively_printable T>
void internal_print(std::ostream &stream, T &s) {
  stream << s;
}
template <natively_printable ElementT, iteratable<ElementT> T>
void internal_print(std::ostream &stream, T &s) {
  for (auto it = s.begin(); it != s.end(); ++it) {
    if (it != s.begin())
      stream << " ";
    internal_print(stream, *it);
  }
}
template <typename GrandChildElementT, iteratable<GrandChildElementT> ChildT,
          iteratable<ChildT> T>
void internal_print(std::ostream &stream, T &s) {
  for (auto it = s.begin(); it != s.end(); ++it) {
    if (it != s.begin())
      stream << "\n";
    internal_print(stream, *it);
  }
}

// color enum-class
enum class Color { GREEN, RED, DEFAULT };

// ansi code color
std::string get_ansi_color(Color color) {
  if (IS_TEST_ENVIROMENT) {
    std::string ansi_code;
    switch (color) {
    case Color::RED:
      ansi_code = "\033[31m\033[1m";
      break;
    case Color::GREEN:
      ansi_code = "\033[32m\033[1m";
      break;
    case Color::DEFAULT:
      ansi_code = "\033[0m";
      break;
    }
    return ansi_code;
  } else {
    return "";
  }
}

template <typename T> void println(T t) {
  internal_print(std::cout, t);
  std::cout << "\n";
}
template <typename T> void println(T begin, T end) {
  print(begin, end);
  std::cout << "\n";
}
// yes or no
void yneos(bool a) {
  if (a) {
    println("Yes");
  } else {
    println("No");
  }
}
#pragma endregion // Print to stdout

#pragma region // ePrint to stderr
// default color(Color::CYAN)
template <typename T> void errprint(T t) {
  if (IS_TEST_ENVIROMENT) {
    std::cerr << get_ansi_color(Color::RED) << generate_string(t)
              << get_ansi_color(Color::DEFAULT);
  }
}
// set color
template <typename T> void errprint(T t, Color color) {
  if (IS_TEST_ENVIROMENT) {
    std::cerr << get_ansi_color(color) << generate_string(t)
              << get_ansi_color(Color::DEFAULT);
  }
}
// print"ln"
template <typename T> void errprintln(T t) {
  if (IS_TEST_ENVIROMENT) {
    errprint(t);
    std::cerr << "\n";
  }
}
template <typename T> void errprintln(T t, Color color) {
  if (IS_TEST_ENVIROMENT) {
    errprint(t, color);
    std::cerr << "\n";
  }
}
// print"ln" with iterator range
template <typename T> void errprintln(T begin, T end) {
  if (IS_TEST_ENVIROMENT) {
    errprint(begin, end);
    std::cerr << "\n";
  }
}
template <typename T> void errprintln(T begin, T end, Color color) {
  if (IS_TEST_ENVIROMENT) {
    errprint(begin, end, color);
    std::cerr << "\n";
  }
}
#pragma endregion // ePrint to stderr

} // namespace comavius::competitive

namespace comavius::competitive { // initial settings
void initial_settings() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout << std::setprecision(15);
  std::cerr << std::setprecision(15);
}
} // namespace comavius::competitive

#pragma region // Read macro
#define GET_1_ARG(TYPE, ARG)                                                   \
  ;                                                                            \
  TYPE ARG;                                                                    \
  std::cin >> ARG;
#define GET_2_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_1_ARG(TYPE, __VA_ARGS__)
#define GET_3_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_2_ARG(TYPE, __VA_ARGS__)
#define GET_4_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_3_ARG(TYPE, __VA_ARGS__)
#define GET_5_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_4_ARG(TYPE, __VA_ARGS__)
#define GET_6_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_5_ARG(TYPE, __VA_ARGS__)
#define GET_7_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_6_ARG(TYPE, __VA_ARGS__)
#define GET_8_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_7_ARG(TYPE, __VA_ARGS__)
#define GET_9_ARG(TYPE, ARG, ...)                                              \
  GET_1_ARG(TYPE, ARG) GET_8_ARG(TYPE, __VA_ARGS__)
#define GET_10_ARG(TYPE, ARG, ...)                                             \
  GET_1_ARG(TYPE, ARG) GET_9_ARG(TYPE, __VA_ARGS__)

#define GET_MACRO(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, NAME, ...) NAME
#define read(TYPE, ...)                                                        \
  GET_MACRO(__VA_ARGS__, GET_10_ARG, GET_9_ARG, GET_8_ARG, GET_7_ARG,          \
            GET_6_ARG, GET_5_ARG, GET_4_ARG, GET_3_ARG, GET_2_ARG,             \
            GET_1_ARG)(TYPE, __VA_ARGS__)

#define readv(TYPE, NAME, SIZE)                                                \
  std::vector<TYPE> NAME(SIZE);                                                \
  for (long long i = 0; i < SIZE; i++)                                         \
    std::cin >> NAME[i];
#define readvv(TYPE, NAME, H, W)                                               \
  std::vector<std::vector<TYPE>> NAME(H, std::vector<TYPE>(W));                \
  for (long long i = 0; i < H; i++)                                            \
    for (long long j = 0; j < W; j++)                                          \
      std::cin >> NAME[i][j];
#pragma endregion // Read macro

#pragma region // Other macro
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, start, goal, diff) for (ll i = start; i != goal; i += diff)
#define all(a) a.begin(), a.end()
//    #define chmax(a, b) a = std::max(a, b)
//    #define chmin(a, b) a = std::min(a, b)
#pragma endregion // Other macro

#pragma region // namespace expansion
using namespace std;
using namespace comavius::competitive;
#pragma endregion // namespace expansion

#pragma endregion // comavius::competitive library

int main() {
  read(ll, n, k, q);
  readv(ll, a, n);
  priority_queue<ll> pql;
  priority_queue<ll, vll, greater<ll>> pqr;
  rep(i, n) { pql.push(a[i]); }
  rep(i, n - k) {
    pqr.push(pql.top());
    pql.pop();
  }
  rep(qi, q) {
    read(ll, t);
    if (t == 1) {
      read(ll, x);
      pql.push(x);
      pqr.push(pql.top());
      pql.pop();
    } else if (t == 2) {
      read(ll, y);
      ll kth = pql.top();
      pql.pop();
      pqr.push(kth + y);
      pql.push(pqr.top());
      pqr.pop();
    } else {
      ll kth = pql.top();
      cout << kth << "\n";
    }
  }
}