macros.cpp

//--------------------------------------
// clang-format off
#ifndef MACROS
#define MACROS
#include <bits/stdc++.h>
using namespace std;
//--------------- MACROS ---------------
#ifdef LOCAL
    #define exeLOCAL(...)  __VA_ARGS__; 
    #define exeFUERA(...)  // do nothing
#else
    #define exeLOCAL(...)  // do nothing
    #define exeFUERA(...)  __VA_ARGS__; 
#endif

// Macros for colors
#define RESET "\033[0m"
#define COLOR(c, ...) c, __VA_ARGS__, RESET
#define RED(...)     COLOR("\033[1;31m", __VA_ARGS__)
#define GREEN(...)   COLOR("\033[1;32m", __VA_ARGS__)
#define YELLOW(...)  COLOR("\033[1;33m", __VA_ARGS__)
#define BLUE(...)    COLOR("\033[1;34m", __VA_ARGS__)
#define MAGENTA(...) COLOR("\033[1;35m", __VA_ARGS__)
#define CIAN(...)    COLOR("\033[1;36m", __VA_ARGS__)

using u64 = unsigned long long;
using uint = unsigned int;
using u32 = unsigned int;
using u16 = uint16_t;
using u8 = uint8_t;

using realint = int;
#define int ll
using ll = long long;



#define CONCAT2(a, b) a##b
#define CONCAT(a, b) CONCAT2(a, b)

#define LINEVAR(base) CONCAT(base, __LINE__)

template <typename T>
std::vector<T> operator+(const std::vector<T>& a,
                         const std::vector<T>& b) {
    std::vector<T> res;
    res.reserve(a.size() + b.size());
    res.insert(res.end(), a.begin(), a.end());
    res.insert(res.end(), b.begin(), b.end());
    return res;
}


template <typename T>
struct vvt : public vector<vector<T>> {
    using vector<vector<T>>::vector;
    vvt(int h, int w, const T& value = T()) {
        this->resize(h, vector<T>(w, value));
    }
};

template <typename T>
struct vvvt : public vector<vector<vector<T>>> {
    using vector<vector<vector<T>>>::vector;
    vvvt(int h, int w, int d, const T& value = T()) {
        this->resize(h, vvt<T>(w, d, value));
    }
};


using ld = long double;

using pii = pair<int, int>;

using vi = vector<int>;
using vvi = vvt<int>;
using vvvi = vvvt<int>;

using vb = vector<bool>;
using vvb = vvt<bool>;

using vpii = vector<pii>;
using vvpii = vvt<pii>;

template <typename T> using vt = vector<T>;

// tipos de datos no constructores
#define ar(T, n) array<T, n>
#define aar(T, n, m) array<array<T, m>, n>
#define aaar(T, n, m, l) array<array<array<T, l>, m>, n>

template <class T> using pqmax = priority_queue<T>;
template <class T> using pqmin = priority_queue<T, vector<T>, greater<T>>;

using sti = set<int>;

using vs = vector<string>;
using vvs = vvt<string>;

template <class T> using uset = unordered_set<T>;
template <class T> using umset = unordered_multiset<T>;
template <typename T1, typename T2> using umap = unordered_map<T1, T2>;

using unif = uniform_int_distribution<int>;
random_device fuente; mt19937 gen(fuente());

// #define vv(T, name, h, ...) vvt<T> name(h, vt<T>(__VA_ARGS__))
// #define vvv(T, name, h, w, ...) vvvt<T> name(h, vvt<T>(w, vt<T>(__VA_ARGS__)))

/* 1 mas grande */ 
inline int topbit(int x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); };
inline int countbits(int x) { return __builtin_popcountll(x); };
inline int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctzll(x)); };
inline bool getBit(int n, int i){ return (n >> i) & 1; };
inline int setBit(int n, int i) { return n | (1 << i); };
inline int clearBit(int n, int i) {return n & ~(1 << i); }
inline int flipBit(int n, int i) { return n ^ (1 << i); }


template <typename T> ostream& operator<<(ostream& os, const vvt<T>& vec); template <typename T> ostream& operator<<(ostream& os, const set<T>& st); template <typename T> istream& operator>>(istream& is, vector<T>& vec);template <typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p);
template <typename T> 
istream& operator>>(istream& is, vector<T>& vec) {
    for (auto& elem : vec) is >> elem;
    return is;
};
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
};

template <typename T>
ostream& operator<<(ostream& os, const set<T>& st) {
    if (st.empty()) return os;
    auto it = st.begin();
    for (int i = 0; i < st.size() - 1; ++i, ++it) os << *it << " ";
    return os << *it;
};
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << p.first << " " << p.second; };
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    if (vec.empty()) {
        return os;
    }
    for (int i = 0; i < vec.size() - 1; ++i) {
        os << vec[i] << " ";
    };
    return os << vec.back();
};
template <typename T>
ostream& operator<<(ostream& os, const vvt<T>& vec) {
    if (vec.empty()) {
        return os;
    }
    for (int i = 0; i < vec.size()-1; ++i) {
        os << vec[i] << "\n";
    };
    return os << vec.back();
};

void putAux(ostream&, string, string) {
    return;
};

template <typename T>
void putAux(ostream& os, string, string last, const T t) { 
    os << t << last; 
};

template <typename T, typename... TAIL>
void putAux(ostream& os, string middle, string last, const T t, TAIL... tail) {
    os << t << middle;
    putAux(os, forward<string>(middle), forward<string>(last), forward<TAIL>(tail)...);
};


#define STRINGIFY_HELPER(...) #__VA_ARGS__
#define STRINGIFY(...) STRINGIFY_HELPER(__VA_ARGS__)

#define lput(...) exeLOCAL(putAux(cerr, " ", "\n", __VA_ARGS__))
#define putd(...) lput(STRINGIFY(__VA_ARGS__), "\b:", __VA_ARGS__)
#define RAYA lput("------------------------")

#define put(...) putAux(cout, " ", "\n", __VA_ARGS__)
#define pute(...) putAux(cout, " ", " ", __VA_ARGS__)
#define putb(...) put((__VA_ARGS__) ? "YES" : "NO")
#define putf(...) put(__VA_ARGS__); cout.flush()


void cinall() {};
template <class T, class... ARGS>
void cinall(T& t, ARGS&... args) {
    cin >> t;
    cinall(args...);
};

#define UNWRAP(X) ESC(ISH X)
#define ISH(...) ISH __VA_ARGS__
#define ESC(...) ESC_(__VA_ARGS__)
#define ESC_(...) VAN ## __VA_ARGS__
#define VANISH

#define rd(...)  __VA_ARGS__; cinall(__VA_ARGS__)
#define pb push_back
#define ppb pop_back
#define len(x) (int)(x.size())
#define forv(i, v) for (int i = 0ll; i < len(v); ++i)
#define forn1(n) for (int _ = 0ll; _ < (n); ++_)
#define forn2(i, n) for (int i = 0ll; i < (n); ++i)
#define forn3(i, a, n) for (int i = (a); i < (n); ++i)
#define forn4(i, a, n, s) for (int i = (a); i < (n); i += (s))

#define forin(i, ...) for(int i = -1; i == -1; ++i) for(__VA_ARGS__) if(++i || true)


// #define forbit(i, x) for(u64 _tb = topbit(x), i = 0; i <= _tb; ++i) if(((x) >> i) & 1UL)  
#define forbit(i, x) for(u64 i = lowbit(x), _x = (x); _x; _x -= (1ll << i), i = lowbit(_x))  

#define partes(vbits, vbits_inicial) for (int vbits = (vbits_inicial); vbits >= 0; vbits = (vbits == 0 ? -1 : (vbits - 1) & (vbits_inicial)))
#define forch(x, n, k) for(u64 _a, _b, _c, x = (1UL << (k)) - 1UL; x < (1UL << (n)); _a = x & -x, _b = x + _a, _c = _c = ((x ^ _b) / _a) >> 2, x = _b | _c) 

#define permutaciones(v) sortv(v); for(int _ = 0; _ == 0;) while(_++ == 0 || next_permutation(all(v))) 

#define CONCAT2(a, b) a##b
#define CONCAT(a, b) CONCAT2(a, b)

#define lineVar(base) CONCAT(base, __LINE__)

#define overload2(a, b, c, ...) c
#define overload4(a, b, c, d, e, ...) e

// -----------------------------------------------
#define NOT(...) (!(__VA_ARGS__))
#define ifnot(...) if(!(__VA_ARGS__))

jmp_buf __JMP_AUX__;
bool __BOOL_CJMP_AUX__;

// #define GET_COUNTER (__COUNTER__ + 0)
// #define UNIQUE_NAME(base) base##__COUNTER__
// #define GET_VAR(base) base##GET_COUNTER

#define control_flow(check, ...) __BOOL_CJMP_AUX__ = (check); if(__BOOL_CJMP_AUX__ && setjmp(__JMP_AUX__) != 0){ __VA_ARGS__;} else for (; __BOOL_CJMP_AUX__; longjmp(__JMP_AUX__, 1))
#define contif(check) control_flow((check), continue)
#define breakif(check) control_flow((check), break)

#define retif1(check) control_flow((check), return)
#define retif2(check, ...) control_flow((check), return __VA_ARGS__)
#define retif(...) overload2(__VA_ARGS__, retif2, retif1)(__VA_ARGS__)

// -----------------------------------------------
#define forn(...) overload4(__VA_ARGS__, forn4, forn3, forn2, forn1)(__VA_ARGS__)

#define dowhile(i, inicializar, b, ...) for(int LINEVAR(f) = 1, i = -1; i == -1;) for( inicializar ; ++i >= 0 && LINEVAR(f) && (b) || LINEVAR(f)--; __VA_ARGS__)

#define forc(i, a, n, ...) for (int i = (a); i < (n); ++i) if (__VA_ARGS__)
#define forb(i, a, n, b) for (int i = (a); i < (n) && (b); ++i)
#define forr(i, n, a) for (int i = (n); i >= (a); --i)

#define inf ((int)3e18)
#define infll ((int)3e18)
#define infi ((int)3e18)

#define all(v) v.begin(), v.end()
#define revv(x) reverse(all(x))
#define sortv(v) sort(all(v))
#define sortvc(v, ...) sort(all(v), __VA_ARGS__)
// modo de uso, x es el elemento de x filterv(algun vector<t>, (condicion para x))
#define filterv(v, ...) v.erase(remove_if(all(v), [&](auto& x) { return (__VA_ARGS__); }), v.end())
#define filterc(v, newv, ...) auto newv = v; filterv(newv, (__VA_ARGS__))
/*defino las funciones de antemano para evitar problemas con el orden*/ 


template <typename T>
inline bool mineq(T& a, T b) { return (b < a ? a = b, true : false); };

template <typename T>
inline bool maxeq(T& a, T b) { return (a < b ? a = b, true : false); };

template <typename T>
inline bool even(T x) {return (x % 2) == 0;};

template <typename F>
int binary(F check, int ok, int ng, bool check_ok = true) {
  if (check_ok) assert(check(ok));
  while (abs(ok - ng) > 1) {
    auto x = (ng + ok) / 2;
    (check(x) ? ok : ng) = x;
  }
  return ok;
}


/*
 lowbp({1,3,3,5}, 2) = 1
 lowbp({1,3,3,5}, 3) = 1
 lowbp({1,3,3,5}, 6) = 4
 */
template <typename T>
int lowbp(vt<T>& v, T e) { 
    return distance(v.begin(), lower_bound(all(v), e)); 
};

/*
 uppbpos({1,3,3,5}, 2) = 1
 uppbpos({1,3,3,5}, 3) = 3
 uppbpos({1,3,3,5}, 6) = 4
 */
template <typename T>
int uppbpos(vt<T>& v, T e) {
    return distance(v.begin(), upper_bound(all(v), e));
};

/*
 lowb({1,3,3,5}, 2, inf) = 3
 lowb({1,3,3,5}, 3, inf) = 3
 lowb({1,3,3,5}, 6, inf) = inf
 */
template <typename T>
T lowb(vt<T>& v, T x, T mx) {
    auto it = lower_bound(all(v), (x));
    return it == v.end() ? mx : *it;
};

/*
 Si querés la posición del anterior a x en v simplemente lowbp(v, x)-1
 llowb({1,3,3,5}, 2, -inf) = 1
 llowb({1,3,3,5}, 3, -inf) = 1
 llowb({1,3,3,5}, 1, -inf) = -inf
 */
template <typename T>
T llowb(vt<T>& v, T x, T mn) {
    int pos = lowbp(v, x);
    if (pos == 0) return mn;
    return v[pos - 1];
};

/*
 uppb({1,3,3,5}, 2, inf) = 3
 uppb({1,3,3,5}, 3, inf) = 5
 uppb({1,3,3,5}, 6, inf) = inf
 */
template <typename T>
T uppb(vt<T>& v, T x, T mx) {
    auto it = upper_bound(all(v), (x));
    return it == v.end() ? mx : *it;
};


template <typename Container>
inline auto minv(Container& v) {return *min_element(all(v));};

template <typename Container>
inline auto minv(Container& v, int hasta) {return *min_element(v.begin(), v.begin() + hasta);};

template <typename Container>
inline auto minv(Container& v, int desde, int hasta) {return *min_element(v.begin()+desde, v.begin() + hasta);};

template <typename Container>
inline auto maxv(Container& v) {return *max_element(all(v));};

template <typename Container>
inline auto maxv(Container& v, int hasta) {return *max_element(v.begin(), v.begin() + hasta);};

template <typename Container>
inline auto maxv(Container& v, int desde, int hasta) {return *max_element(v.begin()+desde, v.begin() + hasta);};

template <typename Container>
inline int sumv(Container& v) {return accumulate(all(v), 0ll);};

template <typename Container>
inline int sumv(Container& v, int hasta) {return accumulate(v.begin(), v.begin() + hasta, 0ll);};

template <typename Container>
inline int sumv(Container& v, int desde, int hasta) {return accumulate(v.begin() + desde, v.begin() + hasta, 0ll);};



bool esDiv(int multiplo, int divisor) {
    return (multiplo % divisor) == 0;
};

int ceil(int a, int b) {
    return a / b + !esDiv(a, b);
};




template <typename T>
T mmax(T arg) { return arg; }

template <typename T, typename... Args>
T mmax(T arg, Args... args) {
    return max(arg, mmax(forward<Args>(args)...));
}

template <typename T>
T mmin(T arg) { return arg; }

template <typename T, typename... Args>
T mmin(T arg, Args... args) {
    return min(arg, mmin(forward<Args>(args)...));
}

#define max mmax
#define min mmin


template <typename T>
vector<int> discretizar(const vector<T> &A) {
  vector<int> ids(len(A));
  iota(all(ids), 0); 
  sort(all(ids),
       [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
  return ids;
}

int gcd(int a, int b){
    if(a==0) return b;
    return gcd(b%a, a);
}

template <typename T>
bool eraseOne(multiset<T>& m, T k) {
    auto it = m.find(k);
    if (it == m.end()) return false;
    m.erase(it);
    return true;
};

// [desde, hasta]
int randInt(int desde, int hasta, vi excluyendo = {}) {
    int num = unif(desde, hasta)(gen);
    sortv(excluyendo);
    for (int ex : excluyendo) 
        if (num >= ex) 
            num++;
    
    return num;
}

template <typename Container>
void shufflev(Container& v){
    shuffle(all(v), gen);
}


template <typename T>
vt<T> samplev(vt<T>& v, int cantidad) {
    int n = len(v);
    assert(cantidad <= n);
    if (v.empty() || cantidad <= 0) return {};

    vt<T> rta(cantidad);
    vi pos(cantidad);

    forn(i, cantidad) {
        pos[i] = randInt(i, n-1);
        rta[i] = v[pos[i]];
        swap(v[i], v[pos[i]]);
    }
    
    forr(i, cantidad-1, 0) 
        swap(v[i], v[pos[i]]);
    
    return rta;
}

template <typename Container>
vt<typename Container::value_type> samplev(Container& v, int cantidad) {
    vt<typename Container::value_type> result;
    if (v.empty() || cantidad <= 0) return result;

    sample(all(v), back_inserter(result), cantidad, gen);

    return result;
}



// sqf(n, k) te devuelve la raiz k-esima en O(log(n) * exp)
int sqf2(int n, int exp) {
    if (n == 1 || exp > 64) return 1;
    int tb = topbit(n);
    int rta = 0;
    forr(i, tb, 0) {
        int bit = 1ll << i;
        int producto = 1;
        forn(exp){
            if(producto > n / (rta + bit)) goto noanda; 
            producto *= (rta + bit);
        } 
        if (producto <= n) rta += bit; 
        noanda:
    }
    return rta;
}

int logf(int n, int base) {
    int rta = 0, actual = 1;
    while(actual <= INT64_MAX / base &&  actual * base <= n) 
        actual *= base, ++rta;
    return rta;
}

int gauss(int n){
    return n * (n+1) / 2;
}
int gauss(int desde, int hasta){
    return gauss(hasta) - gauss(desde-1);
}

/* mineq / maxeq / ceil / even / mmin / mmax / sumv, minv, maxv */
/* lowb - el primer >= a x o mx /  llowb - el ultimo < a x o mn / uppb - el primer > a x o mx / lowbp / uppbpos / eraseOne para multiset */
#endif
// clang-format on
//--------------------------------------