#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include #ifdef DEBUG # include # include #endif namespace tomolatoon { using namespace std::views; using std::cin; using std::cout; using std::endl; using std::array; using std::deque; using std::map; using std::multimap; using std::multiset; using std::pair; using std::queue; using std::set; using std::span; using std::stack; using std::string; using std::string_view; using std::tuple; using std::vector; using std::ranges::subrange; template using vec = vector; using uint = uint32_t; using ull = uint64_t; using ll = int64_t; // clang-format off using std::ranges::all_of; using std::ranges::any_of; using std::ranges::none_of; using std::ranges::for_each; using std::ranges::for_each_n; using std::ranges::find; using std::ranges::find_if; using std::ranges::find_if_not; using std::ranges::find_end; using std::ranges::find_first_of; using std::ranges::adjacent_find; using std::ranges::count; using std::ranges::count_if; using std::ranges::mismatch; using std::ranges::equal; using std::ranges::search; using std::ranges::search_n; // clang-format on using std::ranges::sort; using std::ranges::stable_sort; using std::ranges::unique; using std::ranges::max_element; using std::ranges::min_element; using std::ranges::binary_search; using std::ranges::equal_range; using std::ranges::lower_bound; using std::ranges::upper_bound; using std::ranges::next_permutation; using std::ranges::prev_permutation; using std::ranges::begin; using std::ranges::distance; using std::ranges::end; using std::ranges::ssize; using std::ranges::swap; // for (auto i : iota(0, n)) を使う namespace rng = std::ranges; using std::back_inserter; using std::front_inserter; using std::inserter; using namespace std::placeholders; void yn(bool f) { cout << (f ? "Yes" : "No") << endl; } string yns(bool f) { return f ? "Yes" : "No"; } struct P { using type = ll; type i; type j; P moved(type id, type jd) const { return {i + id, j + jd}; } P moved(P pd) const { return moved(pd.i, pd.j); } template T& operator[](vec>& v) const { return v[i][j]; } char& operator[](vec& v) const { return v[i][j]; } friend bool operator==(const P& lhs, const P& rhs) { return lhs.i == rhs.i && lhs.j == rhs.j; } friend auto operator<=>(const P& lhs, const P& rhs) { return lhs.i != rhs.i ? lhs.i <=> rhs.i : lhs.j <=> rhs.j; } }; // clang-format off auto in_f = [](P::type h, P::type w) { return [=](P p) { return 0 <= p.i && p.i < h && 0 <= p.j && p.j < w; }; }; static const auto P4 = array{P{-1, 0}, P{ 0, -1}, P{ 1, 0}, P{ 0, 1}}; static const auto P8 = array{P{-1, 0}, P{-1, -1}, P{ 0, -1}, P{ 1, -1}, P{ 1, 0}, P{ 1, 1}, P{ 0, 1}, P{-1, 1}}; // clang-format on ll pow(ll base, ll pow) { ll res = 1; for (auto i : iota(0, pow)) { res *= base; } return res; } template T shared_length(T l1, T r1, T l2, T r2) { return rng::max(0, rng::min(r1, r2) - rng::max(l1, l2)); } namespace detail { using namespace std::ranges; template , size_t>> I> requires std::copyable> && std::equality_comparable> void run_length(R&& t, I out) { using pair = std::pair, size_t>; auto it = begin(t); auto e = end(t); if (it == e) { return; } size_t size = 1; range_value_t prev = *it; ++it; for (; it != e; ++it) { if (*it == prev) { ++size; } else { *out++ = pair(std::move(prev), size); prev = *it; size = 1; } } *out++ = pair(std::move(prev), size); } } // namespace detail using detail::run_length; namespace detail { template struct get { template constexpr decltype(auto) operator()(T&& t) const noexcept(noexcept(std::get(t))) { return std::get(t); } }; } // namespace detail template inline constexpr auto get = detail::get{}; } // namespace tomolatoon #include namespace tomolatoon { using atcoder::dsu; } // namespace tomolatoon namespace tomolatoon { void solve() { ll n, k, q; cin >> n >> k >> q; map st; for (ll i : iota(0, n)) { ll a; cin >> a; if (auto it = st.find(a); it == st.end()) { st[a] = 1; } else { ++it->second; } } ll idx = 0; ll key = 0; for (auto&& [acc, cur] = tuple{0ll, st.begin()}; auto i : iota(0ll, ssize(st))) { if (acc + cur->second >= k) { key = cur->first; idx = rng::max(0ll, k - acc - 1); break; } acc += cur->second; ++cur; } // insert with update auto iwu = [&](ll v) { auto ih = [&](ll v) { if (auto it = st.find(v); it == st.end()) { st.insert({v, 1}); } else { ++st[v]; } }; if (key == -1) { ih(v); key = (st.begin())->first; idx = 0; return; } if (key == -2) { ih(v); key = (--st.end())->first; idx = 0; return; } if (v >= key) { ih(v); } else { if (idx == 0) { if (k == 0) { ih(v); key = v; idx = 0; } else { auto it = st.find(key); auto tmpkey = (--it)->first; if (v <= tmpkey) { ih(v); key = tmpkey; idx = st[tmpkey] - 1; } else { ih(v); key = v; idx = 0; } } } else { --idx; ih(v); } } }; // erase with update auto ewu = [&](ll v) { auto eh = [&](ll v) { if (auto it = st.find(v); it->second == 1) { st.erase(it); } else { --it->second; } }; if (v > key) { eh(v); } else // if (v <= key) { if (st[v] == idx + 1) { if (++st.find(v) == st.end()) { eh(v); key = -2; idx = 0; } /*if (st.size() == 1) { if (st.begin()->second == 1) { eh(v); key = -1; idx = 0; } else { eh(v); key = -2; idx = 0; } }*/ else { auto nkey = (++st.find(v))->first; eh(v); key = nkey; idx = 0; } } else { eh(v); } } /*else { if (st[v] == idx + 1) { auto nkey = (++st.find(v))->first; eh(v); key = nkey; idx = 0; } else { ++idx; eh(v); } }*/ }; for (ll i : iota(0, q)) { ll o; cin >> o; switch (o) { case 1: { ll x; cin >> x; iwu(x); } break; case 2: { ll y; cin >> y; ll ikey = key + y; ewu(key); iwu(ikey); } break; case 3: { cout << key << endl; } break; } } } } // namespace tomolatoon int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(16); tomolatoon::solve(); std::cout << std::flush; }