// https://yukicoder.me/users/18400/ai_code
#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using lint = long long;
using loub = long double;
template <typename T> using vec = vector<T>;
template <typename T> using deq = deque<T>;
template <typename T> using priq = priority_queue<T>;
template <typename T> using prig = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using uset = unordered_set<T>;
template <typename K, typename V> using umap = unordered_map<K, V>;
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K, typename V> using omap = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename F, typename S, typename T> struct trip { F first = F(); S second = S(); T third = T(); auto operator<=>(const trip&) const = default; };
#define fst first
#define snd second
#define trd third
#define REP1(i, r) for (lint i = 0; i < (r); i++)
#define REP2(i, l, r) for (lint i = (l); i < (r); i++)
#define REP3(i, l, r, d) for (lint i = (l); (d) > 0 ? i < (r) : i > (r); i += (d))
#define SELECT_REP(_0, _1, _2, _3, REP_NAME, ...) REP_NAME
#define rep(...) SELECT_REP(__VA_ARGS__, REP3, REP2, REP1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define part(v, l, r) v.begin() + (l), v.begin() + (r)
#define rpart(v, l, r) make_reverse_iterator(v.begin() + (r)), make_reverse_iterator(v.begin() + (l))
template <typename C> void vecin(C &v, lint l, lint r) { rep(i, l, r) cin >> v[i]; }
template <typename C> void vecin(C &v) { vecin(v, 0, v.size()); };
template <typename C> void vecho(const C &v, lint l, lint r) { rep(i, l, r) cout << (i > l ? " " : "") << v[i]; cout << endl; }
template <typename C> void vecho(const C &v) { vecho(v, 0, v.size()); }
template <typename T> void echo(const T &val) { cout << val << endl; }
template <typename T, typename... Ts> void echo(const T &val, const Ts &...vals) { cout << val << " "; echo(vals...); }
template <typename T> int chmin(T &a, const T &b) { if (a <= b) return a == b; a = b; return 2; }
template <typename T> int chmax(T &a, const T &b) { if (a >= b) return a == b; a = b; return 2; }
template <typename T> T sq(T x) { return x * x; }
template <typename T> T cb(T x) { return x * x * x; }
template <typename T> T pw(T x, int n) { T ret = 1; rep(i, n) ret *= x; return ret; }
lint isqrt(lint n) { lint m = sqrt(n); while (sq(m) > n) m--; while(n >= sq(m + 1)) m++; return m; }
lint icbrt(lint n) { lint m = cbrt(n); while (cb(m) > n) m--; while(n >= cb(m + 1)) m++; return m; }
const int INF = 2'000'000'002; 
const lint LINF = 2'000'000'000'000'000'002;
const pair<int, int> DIJ4[]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
const pair<int, int> DIJ8[]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1}};

void solve();
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(15);
  
  int T = 1;
  // cin >> T;
  rep(t, T) solve();
}

lint dist(lint Px, lint Py, lint Qx, lint Qy) {
  return sq(Px - Py) + sq(Qx - Qy);
}
lint area(lint Px, lint Py, lint Qx, lint Qy, lint Rx = 0, lint Ry = 0) {
  Px -= Rx, Py -= Ry, Qx -= Rx, Qy -= Ry;
  return Px * Qy - Py * Qx;
};

bool frcmp(const pair<lint, lint> &a, const pair<lint, lint> &b) {
  return a.fst * b.snd - b.fst * a.snd > 0;
}

lint digit_sum(lint n, lint b = 10) {
  lint ds = 0;
  while (n > 0) ds += n % b, n /= b;
  return ds;
}

vec<lint> divisors(lint N) {
  vec<lint> D; lint k = 1;
  while (k * k < N) {
    if (N % k == 0) D.push_back(k);
    k++;
  }
  int M = D.size();
  if (k * k == N) D.push_back(k);
  rep(i, M - 1, -1, -1) D.push_back(N / D[i]);
  return D;
}

vec<int> min_factor_list(int M) {
  vec<int> ret(M + 1); ranges::iota(ret, 0);
  ret[0] = ret[1] = -1;
  for (int i = 2; i * i <= M; i++) if (ret[i] == i) {
    rep(j, i * i, M + 1, i) if (ret[j] == j) ret[j] = i;
  }
  return ret;
}

lint comb(lint n, lint r) {
  if (r < 0 || n < r) return 0;
  lint ret = 1;
  rep(k, r) ret *= n - k, ret /= k + 1;
  return ret;
}

struct mod_calc {
  lint MOD; umap<lint, vec<lint>> _POW; vec<lint> _FACT, _FINV, _DFAC, _DFIN;

  mod_calc(lint mod = 998244353) { MOD = mod; }

  lint rem(lint n) { return (n %= MOD) >= 0 ? n : n + MOD; }

  lint _pow(lint b, lint e) {
    lint ret = 1; b %= MOD;
    while (e) { if (e & 1) ret *= b, ret %= MOD;
                e >>= 1; b *= b, b %= MOD; }
    return ret;
  }
  lint _inv(lint n) { return _pow(n, MOD - 2); }

  void init_pows(lint b, lint MAX) {
    vec<lint> tmp(MAX + 1, 1); b %= MOD;
    rep(i, 1, MAX + 1) tmp[i] = tmp[i - 1] * b % MOD;
    _POW[b] = tmp;
  }
  void init_facts(lint MAX) {
    _FACT.resize(MAX + 1); _FACT[0] = 1;
    rep(i, 1, MAX + 1) _FACT[i] = _FACT[i - 1] * i % MOD;
    _FINV.resize(MAX + 1); _FINV[MAX] = _inv(_FACT[MAX]);
    rep(i, MAX - 1, -1, -1) _FINV[i] = _FINV[i + 1] * (i + 1) % MOD;
  }
  void init_dfacs(lint MAX) {
    _DFAC.resize(MAX + 1); _DFAC[0] = 1, _DFAC[1] = 1;
    rep(i, 2, MAX + 1) _DFAC[i] = _DFAC[i - 2] * i % MOD;
    _DFIN.resize(MAX + 1); _DFIN[MAX] = _inv(_DFAC[MAX]), _DFIN[MAX - 1] = _inv(_DFAC[MAX - 1]);
    rep(i, MAX - 2, -1, -1) _DFIN[i] = _DFIN[i + 2] * (i + 2) % MOD;
  }

  lint pow(lint b, lint e) { return _POW[b % MOD][e]; }
  lint fact(lint n) { return n >= 0 ? _FACT[n] : 0; }
  lint finv(lint n) { return n >= 0 ? _FINV[n] : 0; }
  lint dfac(lint n) { return n >= 0 ? _DFAC[n] : 0; }
  lint dfin(lint n) { return n >= 0 ? _DFIN[n] : 0; }
  lint perm(lint n, lint r) { return fact(n) * finv(n - r) % MOD; }
  lint comb(lint n, lint r) { return perm(n, r) * finv(r) % MOD; }
  lint crep(lint n, lint r) { return comb(n + r - 1, r); }

  lint _perm(lint n, lint r) {
    if (n < 0 || r < 0 || n < r) return 0;
    lint ret = 1; rep(i, n, n - r, -1) ret *= i % MOD, ret %= MOD;
    return ret;
  }
  lint _comb(lint n, lint r) { return _perm(n, r) * finv(r) % MOD; }
  lint _crep(lint n, lint r) { return _comb(n + r - 1, r); }
};

template <typename C>
vec<C> transposed(vec<C> &A) {
  if (A.empty()) return A;
  const int H = A.size(), W = A[0].size();
  vec<C> B(W, C(H, ' '));
  rep(i, H) rep(j, W) B[j][i] = A[i][j];
  return B;
}

struct countable_mset {
  map<lint, lint> cnt;
  lint num = 0, sum = 0;

  void insert(lint x) {
    cnt[x]++; num++; sum += x;
  }
  bool erase(lint x) {
    if (!cnt.contains(x)) return false;
    cnt[x]--; num--; sum -= x;
    if (cnt[x] == 0) cnt.erase(x);
    return true;
  }

  lint min() { return (*cnt.begin()).fst; }
  lint max() { return (*cnt.rbegin()).fst; }
};

struct addonly_mset {
  priq<lint> lset; prig<lint> rset;
  lint _lsum = 0, _rsum = 0, _min = LINF, _max = -LINF;

  void insert(lint x) {
    chmin(_min, x); chmax(_max, x);
    if (lset.empty() || x <= lset.top()) {
      lset.push(x); _lsum += x;
    } else {
      rset.push(x); _rsum += x;
    }
    if (lset.size() > rset.size() + 1) {
      lint m = lset.top(); lset.pop(); rset.push(m);
      _lsum -= m; _rsum += m;
    } else if (lset.size() < rset.size()) {
      lint m = rset.top(); rset.pop(); lset.push(m);
      _rsum -= m; _lsum += m;
    }
  }

  bool empty() { return lset.empty(); }
  lint size() { return lset.size() + rset.size(); }
  lint min() { return _min; }
  lint max() { return _max; }
  lint lmed() { return lset.top(); }
  lint rmed() { return lset.size() == rset.size()
                     ? rset.top() : lset.top(); }
  lint lsum() { return _lsum; }
  lint rsum() { return lset.size() == rset.size()
                     ? _rsum : lset.top() + _rsum; }
  lint sum() { return _lsum + _rsum; }
};

struct interval_set {
  map<lint, lint> LR; lint tot_len = 0;

  bool insert(lint l, lint r) {
    if (r <= l) return false;
    auto it = LR.upper_bound(l);
    if (it != LR.begin() && l <= prev(it)->snd) {
      lint &pr = prev(it)->snd;
      if (r <= pr) return false;
      else tot_len += r - pr, pr = r;
    } else {
      tot_len += r - l;
      it = next(LR.insert({l, r}).fst);
    }
    while (it != LR.end() && it->fst <= r) {
      auto [nl, nr] = *it;
      if (nr <= r) tot_len -= nr - nl; 
      else tot_len -= r - nl, prev(it)->snd = nr;
      it = LR.erase(it);
    }
    return true;
  }

  lint count_intervals() { return LR.size(); }

  lint total_length() { return tot_len; }
};

template <typename C, typename T = typename C::value_type>
vec<pair<T, int>> rle(C A, function<bool(T, T)> cond = equal_to{}) {
  vec<pair<T, int>> ret;
  for (T a : A) {
    if (ret.empty() || !cond(ret.back().fst, a)) ret.emplace_back(a, 0);
    ret.back().snd++;
  }
  return ret;
}

bool valid_brackets(const string &S) {
  int cnt = 0;
  for (char c : S) {
    if (c == '(') cnt++; else if (c == ')') cnt--;
    if (cnt < 0) return false;
  }
  return true;
}

vec<string> split_brackets(const string &S) {
  vec<string> T; int cnt = 0;
  for (char c : S) {
    if (cnt == 0) T.push_back("");
    T.back() += c;
    if (c == '(') cnt++; else if (c == ')') cnt--;
  }
  return T;
}

struct rolling_hash {
  const lint M1 = 1'000'000'007, M2 = 1'000'000'009;
  const lint B = 1'000'000'001;
  vec<lint> B1, B2, H1, H2;

  template <typename C>
  rolling_hash(C v) {
    int n = v.size();
    B1.resize(n+1, 1), B2.resize(n+1, 1);
    H1.resize(n+1), H2.resize(n+1);
    rep(i, n) {
      B1[i+1] = B1[i] * B % M1;
      B2[i+1] = B2[i] * B % M2;
      H1[i+1] = (H1[i] * B + v[i]) % M1;
      H2[i+1] = (H2[i] * B + v[i]) % M2;
    } 
  }

  pair<lint, lint> hash(lint l, lint r) {
    lint h1 = (H1[r] - H1[l] * B1[r-l] % M1 + M1) % M1;
    lint h2 = (H2[r] - H2[l] * B2[r-l] % M2 + M2) % M2;
    return {h1, h2};
  }
  pair<lint, lint> hash() { return hash(0, H1.size()-1); }

  bool equal(lint a, lint b, lint c, lint d) {
    return hash(a, b) == hash(c, d);
  }
};

lint hash_lshift(lint h, lint c, lint P, lint B, lint M) {
  lint h2 = ((h - c * P) % M * B + c) % M;
  return h2 < 0 ? h2 + M : h2;
}

template <typename T, typename F>
struct segtree {
  int siz; vec<T> dat; F ope;
 
  segtree(unsigned int n, T e, F f) : ope(f) {
    siz = bit_ceil(n); dat.resize(2 * siz, e);
  }
  segtree(const vec<T> &v, T e, F f) : ope(f) {
    unsigned int n = v.size();
    siz = bit_ceil(n); dat.resize(2 * siz, e);
    rep(i, n) dat[siz + i] = v[i];
    rep(j, siz - 1, 0, -1) dat[j] = ope(dat[2 * j], dat[2 * j + 1]);
  }

  T get(int i) { return dat[siz + i]; }

  void set(int i, T x) {
    int j = siz + i; dat[j] = x;
    while (j > 1) j /= 2, dat[j] = ope(dat[2 * j], dat[2 * j + 1]);
  }
  void add(int i, T d) { set(i, get(i) + d); }

  T prod_impl(int l, int r, unsigned int j) {
    int W = siz / bit_floor(j), L = j * W - siz, R = L + W;
    if (r <= L || R <= l) return dat[0];
    if (l <= L && R <= r) return dat[j];
    return ope(prod_impl(l, r, 2 * j), prod_impl(l, r, 2 * j + 1));
  }
  T prod(int l, int r) { return prod_impl(l, r, 1); }
  T prod() { return dat[1]; }

  template <typename G>
  int first_right_impl(int l, int r, G &check, T &acc, unsigned int j) {
    int W = siz / bit_floor(j), L = j * W - siz, R = L + W;
    if (r <= L || R <= l) return -1;
    if (l <= L && R <= r) {
      T new_acc = ope(acc, dat[j]);
      if (!check(new_acc)) { acc = new_acc; return -1; }
      if (W == 1) return R;
    }
    int pos = first_right_impl(l, r, check, acc, 2 * j);
    return pos != -1 ? pos : first_right_impl(l, r, check, acc, 2 * j + 1);
  }
  template <typename G>
  int first_right(int l, int r, G check) {
    T acc = dat[0]; int pos = first_right_impl(l, r, check, acc, 1);
    return pos != -1 ? pos : r + 1;
  }

  template <typename G>
  int last_left_impl(int l, int r, G &check, T &acc, unsigned int j) {
    int W = siz / bit_floor(j), L = j * W - siz, R = L + W;
    if (r <= L || R <= l) return -1;
    if (l <= L && R <= r) {
      T new_acc = ope(dat[j], acc);
      if (!check(new_acc)) { acc = new_acc; return -1; }
      if (W == 1) return L;
    }
    int pos = last_left_impl(l, r, check, acc, 2 * j + 1);
    return pos != -1 ? pos : last_left_impl(l, r, check, acc, 2 * j);
  }
  template <typename G>
  int last_left(int l, int r, G check) {
    T acc = dat[0]; int pos = last_left_impl(l, r, check, acc, 1);
    return pos != -1 ? pos : l - 1;
  }
};

template <typename T, typename F>
struct dual_segtree {
  int siz; vec<T> dat; F comp;

  dual_segtree(unsigned int n, T e, F f) : comp(f) {
    siz = bit_ceil(n); dat.resize(2 * siz, e);
  }
  dual_segtree(const vec<T> &v, T e, F f) : comp(f) {
    unsigned int n = v.size();
    siz = bit_ceil(n); dat.resize(2 * siz, e);
    rep(i, n) dat[siz + i] = v[i];
  }

  void push_impl(unsigned int j) {
    dat[2 * j] = comp(dat[2 * j], dat[j]);
    dat[2 * j + 1] = comp(dat[2 * j + 1], dat[j]);
    dat[j] = dat[0];
  }

  T get_impl(int i, unsigned int j) {
    if (j >= siz) return dat[j];
    push_impl(j);
    int W = siz / bit_floor(j), L = j * W - siz, M = L + W / 2;
    if (i < M) return get_impl(i, 2 * j);
    else return get_impl(i, 2 * j + 1);
  }
  T get(int i) { return get_impl(i, 1); }

  void set(int i, T x) { get(i); dat[siz + i] = x; }

  void apply_impl(int l, int r, T y, unsigned int j) {
    int W = siz / bit_floor(j), L = j * W - siz, R = L + W;
    if (r <= L || R <= l) return;
    if (l <= L && R <= r) { dat[j] = comp(dat[j], y); return; }
    push_impl(j);
    apply_impl(l, r, y, 2 * j); apply_impl(l, r, y, 2 * j + 1);
  }
  void apply(int l, int r, T y) { apply_impl(l, r, y, 1); }
};

template <typename T1, typename T2, typename F1, typename F2, typename F3>
struct lazy_segtree {
  int siz; vec<T1> dat; vec<T2> laz; F1 ope; F2 mapp; F3 comp;

  lazy_segtree(unsigned int n, T1 e1, T2 e2, F1 f1, F2 f2, F3 f3)
      : ope(f1), mapp(f2), comp(f3) {
    siz = bit_ceil(n); dat.resize(2 * siz, e1); laz.resize(siz, e2);
  }
  lazy_segtree(const vec<T1> &v, T1 e1, T2 e2, F1 f1, F2 f2, F3 f3)
      : ope(f1), mapp(f2), comp(f3) {
    unsigned int n = v.size();
    siz = bit_ceil(n); dat.resize(2 * siz, e1); laz.resize(siz, e2);
    rep(i, n) dat[siz + i] = v[i];
    rep(j, siz - 1, 0, -1) dat[j] = ope(dat[2 * j], dat[2 * j + 1]);
  }

  void update_impl(unsigned j, T2 y) {
    int W = siz / bit_floor(j); dat[j] = mapp(dat[j], y, W);
    if (j < siz) laz[j] = comp(laz[j], y);
  }
  void push_impl(unsigned int j) {
    update_impl(2 * j, laz[j]); update_impl(2 * j + 1, laz[j]);
    laz[j] = laz[0];
  }

  T1 get_impl(int i, unsigned int j) {
    if (j >= siz) return dat[j];
    push_impl(j);
    int W = siz / bit_floor(j), L = j * W - siz, M = L + W / 2;
    if (i < M) return get_impl(i, 2 * j);
    else return get_impl(i, 2 * j + 1);
  }
  T1 get(int i) { return get_impl(i, 1); }

  void set_impl(int i, T1 x, unsigned int j) {
    if (j >= siz) { dat[j] = x; return; }
    push_impl(j);
    int W = siz / bit_floor(j), L = j * W - siz, M = L + W / 2;
    if (i < M) set_impl(i, x, 2 * j);
    else set_impl(i, x, 2 * j + 1);
    dat[j] = ope(dat[2 * j], dat[2 * j + 1]);
  }
  void set(int i, T1 x) { set_impl(i, x, 1); }

  void apply_impl(int l, int r, T2 y, unsigned int j) {
    int W = siz / bit_floor(j), L = j * W - siz, R = L + W;
    if (r <= L || R <= l) return;
    if (l <= L && R <= r) { update_impl(j, y); return; }
    push_impl(j);
    apply_impl(l, r, y, 2 * j); apply_impl(l, r, y, 2 * j + 1);
    dat[j] = ope(dat[2 * j], dat[2 * j + 1]);
  }
  void apply(int l, int r, T2 y) { apply_impl(l, r, y, 1); }

  T1 prod_impl(int l, int r, unsigned int j) {
    int W = siz / bit_floor(j), L = j * W - siz, R = L + W;
    if (r <= L || R <= l) return dat[0];
    if (l <= L && R <= r) return dat[j];
    push_impl(j);
    return ope(prod_impl(l, r, 2 * j), prod_impl(l, r, 2 * j + 1));
  }
  T1 prod(int l, int r) { return prod_impl(l, r, 1); }
  T1 prod() { return dat[1]; }

  template <typename G>
  int first_right_impl(int l, int r, G &check, T1 &acc, unsigned int j) {
    int W = siz / bit_floor(j), L = j * W - siz, R = L + W;
    if (r <= L || R <= l) return -1;
    if (l <= L && R <= r) {
      T1 new_acc = ope(acc, dat[j]);
      if (!check(new_acc)) { acc = new_acc; return -1; }
      if (W == 1) return R;
    }
    push_impl(j);
    int pos = first_right_impl(l, r, check, acc, 2 * j);
    return pos != -1 ? pos : first_right_impl(l, r, check, acc, 2 * j + 1);
  }
  template <typename G>
  int first_right(int l, int r, G check) {
    T1 acc = dat[0]; int pos = first_right_impl(l, r, check, acc, 1);
    return pos != -1 ? pos : r + 1;
  }

  template <typename G>
  int last_left_impl(int l, int r, G &check, T1 &acc, unsigned int j) {
    int W = siz / bit_floor(j), L = j * W - siz, R = L + W;
    if (r <= L || R <= l) return -1;
    if (l <= L && R <= r) {
      T1 new_acc = ope(dat[j], acc);
      if (!check(new_acc)) { acc = new_acc; return -1; }
      if (W == 1) return L;
    }
    push_impl(j);
    int pos = last_left_impl(l, r, check, acc, 2 * j + 1);
    return pos != -1 ? pos : last_left_impl(l, r, check, acc, 2 * j);
  }
  template <typename G>
  int last_left(int l, int r, G check) {
    T1 acc = dat[0]; int pos = last_left_impl(l, r, check, acc, 1);
    return pos != -1 ? pos : l - 1;
  }
};

template <typename T = lint, typename F = plus<T>>
struct doubling {
  int rnk = 1, ord; T ide; F ope;
  vec<vec<pair<int, T>>> dst;

  doubling(int n, T e = T{}, F f = F{}) {
    ord = n, ide = e, ope = f;
    dst = vec(1, vec(n, pair{-1, e}));
    rep(u, n) dst[0][u].fst = u;
  }

  void set_dst(int u, int v, T w) { dst[0][u] = {v, w}; }
  void set_dst(int u, int v) { dst[0][u] = {v, ide}; }

  void calc_dsts(unsigned long long max_t) {
    rnk = bit_width(max_t);
    dst.resize(rnk, vec(ord, pair{-1, ide}));
    rep(s, 1, rnk) rep(u, ord) {
      int v = dst[s-1][u].fst;
      dst[s][u] = {dst[s-1][v].fst,
        ope(dst[s-1][u].snd, dst[s-1][v].snd)};
    }
  }

  pair<int, T> get_dst(int u, lint t) {
    int v = u; T r = ide;
    rep(s, rnk) if (t>>s&1) {
      r = ope(r, dst[s][v].snd), v = dst[s][v].fst;
    }
    return {v, r};
  }
};

pair<vec<int>, vec<vec<int>>> conn_comp(vec<vec<int>> &G) {
  vec<int> comp_id(G.size(), -1); vec<vec<int>> comps;
  rep(i, G.size()) {
    if (comp_id[i] != -1) continue;
    comp_id[i] = comps.size(); comps.push_back({(int)i});
    rep(k, comps.back().size()) {
      for (int j : G[comps.back()[k]]) {
        if (comp_id[j] != -1) continue;
        comp_id[j] = comp_id[i]; comps.back().push_back(j);
      }
    }
  }
  return {comp_id, comps};
}

struct disjoint_sets {
  int tot_siz = 0, num_ccs = 0; vec<int> siz, par, nex;

  disjoint_sets(int n) {
    tot_siz = num_ccs = n;
    siz.resize(n, 1), par.resize(n), nex.resize(n);
    rep(i, n) par[i] = nex[i] = i;
  }

  int root(int x) {
    if (par[x] != x) par[x] = root(par[x]);
    return par[x];
  }

  bool unite(int x, int y) {
    x = root(x), y = root(y);
    if (x == y) return false;
    if (siz[x] < siz[y]) swap(x, y);
    siz[x] += siz[y], par[y] = x, swap(nex[x], nex[y]);
    num_ccs--; return true;
  }

  bool same(int x, int y) { return root(x) == root(y); }

  int size(int x) { return siz[root(x)]; }

  vec<int> members(int x) {
    vec<int> mems{x};
    while ((x = nex[x]) != mems[0]) mems.push_back(x);
    return mems;
  }

  vec<vec<int>> groups() {
    vec<vec<int>> grps;
    rep(i, tot_siz) if (par[i] == i) grps.push_back(members(i));
    return grps;
  }
};

pair<vec<int>, vec<vec<int>>> bfs(vec<vec<int>> &G, const vec<int> &S) {
  const int N = G.size();
  vec<int> dist(N, -1); vec<vec<int>> prvs(N); queue<int> que;
  for (int s : S) dist[s] = 0, que.push(s);
  while (!que.empty()) {
    int u = que.front(); que.pop();
    for (int v : G[u]) {
      if (dist[v] == -1) dist[v] = dist[u] + 1, que.push(v);
      if (dist[v] == dist[u] + 1) prvs[v].push_back(u);
    }
  }
  return {dist, prvs};
}

pair<vec<int>, vec<vec<int>>> bfs01(vec<vec<pair<int, int>>> &G, const vec<int> &S) {
  const int N = G.size();
  vec<int> dist(N, -1), visited(N); vec<vec<int>> prvs(N); deq<int> que;
  for (int s : S) dist[s] = 0, que.push_back(s);
  while (!que.empty()) {
    int u = que.front(); que.pop_front();
    if (visited[u]) continue; else visited[u] = true;
    for (auto [v, w] : G[u]) {
      if (dist[v] == -1 || dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w; prvs[v].clear();
        if (w == 0) que.push_front(v); else que.push_back(v);
      }
      if (dist[v] == dist[u] + w) prvs[v].push_back(u);
    }
  }
  return {dist, prvs};
}

pair<vec<lint>, vec<vec<int>>> dijkstra(vec<vec<pair<int, lint>>> &G, const vec<int> &S) {
  const int N = G.size();
  vec<lint> dist(N, -1); vec<vec<int>> prvs(N); prig<pair<lint, int>> que;
  for (int s : S) dist[s] = 0, que.emplace(0, s);
  while (!que.empty()) {
    auto [d, u] = que.top(); que.pop();
    if (d != dist[u]) continue;
    for (auto [v, w] : G[u]) {
      if (dist[v] == -1 || dist[v] > d + w) {
        dist[v] = d + w; prvs[v].clear(); que.emplace(dist[v], v);
      }
      if (dist[v] == d + w) prvs[v].push_back(u);
    }
  }
  return {dist, prvs};
}

template <typename T>
T soln_tsp(vec<vec<T>> &D, T inf) {
  const int N = D.size();
  vec<vec<T>> dp(1<<N, vec(N, inf));
  dp[1][0] = 0;
  rep(S, 1<<N) rep(i, N) if (dp[S][i] < inf) {
    rep(j, N) if (!(S>>j&1)) {
      chmin(dp[S|1<<j][j], dp[S][i] + D[i][j]);
    }
  }
  T soln = inf;
  rep(i, 1, N) chmin(soln, dp[(1<<N)-1][i] + D[i][0]);
  return soln;
}

struct max_flow {
  vec<vec<int>> out; vec<int> to, cap;

  max_flow(int n) { out.resize(n); }

  int add_arc(int u, int v, int c) {
    int a = to.size();
    out[u].push_back(a);   to.push_back(v); cap.push_back(c);
    out[v].push_back(a+1); to.push_back(u); cap.push_back(0);
    return a;
  }

  void dfs(vec<int> &in, int u) {
    for (int e : out[u]) {
      int v = to[e];
      if (cap[e] > 0 && in[v] == -2) in[v] = e, dfs(in, v);
    }
  }

  int soln(int s, int t) {
    int ret = 0;
    while (true) {
      vec<int> in(out.size(), -2); in[s] = -1; dfs(in, s);
      if (in[t] == -2) break;
      vec<int> path; int f = INF, v = t;
      while (v != s) {
        int e = in[v]; path.push_back(e);
        chmin(f, cap[e]); v = to[e^1];
      }
      for (int e : path) cap[e] -= f, cap[e^1] += f;
      ret += f;
    }
    return ret;
  }
};

template <typename T, typename F>
T bisearch(F check, T ok, T ng, T eps = 1) {
  while (abs(ok - ng) > eps) {
    T mid = (ok + ng) / 2;
    if (check(mid)) ok = mid;
    else ng = mid;
  }
  return ok;
}

lint mex(vec<lint> &A, lint K = 1, lint L = 0, lint inf = LINF) {
  auto it_L = ranges::lower_bound(A, L);
  auto check = [&](lint x) {
    auto it_x = ranges::upper_bound(A, x);
    lint cnt_ex = (x+1 - L) - (it_x - it_L);
    return cnt_ex >= K;
  };
  return bisearch(check, inf, L-1);
}

template <typename T>
void inv_nums_impl(vec<int> &C, vec<pair<T, int>> &VI) {
  const int M = VI.size(); if (M <= 1) return;
  const int M1 = M / 2, M2 = M - M / 2;
  vec<pair<T, int>> VI1(part(VI, 0, M1)), VI2(part(VI, M1, M));
  inv_nums_impl(C, VI1), inv_nums_impl(C, VI2);
  int j1 = 0, j2 = 0;
  rep(j, M) {
    if (j2 == M2 || j1 < M1 && VI1[j1] < VI2[j2]) {
      VI[j] = VI1[j1]; j1++;
    } else {
      C[VI2[j2].snd] += M1 - j1; VI[j] = VI2[j2]; j2++;
    }
  }
}
template <typename T>
vec<int> inv_nums(vec<T> &V) {
  const int N = V.size();
  vec<int> C(N); vec<pair<T, int>> VI(N);
  rep(i, N) VI[i] = pair{V[i], i};
  inv_nums_impl(C, VI); return C;
}

template <typename T>
vec<int> ids_subseq(vec<T> &A, vec<T> &B) {
  vec<int> ids; int i = 0;
  for (T b : B) {
    while (i < A.size() && A[i] != b) i++;
    if (i == A.size()) break;
    ids.push_back(i); i++;
  }
  return ids;
}

template <typename T>
vec<int> ids_lis(vec<T> &A, bool strict = true) {
  if (A.empty()) return {};
  const int N = A.size();
  vec<int> prv(N, -1), pos; pos.reserve(N);
  auto f = [&](int i) { return A[i]; };
  rep(i, N) {
    auto it = strict
      ? ranges::lower_bound(pos, A[i], {}, f)
      : ranges::upper_bound(pos, A[i], {}, f);
    if (it != pos.begin()) prv[i] = *prev(it);
    if (it == pos.end()) pos.push_back(i);
    else *it = i;
  }
  vec<int> ret; int i = pos.back();
  while (i != -1) ret.push_back(i), i = prv[i];
  ranges::reverse(ret);
  return ret;
}

template <typename T>
vec<pair<int, int>> cartesian_tree(vec<T> A) {
  vec<pair<int, int>> LR(A.size(), {-1, -1});
  stack<int> S;
  rep(i, A.size()) {
    // min: >, max: <
    while (!S.empty() && A[S.top()] > A[i]) {
      LR[i].fst = S.top(); S.pop();
    }
    if (!S.empty()) LR[S.top()].snd = i;
    S.push(i);
  }
  return LR;
}

void solve() {
  lint i, l, r, v, d, a;

  // point update, range sum
  segtree rsq(1'000'000, 0LL, plus{});

  // point update, range min
  auto min_ = [](lint a, lint b) { return min(a, b); };
  segtree rmq(1'000'000, LINF, min_);

  // range add, point get
  segtree raq(1'000'000, 0LL, plus{});
  raq.add(l, d), raq.add(r, -d);
  raq.prod(0, i + 1);

  // range chmax, point get
  auto max_ = [](lint a, lint b) { return max(a, b); };
  dual_segtree rcmq(1'000'000, -LINF, max_);

  // range chmin, range chmax, point get
  auto meet = [](pair<int, int> p, pair<int, int> q) {
    if (p.snd <= q.fst) return pair{q.fst, q.fst};
    if (q.snd <= p.fst) return pair{q.snd, q.snd};
    return pair{max(p.fst, q.fst), min(p.snd, q.snd)};
  };
  dual_segtree rcm2q(vec(1'000'000, pair{0LL, 0LL}), {-LINF, LINF}, meet);
  rcm2q.apply(l, r, {-LINF, a});
  rcm2q.apply(l, r, {a, LINF});
  rcm2q.get(i).fst;

  // range update, point get
  auto update = [](lint a, lint b) { return b == LINF ? a : b; };
  dual_segtree ruq(vec(1'000'000, 0LL), LINF, update);

  // range add, range min
  auto add0 = [](lint m, lint d, int W) { return m + d; };
  lazy_segtree ramq(vec(1'000'000, 0LL), LINF, 0LL, min_, add0, plus{});

   // range add, range sum
  auto add1 = [](lint s, lint d, int W) { return s + W * d; };
  lazy_segtree rasq(1'000'000, 0LL, 0LL, plus{}, add1, plus{});
  // range add arithmetic, point get
  rasq.apply(l - 1, l, a);
  rasq.apply(l, r, d);
  rasq.apply(r, r + 1, -(a + (r - l) * d));
  rasq.prod(0, i);

  // range update, range min
  auto upd0 = [](lint m, lint v, int W) { return v == LINF ? m : v; };
  lazy_segtree rumq(vec(1'000'000, 0LL), LINF, LINF, min_, upd0, update);

  // range update, range sum
  auto upd1 = [](lint s, lint v, int W) { return v == LINF ? s : W * v; };
  lazy_segtree rusq(1'000'000, 0LL, LINF, plus{}, upd1, update);

  // range affine, range sum
  auto afadd = [](lint s, pair<lint, lint> p, int W) { return p.fst * s + W * p.snd; };
  auto afcom = [](pair<lint, lint> p, pair<lint, lint> q) { return pair{q.fst * p.fst, q.fst * p.snd + q.snd}; };
  lazy_segtree affine(1'000'000, 0LL, pair{1, 0}, plus{}, afadd, afcom);
  affine.apply(l, r, {0, v}); // range update
  affine.apply(l, r, {1, d}); // range add

}