#ifdef __LOCAL
#include <mytemplate.hpp> // プリコンパイル済みヘッダ ~/local/include/mytemplate.hpp.gch
#else
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#endif
using namespace std;
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using int128 = __int128_t;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
#define REP1(i, n) REP3(i, 0, n, 1)
#define REP2(i, s, n) REP3(i, s, n, 1)
#define REP3(i, s, n, d) for (ll i = (ll)(s); i < (ll)(n); i += (d))
#define REP_OVERLOAD(e1, e2, e3, e4, NAME, ...) NAME
#define rep(...) REP_OVERLOAD(__VA_ARGS__, REP3, REP2, REP1)(__VA_ARGS__)
#define DEP1(i, n) DEP3(i, n, -1, 1)
#define DEP2(i, n, s) DEP3(i, n, s, 1)
#define DEP3(i, n, s, d) for (ll i = (ll)(n); (ll)(s) < i; i -= (d))
#define DEP_OVERLOAD(e1, e2, e3, e4, NAME, ...) NAME
#define dep(...) DEP_OVERLOAD(__VA_ARGS__, DEP3, DEP2, DEP1)(__VA_ARGS__)
#define fore(e, a) for (auto &&e : (a))
#define len(a) (ll)(a).size()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define th third
/*********    C O N S T A N T    **********/
constexpr ll INF =
    LONG_LONG_MAX / 2 - 10000LL; // 4,611,686,018,427,377,903  ~= 4.6e+18, 19桁
const double PI = acos(-1);
/*********       P A I R       **********/
template <class T, class U>
inline pair<T, U> &operator+=(pair<T, U> &a, const pair<T, U> &b) {
    a.fi += b.fi;
    a.se += b.se;
    return a;
}
template <class T, class U>
inline pair<T, U> &operator-=(pair<T, U> &a, const pair<T, U> &b) {
    a.fi -= b.fi;
    a.se -= b.se;
    return a;
}
template <class T, class U>
inline pair<T, U> &operator*=(pair<T, U> &a, const pair<T, U> &b) {
    a.fi *= b.fi;
    a.se *= b.se;
    return a;
}
template <class T, class U>
inline pair<T, U> &operator/=(pair<T, U> &a, const pair<T, U> &b) {
    a.fi /= b.fi;
    a.se /= b.se;
    return a;
}
template <class T, class U>
inline pair<T, U> &operator%=(pair<T, U> &a, const pair<T, U> &b) {
    a.fi %= b.fi;
    a.se %= b.se;
    return a;
}
template <class T, class U, class V>
inline pair<T, U> &operator+=(pair<T, U> &a, const V &b) {
    a.fi += b;
    a.se += b;
    return a;
}
template <class T, class U, class V>
inline pair<T, U> &operator-=(pair<T, U> &a, const V &b) {
    a.fi -= b;
    a.se -= b;
    return a;
}
template <class T, class U, class V>
inline pair<T, U> &operator*=(pair<T, U> &a, const V &b) {
    a.fi *= b;
    a.se *= b;
    return a;
}
template <class T, class U, class V>
inline pair<T, U> &operator/=(pair<T, U> &a, const V &b) {
    a.fi /= b;
    a.se /= b;
    return a;
}
template <class T, class U, class V>
inline pair<T, U> &operator%=(pair<T, U> &a, const V &b) {
    a.fi %= b;
    a.se %= b;
    return a;
}
template <class T, class U, class V>
inline pair<T, U> operator+(pair<T, U> a, const V &b) {
    a += b;
    return a;
}
template <class T, class U, class V>
inline pair<T, U> operator-(pair<T, U> a, const V &b) {
    a -= b;
    return a;
}
template <class T, class U, class V>
inline pair<T, U> operator*(pair<T, U> a, const V &b) {
    a *= b;
    return a;
}
template <class T, class U, class V>
inline pair<T, U> operator/(pair<T, U> a, const V &b) {
    a /= b;
    return a;
}
template <class T, class U, class V>
inline pair<T, U> operator%(pair<T, U> a, const V &b) {
    a %= b;
    return a;
}
template <class T, class U> inline pair<T, U> operator+(pair<T, U> a) {
    return a;
}
template <class T, class U> inline pair<T, U> operator-(pair<T, U> a) {
    return a * (-1);
}
template <class T, class U>
istream &operator>>(istream &stream, pair<T, U> &a) {
    stream >> a.fi >> a.se;
    return stream;
}
template <class T, class U>
ostream &operator<<(ostream &stream, const pair<T, U> &a) {
    stream << a.fi << " " << a.se;
    return stream;
}
/*********       V E C T O R      **********/
template <class T>
inline vector<T> &operator+=(vector<T> &a, const vector<T> &b) {
    assert(a.size() == b.size());
    rep(i, 0, a.size()) a[i] += b[i];
    return a;
}
template <class T>
inline vector<T> &operator-=(vector<T> &a, const vector<T> &b) {
    assert(a.size() == b.size());
    rep(i, 0, a.size()) a[i] -= b[i];
    return a;
}
template <class T>
inline vector<T> &operator*=(vector<T> &a, const vector<T> &b) {
    assert(a.size() == b.size());
    rep(i, 0, a.size()) a[i] *= b[i];
    return a;
}
template <class T>
inline vector<T> &operator/=(vector<T> &a, const vector<T> &b) {
    assert(a.size() == b.size());
    rep(i, 0, a.size()) a[i] /= b[i];
    return a;
}
template <class T>
inline vector<T> &operator%=(vector<T> &a, const vector<T> &b) {
    assert(a.size() == b.size());
    rep(i, 0, a.size()) a[i] %= b[i];
    return a;
}
template <class T, class U>
inline vector<T> &operator+=(vector<T> &a, const U &b) {
    fore(e, a) e += b;
    return a;
}
template <class T, class U>
inline vector<T> &operator-=(vector<T> &a, const U &b) {
    fore(e, a) e -= b;
    return a;
}
template <class T, class U>
inline vector<T> &operator*=(vector<T> &a, const U &b) {
    fore(e, a) e *= b;
    return a;
}
template <class T, class U>
inline vector<T> &operator/=(vector<T> &a, const U &b) {
    fore(e, a) e /= b;
    return a;
}
template <class T, class U>
inline vector<T> &operator%=(vector<T> &a, const U &b) {
    fore(e, a) e %= b;
    return a;
}
template <class T, class U>
inline vector<T> operator+(vector<T> a, const U &b) {
    a += b;
    return a;
}
template <class T, class U>
inline vector<T> operator-(vector<T> a, const U &b) {
    a -= b;
    return a;
}
template <class T, class U>
inline vector<T> operator*(vector<T> a, const U &b) {
    a *= b;
    return a;
}
template <class T, class U>
inline vector<T> operator/(vector<T> a, const U &b) {
    a /= b;
    return a;
}
template <class T, class U>
inline vector<T> operator%(vector<T> a, const U &b) {
    a %= b;
    return a;
}
template <class T> inline vector<T> operator+(vector<T> a) {
    return a;
}
template <class T> inline vector<T> operator-(vector<T> a) {
    return a * (-1);
}
template <class T> istream &operator>>(istream &stream, vector<T> &a) {
    fore(e, a) stream >> e;
    return stream;
}
template <class T> ostream &operator<<(ostream &stream, const vector<T> &v) {
    if (v.size()) {
        stream << v[0];
        rep(i, 1, v.size()) cout << " " << v[i];
    }
    return stream;
}
template <class T>
ostream &operator<<(ostream &stream, const vector<vector<T>> &vv) {
    if (vv.size()) {
        stream << vv[0];
        rep(i, 1, vv.size()) cout << '\n' << vv[i];
    }
    return stream;
}
template <class T> inline T Sum(const vector<T> &v) {
    return reduce(all(v));
} // v.size() == 0 のとき T() を返す
template <class T> inline T Max(const vector<T> &v) {
    assert(v.size());
    return *max_element(all(v));
}
template <class T> inline T Min(const vector<T> &v) {
    assert(v.size());
    return *min_element(all(v));
}
template <class T> inline ll Argmax(const vector<T> &v) {
    assert(v.size());
    return max_element(all(v)) - v.begin();
}
template <class T> inline ll Argmin(const vector<T> &v) {
    assert(v.size());
    return min_element(all(v)) - v.begin();
}
template <class T, class U>
inline bool Contains(const vector<T> &v, const U &a) {
    return find(all(v), a) != v.end();
}
template <class T, class U> vector<T> make_vector(int n, U v) {
    return vector<T>(n, v);
}
template <class T, class... Args> auto make_vector(int n, Args... args) {
    auto val = make_vector<T>(args...);
    return make_vector<decltype(val)>(n, move(val));
}
/*********        S E T        **********/
template <class T> istream &operator>>(istream &stream, set<T> &st) {
    T e;
    stream >> e;
    st.insert(e);
    return stream;
}
template <class T> ostream &operator<<(ostream &stream, const set<T> &st) {
    if (st.size()) {
        auto it = st.begin();
        stream << *it++;
        for (; it != st.end(); it++)
            cout << " " << *it;
    }
    return stream;
}
template <class T> inline T Max(const set<T> &st) {
    assert(st.size());
    return *prev(st.end());
}
template <class T> inline T Min(const set<T> &st) {
    assert(st.size());
    return *st.begin();
}
template <class T> inline bool Contains(const set<T> &st, T x) {
    return st.find(x) != st.end();
}
/*********   M U L T I S E T   **********/
template <class T> istream &operator>>(istream &stream, multiset<T> &st) {
    T e;
    stream >> e;
    st.insert(e);
    return stream;
}
template <class T> ostream &operator<<(ostream &stream, const multiset<T> &st) {
    if (st.size()) {
        auto it = st.begin();
        stream << *it++;
        for (; it != st.end(); it++)
            cout << " " << *it;
    }
    return stream;
}
template <class T> inline T Max(const multiset<T> &st) {
    assert(st.size());
    return *prev(st.end());
}
template <class T> inline T Min(const multiset<T> &st) {
    assert(st.size());
    return *st.begin();
}
template <class T> inline bool Contains(const multiset<T> &st, T x) {
    return st.find(x) != st.end();
}
template <class T> inline bool EraseOne(multiset<T> &st, T x) {
    auto it = st.find(x);
    if (it != st.end()) {
        st.erase(it);
        return true;
    } else
        return false;
} // 要素xを1つ削除. 消せたらtrueを返す.
/*********     S T R I N G     **********/
template <class T> inline bool Contains(const string &s, const T &c) {
    return s.find(c) != string::npos;
} // cはchar, string共に可
inline string ToUpper(const string &s) {
    string t;
    t.resize(s.size());
    std::transform(all(s), t.begin(), ::toupper);
    return t;
}
inline string ToLower(const string &s) {
    string t;
    t.resize(s.size());
    std::transform(all(s), t.begin(), ::tolower);
    return t;
}
/*********       T R I O       **********/
template <class T1, class T2, class T3> struct trio {
    T1 first;
    T2 second;
    T3 third;
    // コンストラクタ・代入演算子
    trio() {
        first = T1();
        second = T2();
        third = T3();
    }
    trio(const T1 &x) : first(x), second(x), third(x) {}
    trio(const T1 &x, const T2 &y, const T3 &z)
        : first(x), second(y), third(z) {}
    trio(const trio &t) {
        first = t.first;
        second = t.second;
        third = t.third;
    } // コピーコンストラクタ
    trio &operator=(const trio &t) {
        first = t.first;
        second = t.second;
        third = t.third;
        return *this;
    }
    // 比較演算子
    bool operator<(const trio &t) const {
        return tie(first, second, third) < tie(t.first, t.second, t.third);
    }
    bool operator==(const trio &t) const {
        return tie(first, second, third) == tie(t.first, t.second, t.third);
    }
    bool operator!=(const trio &other) const {
        return !(*this == other);
    }
    bool operator>(const trio &other) const {
        return other < *this;
    }
    bool operator<=(const trio &other) const {
        return !(*this > other);
    }
    bool operator>=(const trio &other) const {
        return !(*this < other);
    }
    // 単項演算子（+ -）
    trio operator+() const {
        return *this;
    }
    trio operator-() const {
        return (-1) * (*this);
    }
    // 複合代入演算子
    trio &operator+=(const trio &t) {
        first += t.first;
        second += t.second;
        third += t.third;
        return *this;
    }
    trio &operator-=(const trio &t) {
        first -= t.first;
        second -= t.second;
        third -= t.third;
        return *this;
    }
    trio &operator*=(const trio &t) {
        first *= t.first;
        second *= t.second;
        third *= t.third;
        return *this;
    }
    trio &operator/=(const trio &t) {
        first /= t.first;
        second /= t.second;
        third /= t.third;
        return *this;
    }
    trio &operator%=(const trio &t) {
        first %= t.first;
        second %= t.second;
        third %= t.third;
        return *this;
    }
    // 算術演算子
    friend trio operator+(const trio &lhs, const trio &rhs) {
        return trio(lhs) += rhs;
    }
    friend trio operator-(const trio &lhs, const trio &rhs) {
        return trio(lhs) -= rhs;
    }
    friend trio operator*(const trio &lhs, const trio &rhs) {
        return trio(lhs) *= rhs;
    }
    friend trio operator/(const trio &lhs, const trio &rhs) {
        return trio(lhs) /= rhs;
    }
    friend trio operator%(const trio &lhs, const trio &rhs) {
        return trio(lhs) %= rhs;
    }
    // 入出力
    friend istream &operator>>(istream &stream, trio &t) {
        return stream >> t.first >> t.second >> t.third;
    }
    friend ostream &operator<<(ostream &stream, const trio &t) {
        return stream << t.first << " " << t.second << " " << t.third;
    }
    operator tuple<T1 &, T2 &, T3 &>() {
        return tie(first, second, third);
    }
};
using tll = trio<ll, ll, ll>;
/*********     R A N D O M     **********/
struct Random {
    mt19937_64 rnd;
    Random() {
        random_device seed_gen;
        rnd.seed(seed_gen());
    }
    ll randint(ll a, ll b) { // [a, b]
        uniform_int_distribution<ll> dist(a, b);
        return dist(rnd);
    }
    double randreal(double a, double b) {
        uniform_real_distribution<double> dist(a, b);
        return dist(rnd);
    }
    char randchar(char a, char b) { // [a, b]
        uniform_int_distribution<ll> dist(a, b);
        return dist(rnd);
    }
};
/*********       P R I N T       **********/
template <class T> inline void print(const T &e) {
    cout << e << '\n';
}
template <class H, class... T> inline void print(const H &h, const T &...t) {
    cout << h << ' ';
    print(t...);
}
template <class... T> inline void End(const T &...t) {
    print(t...);
    exit(0);
}
/*********       D E B U G       **********/
#ifdef __LOCAL
#define debug(...)                                                             \
    if (DEBUG) do {                                                            \
            cout << '[' << #__VA_ARGS__ << "] ";                               \
            debug_(__VA_ARGS__);                                               \
    } while (0)
#else
#define debug(...)
#endif
void dbg_(const long long &e) {
    if (e == INF)
        cout << "INF";
    else if (e == -INF)
        cout << "-INF";
    else
        cout << e;
}
template <class T> void dbg_(const T &e) {
    cout << e;
}
template <class T, class U> void dbg_(const pair<T, U> &p) {
    cout << '(';
    dbg_(p.first);
    cout << ' ';
    dbg_(p.second);
    cout << ')';
}
template <class T1, class T2, class T3> void dbg_(const trio<T1, T2, T3> &t) {
    cout << '(';
    dbg_(t.first);
    cout << ' ';
    dbg_(t.second);
    cout << ' ';
    dbg_(t.third);
    cout << ')';
}
template <class T> void debug_(const T &e) {
    dbg_(e);
    cout << '\n';
}
template <class T> void debug_(const vector<T> &v) {
    if (v.size()) {
        auto it = v.begin();
        dbg_(*it++);
        for (; it != v.end(); ++it) {
            cout << ' ';
            dbg_(*it);
        }
    }
    cout << '\n';
}
template <class T> void debug_(const vector<vector<T>> &vv) {
    cout << '\n';
    ll cnt = 0;
    for (auto &&v : vv) {
        cout << cnt++ << ": ";
        debug_(v);
    }
}
template <class T, class U> void debug_(const map<T, U> &mp) {
    if (mp.size()) {
        auto it = mp.begin();
        dbg_(*it++);
        for (; it != mp.end(); ++it) {
            cout << ' ';
            dbg_(*it);
        }
    }
    cout << '\n';
}
template <class T, class U> void debug_(const vector<map<T, U>> &vm) {
    cout << '\n';
    ll cnt = 0;
    for (auto &&mp : vm) {
        cout << cnt++ << ": ";
        debug_(mp);
    }
}
template <class T> void debug_(const set<T> &st) {
    if (st.size()) {
        auto it = st.begin();
        dbg_(*it++);
        for (; it != st.end(); ++it) {
            cout << ' ';
            dbg_(*it);
        }
    }
    cout << '\n';
}
template <class T> void debug_(const multiset<T> &st) {
    if (st.size()) {
        auto it = st.begin();
        dbg_(*it++);
        for (; it != st.end(); ++it) {
            cout << ' ';
            dbg_(*it);
        }
    }
    cout << '\n';
}
template <class T> void debug_(const vector<set<T>> &vs) {
    cout << '\n';
    ll cnt = 0;
    for (auto &&st : vs) {
        cout << cnt++ << ": ";
        debug_(st);
    }
}
template <class T> void debug_(const vector<multiset<T>> &vs) {
    cout << '\n';
    ll cnt = 0;
    for (auto &&st : vs) {
        cout << cnt++ << ": ";
        debug_(st);
    }
}
template <class H, class... T> void debug_(const H &h, const T &...t) {
    dbg_(h);
    cout << ", ";
    debug_(t...);
}
/*********       O T H E R S       **********/
template <class T, class U> inline bool chmin(T &a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
} // bは値渡し!
template <class T, class U> inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U> inline auto Mod(const T &a, const U &m) {
    return (a % m + m) % m;
} // 負もOK
template <class T, class U> inline auto Ceil(const T &x, const U &y) {
    return x < 0 ? x / y : (x + y - 1) / y;
} // 負もOK
template <class T, class U> inline auto Floor(const T &x, const U &y) {
    return -(Ceil(-x, y));
} // 負もOK
inline ll Isqrt(ll n) {
    assert(n >= 0);
    ll x = round(sqrt(n));
    while (x * x > n)
        --x;
    return x;
}
inline ll Comb(ll n, ll r) {
    if (r < 0 || n < r) return 0;
    r = min(r, n - r);
    ll ret = 1;
    rep(i, r) {
        ret *= n - i;
        ret /= i + 1;
    }
    return ret;
} // n=60, r=30までOK
template <class T> inline T Pow(T x, ll n) {
    assert(n >= 0);
    T ret = 1;
    while (1) {
        if (n % 2) ret *= x;
        n /= 2;
        if (!n) return ret;
        x = x * x;
    }
} // べき乗 mintもOK
template <class T> inline T Aseries(T a, T d, ll n) {
    assert(n >= 0);
    return a * n + n * (n - 1) / 2 * d;
} // 等差級数 mintもOK
template <class T> inline T Gseries(T a, T r, ll n) {
    assert(n >= 0);
    if (r == 1)
        return a * n;
    else
        return a * (1 - Pow(r, n)) / (1 - r);
} // 等比級数 mintもOK
template <class T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
inline bool Bit(ll b, int i) {
    assert(0 <= i && i < 64);
    return (b >> i) & 1;
}
inline ll Popcount(ll b) {
    return __builtin_popcountll(b);
}
inline ll Mask(ll n) {
    assert(0 <= n && n < 63);
    return (1LL << n) - 1LL;
} // [0, n)のbitが立った64bit整数を返す。
inline ll Mask(ll n, ll m) {
    assert(n >= m);
    return Mask(n) ^ Mask(m);
} // [m, n)のbitが立った64bit整数を返す。
/*********       M  O  D       **********/
// #include <atcoder/modint>  //
// https://atcoder.github.io/ac-library/production/document_ja/ using namespace
// atcoder; using mint = modint998244353;     // modint1000000007; istream&
// operator >>(istream& stream, mint& e) {ll n; stream >> n; e = n; return
// stream; } ostream& operator <<(ostream& stream, const mint& e) { stream <<
// e.val(); return stream; } using vm = vector<mint>; using vvm = vector<vm>;
/***************************************/
constexpr bool DEBUG = true;

// 参考:   https://pages.soi.ch/soiminar/treap.pdf
// verify:
template <class T> struct TreapMultiSet {
  private:
    struct Node {
        int priority;
        T key;
        size_t size = 1;
        size_t cnt = 1;
        unique_ptr<Node> left, right;

        Node(T key) : priority(rand()), key(key) {}
    };

    using upn = unique_ptr<Node>;
    upn root;

    // 分離。keyの値が含まれるとき、eq2rightがfalseならl, trueならrに行く。
    pair<upn, upn> split(upn current, const T &key, bool eq2right = false) {
        upn l, r;

        if (!current) return {move(l), move(r)};
        if (key < current->key || (key == current->key && eq2right)) {
            r = move(current);
            tie(l, r->left) = split(move(r->left), key, eq2right);
            r->size -= (!l ? 0 : l->size);
        } else {
            l = move(current);
            tie(l->right, r) = split(move(l->right), key, eq2right);
            l->size -= (!r ? 0 : r->size);
        }
        return {move(l), move(r)};
    }

    // 結合。必要条件: l->key <= r->key
    upn merge(upn l, upn r) {
        if (!l || !r) return l ? move(l) : move(r);
        if (l->priority > r->priority) {
            l->size += r->size;
            l->right = merge(move(l->right), move(r));
            return l;
        } else {
            r->size += l->size;
            r->left = merge(move(l), move(r->left));
            return r;
        }
    }

    // x未満の要素数, eq = trueならx以下
    size_t index_(const T &x, bool eq) {
        if (!root) return 0;
        Node *current = root.get();

        size_t cnt = 0;
        while (current) {
            int left_size = !current->left ? 0 : current->left->size;
            if (current->key == x) {
                cnt += left_size;
                if (eq) cnt += current->cnt;
                break;
            } else if (current->key < x) {
                cnt += left_size + current->cnt;
                current = current->right.get();
            } else {
                current = current->left.get();
            }
        }
        return cnt;
    }

    // x未満の最大値, eq = trueならkey以下.
    optional<T> less_(const T &x, bool eq) {
        if (!root) return nullopt;
        Node *current = root.get();

        T ret = T();
        bool exists = false;
        while (current) {
            if (eq && current->key == x) return x;
            if (current->key < x) {
                ret = current->key;
                exists = true;
                current = current->right.get();
            } else {
                current = current->left.get();
            }
        }
        if (exists)
            return ret;
        else
            return nullopt;
    }

    // x超過の最小値, eq = trueならkey以上.
    optional<T> greater_(const T &x, bool eq) {
        if (!root) return nullopt;
        Node *current = root.get();

        T ret = T();
        bool exists = false;
        while (current) {
            if (eq && current->key == x) return x;
            if (current->key > x) {
                ret = current->key;
                exists = true;
                current = current->left.get();
            } else {
                current = current->right.get();
            }
        }
        if (exists)
            return ret;
        else
            return nullopt;
    }

  public:
    TreapMultiSet() {}

    TreapMultiSet(const vector<T> &vec) {
        fore(e, vec) insert(e);
    }

    // keyを追加
    void insert(const T &key) {
        unique_ptr<Node> l, r, eq;
        tie(l, r) = split(move(root), key);
        tie(l, eq) = split(move(l), key, true);

        if (eq) {
            eq->cnt++;
            eq->size++;
            root = merge(merge(move(l), move(eq)), move(r));
        } else {
            auto node = make_unique<Node>(key);
            root = merge(merge(move(l), move(node)), move(r));
        }
    }

    // keyを消去。消去前にkeyが存在したかを返す
    bool erase(const T &key) {
        unique_ptr<Node> l, r, eq;
        tie(l, r) = split(move(root), key);
        tie(l, eq) = split(move(l), key, true);

        bool key_exists = eq;
        if (eq) {
            if (eq->cnt == 1) { // keyが1個しかないときはNodeを削除
                eq = merge(move(eq->left), move(eq->right));
            } else {
                eq->cnt--;
                eq->size--;
            }
        }
        root = merge(merge(move(l), move(eq)), move(r));

        return key_exists;
    }

    // 値xが含まれるかどうか
    bool contains(const T &x) {
        return count(x) > 0;
    }

    // 要素数
    size_t size() {
        if (!root) return 0;
        return root->size;
    }

    // xの要素数
    size_t count(const T &x) {
        if (!root) return 0;
        Node *current = root.get();

        while (current) {
            if (x == current->key)
                return current->cnt;
            else if (x < current->key)
                current = current->left.get();
            else
                current = current->right.get();
        }
        return 0;
    }

    // index番目の値（0-origin）
    T operator[](size_t index) const {
        assert(root);
        assert(0 <= index && index < root->size);
        Node *current = root.get();

        while (current) {
            size_t left_size = (!current->left ? 0 : current->left->size);

            if (index < left_size) {
                current = current->left.get();
            } else if (index >= left_size + current->cnt) {
                index -= left_size + current->cnt;
                current = current->right.get();
            } else {
                break;
            }
        }
        return current->key;
    }

    // x未満の要素数
    size_t index(const T &x) {
        return index_(x, false);
    }

    // x以下の要素数
    size_t index_right(const T &x) {
        return index_(x, true);
    }

    // x未満の最大値
    optional<T> lt(const T &x) {
        return less_(x, false);
    }

    // x以下の最大値
    optional<T> le(const T &x) {
        return less_(x, true);
    }

    // x超過の最小値（upper_bound）
    optional<T> gt(const T &x) {
        return greater_(x, false);
    }

    // x以上の最小値（lower_bound）
    optional<T> ge(const T &x) {
        return greater_(x, true);
    }
};
// Treap<ll> trp = vl{0, 0, 5};      // 0, 0, 5を挿入したインスタンスを得る
// trp.insert(3);                    // 挿入, 重複する値は無視
// bool erased = trp.erase(3);       // 削除
// bool exists = trp.contains(3);    // 存在判定
// size_t siz = trp.size();          // 要素数
// size_t cnt = trp.count(3);        // 3の要素数
// ll value = trp[i];                // i番目の値, 0-indexed
// size_t num1 = trp.index(5);       // 5未満の要素数
// size_t num2 = trp.index_right(5); // 5以下の要素数
// optional<ll> val1 = trp.lt(5);    // 5未満の最大値. 値取り出しは val1.value()
// optional<ll> val2 = trp.le(5);    // 5以下の最大値
// optional<ll> val3 = trp.gt(5);    // 5超過の最小値
// optional<ll> val4 = trp.ge(5);    // 5以上の最小値

int main() {
    cin.tie(nullptr);
    cout << fixed << setprecision(10);

    ll Q, K;
    cin >> Q >> K;
    TreapMultiSet<ll> trp;

    vl ans;
    rep(q, Q) {
        ll t, v;
        cin >> t;
        if (t == 1) {
            cin >> v;
            trp.insert(v);
        } else {
            if (len(trp) < K)
                ans.pb(-1);
            else {
                ll val = trp[K - 1];
                ans.pb(val);
                trp.erase(val);
            }
        }
    }
    fore(e, ans) print(e);
}