/* -*- coding: utf-8 -*- * * 3298.cc: No.3298 K-th Slime - yukicoder */ #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; /* typedef */ using ll = long long; using mslg = multiset>; using msl = multiset; /* global variables */ ll as[MAX_N]; /* subroutines */ /* main */ int main() { int n, k, qn; scanf("%d%d%d", &n, &k, &qn); for (int i = 0; i < n; i++) scanf("%lld", as + i); sort(as, as + n); mslg ss0(as, as + k); msl ss1(as + k, as + n); while (qn--) { int op; scanf("%d", &op); if (op == 1) { int x; scanf("%d", &x); if (x < *ss0.begin()) { ss0.insert(x); ss1.insert(*ss0.begin()); ss0.erase(ss0.begin()); } else { ss1.insert(x); } } else if (op == 2) { int y; scanf("%d", &y); ll sk = *ss0.begin(); ss0.erase(ss0.begin()); ss1.insert(sk + y); sk = *ss1.begin(); ss1.erase(ss1.begin()); ss0.insert(sk); } else { printf("%lld\n", *ss0.begin()); } } return 0; }