#include <bits/stdc++.h>
#include <boost/functional/hash/hash.hpp>

using lnt = long long int;
using Pl = std::pair<lnt, lnt>;

template<class T>
using VC = std::vector<T>;

template<class T>
using VVC = VC<VC<T>>;

using Vl = VC<lnt>;
using VVl = VC<Vl>;

#define FS first
#define SC second

#define EP emplace

#define PB push_back
#define BI back_inserter
#define BG begin()
#define ED end()

#define LB lower_bound
#define UB upper_bound

#define MAX max_element
#define MIN min_element

#define LP(n) for (lnt _ = 0; _ < (n); _++)
#define RP(i, n) for (lnt i = 0; i < (n); i++)            // 0, 1, ..., n-1
#define IR(i, n) for (lnt i = (n)-1; i >= 0; i--)      // n-1, n-2, ..., 0
#define FR(i, a, b) for (lnt i = (a); i < (b); i++)       // a, a+1, ..., b-1
#define IF(i, a, b) for (lnt i = (b)-1; i >= (a); i--) // b-1, b-2, ..., a
#define AL(a) a.begin(), a.end()
#define DISPLAY_DOUBLE(d) (cout << scientific << setprecision(15) << (d))
#define INF (lnt)(1e18)

lnt MOD = (1e9 + 7); // AtCoderのMOD

//CHANGE_MOD(n): グローバル変数のMODをnに変更する
inline void CHANGE_MOD(const lnt &n) {
  MOD = n;
}

// 習慣付けの為'int'を一切タイプしない
#define MAIN int main

// 各アルゴリズムをlntに揃える
template <class InputIterator, class T>
lnt inline CN(const InputIterator &first, const InputIterator &last,
               const T &value) {
  return std::count(first, last, value);
}

template <class T> lnt inline SZ(const T &sequence) {
  return (lnt)(sequence.size());
}

lnt inline AB(const lnt &value) { return std::abs(value); }

lnt inline MA(const lnt &value1, const lnt &value2) {
  return std::max(value1, value2);
}

lnt inline MI(const lnt &value1, const lnt &value2) {
  return std::min(value1, value2);
}

template <class InputIterator>
lnt inline AC(const InputIterator &first, const InputIterator &last,
               const lnt &init = 0) {
  return std::accumulate(first, last, init);
}

template <class InputIterator, class BinaryOperation>
lnt inline AC(const InputIterator &first, const InputIterator last,
               const lnt init, const BinaryOperation binary_op) {
  return std::accumulate(first, last, init, binary_op);
}

//同じ文字を繰り返す文字列
std::string STR(const lnt &n, const char &c) {
  std::string s;
  for (lnt _ = 0; _ < n; _++) {
    s.push_back(c);
  }
  return s;
}

// unordered_set，unordered_mapの為のハッシュの拡張
template <class T> struct boost_hash {
  inline std::size_t operator()(const T &val) const {
    return boost::hash_value(val);
  }
};

template <class T> using ST = std::unordered_set<T, boost_hash<T>>;
template <class T, class S> using MP = std::unordered_map<T, S, boost_hash<T>>;

using Sl = ST<lnt>;
using Ml = MP<lnt, lnt>;

/*setdefalut(map, key, val): map: T-> S, key: T-value, val: S-value
  pythonのsetdefaultメソッド */
template <class T, class S>
S &setdefault(MP<T, S> &map, const T &key, const S &val) {
  if (map.count(key)) {
    return map.at(key);
  }
  map.emplace(key, val);
  return map.at(key);
}

// next_partial_permutation関数
template <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first,
                              BidirectionalIterator middle,
                              BidirectionalIterator last) {
  reverse(middle, last);
  return next_permutation(first, last);
}

template <class BidirectionalIterator, class Compare>
bool next_partial_permutation(BidirectionalIterator first,
                              BidirectionalIterator middle,
                              BidirectionalIterator last, const Compare comp) {
  reverse(middle, last, comp);
  return next_permutation(first, last, comp);
}

// vector<lnt>({first, first+1, ..., first + size - 1})を生成
std::vector<lnt> init_comb(const lnt size, const lnt first = 0) {
  std::vector<lnt> v;
  for (lnt i = 0; i < size; i++) { v.push_back(i + first); }
  return v;
}

// next_combination関数
// vector<lnt>の昇順列vと, 数Nを入力すると， {順列:N未満の数からなる相異なる#v要素の昇順列}
// の中で， 辞書順でvを次の順列に変更し， trueを返す． もし最後の順列だったら， 何もせずfalseを返す.
// 例：v = {0, 1}, N = 4 なら， {0, 1} → {0, 2} → {0, 3} → {1, 2} → {1, 3} → {2, 3}
bool next_combination(std::vector<lnt> &v, const lnt last) {
  if (SZ(v) == 1 and v.at(0) != last - 1) {
    v.at(0)++;
    return true;
  }
  if (SZ(v) == 1) {
    return false;
  }
  if (SZ(v) > 1) {
    std::vector<lnt> w = v;
    w.erase(w.begin());
    if (next_combination(w, last)) {
      v = std::vector<lnt>(1, v.at(0));
      v.insert(v.end(), w.begin(), w.end());
      return true;
    }
    if (v.at(0) == last - SZ(v)) {
      return false;
    }
    v = init_comb(SZ(v), v.at(0) + 1);
    return true;
  } else
    return false;
}

// Primes(n): n以下の素数をvector<lnt>に格納（エラトステネスの篩）　O(nloglogn)
std::vector<lnt> Primes(const lnt n) {
  if (n < 2) {
    return std::vector<lnt>(0);
  }

  std::deque<lnt> dqPri, dqTab;
  for (lnt i = 2; i < n + 1; i++) {
    dqTab.push_back(i);
  }

  const lnt nRoot = sqrt(n);
  while (dqTab.front() <= nRoot) {
    dqPri.push_back(dqTab.front());
    dqTab.pop_front();
    std::deque<lnt> dqTab_fil; //dqTab_filtered
    std::copy_if(dqTab.begin(), dqTab.end(), back_inserter(dqTab_fil),
                 [&dqPri](lnt x) -> bool { return x % dqPri.back(); });
    dqTab = dqTab_fil;
    if (dqTab.empty()) {
      break;
    }
  }

  std::vector<lnt> vcPri, vcTab;
  vcPri.reserve(dqPri.size()); vcTab.reserve(dqTab.size());
  for (lnt x : dqPri) { vcPri.push_back(x); }
  for (lnt x : dqTab) { vcTab.push_back(x); }

  vcPri.reserve(vcPri.size() + vcTab.size());
  vcPri.insert(vcPri.end(), vcTab.begin(), vcTab.end());
  return vcPri;
}

// 素数列挙Primes(n)のテーブル
// デフォルトのサイズは0
std::vector<lnt> vcPRIMES_PREPARED = Primes(0);

//素数列挙Primes(n)のテーブルにおけるリストサイズ指定関数
inline void SPECIFY_LISTSIZE_PRIMES(const lnt max_size) {
  vcPRIMES_PREPARED = Primes(max_size);
}

/* 素因数分解:PrimeDecomp(n)
   SPECIFY_LISTSIZE_PRIMES(k) (kは十分大 >= floor(sqrt(n)))を事前に実行すること
   O(√n * logn) （事前の素数テーブル生成処理を含む）*/
MP<lnt, lnt>
PrimeDecomp(const lnt n,
            const std::vector<lnt> &vcPrimesRoot_n = vcPRIMES_PREPARED) {
  if (n < 2) {
    return MP<lnt, lnt>();
  }

  MP<lnt, lnt> PrimeDecomp;

  lnt m = n;
  for (lnt p : vcPrimesRoot_n) {
    while (m % p == 0) {
      m /= p;
      setdefault(PrimeDecomp, p, (lnt)0)++;
    }

    if (m == 1) { break; }
  }
  if (m != 1) { //mが1でない場合, vcPrimesRoot_nに無い素数が残っている
    PrimeDecomp.emplace(m, 1);
  }
  return PrimeDecomp;
}

/* 約数列挙:Divisors(n)
 SPECIFY_LISTSIZE_PRIMES(k) (kは十分大 >= floor(sqrt(n)))を事前に実行すること
 O(√n * logn + (logn)^4 * loglogn) (事前の素数テーブル生成処理含む)
*/
std::vector<lnt>
Divisors(const lnt n,
         const std::vector<lnt> &vcPrimesRoot_n = vcPRIMES_PREPARED) {
  std::vector<lnt> vcDiv(1, 1), vcBuf;
  auto mpPD = PrimeDecomp(n, vcPrimesRoot_n);
  for (auto itrPD = mpPD.begin(); itrPD != mpPD.end(); itrPD++) {
    lnt nPri = itrPD->first, nMulti = itrPD->second;
    vcBuf.resize(vcDiv.size() * (nMulti + 1));
    lnt pw = 1;
    for (lnt i = 0; i < nMulti + 1; i++) {
      std::transform(vcDiv.begin(), vcDiv.end(),
                     vcBuf.begin() + (i * vcDiv.size()),
                     [pw](lnt x) -> lnt { return x * pw; });
      pw *= nPri;
    }
    vcDiv = vcBuf;
  }
  std::sort(vcDiv.begin(), vcDiv.end());
  return vcDiv;
}

//最大公約数:gcd(n, m) (gcd(0, 0)=0)　O(log(min(abs(n), abs(m))
lnt GCD(const lnt n, const lnt m) {
  if (!n || !m) {
    return (lnt)std::max(std::abs(n), std::abs(m));
  }
  lnt nDivided = (lnt)std::max(n, m), nDividing = (lnt)std::min(n, m);
  while (nDivided % nDividing) {
    nDivided = nDivided % nDividing;
    std::swap(nDivided, nDividing);
  }
  return std::abs(nDividing);
}

//最小公倍数:lcm(n, m) O(log(min(abs(n), abs(m))))
lnt LCM(const lnt n, const lnt m) {
  if (!n && !m) {
    return 0;
  }
  return std::abs(n / GCD(n, m) * m);
}

// mod2乘
lnt inline SQ(const lnt n, const lnt mod = MOD) {
  return ((n % mod) * (n % mod)) % mod;
}

// POW(x, y)= x^y mod MOD: mod冪乗 O(logy)
lnt POW(const lnt x, const lnt y, const lnt mod = MOD) {
  if (x >= 0 and y >= 0) {
    if (y == 0) {
      return 1 % mod;
    }
    if (y == 1) {
      return x % mod;
    }
    if (y % 2 == 0) {
      return SQ(POW(x, y / 2, mod), mod);
    }
    return SQ(POW(x, y / 2, mod), mod) * (x % mod) % mod;
  }
  std::cout << "Warning!"
            << "\n";
  return 0;
}

// BIT(i)=2^i mod MOD: mod 2の冪 O(logi)
lnt inline BIT(const lnt i) {
  if (i >= 0) {
    return POW(2, i);
  }
  std::cout << "Warning!"
            << "\n";
  return 0;
}

// long long まで許すSQ
lnt inline LSQ(const lnt n) { return n * n; }

// LPOW(x, y)=x^y: long long まで許すPOW O(logy)
lnt LPOW(const lnt x, const lnt y) {
  if (x >= 0 and y >= 0) {
    if (y == 0) {
      return 1;
    }
    if (y == 1) {
      return x;
    }
    if (y % 2 == 0) {
      return LSQ(LPOW(x, y / 2));
    }
    return LSQ(LPOW(x, y / 2)) * x;
  }
  std::cout << "Warning!"
            << "\n";
  return 0;
}

// LBIT(i)=2^i: long longまで許すBIT O(logi)
lnt inline LBIT(const lnt i) {
  if (i >= 0) {
    return LPOW(2, i);
  }
  std::cout << "Warning!"
            << "\n";
  return 0;
}

// n以下の階乗/mod階乗のリストを生成　O(n)
std::vector<lnt> vcFACT(const lnt n, const lnt mod = MOD) {
  if (n >= 0) {
    std::vector<lnt> vcFact = {1 % mod};
    lnt fact = 1 % mod;
    for (lnt k = 1; k < n + 1; k++) {
      fact = (fact * (k % mod)) % mod;
      vcFact.push_back(fact);
    }
    return vcFact;
  }
  std::cout << "Warning!　The 1st argument is negative!"
            << "\n";
  return std::vector<lnt>(0);
}

// n以下のmod階乗の逆元のリストを生成(mod:素数を想定) O(n)
std::vector<lnt> vcINVFACT(const lnt n, const lnt mod = MOD) {
  std::vector<lnt> vcInvFact;
  lnt invfact = POW(vcFACT(n, mod).at(n), mod - 2);
  vcInvFact.push_back(invfact);
  for (lnt k = n; k > 0; k--) {
    invfact = invfact * (k % mod) % mod;
    vcInvFact.push_back(invfact);
  }
  std::reverse(vcInvFact.begin(), vcInvFact.end());
  return vcInvFact;
}

// mod階乗のリストvcFACT(n, MOD)，mod階乗の逆元リストvcINVFACT(n, MOD)の
//テーブル化 デフォルトのサイズは0
std::vector<lnt> vcMODFACT_PREPARED = vcFACT(0, MOD);
std::vector<lnt> vcMODINVFACT_PREPARED = vcINVFACT(0, MOD);

// mod階乗リストvcFACT(n, mod)，mod階乗の逆元リストvcINVFACT(n, mod)の，
// テーブルにおけるリストサイズ・mod指定関数
inline void SPECIFY_LISTSIZE_MODFACT(const lnt max_size,
  const lnt mod = MOD) {
  vcMODFACT_PREPARED = vcFACT(max_size, mod);
}
inline void SPECIFY_LISTSIZE_MODINVFACT(const lnt max_size,
  const lnt mod = MOD) {
  vcMODINVFACT_PREPARED = vcINVFACT(max_size, mod);
}

// 階乗（テーブル参照） O(1)
// mod > 0． SPECIFY_LISTSIZE_PRIMES(m)を事前に実行すること(m >= n:十分大)
lnt inline FACT(const lnt n,
                const std::vector<lnt> &vcModFact = vcMODFACT_PREPARED) {
  return vcModFact.at(n);
}

// 順列の数
// mod:素数を想定．4, 5番目の引数にはvcFACT(m1, mod)，vcINVFACT(m2, mod)を入れる
// (m1 >= n, m2 >= n-k :十分大)
lnt PERM(const lnt n, const lnt k, const lnt mod = MOD,
         const std::vector<lnt> &vcModFact = vcMODFACT_PREPARED,
         const std::vector<lnt> &vcModInvFact = vcMODINVFACT_PREPARED) {
  if (k >= 0) {
    return vcModFact.at(n) * vcModInvFact.at(n - k) % mod;
  }
  return 0;
}

//二項係数
// mod:素数を想定．4, 5番目の引数にはvcFACT(m1, mod)，vcINVFACT(m2, mod)を入れる
// (m1 >= n, m2 >= n-k, k :十分大)
lnt inline COMB(const lnt n, const lnt k, const lnt mod = MOD,
                const std::vector<lnt> &vcModFact = vcMODFACT_PREPARED,
                const std::vector<lnt> &vcModInvFact = vcMODINVFACT_PREPARED) {
  return PERM(n, k, mod, vcModFact, vcModInvFact) * vcModInvFact.at(k) % mod;
}

//重複組み合わせの数
// mod:素数を想定．4, 5番目の引数にはvcFACT(m1, mod)，vcINVFACT(m2,mod)を入れる
// (m1 >= n+k-1, m2 >= n-1, k :十分大)
lnt inline HCOMB(const lnt n, const lnt k, const lnt mod = MOD,
                 const std::vector<lnt> &vcModFact = vcMODFACT_PREPARED,
                 const std::vector<lnt> &vcModInvFact = vcMODINVFACT_PREPARED) {
  return COMB(n + k - 1, k, mod, vcModFact, vcModInvFact);
}

// 非負整数valueのbase進数表示でのposition桁目を表示
lnt inline MASK(const lnt value, const lnt position, const lnt base = 10) {
  if (value >= 0 and base >= 2) {
    return (value / LPOW(base, position)) % base;
  }
  std::cout << "WARNING! The MASK fucntion is applyed in a wrong manner."
            << "\n";
  return 0;
}

// ビットマスク
lnt inline BMASK(const lnt value, const lnt position) {
  return MASK(value, position, 2);
}

// MASKにおいて，position桁目に数字がない時0ではなくbaseを返す
lnt inline DIGIT(const lnt value, const lnt position, const lnt base = 10) {
  if (value >= 0 and base >= 2) {
    if (value == 0) {
      if (position == 0) {
        return 0;
      }
      return base;
    }
    if (value < LPOW(base, position)) {
      return base;
    }
    return MASK(value, position, base);
  }

  std::cout << "WARNING!"
            << "\n";
  return 0;
}

// base=2のDIGIT
lnt inline BDIGIT(const lnt value, const lnt position) {
  return DIGIT(value, position, 2);
}

// ポテンシャル付きUnion-Find木
template <class T> class UnionFind {
private:
  MP<T, T> par;
  MP<T, lnt> rank;
  MP<T, lnt> diff_from_par;
  MP<T, lnt> sz;
  lnt nTree = 0;
  lnt weight(const T &);

public:
  UnionFind<T>();
  UnionFind<T>(const ST<T> &);
  T find(const T &);
  lnt diff(const T &, const T &);
  bool unite(const T &, const T &, const lnt = 0);
  bool equi(const T &x, const T &y) { return find(x) == find(y); }
  lnt size_at(const T &x) { return sz.at(find(x)); }
  lnt n_tree() const { return nTree; }
};

template <class T> UnionFind<T>::UnionFind(const ST<T> &st) {
  par.reserve(SZ(st));
  rank.reserve(SZ(st));
  diff_from_par.reserve(SZ(st));
  sz.reserve(SZ(st));
  for (T x : st) {
    par.emplace(x, x);
    rank.emplace(x, 0);
    diff_from_par.emplace(x, 0);
    sz.emplace(x, 1);
  }
  nTree = SZ(st);
}

// 経路圧縮しながらrootを返す
template <class T> T UnionFind<T>::find(const T &x) {
  if (par.at(x) == x) {
    return x;
  }
  T root = find(par.at(x));
  diff_from_par.at(x) += diff_from_par.at(par.at(x));
  return par.at(x) = root;
}

// rootを基準としたポテンシャル
template <class T> lnt UnionFind<T>::weight(const T &x) {
  find(x);
  return diff_from_par.at(x);
}

// yを基準としたxのポテンシャルを返す
// 異なる木に対するdiff関数は意味を持たないので，警告も出力
template <class T> lnt UnionFind<T>::diff(const T &x, const T &y) {
  if (not equi(x, y)) {
    std::cout << "Warning! The roots of x and y are not same."
              << "\n";
  }
  return weight(x) - weight(y);
}

// diff(x, y) = w となるようにxのtreeとyのtreeを繋ぐ
// xのtreeとyのtreeが既に同じで，diff(x, y) ≠ w　なら何もせずにfalseを返す
template <class T>
bool UnionFind<T>::unite(const T &x, const T &y, const lnt w) {
  T p = find(x);
  T q = find(y);
  if (p == q) {
    if (diff(x, y) == w) {
      return true;
    }
    return false;
  }
  lnt v = w + weight(y) - weight(x);
  if (rank.at(p) > rank.at(q)) {
    std::swap(p, q);
    v = -v;
  }
  if (rank.at(p) == rank.at(q)) {
    rank.at(q)++;
  }
  par.at(p) = q;
  diff_from_par.at(p) = v;
  sz.at(q) += sz.at(p);
  nTree--;
  return true;
}

// UnionFind<lnt>
template <> class UnionFind<lnt> {
private:
  MP<lnt, lnt> par;
  MP<lnt, lnt> rank;
  MP<lnt, lnt> diff_from_par;
  MP<lnt, lnt> sz;
  lnt nTree = 0;
  lnt weight(const lnt);

public:
  UnionFind<lnt>();
  UnionFind<lnt>(const ST<lnt> &);
  UnionFind<lnt>(const lnt);
  lnt find(const lnt);
  lnt diff(const lnt, const lnt);
  bool unite(const lnt, const lnt, const lnt = 0);
  bool equi(const lnt x, const lnt y) { return find(x) == find(y); }
  lnt size_at(const lnt x) { return sz.at(find(x)); }
  lnt n_tree() const { return nTree; }
};

UnionFind<lnt>::UnionFind(const ST<lnt> &st) {
  par.reserve(SZ(st));
  rank.reserve(SZ(st));
  diff_from_par.reserve(SZ(st));
  sz.reserve(SZ(st));
  for (lnt x : st) {
    par.emplace(x, x);
    rank.emplace(x, 0);
    diff_from_par.emplace(x, 0);
    sz.emplace(x, 1);
  }
  nTree = SZ(st);
}

UnionFind<lnt>::UnionFind(const lnt num) {
  par.reserve(num);
  rank.reserve(num);
  diff_from_par.reserve(num);
  sz.reserve(num);
  RP(i, num) {
    par.emplace(i, i);
    rank.emplace(i, 0);
    diff_from_par.emplace(i, 0);
    sz.emplace(i, 1);
  }
  nTree = num;
}

// 経路圧縮しながらrootを返す
lnt UnionFind<lnt>::find(const lnt x) {
  if (par.at(x) == x) {
    return x;
  }
  lnt root = find(par.at(x));
  diff_from_par.at(x) += diff_from_par.at(par.at(x));
  return par.at(x) = root;
}

// rootを基準としたポテンシャル
lnt UnionFind<lnt>::weight(const lnt x) {
  find(x);
  return diff_from_par.at(x);
}

// yを基準としたxのポテンシャルを返す
// 異なる木に対するdiff関数は意味を持たないので，警告も出力
lnt UnionFind<lnt>::diff(const lnt x, const lnt y) {
  if (not equi(x, y)) {
    std::cout << "Warning! The roots of x and y are not same."
              << "\n";
  }
  return weight(x) - weight(y);
}

// diff(x, y) = w となるようにxのtreeとyのtreeを繋ぐ
// xのtreeとyのtreeが既に同じで，diff(x, y) ≠ w　なら何もせずにfalseを返す
bool UnionFind<lnt>::unite(const lnt x, const lnt y, const lnt w) {
  lnt p = find(x);
  lnt q = find(y);
  if (p == q) {
    if (diff(x, y) == w) {
      return true;
    }
    return false;
  }
  lnt v = w + weight(y) - weight(x);
  if (rank.at(p) > rank.at(q)) {
    std::swap(p, q);
    v = -v;
  }
  if (rank.at(p) == rank.at(q)) {
    rank.at(q)++;
  }
  par.at(p) = q;
  diff_from_par.at(p) = v;
  sz.at(q) += sz.at(p);
  nTree--;
  return true;
}

//セグメント木
/*SegmentTree<X, M>(n1, fx, fa, fm, ex, em):
    (X, ex, fx), (M, em, fm): モノイド,
    写像fa: X * M -> X によって, XはM-monoid,
    n1: セグメント木の葉の数(実際の内部的な葉の数は, n1 <= 2^m なる最小の2^m = n)
  set(i, x): i番目の葉にxをセット.
  build(): 葉からセグメント木を構築. O(n)
  update(a, b, m): [a, b)の要素xをfm(x, m)に更新. O(log(n))
  query(a, b): [a, b)全てにfxを作用させた値を取得. O(log(n))
  参考: https://algo-logic.info/segment-tree/
*/
template <class X, class M>
class SegmentTree {
  using FX = std::function<X(X, X)>;
  using FM = std::function<M(M, M)>;
  using FA = std::function<X(X, M)>;

private:
  lnt n; //葉の数(2の冪乗)
  FX fx;
  FM fm;
  FA fa;
  const X ex;
  const M em;
  std::vector<X> dat; //完全二分木全体の配列
  std::vector<M> lazy; //遅延評価用の配列
  void lupd(const lnt); //局所的な更新
  void upd_sub(const lnt, const lnt, const M &,
    const lnt, const lnt, const lnt); //区間更新のサブ関数
  X query_sub(const lnt, const lnt, const lnt, const lnt, const lnt);
  //クエリ区間走行中のサブクエリ

public:
  SegmentTree(const lnt, const FX &, const FM &, const FA &,
    const X &, const M &); //コンストラクタ
  void set(const lnt, const X &); //葉に値をセット
  void build(); //セットされた値を用いて，セグメント木を構成
  void update(const lnt, const lnt, const M &); //区間更新
  X query(const lnt a, const lnt b); //クエリ区間走行
};

//コンストラクタ
template <class X, class M> SegmentTree<X, M>::SegmentTree(
  const lnt n1, const FX &fx_, const FM &fm_,
  const FA &fa_, const X &ex_, const M &em_)
  : n(), fx(fx_), fa(fa_), fm(fm_), ex(ex_), em(em_),
  dat(n1 * 4, ex), lazy(n1 * 4, em){ // n1は2の冪とは限らない→2ではなく4
  lnt x = 1;
  while (n1 > x) { x *= 2; }
  n = x;
};

template <class X, class M> void SegmentTree<X, M>::set(
  const lnt i, const X &x) {
  dat.at(i + n - 1) = x;
}; //葉の内部的な位置はn-1ずれる
template <class X, class M> void SegmentTree<X, M>::build() {
  for (lnt k = n-2; k>=0; k--) {
    dat.at(k) = fx(dat.at(2*k + 1), dat.at(2*k + 2));
    //kの子は(存在するなら)2*k+1,2*k+2
  }
};

//局所的な更新: 位置kで，lazyにプールしてある値mを子に伝播し，自身をfa(・, m)に更新
template <class X, class M> void SegmentTree<X, M>::lupd(const lnt k) {
  if (lazy.at(k) == em) { return; } //何もプールされていなければ終了
  if (k < n - 1) { //子に伝播(予め伝播先に値があるなら, fmを用いてプール値を更新)
    lazy.at(2*k + 1) = fm(lazy.at(2*k + 1), lazy.at(k));
    lazy.at(2*k + 2) = fm(lazy.at(2*k + 2), lazy.at(k));
  }
  //自身を更新
  dat.at(k) = fa(dat.at(k), lazy.at(k));
  lazy.at(k) = em; //更新後はlazyを空に
};

/*区間更新(内部的には,実際に全ての更新はせず,必要最低限の更新のみし,
他はできるだけ親のlazyにプールしておくだけ)update(a, b, m)のサブ関数 */
template <class X, class M> void SegmentTree<X, M>::upd_sub(
  const lnt a, const lnt b, const M &m,
  const lnt k, const lnt l, const lnt r) {
  //k: 現在の位置
  //元々の更新区間:[a, b), fa(・, m)を使って更新, 現在の区間:[l, r)

  if (a <= l && r <= b) { //[l, r)が[a, b)に含まれる場合

    /*この場合は,mによる更新を行う.ただし,更新の際は古い値がプールされている場合を考慮する.
      (根でなければ)親にこの更新後の値が送り返される事になる*/
    lazy.at(k) = fm(lazy.at(k), m); lupd(k);

    /*これより下の全ての子も(遅延評価でなければ)mにより更新させるはずだが,
      実際はすぐ下の子にプールさせておくだけで,更新しない(これが計算量の肝)*/
    return;
  }

  if (a < r && l < b) { //[l, r)と[a, b)の一部区間が被る場合

    /*自身はmによる更新対象ではないが,子がmによる更新対象となり変化する可能性がある.
      そこで最終的には親=fx(子1, 子2)の関係を保てるよう,子以降を調べてから,
      親=fx(子1, 子2)とする*/

    lupd(k); //古い値がプールされていれば， 子への伝播と自身の更新を行っておく

    upd_sub(a, b, m, 2*k + 1, l, (l+r)/2); //左の子を調べる
    upd_sub(a, b, m, 2*k + 2, (l+r)/2, r); //右の子を調べる

    //子以下は更新処理が完了したため,親=fx(子1, 子２)とし直す.
    dat.at(k) = fx(dat.at(2*k + 1), dat.at(2*k + 2));
    return;
  }

  //[l, r)と[a, b)が交わらない時は，自身と子以下にmによる変化は起き得ないため,何もしない
};

/*区間更新 update(a, b, m)
  更新区間:[a, b), fa(・, m)を使って更新 */
template <class X, class M> void SegmentTree<X, M>::update(
  const lnt a, const lnt b, const M &m) { upd_sub(a, b, m, 0, 0, n); };

//クエリ走行query(a, b)のサブクエリ
template <class X, class M> X SegmentTree<X, M>::query_sub(
  const lnt a, const lnt b, const lnt k, const lnt l, const lnt r) {
  //k: 現在の位置
  //元々のクエリ走行区間:[a, b), 現在の区間:[l, r)

  if (a <= l && r <= b) { //[l, r)が[a, b)に含まれる場合

    //この場合は,親のサブクエリに自身の値を返す.ただし,値がプールされている場合を考慮する.
    lupd(k); return dat.at(k);
  }

  if (a < r && l < b) { //[l, r)と[a, b)の一部区間が被る場合

    /*この場合は,自身の値をそのまま親のサブクエリに返すわけにはいかない.
      すっぽり含まれるような子に行き着くまで,子以下を調べる.
      最終的に調べおわったあと,返ってきた値にfx(・,・)を作用させ，親のサブクエリに返す*/

    lupd(k); //古い値がプールされていれば， 子への伝播と自身の更新を行っておく

    X xl = query_sub(a, b, 2*k + 1, l, (l+r)/2); //左の子のサブクエリを処理
    X xr = query_sub(a, b, 2*k + 2, (l+r)/2, r); //右の子のサブクエリを処理

    //子のサブクエリが完了したため,渡された値を用いて親のサブクエリに値を返す
    return fx(xl, xr);
  }

  //[l, r)と[a, b)が交わらない時は，単位元exを親のサブクエリに返す.
  return ex;
};

/*クエリ走行query(a, b)
  クエリ走行区間:[a, b), fxを区間に作用させた結果を返す*/
template <class X, class M> X SegmentTree<X, M>::query(
  const lnt a, const lnt b) { return query_sub(a, b, 0, 0, n); };

using namespace std;

MAIN() {
  lnt N; cin >> N;
  VC<Sl> sml(N+1);
  VC<Sl> big(N+1);

  LP(N-1) {
    lnt u, v; cin >> u >> v;
    if (u > v) { swap(u, v); }
    sml.at(v).emplace(u);
    big.at(u).emplace(v);
  }

  lnt s = 1, now = 1;
  FR(n, 2, N+1) {
    now += 1 - SZ(sml.at(n));
    s += now;
  }

  lnt res = s;
  FR(n, 2, N+1) {
    s -= N - (n-2);

    for (lnt r : big.at(n-1)) {
      s += N - (r-1);
    }

    res += s;
  }

  cout << res << endl;
}


Measured memory_bytes: 50212