Wesley's Code Templates!

bidirrectional_BFS.cpp

template <const int MAXV> struct BidirectionalBFS {
    int dist[MAXV], to[MAXV], q[MAXV], vis[MAXV], stamp = 0; vector<int> adj[MAXV]; pair<int, int> edgeOnPath;
    void addBiEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); }
    void clear(int V = MAXV) { stamp = 0; for (int i = 0; i < MAXV; i++) adj[i].clear(); }
    int run(int V, int s, int t) {
        if (s == t) return 0;
        if (stamp == 0) fill(vis, vis + V, stamp);
        stamp++; int front = 0, back = 0; dist[s] = dist[t] = 0; q[back++] = s; q[back++] = t; vis[s] = stamp; vis[t] = -stamp;
        while (front < back) {
            int v = q[front++];
            for (int w : adj[v]) {
                if (vis[v] == -vis[w]) { edgeOnPath = make_pair(v, w); return dist[v] + dist[w] + 1; }
                else if (vis[v] != vis[w]) { dist[w] = dist[v] + 1; vis[w] = vis[v]; to[w] = v; q[back++] = w; }
            }
        }
        return -1;
    }
};

BIT.cpp

template <class T, const bool ONE_INDEXED, const int ...Args> struct FenwickTree {
    T val;
    void init() { val = 0; }
    void update(T v) { val += v; }
    T rsq() { return val; }
};

template <class T, const bool ONE_INDEXED, const int MAXN, const int ...Ns> struct FenwickTree <T, ONE_INDEXED, MAXN, Ns...> {
    FenwickTree<T, ONE_INDEXED, Ns...> BIT[MAXN];
    void init() { for (int i = 0; i < MAXN; i++) BIT[i].init(); }
    template <class ...Args> void update(int i, Args ...args) { for (i += !ONE_INDEXED; i < MAXN; i += i & -i) BIT[i].update(args...); }
    template <class ...Args> T rsq(int l, int r, Args ...args) {
        T ret = 0;
        for (r += !ONE_INDEXED; r > 0; r -= r & -r) ret += BIT[r].rsq(args...);
        for (l -= ONE_INDEXED; l > 0; l -= l & -l) ret -= BIT[l].rsq(args...);
        return ret;
    }
};

cbrt.cpp

#define FACTOR 4

struct Sqrt {
    vector<vector<int>> a;
    vector<int> prefixSZ;
    int n;

    Sqrt() : n(0) {}

    template <typename It>
    Sqrt(It st, It en) : n(en - st) {
        int sqrtn = (int) sqrt(n) * FACTOR;
        for (It i = st; i < en; i += sqrtn) {
            a.emplace_back(i, min(i + sqrtn, en));
            prefixSZ.push_back(0);
        }
        for (int i = 1; i < (int) a.size(); i++) {
            prefixSZ[i] = prefixSZ[i - 1] + (int) a[i - 1].size();
        }
    }

    void insert(int val) {
        int lo = 0, hi = (int) a.size(), mid;
        while (lo < hi) {
            mid = lo + (hi - lo) / 2;
            if (val < a[mid].back()) hi = mid;
            else lo = mid + 1;
        }
        int i = lo;
        if (lo != (int) a.size()) {
            lo = 0, hi = (int) a[i].size();
            while (lo < hi) {
                mid = lo + (hi - lo) / 2;
                if (val < a[i][mid]) hi = mid;
                else lo = mid + 1;
            }
        }
        if (n++ == 0) {
            a.emplace_back();
            prefixSZ.push_back(0);
        }
        if (i == (int) a.size()) a[--i].push_back(val);
        else a[i].insert(a[i].begin() + lo, val);
        int sqrtn = (int) sqrt(n) * FACTOR;
        if ((int) a[i].size() > 2 * sqrtn) {
            a.emplace(a.begin() + i + 1, a[i].begin() + sqrtn, a[i].end());
            a[i].resize(sqrtn);
            prefixSZ.push_back(0);
        }
        for (int j = i + 1; j < (int) a.size(); j++) {
            prefixSZ[j] = prefixSZ[j - 1] + (int) a[j - 1].size();
        }
    }

    bool erase(int val) {
        int lo = 0, hi = (int) a.size(), mid;
        while (lo < hi) {
            mid = lo + (hi - lo) / 2;
            if (a[mid].back() < val) lo = mid + 1;
            else hi = mid;
        }
        if (lo == (int) a.size()) return false;
        int i = lo;
        lo = 0, hi = (int) a[i].size();
        while (lo < hi) {
            mid = lo + (hi - lo) / 2;
            if (a[i][mid] < val) lo = mid + 1;
            else hi = mid;
        }
        if (a[i][lo] != val) return false;
        --n;
        a[i].erase(a[i].begin() + lo);
        if (a[i].empty()) {
            a.erase(a.begin() + i);
            prefixSZ.pop_back();
        }
        for (int j = i + 1; j < (int) a.size(); j++) {
            prefixSZ[j] = prefixSZ[j - 1] + (int) a[j - 1].size();
        }
        return true;
    }

    void pop_back() {
        --n;
        a.back().pop_back();
        if (a.back().empty()) {
            a.pop_back();
            prefixSZ.pop_back();
        }
    }

    int back() {
        return a.back().back();
    }

    int at(int k) {
        int lo = 0, hi = (int) (a.size()) - 1, mid;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if (k < prefixSZ[mid]) hi = mid - 1;
            else lo = mid + 1;
        }
        return a[hi][k - prefixSZ[hi]];
    }

    int getRank(int val) {
        int lo = 0, hi = (int) a.size(), mid;
        while (lo < hi) {
            mid = lo + (hi - lo) / 2;
            if (a[mid].back() < val) lo = mid + 1;
            else hi = mid;
        }
        if (lo == (int) a.size()) return -1;
        int i = lo;
        lo = 0, hi = (int) a[i].size();
        while (lo < hi) {
            mid = lo + (hi - lo) / 2;
            if (a[i][mid] < val) lo = mid + 1;
            else hi = mid;
        }
        return a[i][lo] == val ? prefixSZ[i] + lo : -1;
    }

    void print() {
        for (int i = 0; i < (int) a.size(); i++) {
            for (int j = 0; j < (int) a[i].size(); j++) {
                cout << a[i][j] << sp;
            }
        }
    }
};

#define MAXN 100005

int N, M, A[MAXN];

vector<Sqrt> a;
vector<int> prefixSZ;
int n;

void init() {
    n = N;
    int cbrtnsq = (int) cbrt(n) * cbrt(n) * FACTOR;
    for (int i = 0; i < n; i += cbrtnsq) {
        a.emplace_back(A + i, A + min(i + cbrtnsq, n));
        prefixSZ.push_back(0);
    }
    for (int i = 1; i < (int) a.size(); i++) {
        prefixSZ[i] = prefixSZ[i - 1] + (int) a[i - 1].n;
    }
}

void insert(int val) {
    int lo = 0, hi = (int) a.size(), mid;
    while (lo < hi) {
        mid = lo + (hi - lo) / 2;
        if (val < a[mid].back()) hi = mid;
        else lo = mid + 1;
    }
    if (n++ == 0) {
        a.emplace_back();
        prefixSZ.push_back(0);
    }
    if (lo == (int) a.size()) a[--lo].insert(val);
    else a[lo].insert(val);
    int cbrtnsq = (int) cbrt(n) * cbrt(n) * FACTOR;
    if (a[lo].n > 2 * cbrtnsq) {
        vector<int> b;
        while (a[lo].n > cbrtnsq) {
            b.push_back(a[lo].back());
            a[lo].pop_back();
        }
        reverse(b.begin(), b.end());
        a.emplace(a.begin() + lo + 1, b.begin(), b.end());
        prefixSZ.push_back(0);
    }
    for (int j = lo + 1; j < (int) a.size(); j++) {
        prefixSZ[j] = prefixSZ[j - 1] + (int) a[j - 1].n;
    }
}

void erase(int val) {
    int lo = 0, hi = (int) a.size(), mid;
    while (lo < hi) {
        mid = lo + (hi - lo) / 2;
        if (a[mid].back() < val) lo = mid + 1;
        else hi = mid;
    }
    if (lo == (int) a.size()) return;
    if (!a[lo].erase(val)) return;
    --n;
    if (a[lo].n == 0) {
        a.erase(a.begin() + lo);
        prefixSZ.pop_back();
    }
    for (int j = lo + 1; j < (int) a.size(); j++) {
        prefixSZ[j] = prefixSZ[j - 1] + (int) a[j - 1].n;
    }
}

int at(int k) {
    int lo = 0, hi = ((int) a.size()) - 1, mid;
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        if (k < prefixSZ[mid]) hi = mid - 1;
        else lo = mid + 1;
    }
    return a[hi].at(k - prefixSZ[hi]);
}

int getRank(int val) {
    int lo = 0, hi = (int) a.size(), mid;
    while (lo < hi) {
        mid = lo + (hi - lo) / 2;
        if (a[mid].back() < val) lo = mid + 1;
        else hi = mid;
    }
    if (lo == (int) a.size()) return -1;
    int r = a[lo].getRank(val);
    return r == -1 ? -1 : prefixSZ[lo] + r;
}

void print() {
    for (int i = 0; i < (int) a.size(); i++) {
        a[i].print();
    }
    cout << nl;
}

DSU.cpp

template <const int MAXN, const bool ONE_INDEXED> struct UnionFind {
    int UF[MAXN], cnt;
    void init(int N) { cnt = N; fill(UF, UF + N + ONE_INDEXED, -1); }
    int find(int v) { return UF[v] < 0 ? v : UF[v] = find(UF[v]); }
    bool join(int v, int w) {
        if ((v = find(v)) == (w = find(w))) return false;
        if (UF[v] > UF[w]) swap(v, w);
        UF[v] += UF[w]; UF[w] = v; cnt--; return true;
    }
    bool connected(int v, int w) { return find(v) == find(w); }
    int getSize(int v) { return -UF[find(v)]; }
};

lct-old.cpp

#define INC 1
#define ASSIGN 2

int N, M, ROOT, VAL[MAXN], MN[MAXN], MX[MAXN], SUM[MAXN], LZ[MAXN], FL[MAXN], SZ[MAXN], L[MAXN], R[MAXN], P[MAXN];
bool REV[MAXN];
vector<int> adj[MAXN];

void makeNode(int vert, int val) {
    FL[vert] = LZ[vert] = L[vert] = R[vert] = P[vert] = 0;
    REV[vert] = false;
    VAL[vert] = SUM[vert] = MN[vert] = MX[vert] = val;
    SZ[vert] = 1;
}

bool isRoot(int x) {
    return !P[x] || (x != L[P[x]] && x != R[P[x]]);
}

int getSize(int x) {
    return x ? SZ[x] : 0;
}

int getMin(int x) {
    return x ? MN[x] : INT_MAX;
}

int getMax(int x) {
    return x ? MX[x] : INT_MIN;
}

int getSum(int x) {
    return x ? SUM[x] : 0;
}

int apply(int val, int lz, int fl) {
    if (fl == ASSIGN) return lz;
    else if (fl == INC) return val + lz;
    else return val;
}

void propagate(int x) {
    if (x) {
        if (REV[x]) {
            REV[x] ^= 1;
            swap(L[x], R[x]);
            if (L[x]) REV[L[x]] ^= 1;
            if (R[x]) REV[R[x]] ^= 1;
        }
        VAL[x] = apply(VAL[x], LZ[x], FL[x]);
        SUM[x] = apply(SUM[x], LZ[x] * SZ[x], FL[x]);
        MN[x] = apply(MN[x], LZ[x], FL[x]);
        MX[x] = apply(MX[x], LZ[x], FL[x]);
        if (L[x]) {
            LZ[L[x]] = apply(LZ[L[x]], LZ[x], FL[x]);
            MAX(FL[L[x]], FL[x]);
        }
        if (R[x]) {
            LZ[R[x]] = apply(LZ[R[x]], LZ[x], FL[x]);
            MAX(FL[R[x]], FL[x]);
        }
        LZ[x] = FL[x] = 0;
    }
}

void update(int x) {
    if (x) {
        SUM[x] = MN[x] = MX[x] = apply(VAL[x], LZ[x], FL[x]);
        SZ[x] = 1;
        if (L[x]) {
            SUM[x] += apply(SUM[L[x]], apply(LZ[L[x]], LZ[x], FL[x]) * SZ[L[x]], max(FL[L[x]], FL[x]));
            MIN(MN[x], apply(MN[L[x]], apply(LZ[L[x]], LZ[x], FL[x]), FL[L[x]]));
            MAX(MX[x], apply(MX[L[x]], apply(LZ[L[x]], LZ[x], FL[x]), FL[L[x]]));
            SZ[x] += SZ[L[x]];
        }
        if (R[x]) {
            SUM[x] += apply(SUM[R[x]], apply(LZ[R[x]], LZ[x], FL[x]) * SZ[R[x]], max(FL[R[x]], FL[x]));
            MIN(MN[x], apply(MN[R[x]], apply(LZ[R[x]], LZ[x], FL[x]), FL[R[x]]));
            MAX(MX[x], apply(MX[R[x]], apply(LZ[R[x]], LZ[x], FL[x]), FL[R[x]]));
            SZ[x] += SZ[R[x]];
        }
    }
}

void connect(int ch, int par, bool hasCh, bool isL) {
    if (ch) P[ch] = par;
    if (hasCh) {
        if (isL) L[par] = ch;
        else R[par] = ch;
    }
}

void rotate(int x) {
    int p = P[x];
    int g = P[p];
    bool isRootP = isRoot(p);
    bool isL = x == L[p];
    connect(isL ? R[x] : L[x], p, true, isL);
    connect(p, x, true, !isL);
    connect(x, g, !isRootP, isRootP ? false : p == L[g]);
    update(p);
}

void splay(int x) {
    while (!isRoot(x)) {
        int p = P[x];
        int g = P[p];
        if (!isRoot(p)) propagate(g);
        propagate(p);
        propagate(x);
        if (!isRoot(p)) rotate((x == L[p]) == (p == L[g]) ? p : x);
        rotate(x);
    }
    propagate(x);
    update(x);
}

int expose(int x) {
    int last = 0;
    for (int y = x; y; y = P[y]) {
        splay(y);
        L[y] = last;
        last = y;
    }
    splay(x);
    return last;
}

void makeRoot(int x) {
    expose(x);
    REV[x] ^= 1;
}

int lca(int x, int y) {
    makeRoot(ROOT);
    expose(x);
    return expose(y);
}

bool link(int x, int y) {
    makeRoot(ROOT);
    expose(x);
    if (R[x]) return false;
    P[x] = y;
    return true;
}

bool cutParent(int x) {
    makeRoot(ROOT);
    expose(x);
    if (!R[x]) return false;
    R[x] = P[R[x]] = 0;
    return true;
}

void update(int from, int to, int val, int fl) {
    makeRoot(from);
    expose(to);
    LZ[to] = apply(LZ[to], val, fl);
    MAX(FL[to], fl);
    update(to);
}

int querySum(int from, int to) {
    makeRoot(from);
    expose(to);
    return getSum(to);
}

int queryMin(int from, int to) {
    makeRoot(from);
    expose(to);
    return getMin(to);
}

int queryMax(int from, int to) {
    makeRoot(from);
    expose(to);
    return getMax(to);
}

void dfs(int v, int prev) {
    for (int w : adj[v]) {
        if (w == prev) continue;
        assert(link(w, v));
        dfs(w, v);
    }
}

RBT.cpp

class no_such_element_exception: public runtime_error {
public:
    no_such_element_exception(): runtime_error("No such element exists"){}
    no_such_element_exception(string message): runtime_error(message){}
};

template <typename Value, typename Comparator = less<Value>>
struct RBTreeSet {
private:
    Comparator cmp;
    enum Color {BLACK = 0, RED = 1};

    /**
     * Represents an inner node of the tree.
     */
    struct Node {
        Value val;
        bool color;
        int size;
        Node *left = nullptr, *right = nullptr;
        Node(Value val, bool color, int size) {
            this->val = val;
            this->color = color;
            this->size = size;
        }
    };

    /**
     * The root node.
     */
    Node *root = nullptr;

    /**
     * Returns true if the node is red, false otherwise.
     *
     * @param x the node
     * @return true if the node is red, false otherwise
     */
    bool isRed(Node *&x) {
        if (x == nullptr) return false;
        return x->color == RED;
    }

    /**
     * Returns the number of nodes in the subtree.
     *
     * @param x the subtree
     * @return the number of nodes in the subtree
     */
    int size(Node *&x) {
        if (x == nullptr) return 0;
        return x->size;
    }


    /**
     * Updates the size and height of the subtree.
     *
     * @param x the subtree
     */
    void update(Node *&x) {
        x->size = 1 + size(x->left) + size(x->right);
    }

    /**
     * Flips the colors of the node and its children
     *
     * @param x the node to flip
     */
    void flipColors(Node *&x) {
        x->color = !x->color;
        x->left->color = !x->left->color;
        x->right->color = !x->right->color;
    }

    /**
     * Rotates the given subtree to the right.
     *
     * @param x the subtree
     * @return the right rotated subtree
     */
    Node *rotateRight(Node *&x) {
        Node *y = x->left;
        x->left = y->right;
        y->right = x;
        y->color = y->right->color;
        y->right->color = RED;
        update(x);
        update(y);
        return y;
    }

    /**
     * Rotates the given subtree to the left.
     *
     * @param x the subtree
     * @return the left rotated subtree
     */
    Node *rotateLeft(Node *&x) {
        Node *y = x->right;
        x->right = y->left;
        y->left = x;
        y->color = y->left->color;
        y->left->color = RED;
        update(x);
        update(y);
        return y;
    }

    /**
     * If x is red, and both x->left and x->left->left are black,
     * make x->left or one of its children red.
     *
     * @param x the subtree
     * @return updated subtree
     */
    Node *moveRedLeft(Node *&x) {
        flipColors(x);
        if (isRed(x->right->left)) {
            x->right = rotateRight(x->right);
            x = rotateLeft(x);
            flipColors(x);
        }
        return x;
    }

    /**
     * If x is red, and both x->right and x->right->left are black,
     * make x->right or one of its children red.
     *
     * @param x the subtree
     * @return updated subtree
     */
    Node *moveRedRight(Node *&x) {
        flipColors(x);
        if (isRed(x->left->left)) {
            x = rotateRight(x);
            flipColors(x);
        }
        return x;
    }

    /**
     * Balances the red-black subtree.
     *
     * @param x the subtree
     * @param fixRight whether a right-leaning fix is needed
     * @return the balanced subtree
     */
    Node *balance(Node *&x, bool fixRight) {
        if (isRed(x->right) && (!fixRight || !isRed(x->left))) x = rotateLeft(x);
        if (isRed(x->left) && isRed(x->left->left)) x = rotateRight(x);
        if (isRed(x->left) && isRed(x->right)) flipColors(x);
        update(x);
        return x;
    }

    // auxiliary function for contains
    bool contains(Node *&x, Value val) {
        if (x == nullptr) return false;
        else if (cmp(val, x->val)) return contains(x->left, val);
        else if (cmp(x->val, val)) return contains(x->right, val);
        return true;
    }

    /**
     * Inserts the specified value into the set, not allowing for duplicates.
     *
     * @param x the subtree
     * @param val the value
     * @return the subtree
     */
    Node *add(Node *&x, Value val) {
        if (x == nullptr) return new Node(val, RED, 1);
        if (cmp(val, x->val)) x->left = add(x->left, val);
        else if (cmp(x->val, val)) x->right = add(x->right, val);
        else return x;
        update(x);
        return balance(x, true);
    }

    /**
     * Removes the smallest value from the given subtree.
     *
     * @param x the subtree
     * @return the updated subtree
     */
    Node *removeMin(Node *&x, bool freeMemory) {
        if (x->left == nullptr) {
            if (freeMemory) delete x;
            return nullptr;
        }
        if (!isRed(x->left) && !isRed(x->left->left)) x = moveRedLeft(x);
        x->left = removeMin(x->left, freeMemory);
        update(x);
        return balance(x, false);
    }

    /**
     * Removes the largest value from the given subtree.
     *
     * @param x the subtree
     * @return the updated subtree
     */
    Node *removeMax(Node *&x, bool freeMemory) {
        if (x->right == nullptr) {
            if (freeMemory) delete x;
            return nullptr;
        }
        if (!isRed(x->right) && !isRed(x->right->left)) x = moveRedRight(x);
        x->right = removeMax(x->right, freeMemory);
        update(x);
        return balance(x, false);
    }

    /**
     * Returns the node with the smallest value in the subtree.
     *
     * @param x the subtree
     * @return the node with the smallest value in the subtree
     */
    Node *getMin(Node *&x) {
        if (x->left == nullptr) return x;
        return getMin(x->left);
    }

    /**
     * Returns the node with the largest value in the subtree.
     *
     * @param x the subtree
     * @return the node with the largest value in the subtree
     */
    Node *getMax(Node *&x) {
        if (x->right == nullptr) return x;
        return getMax(x->right);
    }

    /**
     * Removes the specified value and its associated value from the given
     * subtree.
     *
     * @param x the subtree
     * @param val the value
     * @return the updated subtree
     */
    Node *remove(Node *&x, Value val) {
        if (cmp(val, x->val)) {
            if (!isRed(x->left) && !isRed(x->left->left)) x = moveRedLeft(x);
            x->left = remove(x->left, val);
        } else {
            if (isRed(x->left)) x = rotateRight(x);
            if (!cmp(val, x->val) && !cmp(x->val, val) && x->right == nullptr) {
                delete x;
                return nullptr;
            }
            if (!isRed(x->right) && !isRed(x->right->left)) x = moveRedRight(x);
            if (!cmp(val, x->val) && !cmp(x->val, val)) {
                Node *y = getMin(x->right);
                x->val = y->val;
                x->right = removeMin(x->right, true);
            } else {
                x->right = remove(x->right, val);
            }
        }
        update(x);
        return balance(x, false);
    }

    /**
     * Returns the node in the subtree with the largest value less than or equal
     * to the given value.
     *
     * @param x the subtree
     * @param val the value
     * @return the node in the subtree with the largest value less than or equal
     *         to the given value
     */
    Node *floor(Node *&x, Value val) {
        if (x == nullptr) return nullptr;
        if (!cmp(val, x->val) && !cmp(x->val, val)) return x;
        if (cmp(val, x->val)) return floor(x->left, val);
        Node *y = floor(x->right, val);
        if (y != nullptr) return y;
        else return x;
    }

    /**
     * Returns the node in the subtree with the smallest value greater than or
     * equal to the given value.
     *
     * @param x the subtree
     * @param val the value
     * @return the node in the subtree with the smallest value greater than or
     *         equal to the given value
     */
    Node *ceiling(Node *&x, Value val) {
        if (x == nullptr) return nullptr;
        if (!cmp(val, x->val) && !cmp(x->val, val)) return x;
        if (cmp(x->val, val)) return ceiling(x->right, val);
        Node *y = ceiling(x->left, val);
        if (y != nullptr) return y;
        else return x;
    }

    /**
     * Returns the node with value the kth smallest value in the subtree.
     *
     * @param x the subtree
     * @param k the kth smallest value in the subtree
     * @return the node with value the kth smallest value in the subtree
     */
    Node *select(Node *&x, int k) {
        if (x == nullptr) return nullptr;
        int t = size(x->left);
        if (t > k) return select(x->left, k);
        else if (t < k) return select(x->right, k - t - 1);
        return x;
    }

    /**
     * Returns the number of values in the subtree less than val.
     *
     * @param val the value
     * @param x the subtree
     * @return the number of values in the subtree less than val
     */
    int getRank(Node *&x, Value val) {
        if (x == nullptr) return 0;
        if (!cmp(x->val, val)) return getRank(x->left, val);
        else return 1 + size(x->left) + getRank(x->right, val);
    }

    /**
     * Adds the values in the subtree to queue following an in-order traversal.
     *
     * @param x the subtree
     * @param queue the queue
     */
    void valuesInOrder(Node *&x, vector<Value> &queue) {
        if (x == nullptr) return;
        valuesInOrder(x->left, queue);
        queue.push_back(x->val);
        valuesInOrder(x->right, queue);
    }

    /**
     * Adds the values between {@code lo} and {@code hi} in the subtree
     * to the {@code queue}.
     *
     * @param x the subtree
     * @param queue the queue
     * @param lo the lowest value
     * @param hi the highest value
     */
    void values(Node *&x, vector<Value> &queue, Value lo, Value hi) {
        if (x == nullptr) return;
        if (cmp(lo, x->val)) values(x->left, queue, lo, hi);
        if (!cmp(x->val, lo) && !cmp(hi, x->val)) queue.push_back(x->val);
        if (cmp(x->val, hi)) values(x->right, queue, lo, hi);
    }

    void print(Node *&x) {
        if (x == nullptr) return;
        print(x->left);
        cout << x->val.f << ' ';
        print(x->right);
    }

    /**
     * Clears the symbol table.
     * @param x the subtree
     */
    void clear(Node *x) {
        if (x == nullptr) return;
        clear(x->left);
        clear(x->right);
        delete x;
        x = nullptr;
    }

public:
    /**
     * Initializes an empty symbol table.
     */
    RBTreeSet() {}

    /**
     * Deletes the symbol table.
     */
    ~RBTreeSet() {
        clear(root);
    }

    /**
     * Clears the symbol table.
     */
    void clear() {
        clear(root);
        root = nullptr;
    }

    /**
     * Checks if the set is empty.
     *
     * @return {@code true} if the set is empty.
     */
    bool isEmpty() {
        return root == nullptr;
    }

    /**
     * Returns the number values in the set.
     *
     * @return the number values pairs in the set
     */
    int size() {
        return size(root);
    }

    /**
     * Checks if the set contains the given value.
     *
     * @param val the value
     * @return {@code true} if the set contains {@code val}
     *         and {@code false} otherwise
     */
    bool contains(Value val) {
        return contains(root, val);
    }

    /**
     * Inserts the specified value into the set, allowing for duplicates.
     *
     * @param val the value
     */
    void add(Value val) {
        root = add(root, val);
        root->color = BLACK;
    }

    /**
     * Removes the specified value from the set
     *
     * @param val the value
     */
    void remove(Value val) {
        if (!contains(val)) return;
        if (!isRed(root->left) && !isRed(root->right)) root->color = RED;
        root = remove(root, val);
        if (!isEmpty()) root->color = BLACK;
    }

    /**
     * Removes the smallest value from the symbol table.
     *
     * @throws runtime_error if the symbol table is empty
     */
    void removeMin() {
        if (isEmpty()) throw runtime_error("called removeMin() with empty symbol table");
        if (!isRed(root->left) && !isRed(root->right)) root->color = RED;
        root = removeMin(root, true);
        if (!isEmpty()) root->color = BLACK;
    }

    /**
     * Removes the largest value from the symbol table.
     *
     * @throws runtime_error if the symbol table is empty
     */
    void removeMax() {
        if (isEmpty()) throw runtime_error("called removeMax() with empty symbol table");
        if (!isRed(root->left) && !isRed(root->right)) root->color = RED;
        root = removeMax(root, true);
        if (!isEmpty()) root->color = BLACK;
    }

    /**
     * Returns the smallest value in the set.
     *
     * @return the smallest value in the set
     * @throws runtime_error if the set is empty
     */
    Value getMin() {
        if (isEmpty()) throw runtime_error("called getMin() with empty set");
        return getMin(root)->val;
    }

    /**
     * Returns the largest value in the set.
     *
     * @return the largest value in the set
     * @throws runtime_error if the set is empty
     */
    Value getMax() {
        if (isEmpty()) throw runtime_error("called getMax() with empty set");
        return getMax(root)->val;
    }

    /**
     * Returns the largest value in the set less than or equal to {@code val}.
     *
     * @param val the value
     * @return the largest value in the set less than or equal to {@code val}
     * @throws runtime_error if the set is empty
     * @throws no_such_element_exception if there is no value in the set less than or equal to {@code val}
     */
    Value floor(Value val) {
        if (isEmpty()) throw runtime_error("called floor() with empty set");
        Node *x = floor(root, val);
        if (x == nullptr) throw no_such_element_exception("call to floor() resulted in no such value");
        return x->val;
    }

    /**
     * Returns the smallest value in the set greater than or equal to {@code val}.
     *
     * @param val the value
     * @return a pair containing the smallest value in the set greater than or equal to {@code val}
     * @throws runtime_error if the set is empty
     * @throws no_such_element_exception if there is no value in the set greater than or equal to {@code val}
     */
    Value ceiling(Value val) {
        if (isEmpty()) throw runtime_error("called ceiling() with empty set");
        Node *x = ceiling(root, val);
        if (x == nullptr) throw no_such_element_exception("call to ceiling() resulted in no such value");
        return x->val;
    }

    /**
     * Returns the kth smallest value in the set.
     *
     * @param k the order statistic
     * @return the kth smallest value in the set
     * @throws invalid_argument unless {@code k} is between 0 and
     *             {@code size() -1 }
     */
    Value select(int k) {
        if (k < 0 || k >= size()) throw invalid_argument("k is not in range 0 to size");
        return select(root, k)->val;
    }

    /**
     * Returns the number of values in the set strictly less than
     * {@code val}.
     *
     * @param val the value
     * @return the number of values in the set strictly less than
     *         {@code val}
     */
    int getRank(Value val) {
        return getRank(root, val);
    }

    /**
     * Returns all values in the set following an in-order traversal.
     *
     * @return all values in the set following an in-order traversal
     */
    vector<Value> values() {
        vector<Value> queue;
        valuesInOrder(root, queue);
        return queue;
    }

    /**
     * Returns all values in the set in the given range.
     *
     * @param lo the lowest value
     * @param hi the highest value
     * @return all value in the set between {@code lo} (inclusive)
     *         and {@code hi} (exclusive)
     */
    vector<Value> values(Value lo, Value hi) {
        vector<Value> queue;
        values(root, queue, lo, hi);
        return queue;
    }

    void print() {
        print(root);
    }

    /**
     * Returns the number of values in the set in the given range.
     *
     * @param lo minimum endpoint
     * @param hi maximum endpoint
     * @return the number of values in the set between {@code lo}
     *         (inclusive) and {@code hi} (exclusive)
     */
    int size(Value lo, Value hi) {
        if (cmp(hi, lo)) return 0;
        if (contains(hi)) return getRank(hi) - getRank(lo) + 1;
        else return getRank(hi) - getRank(lo);
    }
};

SBT.cpp

class no_such_element_exception: public runtime_error {
public:
    no_such_element_exception(): runtime_error("No such element exists"){}
    no_such_element_exception(string message): runtime_error(message){}
};

// Size Balanced Binary Search (Multi) Set
// Time Complexity:
//   constructor, empty, size: O(1)
//   values: O(N)
//   all other operators: O(log N)
// Memory Complexity: O(N)
template <class Value, class Comparator = less<Value>> struct SBTSet {
    struct Node {
        int l, r, size; Value val;
        Node(const Value &val) : l(-1), r(-1), size(1), val(val) {}
    };
    int root = -1; vector<Node> T; Comparator cmp;
    int Size(int x) { return x == -1 ? 0 : T[x].size; }
    void update(int x) { T[x].size = 1 + Size(T[x].l) + Size(T[x].r); }
    int rotateRight(int x) { int y = T[x].l; T[x].l = T[y].r; T[y].r = x; update(x); update(y); return y; }
    int rotateLeft(int x) { int y = T[x].r; T[x].r = T[y].l; T[y].l = x; update(x); update(y); return y; }
    int maintain(int x, bool flag) {
        if (flag) {
            if (T[x].r == -1) return x;
            else if (Size(T[x].l) < Size(T[T[x].r].l)) { T[x].r = rotateRight(T[x].r); x = rotateLeft(x); }
            else if (Size(T[x].l) < Size(T[T[x].r].r)) x = rotateLeft(x);
            else return x;
        } else {
            if (T[x].l == -1) return x;
            else if (Size(T[x].r) < Size(T[T[x].l].r)) { T[x].l = rotateLeft(T[x].l); x = rotateRight(x); }
            else if (Size(T[x].r) < Size(T[T[x].l].l)) x = rotateRight(x);
            else return x;
        }
        T[x].l = maintain(T[x].l, false); T[x].r = maintain(T[x].r, true); x = maintain(x, true); x = maintain(x, false); return x;
    }
    bool contains(int x, const Value &val) {
        if (x == -1) return false;
        else if (cmp(val, T[x].val)) return contains(T[x].l, val);
        else if (cmp(T[x].val, val)) return contains(T[x].r, val);
        return true;
    }
    int add(int x, const Value &val) {
        if (x == -1) { T.emplace_back(val); return int(T.size()) - 1; }
        if (cmp(val, T[x].val)) { int l = add(T[x].l, val); T[x].l = l; }
        else { int r = add(T[x].r, val); T[x].r = r; }
        update(x); return maintain(x, !cmp(val, T[x].val));
    }
    int removeMin(int x) {
        if (T[x].l == -1) return T[x].r;
        T[x].l = removeMin(T[x].l); update(x); return x;
    }
    int removeMax(int x) {
        if (T[x].r == -1) return T[x].l;
        T[x].r = removeMax(T[x].r); update(x); return x;
    }
    int getMin(int x) { return T[x].l == -1 ? x : getMin(T[x].l); }
    int getMax(int x) { return T[x].r == -1 ? x : getMax(T[x].r); }
    int remove(int x, const Value &val) {
        if (cmp(val, T[x].val)) T[x].l = remove(T[x].l, val);
        else if (cmp(T[x].val, val)) T[x].r = remove(T[x].r, val);
        else {
            if (T[x].l == -1) return T[x].r;
            else if (T[x].r == -1) return T[x].l;
            else { int y = x; x = getMin(T[y].r); T[x].r = removeMin(T[y].r); T[x].l = T[y].l; }
        }
        update(x); return x;
    }
    int floor(int x, const Value &val) {
        if (x == -1) return 0;
        if (!cmp(val, T[x].val) && !cmp(T[x].val, val)) return x;
        if (cmp(val, T[x].val)) return floor(T[x].l, val);
        int y = floor(T[x].r, val); return y == -1 ? x : y;
    }
    int ceiling(int x, const Value &val) {
        if (x == -1) return 0;
        if (!cmp(val, T[x].val) && !cmp(T[x].val, val)) return x;
        if (cmp(T[x].val, val)) return ceiling(T[x].r, val);
        int y = ceiling(T[x].l, val); return y == -1 ? x : y;
    }
    int select(int x, int k) {
        if (x == -1) return 0;
        int t = Size(T[x].l);
        if (t > k) return select(T[x].l, k);
        else if (t < k) return select(T[x].r, k - t - 1);
        return x;
    }
    int getRank(int x, const Value &val) { // number of values less than first occurrence
        if (x == -1) return 0;
        if (!cmp(T[x].val, val)) return getRank(T[x].l, val);
        else return 1 + Size(T[x].l) + getRank(T[x].r, val);
    }
    void valuesInOrder(int x, vector<Value> &queue) {
        if (x == -1) return;
        valuesInOrder(T[x].l, queue); queue.push_back(T[x].val); valuesInOrder(T[x].r, queue);
    }
    void values(int x, vector<Value> &queue, const Value &lo, const Value &hi) {
        if (x == -1) return;
        if (cmp(lo, T[x].val)) values(T[x].l, queue, lo, hi);
        if (!cmp(T[x].val, lo) && !cmp(hi, T[x].val)) queue.push_back(T[x].val);
        if (cmp(T[x].val, hi)) values(T[x].r, queue, lo, hi);
    }
    void clear() { root = 0; T.clear(); }
    bool empty() { return root == 0; }
    int size() { return Size(root); }
    bool contains(const Value &val) { return contains(root, val); }
    void add(const Value &val) { root = add(root, val); }
    void remove(const Value &val) { if (contains(val)) root = remove(root, val); }
    void removeMin() {
        if (empty()) throw runtime_error("called removeMin() with empty symbol table");
        root = removeMin(root);
    }
    void removeMax() {
        if (empty()) throw runtime_error("called removeMax() with empty symbol table");
        root = removeMax(root);
    }
    Value getMin() {
        if (empty()) throw runtime_error("called getMin() with empty symbol table");
        return T[getMin(root)].val;
    }
    Value getMax() {
        if (empty()) throw runtime_error("called getMax() with empty symbol table");
        return T[getMax(root)].val;
    }
    Value floor(const Value &val) {
        if (empty()) throw runtime_error("called floor() with empty symbol table");
        int x = floor(root, val);
        if (x == -1) throw no_such_element_exception("call to floor() resulted in no such value");
        return T[x].val;
    }
    Value ceiling(const Value &val) {
        if (empty()) throw runtime_error("called ceiling() with empty symbol table");
        int x = ceiling(root, val);
        if (x == -1) throw no_such_element_exception("call to ceiling() resulted in no such value");
        return T[x].val;
    }
    Value select(int k) {
        if (k < 0 || k >= size()) throw invalid_argument("k is not in range 0 to size");
        return T[select(root, k)].val;
    }
    int getRank(const Value &val) { return getRank(root, val); }
    vector<Value> values() { vector<Value> queue; valuesInOrder(root, queue); return queue; }
    vector<Value> values(const Value &lo, const Value &hi) { vector<Value> queue; values(root, queue, lo, hi); return queue; }
    int size(const Value &lo, const Value &hi) {
        if (cmp(hi, lo)) return 0;
        else if (contains(hi)) return getRank(hi) - getRank(lo) + 1;
        else return getRank(hi) - getRank(lo);
    }
};

SPLAY.cpp

struct Node {
    Node *l, *r, *p; int size, val;
    Node(int val = 0) : l(nullptr), r(nullptr), p(nullptr), size(1), val(val) {}
    void update();
    void rotate(Node *rootP);
    void splay(Node *rootP);
};
int Size(Node *x) { return x ? x->size : 0; }
void Node::update() { size = 1 + Size(l) + Size(r); }
void connect(Node *ch, Node *par, bool isL) {
    if (ch) ch->p = par;
    if (par) {
        if (isL) par->l = ch;
        else par->r = ch;
    }
}
void Node::rotate(Node *rootP) {
    Node *p = this->p, *g = p->p; bool isRootP = g == rootP, isL = this == p->l;
    connect(isL ? r : l, p, isL); connect(p, this, !isL); connect(this, g, isRootP ? false : p == g->l); p->update();
}
void Node::splay(Node *rootP) {
    while (p != rootP) {
        Node *p = this->p, *g = p->p;
        if (g != rootP) ((this == p->l) == (p == g->l) ? p : this)->rotate(rootP);
        rotate(rootP);
    }
    update();
}
Node T[int(6e5 + 5)], *root = nullptr; int cur = 0;
Node *select(Node *x, int k) {
    if (!x) return nullptr;
    int t = Size(x->l);
    if (t > k) return select(x->l, k);
    else if (t < k) return select(x->r, k - t - 1);
    return x;
}
int select(int k) { return select(root, k)->val; }
Node *last = nullptr;
Node *get(Node *x, int val) {
    if (!x) return nullptr;
    last = x;
    if (val < x->val) return get(x->l, val);
    else if (val > x->val) return get(x->r, val);
    return x;
}
Node *get(int val) {
    last = nullptr; Node *x = get(root, val);
    if (last) (root = last)->splay(nullptr);
    return x;
}
Node *getMin(Node *x) { return x->l ? getMin(x->l) : x; }
int getRank(Node *x, int val) {
    if (!x) return 0;
    if (x->val >= val) return getRank(x->l, val);
    else return 1 + Size(x->l) + getRank(x->r, val);
}
int getRank(int val) {
    Node *x = get(val);
    if (!x) return -1;
    (root = x)->splay(nullptr);
    return getRank(root, val);
}
Node *build(int l, int r, vector<int> &A) {
    if (l > r) return nullptr;
    int m = l + (r - l) / 2, i = cur; T[cur++] = Node(A[m]);
    Node *left = build(l, m - 1, A), *right = build(m + 1, r, A), *x = &(T[i]);
    connect(left, x, true); connect(right, x, false); x->update();
    return x;
}
void build(vector<int> &A) { root = build(0, int(A.size()) - 1, A); }
Node *add(Node *x, int val) {
    if (!x) { return &(T[cur++] = Node(val)); }
    if (val < x->val) connect(add(x->l, val), x, true);
    else connect(add(x->r, val), x, false);
    x->update(); return x;
}
void add(int val) { root = add(root, val); T[cur - 1].splay(nullptr); root = &(T[cur - 1]); }
void remove(int val) {
    Node *x = get(val);
    if (!x) return;
    x->splay(nullptr);
    if (!x->l) root = x->r;
    else if (!x->r) root = x->l;
    else { getMin(x->r)->splay(x); connect(x->l, root = x->r, true); }
    connect(root, nullptr, true);
}
void values(Node *x, vector<int> &A) {
    if (x) { values(x->l, A); A.push_back(x->val); values(x->r, A); }
}
void values(vector<int> &A) { values(root, A); }

wesley.cpp

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;using namespace std::placeholders;using namespace __gnu_pbds;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define all(a) (a).begin(),(a).end()
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(auto i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
#define FORE(i,a) for(auto&&i:a)
template<class C>constexpr int sz(const C&c){return int(c.size());}
using ll=long long;using ld=long double;using uint=unsigned int;using ull=unsigned long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pill=pair<int,ll>;using plli=pair<ll,int>;using pdd=pair<double,double>;using pld=pair<ld,ld>;
constexpr const char nl='\n',sp=' ';constexpr const int INT_INF=0x3f3f3f3f;constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f;
constexpr const double D_INF=numeric_limits<double>::infinity();constexpr const ld LD_INF=numeric_limits<ld>::infinity();
template<class T>constexpr const T&_min(const T&x,const T&y){return x<y?x:y;}template<class T>constexpr const T&_max(const T&x,const T&y){return x<y?y:x;}
template<class T,class...Ts>constexpr const T&_min(const T&x,const Ts&...xs){return _min(x,_min(xs...));}
template<class T,class...Ts>constexpr const T&_max(const T&x,const Ts&...xs){return _max(x,_max(xs...));}
template<class T,class...Ts>void MIN(T&x,const Ts&...xs){x=_min(x,xs...);}template<class T,class...Ts>void MAX(T&x,const Ts&...xs){x=_max(x,xs...);}
template<class T>constexpr const T&_clamp(const T&v,const T&lo,const T&hi){return v<lo?lo:hi<v?hi:v;}template<class T>void CLAMP(T&v,const T&lo,const T&hi){v=_clamp(v,lo,hi);}
template<class T,class...Args>unique_ptr<T>_make_unique(Args&&...args){return unique_ptr<T>(new T(forward<Args>(args)...));}
template<class T,class...Args>shared_ptr<T>_make_shared(Args&&...args){return shared_ptr<T>(new T(forward<Args>(args)...));}
#define min(...) _min(__VA_ARGS__)
#define max(...) _max(__VA_ARGS__)
#define clamp(...) _clamp(__VA_ARGS__)
#define make_unique _make_unique
#define make_shared _make_shared
seed_seq seq {
    (uint64_t)chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
    (uint64_t)__builtin_ia32_rdtsc(),(uint64_t)(uintptr_t)make_unique<char>().get()
};
mt19937 rng(seq);mt19937_64 rng64(seq);const size_t RANDOM=uniform_int_distribution<size_t>(0,(numeric_limits<size_t>::max)())(rng64);
template<class T,class H=hash<T>>struct rand_hash{
    static uint64_t splitmix64(uint64_t x){x+=0x9e3779b97f4a7c15;x=(x^(x>>30))*0xbf58476d1ce4e5b9;x=(x^(x>>27))*0x94d049bb133111eb;return x^(x>>31);}
    size_t operator()(const T&x)const{return splitmix64(H{}(x)+RANDOM);}
};
template<class K,class H=rand_hash<K>,class...Ts>using hashset=gp_hash_table<K,null_type,H,Ts...>;
template<class K,class V,class H=rand_hash<K>,class...Ts>using hashmap=gp_hash_table<K,V,H,Ts...>;
template<class K,class C=less<K>,class...Ts>using treeset=tree<K,null_type,C,rb_tree_tag,tree_order_statistics_node_update,Ts...>;
template<class K,class V,class C=less<K>,class...Ts>using treemap=tree<K,V,C,rb_tree_tag,tree_order_statistics_node_update,Ts...>;
template<class K,class H=rand_hash<K>,class...Ts>using uset=unordered_set<K,H,Ts...>;template<class K,class V,class H=rand_hash<K>,class...Ts>using umap=unordered_map<K,V,H,Ts...>;
template<class T>using minpq=std::priority_queue<T,vector<T>,greater<T>>;template<class T>using maxpq=std::priority_queue<T,vector<T>,less<T>>;
template<class T>using minpairingheap=__gnu_pbds::priority_queue<T,greater<T>,pairing_heap_tag>;template<class T>using maxpairingheap=__gnu_pbds::priority_queue<T,less<T>,pairing_heap_tag>;
template<class T1,class T2,class H1=rand_hash<T1>,class H2=rand_hash<T2>>struct pair_hash{size_t operator()(const pair<T1,T2>&p)const{return 31*H1{}(p.first)+H2{}(p.second);}};
template<class T>struct is_iterator {
    template<class U,typename enable_if<!is_convertible<U,const char*>::value,int>::type=0>constexpr static auto has_indirection(int)->decltype(*declval<U>(),bool()){return true;}
    template<class>constexpr static bool has_indirection(long){return false;}constexpr static bool value=has_indirection<T>(0);
};

#define INTERACTIVE_INPUT 0
constexpr const int _bufferSize=1<<16,_maxNumLength=128;
char _inputBuffer[_bufferSize+1],*_inputPtr=_inputBuffer,_outputBuffer[_bufferSize],_c,_sign,*_tempInputBuf=nullptr,_numBuf[_maxNumLength],_tempOutputBuf[_maxNumLength],_fill=' ';
FILE*_input=stdin,*_output=stdout,*_error=stderr;const char*_delimiter=" ";int _cur,_outputPtr=0,_numPtr=0,_precision=6,_width=0,_tempOutputPtr=0,_cnt;ull _precisionBase=1000000;
#ifdef _WIN32
    #define getchar_unlocked getchar
    #define fread_unlocked fread
    #define fwrite_unlocked fwrite
#endif
#if INTERACTIVE_INPUT
    #define _getchar() getchar_unlocked()
#else
    #define _peekchar() (*_inputPtr?*_inputPtr:(_inputBuffer[fread_unlocked(_inputPtr=_inputBuffer,1,_bufferSize,_input)]='\0',*_inputPtr))
    #define _getchar() (*_inputPtr?*_inputPtr++:(_inputBuffer[fread_unlocked(_inputPtr=_inputBuffer,1,_bufferSize,_input)]='\0',*_inputPtr++))
    #define _hasNext() (*_inputPtr||!feof(_input))
    bool hasNext(){while(_hasNext()&&_peekchar()<=' ')_getchar();return _hasNext();}bool hasNextLine(){while(_hasNext()&&_peekchar()=='\r')_getchar();return _hasNext();}
#endif
#define _readSignAndNum(x) while(((x)=_getchar())<=' ');_sign=(x)=='-';if(_sign)(x)=_getchar();for((x)-='0';(_c=_getchar())>='0';(x)=(x)*10+_c-'0')
#define _readFloatingPoint(x,T) for(T _div=1.0;(_c=_getchar())>='0';(x)+=(_c-'0')/(_div*=10))
#define rc(x) do{while(((x)=_getchar())<=' ');}while(0)
#define ri(x) do{_readSignAndNum(x);if(_sign)(x)=-(x);}while(0)
#define rd(x) do{_readSignAndNum(x);if(_c=='.')_readFloatingPoint(x,double);if(_sign)(x)=-(x);}while(0)
#define rld(x) do{_readSignAndNum(x);if(_c=='.')_readFloatingPoint(x,ld);if(_sign)(x)=-(x);}while(0)
#define rcs(x) do{_cur=0;do{_c=_getchar();}while(_c<=' ');do{(x)[_cur++]=_c;}while((_c=_getchar())>' ');(x)[_cur]='\0';}while(0)
#define rs(x) do{if(!_tempInputBuf)assert(0);rcs(_tempInputBuf);(x)=string(_tempInputBuf,_cur);}while(0)
#define rcln(x) do{while(_inputPtr!=_inputBuffer&&*(_inputPtr-1)=='\r')_getchar();_cur=0;while((_c=_getchar())!='\n'&&_c){if(_c!='\r')(x)[_cur++]=_c;}(x)[_cur]='\0';}while(0)
#define rln(x) do{if(!_tempInputBuf)assert(0);rcln(_tempInputBuf);(x)=string(_tempInputBuf,_cur);}while(0)
void setLength(int x){if(_tempInputBuf)delete[](_tempInputBuf);_tempInputBuf=new char[x+1];}
void read(int&x){ri(x);}void read(uint&x){ri(x);}void read(ll&x){ri(x);}void read(ull&x){ri(x);}void read(double&x){rd(x);}void read(ld&x){rld(x);}
void read(char&x){rc(x);}void read(char*x){rcs(x);}void read(string&x){rs(x);}void readln(char*x){rcln(x);}void readln(string&x){rln(x);}
template<class T1,class T2>void read(pair<T1,T2>&x){read(x.first);read(x.second);}template<class T>void read(complex<T>&x){T _re,_im;read(_re);read(_im);x.real(_re);x.imag(_im);}
template<class T>void read(T&x);template<class T,class...Ts>void read(T&x,Ts&&...xs);
template<class It>typename enable_if<is_iterator<It>::value>::type read(It st,It en){for(It _i=st;_i!=en;_i++)read(*_i);}
template<class It,class...Ts>typename enable_if<is_iterator<It>::value>::type read(It st,It en,Ts&&...xs){read(st,en);read(forward<Ts>(xs)...);}
template<class T>void read(T&x){for(auto&&_i:x)read(_i);}template<class T,class...Ts>void read(T&x,Ts&&...xs){read(x);read(forward<Ts>(xs)...);}
void setInput(FILE*file){*_inputPtr='\0';_input=file;}void setInput(const char*s){*_inputPtr='\0';_input=fopen(s,"r");}void setInput(const string&s){*_inputPtr='\0';_input=fopen(s.c_str(),"r");}
#define _flush() do{_flushBuf();fflush(_output);}while(0)
#define _flushBuf() (fwrite_unlocked(_outputBuffer,1,_outputPtr,_output),_outputPtr=0)
#define _putchar(x) (_outputBuffer[_outputPtr==_bufferSize?_flushBuf():_outputPtr]=(x),_outputPtr++)
#define _writeTempBuf(x) (_tempOutputBuf[_tempOutputPtr++]=(x))
#define _writeOutput() for(int _i=0;_i<_tempOutputPtr;_putchar(_tempOutputBuf[_i++]));_tempOutputPtr=0
#define _writeNum(x,T,digits) _cnt=0;for(T _y=(x);_y;_y/=10,_cnt++)_numBuf[_numPtr++]='0'+_y%10;for(;_cnt<digits;_cnt++)_numBuf[_numPtr++]='0';_flushNumBuf();
#define _writeFloatingPoint(x,T) ull _I=(ull)(x);ull _F=((x)-_I)*_precisionBase+(T)(0.5);if(_F>=_precisionBase){_I++;_F=0;}_writeNum(_I,ull,1);_writeTempBuf('.');_writeNum(_F,ull,_precision)
#define _checkFinite(x) if(std::isnan(x)){wcs("NaN");}else if(std::isinf(x)){wcs("Inf");}
#define _flushNumBuf() for(;_numPtr;_writeTempBuf(_numBuf[--_numPtr]))
#define _fillBuf(x) for(int _i=0;_i<(x);_i++)_putchar(_fill)
#define _flushTempBuf() int _tempLen=_tempOutputPtr;_fillBuf(_width-_tempLen);_writeOutput();_fillBuf(-_width-_tempLen)
#define wb(x) do{if(x)_writeTempBuf('1');else _writeTempBuf('0');_flushTempBuf();}while(0)
#define wc(x) do{_writeTempBuf(x); _flushTempBuf();}while(0)
#define wi(x) do{if((x)<0){_writeTempBuf('-');_writeNum(-(x),uint,1);}else{_writeNum(x,uint,1);}_flushTempBuf();}while(0)
#define wll(x) do{if((x)<0){_writeTempBuf('-');_writeNum(-(x),ull,1);}else{_writeNum(x,ull,1);}_flushTempBuf();}while(0)
#define wd(x) do{_checkFinite(x)else if((x)<0){_writeTempBuf('-');_writeFloatingPoint(-(x),double);}else{_writeFloatingPoint(x,double);}_flushTempBuf();}while(0)
#define wld(x) do{_checkFinite(x)else if((x)<0){_writeTempBuf('-');_writeFloatingPoint(-(x),ld);}else{_writeFloatingPoint(x,ld);}_flushTempBuf();}while(0)
#define wcs(x) do{int _slen=strlen(x);_fillBuf(_width-_slen);for(const char*_p=(x);*_p;_putchar(*_p++));_fillBuf(-_width-_slen);}while(0)
#define ws(x) do{_fillBuf(_width-int((x).length()));for(int _i=0;_i<int((x).length());_putchar(x[_i++]));_fillBuf(-_width-int((x).length()));}while(0)
void setPrecision(int x){_precision=x;_precisionBase=1;for(int _i=0;_i<x;_i++,_precisionBase*=10);}void setWidth(int x){_width=x;}void setFill(char x){_fill=x;}
void setDelimiter(const char*x){_delimiter=x;}void setDelimiter(const string&x){_delimiter=x.c_str();}
void writeDelimiter(){for(const char*_p=_delimiter;*_p;_putchar(*_p++));}
void write(const bool&x){wb(x);}void write(const int&x){wi(x);}void write(const uint&x){wi(x);}void write(const ll&x){wll(x);}void write(const ull&x){wll(x);}
void write(const double&x){wd(x);}void write(const ld&x){wld(x);}void write(const char&x){wc(x);}void write(const char*x){wcs(x);}void write(const string&x){ws(x);}
template<class T1,class T2>void write(const pair<T1,T2>&x){write(x.first);writeDelimiter();write(x.second);}
template<class T>void write(const complex<T>&x){write(x.real());writeDelimiter();write(x.imag());}
template<class T>void write(const T&x);template<class T,class...Ts>void write(const T&x,Ts&&...xs);
template<class It>typename enable_if<is_iterator<It>::value>::type write(It st,It en){bool _first=1;for(It _i=st;_i!=en;_i++){if(_first)_first=0;else writeDelimiter();write(*_i);}}
template<class It,class...Ts>typename enable_if<is_iterator<It>::value>::type write(It st,It en,Ts&&...xs){write(st,en);writeDelimiter();write(forward<Ts>(xs)...);}
template<class T>void write(const T&x){bool _first=1;for(auto&&_i:x){if(_first)_first=0;else writeDelimiter();write(_i);}}
template<class T,class...Ts>void write(const T&x,Ts&&...xs){write(x);writeDelimiter();write(forward<Ts>(xs)...);}
void writeln(){_putchar('\n');}template<class...Ts>void writeln(Ts&&...xs){write(forward<Ts>(xs)...);_putchar('\n');}
void flush(){_flush();}class IOManager{public:~IOManager(){flush();if(_tempInputBuf)delete[](_tempInputBuf);}};unique_ptr<IOManager>iomanager=make_unique<IOManager>();
void setOutput(FILE*file){flush();_output=file;}void setOutput(const char*s){flush();_output=fopen(s,"w");}void setOutput(const string&s){flush();_output=fopen(s.c_str(),"w");}
template<class...Ts>void debug(const Ts&...xs){FILE*_temp=_output;setOutput(_error);write(xs...);setOutput(_temp);}
template<class...Ts>void debugln(const Ts&...xs){FILE*_temp=_output;setOutput(_error);writeln(xs...);setOutput(_temp);}
void setError(FILE*file){flush();_error=file;}void setError(const char*s){flush();_error=fopen(s,"w");}void setError(const string&s){flush();_error=fopen(s.c_str(),"w");}