NamPE286

#include <bits/stdc++.h>

using namespace std;

class Treap {
   private:
    struct Node {
        int priority;
        int count;
        int value;

NamPE286

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class Node {
   public:
    ll value;
    int l, r;
    shared_ptr<Node> left;

NamPE286

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class SegmentTree {
    struct Node {
        pair<ll, ll> range;
        ll left = 0, right = 0, value = INT_MAX;
    };

NamPE286

// https://codeforces.com/problemset/problem/342/E

#include <bits/stdc++.h>

using namespace std;
typedef int ll;

const ll INF = 1e9;

class Tree {

NamPE286

// https://cses.fi/problemset/result/7855807/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class BinaryLifting {
    vector<vector<ll>> graph;
    vector<vector<ll>> parent;

NamPE286

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class MergeSortTreeImmutable {
    struct Node {
        vector<ll> v;
        pair<ll, ll> range;
        Node* left = nullptr;

NamPE286

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class DSU {
    vector<ll> p;             // parent if positive, size if negative, parent of root is the size of component
    stack<pair<ll, ll>> log;  // keep track of p[i] value history, first is index, second is value
    stack<ll> size;

NamPE286

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class DFSTree {
    vector<ll> nums, low;
    vector<bool> deleted;
    stack<ll> st;
    vector<ll> scc;

NamPE286

#include <bits/stdc++.h>

using namespace std;
typedef int ll;

class SegmentTree {
    struct Node {
        pair<ll, ll> range;
        ll left = 0, right = 0, value = 0;
    };

NamPE286

// https://cses.fi/problemset/task/1647

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class SparseTable {
   private:
    vector<vector<ll>> ST;