while (true) ++++++ ++++++ ++++++ RP;

template <typename T> inline void read(T &x) {
  int c; T tag = 1;
  while(!isdigit((c=getchar()))) if(c == '-') tag = -1;
  x = c-'0';
  while(isdigit((c=getchar()))) x = (x<<1)+(x<<3) + c-'0';
  x *= tag;
}

template <typename T> void write(T x) {
  if(x < 0) x = -x, putchar('-');
  if(x > 9) write(x/10);
  putchar(x%10+'0');
}

ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

struct Scanner {
  FILE* fp = nullptr;
  char line[(1 << 15) + 1];
  size_t st = 0, ed = 0;
  void reread() {
    memmove(line, line + st, ed - st);
    ed -= st;
    st = 0;
    ed += fread(line + ed, 1, (1 << 15) - ed, fp);
    line[ed] = '\0';
  }
  bool succ() {
    while (true) {
      if (st == ed) {
        reread();
        if (st == ed) return false;
      }
      while (st != ed && isspace(line[st])) st++;
      if (st != ed) break;
    }
    if (ed - st <= 50) reread();
    return true;
  }
  template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
  bool read_single(T& ref) {
    if (!succ()) return false;
    while (true) {
      size_t sz = 0;
      while (st + sz < ed && !isspace(line[st + sz])) sz++;
      ref.append(line + st, sz);
      st += sz;
      if (!sz || st != ed) break;
      reread();
    }
    return true;
  }
  template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  bool read_single(T& ref) {
    if (!succ()) return false;
    bool neg = false;
    if (line[st] == '-') {
      neg = true;
      st++;
    }
    ref = T(0);
    while (isdigit(line[st])) {
      ref = 10 * ref + (line[st++] - '0');
    }
    if (neg) ref = -ref;
    return true;
  }
  template <class T> bool read_single(V<T>& ref) {
    for (auto& d : ref) {
      if (!read_single(d)) return false;
    }
    return true;
  }
  void read() {}
  template <class H, class... T> void read(H& h, T&... t) {
    bool f = read_single(h);
    assert(f);
    read(t...);
  }
  Scanner(FILE* _fp) : fp(_fp) {}
};

struct Printer {
  public:
  template <bool F = false> void write() {}
  template <bool F = false, class H, class... T>
  void write(const H& h, const T&... t) {
    if (F) write_single(' ');
    write_single(h);
    write<true>(t...);
  }
  template <class... T> void writeln(const T&... t) {
    write(t...);
    write_single('\n');
  }

  Printer(FILE* _fp) : fp(_fp) {}
  ~Printer() { flush(); }

  private:
  static constexpr size_t SIZE = 1 << 15;
  FILE* fp;
  char line[SIZE], small[50];
  size_t pos = 0;
  void flush() {
    fwrite(line, 1, pos, fp);
    pos = 0;
  }
  void write_single(const char& val) {
    if (pos == SIZE) flush();
    line[pos++] = val;
  }
  template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  void write_single(T val) {
    if (pos > (1 << 15) - 50) flush();
    if (val == 0) {
      write_single('0');
      return;
    }
    if (val < 0) {
      write_single('-');
      val = -val; // todo min
    }
    size_t len = 0;
    while (val) {
      small[len++] = char('0' + (val % 10));
      val /= 10;
    }
    for (size_t i = 0; i < len; i++) {
      line[pos + i] = small[len - 1 - i];
    }
    pos += len;
  }
  void write_single(const string& s) {
    for (char c : s) write_single(c);
  }
  void write_single(const char* s) {
    size_t len = strlen(s);
    for (size_t i = 0; i < len; i++) write_single(s[i]);
  }
  template <class T> void write_single(const V<T>& val) {
    auto n = val.size();
    for (size_t i = 0; i < n; i++) {
      if (i) write_single(' ');
      write_single(val[i]);
    }
  }
};

Scanner sc = Scanner(stdin);
Printer pr = Printer(stdout);

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

char str[];
scanf("%3s", str); // 读取长度为n的字符串
scanf("%[abc]", str); // 读取a,b,c,读到之外的立即停止
scanf("%[a-z0-9]", str); // 同上,读取小写字母和数字
scanf("%*[a-z]%s", str); // 过滤掉小写字母读取
scanf("%[^a-z]", str); // 读取小写字符外字符,^表示非 
scanf("%*c"); //清理输入缓冲区中第一个字符，也就是上次遗留下的\n
scanf("%[^\n]%*c",str); // 相当于gets(str), %*c的作用是吸收\n

#include <random>
// 范围 unsigned int
mt19937 rnd(time(NULL));
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
cout << rnd() << endl;

std::random_device rd;  //获取随机数种子
std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
std::uniform_int_distribution<> dis(0, 9);
std::cout << dis(gen) << endl;

inline ull xorshift128(){
  static U SX=335634763,SY=873658265,SZ=192849106,SW=746126501;
  U t=SX^(SX<<11);
  SX=SY;
  SY=SZ;
  SZ=SW;
  return SW=SW^(SW>>19)^t^(t>>8);
}
inline ull myrand(){return (xorshift128()<<32)^xorshift128();}

struct HashNumber {
  static const int HN = 2;
  int a[HN], mod[HN] = {25165843, 50331653};
  HashNumber() { memset(a, 0, sizeof a); }
  template <typename U> HashNumber(const U &x) {
    for (int i = 0; i < HN; ++i) a[i] = x%mod[i];
  }
  friend bool operator ==(const HashNumber &lhs, const HashNumber &rhs) {
    for (int i = 0; i < HN; ++i) if (lhs.a[i] != rhs.a[i]) return false;
    return true;
  }
  friend bool operator !=(const HashNumber &lhs, const HashNumber &rhs) {
    return !(lhs == rhs);
  }
  HashNumber& operator +=(const HashNumber &hs) {
    for (int i = 0; i < HN; ++i) (a[i] += hs.a[i]) %= mod[i];
    return *this;
  }
  HashNumber& operator *=(const HashNumber &hs) {
    for (int i = 0; i < HN; ++i) a[i] = (1ll*a[i]*hs.a[i])%mod[i];
    return *this;
  }
  friend HashNumber operator +(const HashNumber &lhs, const HashNumber &rhs) {
    HashNumber res = lhs;
    return res += rhs;
  }
  friend HashNumber operator *(const HashNumber &lhs, const HashNumber &rhs) {
    HashNumber res = lhs;
    return res *= rhs;
  }
};

#define log(x) (31-__builtin_clz(x))
// #define log(x) (63-__builtin_clzll(x))
// lg2[i] = lg2(i) +1
for(int i = 1; i <= n; ++i) lg2[i] = lg2[i>>1]+1;
// lg2[i] = (int)log2(i)
for(int i = 2; i <= n; ++i) lg2[i] = lg2[i>>1]+1;

double sqrt(const double &a) {
  double x = a, y = .0;
  while (abs(x-y) > err) {
    y = x;
    x = .5*(x+a/x);
  }
  return x;
}

for (int i = 1; i <= n; ++i) {
  for (int j = 1, l, r; j <= n; ++j) {
    l = max(1, i/(j+1));
    while (l-1 >= 1 && i/(l-1) == j) --l;
    while (i/l > j) ++l;
    r = i/j;
    while (r+1 <= i && i/(r+1) == j) ++r;
    while (i/r < j) --r;
    if (r-l+1 != i/j-i/(j+1)) {
        cout << i << " " << j << endl;
    }
  }
}

while (l < r) {
  int mid = (l+r)>>1;
  if (f(mid) < f(mid+1)) r = mid;
  else l = mid+1;
}

while(r-l>5){
    int ml=(l+l+r)/3;
    int mr=(l+r+r)/3;
    if(f(ml)<f(mr))r=mr;
    else l=ml;
}
for (int i = l; i <= r; ++i) res = min(res, f(i));

while (r-l > eps) {
  double ml = l+(r-l)/3, mr = r-(r-l)/3;
  if (f(ml) < f(mr)) r = mr;
  else l = ml;
}

void cdq(int l, int r) {
  if (l >= r) return;
  int mid = (l+r)>>1, i = l, j = mid+1;
  cdq(l, mid); cdq(mid+1, r);
  for (int k = l; k <= r; ++k) {
    if (j > r || (i <= mid && a[i].y <= a[j].y)) {
      tree.add(a[i].z, a[i].w);
      b[k] = a[i++];
    } else {
      a[j].f += tree.query(a[j].z);
      b[k] = a[j++];
    }
  }
  for (int k = l; k <= mid; ++k) tree.add(a[k].z, -a[k].w);
  for (int k = l; k <= r; ++k) a[k] = b[k];
}

void cdq(int l, int r) {
  cdq(l, mid); cdq(mid+1, r);
}

void CDQ(int l, int r) {
  CDQ(l, mid); CDQ(mid+1, r);
  // ...
  cdq(l, r);
}

template <typename T>
void hex_print(const T &y) {
  static const char HEX[] = "0123456789ABCDEF";
  char *x = (char*)(&y);
  printf("0x");
  for (int i = sizeof(T) - 1; i >= 0; --i) { // 小端存储
    char a = *(x + i);
    printf("%c%c",HEX[(a&0xF0)>>4],HEX[a&0x0F]);
  }
  puts("");
}

template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;

// 二维
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        a[i][j] += a[i - 1][j];
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        a[i][j] += a[i][j - 1];
// 三维
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        for(int k = 1; k <= n; k++) 
            a[i][j][k] += a[i - 1][j][k];
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        for(int k = 1; k <= n; k++)
            a[i][j][k] += a[i][j - 1][k];
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        for(int k = 1; k <= n; k++)
            a[i][j][k] += a[i][j][k - 1];
// 以此类推,每一维度都做一遍前缀和

struct Point {
  typedef double T;
  T x, y;
  int id;
  Point(){}
  Point(const T &_x, const T &_y, const int &_i = 0) : x(_x), y(_y), id(_i) {}
  friend Point operator + (const Point &p1, const Point &p2) {
    return Point(p1.x+p2.x, p1.y+p2.y, p1.id);
  }
  friend Point operator - (const Point &p1, const Point &p2) {
    return Point(p1.x-p2.x, p1.y-p2.y, p1.id);
  }
  friend Point operator - (const Point &p) {
    return Point(-p.x, -p.y, p.id);
  }
  // a*b b在a的顺负逆正
  friend T operator * (const Point &p1, const Point &p2) {
    return p1.x*p2.y-p1.y*p2.x;
  }
  template <typename TT>
  friend Point operator / (const Point &p, const TT &k) {
    return Point(p.x/k, p.y/k, p.id);
  }
  template <typename TT>
  friend Point operator * (const Point &p, const TT &k) {
    return Point(p.x*k, p.y*k, p.id);
  }
  Point operator += (const Point &p) { return *this = *this+p; }
  Point operator -= (const Point &p) { return *this = *this+p; }
  template <typename TT>
  Point operator *= (const TT &k) { return *this = *this*k; }
  template <typename TT>
  Point operator /= (const TT &k) { return *this = *this/k; }
  friend bool operator < (const Point &p1, const Point &p2) {
    return make_pair(p1.x, p1.y) < make_pair(p2.x, p2.y);
  }
  friend bool operator > (const Point &p1, const Point &p2) {
    return make_pair(p1.x, p1.y) > make_pair(p2.x, p2.y);
  }
  friend bool operator == (const Point &p1, const Point &p2) {
    return p1.x == p2.x && p1.y == p2.y;
  }
  friend bool operator != (const Point &p1, const Point &p2) {
    return p1.x != p2.x || p1.y != p2.y;
  }
  friend istream& operator >> (istream &is, Point &p) {
    return is >> p.x >> p.y;
  }
  friend ostream& operator << (ostream &os, Point &p) {
    return os << p.x << " " << p.y << " " << p.id << endl;
  }
  double length() { return sqrt(1.0*x*x+1.0*y*y); }
  friend double dis(const Point &p1, const Point &p2) { return (p2-p1).length(); }
  double dis(const Point &p) { return (p-*this).length(); }
  friend T dot(const Point &p1, const Point &p2) { return p1.x*p2.x+p1.y*p2.y; }
  T dot(const Point &p) { return x*p.x+y*p.y; }
  friend Point rotate_90_c(const Point &p) { return Point(p.y, -p.x, p.id); }
  Point rotate_90_c() { return Point(y, -x, id); }
  friend double atan(const Point &p) { return atan2(p.y, p.x); }
};

template <typename T = double>
struct Vec { // 三维向量
  T x, y, z;
  Vec(const T &_x = 0, const T &_y = 0, const T &_z = 0) : x(_x), y(_y), z(_z) {}
  double len() { return sqrt(1.0*x*x+1.0*y*y+1.0*z*z); }
  friend Vec operator +(const Vec &v1, const Vec &v2) { return Vec(v1.x+v2.x, v1.y+v2.y, v1.z+v2.z); }
  friend Vec operator -(const Vec &v1, const Vec &v2) { return Vec(v1.x-v2.x, v1.y-v2.y, v1.z-v2.z); }
  friend Vec operator *(const T &k, const Vec &v) { return Vec(k*v.x, k*v.y, k*v.z); }
  friend Vec operator *(const Vec &v, const T &k) { return k*v; }
  friend Vec operator *(const Vec &v1, const Vec &v2) {
    return Vec(
        v1.y*v2.z-v1.z*v2.y,
        v1.z*v2.x-v1.x*v2.z,
        v1.x*v2.y-v1.y*v2.x
    );
  }
  friend T dot(const Vec &v1, const Vec &v2) { return v1.x*v2.x+v1.y*v2.y+v1.z*v2.z; }
  T dot(const Vec &v) { return dot(*this, v); }
  Vec& operator +=(const Vec &v) { return *this = *this+v; }
  Vec& operator -=(const Vec &v) { return *this = *this-v; }
  Vec& operator *=(const T &k) { return *this = *this*k; }
  Vec& operator *=(const Vec &v) { return *this = *this*v; }
  friend istream& operator >>(istream &is, Vec &v) { return is >> v.x >> v.y >> v.z; }
};

inline bool polar_angle1(const Point &p1, const Point &p2) {
  double d1 = atan(p1), d2 = atan(p2); 
  return d1 == d2 ? p1 < p2 : d1 < d2;
}

inline bool polar_angle2(const Point &p1, const Point &p2) {
  auto tmp = p1*p2;
  return tmp == 0 ? p1 < p2 : tmp > 0;
}

inline long long S(const Point &p1, const Point &p2, const Point &p3) {
  return abs(p1.x*p2.y+p1.y*p3.x+p2.x*p3.y-p1.x*p3.y-p1.y*p2.x-p2.y*p3.x);
}

struct Line {
  Point p1, p2;
  Line(){}
  Line(const Point &_p1, const Point &_p2) : p1(_p1), p2(_p2) {}
  friend bool cross(const Line &l1, const Line &l2) {
    #define SJ1(x) max(l1.p1.x, l1.p2.x) < min(l2.p1.x, l2.p2.x) || \
             max(l2.p1.x, l2.p2.x) < min(l1.p1.x, l1.p2.x)
    if (SJ1(x) || SJ1(y)) return false;
    #undef SJ1
    #define SJ2(a, b, c, d) ((a-b)*(a-c))*((a-b)*(a-d)) <= 0
    return SJ2(l1.p1, l1.p2, l2.p1, l2.p2) &&
         SJ2(l2.p1, l2.p2, l1.p1, l1.p2);
    #undef SJ2
  }
  friend bool on_line(const Line &l, const Point &p) {
    return abs((l.p1-l.p2)*(l.p1-p)) < eps;
  }
  friend Point cross_point(const Line &l1, const Line &l2) {
    Point v1 = l1.p2-l1.p1, v2 = l2.p2-l2.p1;
    if (abs(v1*v2) < eps) return Point(0, 0); // no cross_point
    double t = (l2.p1-l1.p1)*v2/(v1*v2);
    return l1.p1+v1*t;
  }
};

struct Circular {
  Point o;
  double r;
  Circular(){}
  Circular(const Point &_o, const double &_r) : o(_o), r(_r) {}
  template <typename T>
  Circular(const T &_x, const T &_y, const double &_r) : o(Point(_x, _y)), r(_r) {}
  friend bool in_cir(const Circular &c, const Point &p) { return dis(c.o, p) <= c.r; }
  bool in_cir(const Point &p) { return dis(o, p) <= r; }
};

inline Circular get_cir(const Point &p1, const Point &p2, const Point &p3) {
  Circular res;
  res.o = cross_point(Line((p1+p2)/2, (p1+p2)/2+(p2-p1).rotate_90_c()),
            Line((p1+p3)/2, (p1+p3)/2+(p3-p1).rotate_90_c()));
  res.r = dis(res.o, p1);
  return res;
}

int n;
int stk[N], used[N], tp;
Point p[N];

inline void Andrew() {
  memset(used, 0, sizeof used);
  sort(p+1, p+n+1);
  tp = 0;
  stk[++tp] = 1;
  for (int i = 2; i <= n; ++i) {
    while (tp >= 2 && (p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp]]) <= 0)
      used[stk[tp--]] = 0;
    used[i] = 1;
    stk[++tp] = i;
  }
  int tmp = tp;
  for (int i = n-1; i; --i) {
    if (used[i]) continue;
    while (tp >= tmp && (p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp]]) <= 0)
      used[stk[tp--]] = 0;
    used[i] = 1;
    stk[++tp] = i;
  }
}

Point a[N];
int n, ansa, ansb;
double mindist;

inline bool cmp_y(const Point &p1, const Point &p2) { return p1.y < p2.y; }

void upd_ans(const Point &p1, const Point &p2) {
  double dist = dis(p1, p2);
  if (dist < mindist) mindist = dist, ansa = p1.id, ansb = p2.id;
}

void rec(int l, int r) {
  if (r-l <= 3) {
    for (int i = l; i < r; ++i)
      for (int j = i+1; j <= r; ++j)
        upd_ans(a[i], a[j]);
    sort(a+l, a+r+1, cmp_y);
    return;
  }

  static Point t[N];
  int m = (l+r)>>1, midx = a[m].x;
  rec(l, m); rec(m+1, r);
  merge(a+l, a+m+1, a+m+1, a+r+1, t, cmp_y);
  copy(t, t+r-l+1, a+l);

  int tsz = 0;
  for (int i = l; i <= r; ++i)
    if (abs(a[i].x-midx) <= mindist) {
      for (int j = tsz; j && a[i].y-t[j].y < mindist; --j)
        upd_ans(a[i], t[j]);
      t[++tsz] = a[i];
    }
}

inline void mindist_pair() {
  sort(a+1, a+n+1);
  mindist = INF;
  rec(1, n);
}

inline Circular RIA() {
  Circular cir;
  random_shuffle(a+1, a+n+1);
  for (int i = 1; i <= n; ++i) {
    if (cir.in_cir(a[i])) continue;
    cir = Circular(a[i], 0);
    for (int j = 1; j < i; ++j) {
      if (cir.in_cir(a[j])) continue;
      cir = Circular((a[i]+a[j])/2, dis(a[i], a[j])/2);
      for (int k = 1; k < j; ++k) {
        if (cir.in_cir(a[k])) continue;
        cir = get_cir(a[i], a[j], a[k]);
      }
    }
  }
  return cir;
}

struct Heap {
  static const int Maxn = 1e6+7;
  int sz, a[Maxn];
  Heap() { sz = 0; memset(a, 0, sizeof a); }
  inline bool cmp(int x, int y) { return x < y; } // 小根堆
  inline int size() { return sz; }
  inline bool empty() { return sz == 0; }
  inline int top() { return a[1]; }
  inline void push(int x) { a[++sz] = x; swift_up(sz); }
  inline void pop() { swap(a[1], a[sz--]); swift_down(1); }
  inline void swift_up(int p) {
    while(p > 1 && cmp(a[p], a[p>>1])) // a[p] < a[p<<1]
      swap(a[p], a[p>>1]), p >>= 1;
  }
  inline void swift_down(int p) {
    int l, r, s;
    while(true) {
      l = p<<1; r = p<<1|1;
      if(l > sz) break;
      if(r > sz || cmp(a[l], a[r])) s = l; // a[l] < a[r]
      else s = r;
      if(cmp(a[s], a[p])) // a[s] < a[p]
        swap(a[p], a[s]), p = s;
      else break;
    }
  }
};

template <typename T>
struct Heap{
  priority_queue<T> a,b;  // heap=a-b
  void push(T x){a.push(x);}
  void erase(T x){b.push(x);}
  T top(){
    while(!b.empty() && a.top()==b.top())
      a.pop(),b.pop();
    return a.size() ? a.top() : 0; // ???
  }
  void pop(){
    while(!b.empty() && a.top()==b.top())
      a.pop(),b.pop();
    a.pop();
  }
  T top2(){ // 次大值
    T t=top(); pop();
    T ans=top(); push(t);
    return ans;
  }
  size_t size(){return a.size()-b.size();}
};

struct Splay {
  #define root e[0].ch[1]
  typedef int T;
  struct node {
    T v = 0;
    int ch[2] = {0, 0};
    int fa = 0, sum = 0, cnt = 0;
  } e[N];
  int n;
  void update(int x) { e[x].sum = e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].cnt; }
  int identify(int x) { return x == e[e[x].fa].ch[1]; } // check left or right child
  void connect(int x, int f, int son) { e[x].fa = f; e[f].ch[son] = x; }
  void rotate(int x) {
    int y = e[x].fa,
        r = e[y].fa,
        rson = identify(y),
        yson = identify(x),
        b = e[x].ch[yson^1];
    connect(b, y, yson);
    connect(y, x, yson^1);
    connect(x, r, rson);
    update(y); update(x);
  }
  void splay(int at, int to) {
    to = e[to].fa;
    int up;
    while((up = e[at].fa) != to) {
      if(e[up].fa != to)
        rotate(identify(up) == identify(at) ? up : at);
      rotate(at);
    }
  }
  int add_point(T v, int fa) {
    ++n; e[n].v = v; e[n].fa = fa; e[n].sum = e[n].cnt = 1;
    return n;
  }
  int find(T v) {
    int now = root, last = 0;
    while (now && e[now].v != v)
      last = now, now = e[now].ch[v > e[now].v];
    splay((now ? now : last), root);
    return now;
  }
  void insert(T v) {
    if (!root) { root = add_point(v, root); return; }
    int now = root, last = 0;
    while (now && e[now].v != v)
      last = now, now = e[now].ch[v > e[now].v];
    if (now) ++e[now].cnt;
    else now = e[last].ch[v > e[last].v] = add_point(v, last);
    splay(now, root);
  }
  void erase(T v) {
    int del = find(v);
    if (!del) return;
    if (e[del].cnt > 1) {
      --e[del].cnt;
      --e[del].sum;
    } else if (!e[del].ch[0]) {
      root = e[del].ch[1];
      e[root].fa = 0;
    } else {
      int oldroot = root;
      splay(nex(e[del].ch[0], 1), root);
      connect(e[oldroot].ch[1], root, 1);
      update(root);
    }
  }
  int rank(T v) { return e[e[find(v)].ch[0]].sum+1; }
  T atrank(int x) {
    if (x > e[root].sum) return -INF;
    int now = root;
    while (true) {
      if (x <= e[e[now].ch[0]].sum) now = e[now].ch[0];
      else if ((x -= e[e[now].ch[0]].sum) <= e[now].cnt) break;
      else x -= e[now].cnt, now = e[now].ch[1];
    }
    splay(now, root);
    return e[now].v;
  }
  // small 0, big 1
  int nex(int x, int opt) { while (e[x].ch[opt]) x = e[x].ch[opt]; return x; }
  T lower(T v, int opt) {
    insert(v);
    T res = e[nex(e[root].ch[opt], opt^1)].v;
    erase(v);
    return res;
  }
  #undef root
};

struct Splay {
  typedef int T;
  struct node {
    T v = 0;
    int ch[2] = { 0, 0 };
    int fa = 0, sum = 0, cnt = 0, tag = 0;
  } e[N];
  int sz, &root = e[0].ch[1];
  void update(int x) { e[x].sum = e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].cnt; }
  int identify(int x) { return x == e[e[x].fa].ch[1]; }
  void connect(int x,int f,int son) { e[x].fa = f; e[f].ch[son] = x; }
  void rotate(int x) {
    int y = e[x].fa,
      r = e[y].fa,
      rson = identify(y),
      yson = identify(x),
      b = e[x].ch[yson^1];
    connect(b, y, yson);
    connect(y, x, yson^1);
    connect(x, r, rson);
    update(y); update(x);
  }
  void splay(int at,int to = 0) {
    to = e[to].fa;
    int up;
    while((up = e[at].fa) != to) {
      if(e[up].fa != to)
        rotate(identify(up) == identify(at) ? up : at);
      rotate(at);
    }
  }
  int add_point(T v, int fa) {
    ++sz; e[sz].v = v; e[sz].fa = fa; e[sz].sum = e[sz].cnt = 1;
    return sz;
  }
  int find(int x) {
    if (x > e[root].sum) return -INF;
    int now = root;
    while (true) {
      push_down(now);
      if (x <= e[e[now].ch[0]].sum) now = e[now].ch[0];
      else if ((x -= e[e[now].ch[0]].sum) <= e[now].cnt) break;
      else x -= e[now].cnt, now = e[now].ch[1];
    }
    return now;
  }
  int build(int l, int r, int fa) {
    if (l > r) return 0;
    int mid = (l+r)>>1,
      now = add_point(mid, fa);
    e[now].ch[0] = build(l, mid-1, now);
    e[now].ch[1] = build(mid+1, r, now);
    update(now);
    return now;
  }
  void push_down(int x) {
    if (x && e[x].tag) {
      e[e[x].ch[0]].tag ^= 1;
      e[e[x].ch[1]].tag ^= 1;
      swap(e[x].ch[0], e[x].ch[1]);
      e[x].tag = 0;
    }
  }
  void reverse(int l, int r) {
    int pl = find(l-1+1), pr = find(r+1+1);
    splay(pl); splay(pr, pl);
    e[e[e[root].ch[1]].ch[0]].tag ^= 1;
  }
  void print_LMR(int x) {
    if (!x) return;
    push_down(x);
    print_LMR(e[x].ch[0]);
    if (e[x].v != 0 && e[x].v != n+1)
      write(a[e[x].v]), putchar(' ');
    print_LMR(e[x].ch[1]);
  }
} tree;

template <typename T>
struct SegmentTree {
  int sz;
  T tr[N<<2], lazy[N<<2];
  SegmentTree(){}
  void build(const int &n, const T &k = 0) { sz = n; _build(1, n, k); }
  template <typename TT>
  void build(const TT a[], const int &n) { sz = n; _build(a, 1, n); }
  void modify(const int &x, const T &k) { _modify(x, k, 1, sz); }
  void add(const int &x, const T &k) { _add(x, x, k, 1, sz); }
  void add(int l, int r, const T &k) { if (l > r) swap(l, r); _add(l, r, k, 1, sz); }
  T query(const int &x) { return _query(x, x, 1, sz); }
  T query(int l, int r) { if (l > r) swap(l, r); return _query(l, r, 1, sz); }
private :
  void push_up(const int &i) { tr[i] = tr[i<<1]+tr[i<<1|1]; }
  void push_down(const int &i, const int &len) {
    if (!lazy[i]) return;
    tr[i<<1] += lazy[i]*(len-len/2);
    tr[i<<1|1] += lazy[i]*(len/2);
    lazy[i<<1] += lazy[i];
    lazy[i<<1|1] += lazy[i];
    lazy[i] = 0;
  }
  void _build(const int &l, const int &r, const T &k = 0, const int &i = 1) {
    lazy[i] = 0;
    if (l == r) { tr[i] = k; return; }
    int mid = (l+r)>>1;
    _build(l, mid, k, i<<1);
    _build(mid+1, r, k, i<<1|1);
    push_up(i);
  }
  template <typename TT>
  void _build(const TT a[], const int &l, const int &r, const int &i = 1) {
    lazy[i] = 0;
    if (l == r) { tr[i] = a[l]; return; }
    int mid = (l+r)>>1;
    _build(a, l, mid, i<<1);
    _build(a, mid+1, r, i<<1|1);
    push_up(i);
  }
  void _modify(const int &x, const T &k, const int &trl, const int &trr, const int &i = 1) {
    if (trl == x && trr == x) {
      tr[i] = k;
      lazy[i] = 0;
      return;
    }
    push_down(i, trr-trl+1);
    int mid = (trl+trr)>>1;
    if (x <= mid) _modify(x, k, trl, mid, i<<1);
    else _modify(x, k, mid+1, trr, i<<1|1);
    push_up(i);
  }
  void _add(const int &l, const int &r, const T &k, const int &trl, const int &trr, const int &i = 1) {
    if (trl >= l && trr <= r) {
      tr[i] += k*(trr-trl+1);
      lazy[i] += k;
      return;
    }
    push_down(i, trr-trl+1);
    int mid = (trl+trr)>>1;
    if (l <= mid) _add(l, r, k, trl, mid, i<<1);
    if (r >  mid) _add(l, r, k, mid+1, trr, i<<1|1);
    push_up(i);
  }
  T _query(const int &l, const int &r, const int &trl, const int &trr, const int &i = 1) {
    if (trl >= l && trr <= r) return tr[i];
    push_down(i, trr-trl+1);
    int mid = (trl+trr)>>1;
    T res = 0;
    if (l <= mid) res += _query(l, r, trl, mid, i<<1);
    if (r >  mid) res += _query(l, r, mid+1, trr, i<<1|1);
    return res;
  }
};

动态开点

template <typename T>
struct SegmentTree { // 区间加减区间和
  struct TreeNode {
    int l, r;
    TreeNode *ls, *rs;
    T val, lazy;
    TreeNode() { ls = rs = nullptr; }
    TreeNode(const int &_l, const int &_r, const T &_val = 0)
        : l(_l), r(_r), val(_val) {
      ls = rs = nullptr;
      lazy = 0;
    }
    int len() const { return r-l+1; }
  };
  TreeNode *root;
  void clear(TreeNode *rt) {
    if (!rt) return;
    clear(rt->ls);
    clear(rt->rs);
    delete rt;
  }
  void build(const int &n) {
    clear(root);
    root = new TreeNode(1, n);
  }
  void push_up(TreeNode *rt) {
    rt->val = (rt->ls ? rt->ls->val : 0)+(rt->rs ? rt->rs->val : 0);
  }
  void push_down(TreeNode *rt) {
    if (!rt->lazy) return;
    int mid = (rt->l+rt->r)>>1;
    if (!rt->ls) rt->ls = new TreeNode(rt->l, mid);
    if (!rt->rs) rt->rs = new TreeNode(mid+1, rt->r);
    rt->ls->lazy += rt->lazy;
    rt->ls->val += rt->lazy*rt->ls->len();
    rt->rs->lazy += rt->lazy;
    rt->rs->val += rt->lazy*rt->rs->len();
    rt->lazy = 0;
  }
  void update(const int &x, const T &k) { update(x, k, root); }
  void update(const int &x, const T &k, TreeNode *rt) {
    if (rt->l == x && rt->r == x) return rt->val = k, void();
    push_down(rt);
    int mid = (rt->l+rt->r)>>1;
    if (x <= mid) update(x, k, rt->ls ? rt->ls : rt->ls = new TreeNode(rt->l, mid));
    else update(x, k, rt->rs ? rt->rs : rt->rs = new TreeNode(mid+1, rt->r));
    push_up(rt);
  }
  void add(const int &x, const T &k) { add(x, x, k, root); }
  void add(const int &l, const int &r, const T &k) { add(l, r, k, root); }
  void add(const int &l, const int &r, const T &k, TreeNode *rt) {
    if (rt->l >= l && rt->r <= r) {
      rt->val += rt->len()*k;
      rt->lazy += k;
      return;
    }
    push_down(rt);
    int mid = (rt->l+rt->r)>>1;
    if (l <= mid) add(l, r, k, rt->ls ? rt->ls : rt->ls = new TreeNode(rt->l, mid));
    if (r >  mid) add(l, r, k, rt->rs ? rt->rs : rt->rs = new TreeNode(mid+1, rt->r));
    push_up(rt);
  }
  T query(const int &x) { return query(x, x, root); }
  T query(const int &l, const int &r) { return query(l, r, root); }
  T query(const int &l, const int &r, TreeNode *rt) {
    if (rt->l >= l && rt->r <= r) return rt->val;
    push_down(rt);
    int mid = (rt->l+rt->r)>>1;
    if (l <= mid && !rt->ls) rt->ls = new TreeNode(rt->l, mid);
    if (r >  mid && !rt->rs) rt->rs = new TreeNode(mid+1, rt->r);
    if (r <= mid) return query(l, r, rt->ls);
    if (l >  mid) return query(l, r, rt->rs);
    return query(l, r, rt->ls)+query(l, r, rt->rs);
  }
};

内存池

template <typename T>
struct SegmentTree { // 区间加减区间和
  struct TreeNode {
    int l, r;
    TreeNode *ls, *rs;
    T val, lazy;
    int len() const { return r-l+1; }
  } tr[N<<1];
  queue<TreeNode*> memory_pool;
  SegmentTree() { for (int i = 0; i < N<<2; ++i) memory_pool.push(tr+i); }
  TreeNode* fuck(const int &l, const int &r, const T &val = 0) { // new
    TreeNode *ptr = memory_pool.front();
    memory_pool.pop();
    ptr->l = l; ptr->r = r; ptr->val = val;
    ptr->ls = ptr->rs = nullptr;
    return ptr;
  }
  void shit(TreeNode *ptr) { memory_pool.push(ptr); } // delete
  TreeNode *root;
  void clear(TreeNode *rt) {
    if (!rt) return;
    clear(rt->ls);
    clear(rt->rs);
    shit(rt);
  }
  void build(const int &n) {
    clear(root);
    root = fuck(1, n);
  }
  void push_up(TreeNode *rt) {
    rt->val = (rt->ls ? rt->ls->val : 0)+(rt->rs ? rt->rs->val : 0);
  }
  void push_down(TreeNode *rt) {
    if (!rt->lazy) return;
    int mid = (rt->l+rt->r)>>1;
    if (!rt->ls) rt->ls = fuck(rt->l, mid);
    if (!rt->rs) rt->rs = fuck(mid+1, rt->r);
    rt->ls->lazy += rt->lazy;
    rt->ls->val += rt->lazy*rt->ls->len();
    rt->rs->lazy += rt->lazy;
    rt->rs->val += rt->lazy*rt->rs->len();
    rt->lazy = 0;
  }
  void update(const int &x, const T &k) { update(x, k, root); }
  void update(const int &x, const T &k, TreeNode *rt) {
    if (rt->l == x && rt->r == x) return rt->val = k, void();
    push_down(rt);
    int mid = (rt->l+rt->r)>>1;
    if (x <= mid) update(x, k, rt->ls ? rt->ls : rt->ls = fuck(rt->l, mid));
    else update(x, k, rt->rs ? rt->rs : rt->rs = fuck(mid+1, rt->r));
    push_up(rt);
  }
  void add(const int &x, const T &k) { add(x, x, k, root); }
  void add(const int &l, const int &r, const T &k) { add(l, r, k, root); }
  void add(const int &l, const int &r, const T &k, TreeNode *rt) {
    if (rt->l >= l && rt->r <= r) {
      rt->val += rt->len()*k;
      rt->lazy += k;
      return;
    }
    push_down(rt);
    int mid = (rt->l+rt->r)>>1;
    if (l <= mid) add(l, r, k, rt->ls ? rt->ls : rt->ls = fuck(rt->l, mid));
    if (r >  mid) add(l, r, k, rt->rs ? rt->rs : rt->rs = fuck(mid+1, rt->r));
    push_up(rt);
  }
  T query(const int &x) { return query(x, x, root); }
  T query(const int &l, const int &r) { return query(l, r, root); }
  T query(const int &l, const int &r, TreeNode *rt) {
    if (rt->l >= l && rt->r <= r) return rt->val;
    push_down(rt);
    int mid = (rt->l+rt->r)>>1;
    if (l <= mid && !rt->ls) rt->ls = fuck(rt->l, mid);
    if (r >  mid && !rt->rs) rt->rs = fuck(mid+1, rt->r);
    if (r <= mid) return query(l, r, rt->ls);
    if (l >  mid) return query(l, r, rt->rs);
    return query(l, r, rt->ls)+query(l, r, rt->rs);
  }
};

template <typename T>
struct SegmentTree {
  int sz;
  int tag[N<<2];
  T tr[N<<2], lazy[N<<2];
  SegmentTree(){}
  void build(const int &n, const T &k = 0) { sz = n; _build(1, n, k); }
  template <typename TT>
  void build(const TT a[], const int &n) { sz = n; _build(a, 1, n); }
  void update(const int &x, const T &k) { _update(x, x, k, 1, sz); }
  void update(int l, int r, const T &k) { if (l > r) swap(l, r); _update(l, r, k, 1, sz); }
  T query(const int &x) { return _query(x, x, 1, sz); }
  T query(int l, int r) { if (l > r) swap(l, r); return _query(l, r, 1, sz); }
private :
  void push_up(const int &i) { tr[i] = tr[i<<1]+tr[i<<1|1]; }
  void push_down(const int &i, const int &len) {
    if (!tag[i]) return;
    tr[i<<1] = lazy[i]*(len-len/2);
    tr[i<<1|1] = lazy[i]*(len/2);
    lazy[i<<1] = lazy[i<<1|1] = lazy[i];
    tag[i<<1] = tag[i<<1|1] = 1;
    tag[i] = 0;
  }
  void _build(const int &l, const int &r, const T &k = 0, const int &i = 1) {
    lazy[i] = tag[i] = 0;
    if (l == r) { tr[i] = k; return; }
    int mid = (l+r)>>1;
    _build(l, mid, k, i<<1);
    _build(mid+1, r, k, i<<1|1);
    push_up(i);
  }
  template <typename TT>
  void _build(const TT a[], const int &l, const int &r, const int &i = 1) {
    lazy[i] = tag[i] = 0;
    if (l == r) { tr[i] = a[l]; return; }
    int mid = (l+r)>>1;
    _build(a, l, mid, i<<1);
    _build(a, mid+1, r, i<<1|1);
    push_up(i);
  }
  void _update(const int &l, const int &r, const T &k, const int &trl, const int &trr, const int &i = 1) {
    if (trl >= l && trr <= r) {
      tr[i] = k*(trr-trl+1);
      lazy[i] = k;
      tag[i] = 1;
      return;
    }
    push_down(i, trr-trl+1);
    int mid = (trl+trr)>>1;
    if (l <= mid) _update(l, r, k, trl, mid, i<<1);
    if (r >  mid) _update(l, r, k, mid+1, trr, i<<1|1);
    push_up(i);
  }
  T _query(const int &l, const int &r, const int &trl, const int &trr, const int &i = 1) {
    if (trl >= l && trr <= r) return tr[i];
    push_down(i, trr-trl+1);
    int mid = (trl+trr)>>1;
    T res = 0;
    if (l <= mid) res += _query(l, r, trl, mid, i<<1);
    if (r >  mid) res += _query(l, r, mid+1, trr, i<<1|1);
    return res;
  }
};

template <typename T, typename U = greater<T>>
struct SegmentTree {
  U cmp = U();
  int n;
  T tr[N<<2], lazy[N<<2], init_val = cmp(0, 1) ? INF : -INF;
  SegmentTree(){}
  T mv(const T &x, const T &y) { return cmp(x, y) ? x : y;}
  void build(const int &_n, const T &k = 0) { n = _n; _build(1, n, k); }
  template <typename TT>
  void build(const TT a[], const int &_n) { n = _n; _build(a, 1, n); }
  void modify(const int &x, const T &k) { _modify(x, k, 1, n); }
  void add(const int &x, const T &k) { _add(x, x, k, 1, n); }
  void add(const int &l, const int &r, const T &k) { _add(l, r, k, 1, n); }
  T query(const int &x) { return _query(x, x, 1, n); }
  T query(const int &l, const int &r) { return _query(l, r, 1, n); }
private :
  void push_up(const int &i) { tr[i] = mv(tr[i<<1], tr[i<<1|1]); }
  void push_down(const int &i) {
    if (!lazy[i]) return;
    tr[i<<1] += lazy[i];
    tr[i<<1|1] += lazy[i];
    lazy[i<<1] += lazy[i];
    lazy[i<<1|1] += lazy[i];
    lazy[i] = 0;
  }
  void _build(const int &l, const int &r, const T &k = 0, const int &i = 1) {
    lazy[i] = 0;
    if (l == r) { tr[i] = k; return; }
    int mid = (l+r)>>1;
    _build(l, mid, k, i<<1);
    _build(mid+1, r, k, i<<1|1);
    push_up(i);
  }
  template <typename TT>
  void _build(const TT a[], const int &l, const int &r, const int &i = 1) {
    lazy[i] = 0;
    if (l == r) { tr[i] = a[l]; return; }
    int mid = (l+r)>>1;
    _build(a, l, mid, i<<1);
    _build(a, mid+1, r, i<<1|1);
    push_up(i);
  }
  void _modify(const int &x, const T &k, const int &trl, const int &trr, const int &i = 1) {
    if (trl == x && trr == x) return tr[i] = k, void();
    push_down(i);
    int mid = (trl+trr)>>1;
    if (x <= mid) _modify(x, k, trl, mid, i<<1);
    else _modify(x, k, mid+1, trr, i<<1|1);
    push_up(i);
  }
  void _add(const int &l, const int &r, const T &k, const int &trl, const int &trr, const int &i = 1) {
    if (trl >= l && trr <= r) {
      tr[i] += k;
      lazy[i] += k;
      return;
    }
    push_down(i);
    int mid = (trl+trr)>>1;
    if (l <= mid) _add(l, r, k, trl, mid, i<<1);
    if (r >  mid) _add(l, r, k, mid+1, trr, i<<1|1);
    push_up(i);
  }
  T _query(const int &l, const int &r, const int &trl, const int &trr, const int &i = 1) {
    if (trl >= l && trr <= r) return tr[i];
    push_down(i);
    int mid = (trl+trr)>>1;
    if (r <=  mid) return _query(l, r, trl, mid, i<<1);
    if (l >  mid) return _query(l, r, mid+1, trr, i<<1|1);
    return mv(_query(l, r, trl, mid, i<<1), _query(l, r, mid+1, trr, i<<1|1));
  }
};

template <typename T, typename U = greater<T>>
struct SegmentTree {
  SegmentTree(){}
  void build(const int &_n, const T &k = 0) { n = _n; _build(1, n, k); }
  template <typename TT>
  void buiil(const int _n, const TT a[]) { n = _n; _build(1, n, a); }
  void modify(const int &x, const T &k) { _modify(x, x, k); }
  void modify(const int &l, const int &r, const T &k) { _modify(l, r, k); }
  void add(const int &x, const T &k) { _add(x, k); }
  T query(const int &x) { return _query(x, x); }
  T query(const int &l, const int &r) { return _query(l, r); }
private:
  struct TreeNode
  {
    int l, r;
    T v, lazy;
  } tr[N<<2];
  int n;
  T init_val = cmp(0, 1) ? INF : -INF;
  U cmp = U();
  T mv(const T &x, const T &y) { return cmp(x, y) ? x : y;}
  void update(const int &i, const T &k) { tr[i].v = mv(tr[i].v, k); tr[i].lazy = mv(tr[i].lazy, k); }
  void push_up(const int &i) { tr[i].v = mv(tr[i<<1].v, tr[i<<1|1].v); }
  void push_down(const int &i) {
    if (tr[i].lazy == init_val) return;
    update(i<<1, tr[i].lazy);
    update(i<<1|1, tr[i].lazy);
    tr[i].lazy = init_val;
  }
  void _build(const int &l, const int &r, const T &k = 0, const int &i = 1) {
    tr[i].lazy = init_val;
    tr[i].l = l; tr[i].r = r;
    if (l == r) { tr[i].v = k; return; }
    int mid = (l+r)>>1;
    _build(l, mid, k, i<<1);
    _build(mid+1, r, k, i<<1|1);
    push_up(i);
  }
  template <typename TT>
  void _build(const int &l, const int &r, const TT a[], const int &i = 1) {
    tr[i].lazy = init_val;
    tr[i].l = l; tr[i].r = r;
    if (l == r) { tr[i].v = a[l]; return; }
    int mid = (l+r)>>1;
    _build(l, mid, a, i<<1);
    _build(mid+1, r, a, i<<1|1);
    push_up(i);
  }
  void _modify(const int &l, const int &r, const T &k, const int &i = 1) {
    if (tr[i].l  >= l && tr[i].r <= r) { update(i, k); return; }
    push_down(i);
    int mid = (tr[i].l+tr[i].r)>>1;
    if (l <= mid) _modify(l, r, k, i<<1);
    if (r >  mid) _modify(l, r, k, i<<1|1);
    push_up(i);
  }
  void _add(const int &x, const T &k, const int &i = 1) {
    if (tr[i].l == x && tr[i].r == x) { tr[i].v += k; return; }
    push_down(i);
    int mid = (tr[i].l+tr[i].r)>>1;
    if (x <= mid) _add(x, k, i<<1);
    else _add(x, k, i<<1|1);
    push_up(i);
  }
  T _query(const int &l, const int &r, const int &i = 1) {
    if (tr[i].l  >= l && tr[i].r <= r) return tr[i].v;
    push_down(i);
    int mid = (tr[i].l+tr[i].r)>>1;
    T res = init_val;
    if (l <= mid) res = mv(res, _query(l, r, i<<1));
    if (r >  mid) res = mv(res, _query(l, r, i<<1|1));
    return res;
  }
};

struct SegmentTree {
  struct TreeNode {
    long long s, ls, rs, ms;
    void set(long long x) { s = ls = rs = ms = x; }
    friend TreeNode operator +(const TreeNode &lc, const TreeNode &rc) {
      return TreeNode {
          lc.s+rc.s,
          max(lc.ls, lc.s+rc.ls),
          max(rc.rs, lc.rs+rc.s),
          max({lc.ms, rc.ms, lc.rs+rc.ls})
      };
    }
  } tr[N<<2];
  int *a, n;
  void build(int a[], int n) {
    this->a = a;
    this->n = n;
    build(1, n, 1);
  }
  void build(int l, int r, int i) {
    if (l == r) return tr[i].set(a[l]);
    int mid = (l+r)>>1;
    build(l, mid, i<<1);
    build(mid+1, r, i<<1|1);
    tr[i] = tr[i<<1]+tr[i<<1|1];
  }
  void update(int x, long long v) { update(x, v, 1, n, 1); }
  void update(int x, long long v, int l, int r, int i) {
    if (l == r) return tr[i].set(v);
    int mid = (l+r)>>1;
    if (x <= mid) update(x, v, l, mid, i<<1);
    else update(x, v, mid+1, r, i<<1|1);
    tr[i] = tr[i<<1]+tr[i<<1|1];
  }
  long long query(int L, int R) { return query(L, R, 1, n, 1).ms; }
  TreeNode query(int L, int R, int l, int r, int i) {
    if (l >= L && r <= R) return tr[i];
    int mid = (l+r)>>1;
    if (R <= mid) return query(L, R, l, mid, i<<1);
    if (L >  mid) return query(L, R, mid+1, r, i<<1|1);
    return query(L, R, l, mid, i<<1)+query(L, R, mid+1, r, i<<1|1);
  }
};

template <typename T>
struct zkwSegmentTree {
  int sz;
  T sum[N<<2], mn[N<<2], mx[N<<2], add[N<<2];
  void update(const int &x) {
    T tmp;
    tmp = min(mn[x], mn[x^1]); mn[x] -= tmp; mn[x^1] -= tmp; mn[x>>1] += tmp;
    tmp = max(mx[x], mx[x^1]); mx[x] -= tmp; mx[x^1] -= tmp; mx[x>>1] += tmp;
  }
  template <typename TT>
  void build(const TT a[], const int &n) {
    for (sz = 1; sz <= n+1; sz <<= 1);
    for (int i = sz+1; i <= sz+n; ++i)
      sum[i] = mn[i] = mx[i] = a[i-sz];
    for (int i = sz-1; i; --i) {
      sum[i] = sum[i<<1]+sum[i<<1|1];
      mn[i] = min(mn[i<<1], mn[i<<1|1]); mn[i<<1] -= mn[i]; mn[i<<1|1] -= mn[i];
      mx[i] = max(mx[i<<1], mx[i<<1|1]); mx[i<<1] -= mx[i]; mx[i<<1|1] -= mx[i];
    }
  }
  void update(int x, const T &v) {
    x += sz; mx[x] += v; mn[x] += v; sum[x] += v;
    for ( ; x > 1; x >>= 1) {
      sum[x] += v;
      update(x);
    }
  }
  void update(int s, int t, const T &v) {
    int lc = 0, rc = 0, len = 1;
    for (s += sz-1, t += sz+1; s^t^1; s >>= 1, t >>= 1, len <<= 1) {
      if (~s&1) add[s^1] += v, lc += len, mn[s^1] += v, mx[s^1] += v;
      if ( t&1) add[t^1] += v, rc += len, mn[t^1] += v, mx[t^1] += v;
      sum[s>>1] += v*lc; sum[t>>1] += v*rc;
      update(s); update(t);
    }
    for (lc += rc; s; s >>= 1) {
      sum[s>>1] += v*lc;
      update(s);
    }
  }
  T query(int x) {
    T res = 0;
    for (x += sz; x; x >>= 1) res += mn[x];
    return res;
  }
  T query_sum(int s, int t) {
    int lc = 0, rc = 0, len = 1;
    T res = 0;
    for (s += sz-1, t += sz+1; s^t^1; s >>= 1, t >>= 1, len <<= 1) {
      if (~s&1) res += sum[s^1]+len*add[s^1], lc += len;
      if ( t&1) res += sum[t^1]+len*add[t^1], rc += len;
      if (add[s>>1]) res += add[s>>1]*lc;
      if (add[t>>1]) res += add[t>>1]*rc;
    }
    for (lc += rc, s >>= 1; s; s >>= 1) if (add[s]) res += add[s]*lc;
    return res;
  }
  T query_min(int s, int t) {
    if (s == t) return query(s);
    T l = 0, r = 0, res = 0;
    for (s += sz, t += sz; s^t^1; s >>= 1, t >>= 1) {
      l += mn[s]; r += mn[t];
      if (~s^1) l = min(l, mn[s^1]);
      if ( t^1) r = min(r, mn[t^1]);
    }
    for (res = min(l, r), s >>= 1; s; s >>= 1) res += mn[s];
    return res;
  }
  T query_max(int s, int t) {
    if (s == t) return query(s);
    T l = 0, r = 0, res = 0;
    for (s += sz, t += sz; s^t^1; s >>= 1, t >>= 1) {
      l += mx[s]; r += mx[t];
      if (~s^1) l = max(l, mx[s^1]);
      if ( t^1) r = max(r, mx[t^1]);
    }
    for (res = max(l, r), s >>= 1; s; s >>= 1) res += mx[s];
    return res;
  }
};

int merge(int x, int y) { // 太难了,现场全重写吧
  if (!x || !y) return x+y;
  int &z = x; // int z = new_node(); // 新建结点?
  lc[z] = merge(lc[x], lc[y]);
  rc[z] = merge(rc[x], rc[y]);
  if (!lc[z] && !rc[z]) tr[z].first = tr[x].first+tr[y].first;
  else push_up(z); // tr[z] = giao(x, y);
  // del(y); // del(x); // 保留结点?
  return z;
}

template <typename T>
struct Tree {
  int tot, lc[NLOG], rc[NLOG];
  T tr[NLOG];
  void init() { tot = 0; }
  T giao(const T &x, const T &y) { return x+y; }
  void push_up(int i) { tr[i] = giao(tr[lc[i]], tr[rc[i]]); }
  int new_node(T v = 0) {
    ++tot; // assert(++tot < NLOG);
    lc[tot] = rc[tot] = 0;
    tr[tot] = v;
    return tot;
  }
  void add(int x, T v, int l, int r, int &i) {
    if (!i) i = new_node();
    if (l == r) return tr[i] += v, void();
    int mid = (l+r)>>1;
    if (x <= mid) add(x, v, l, mid, lc[i]);
    else add(x, v, mid+1, r, rc[i]);
    push_up(i);
  }
  void merge(int l, int r, int &x, int &y) { // merge y to x
    if (!x || !y) return x += y, void();
    if (l == r) return tr[x] += tr[y], void();
    int mid = (l+r)>>1;
    merge(l, mid, lc[x], lc[y]);
    merge(mid+1, r, rc[x], rc[y]);
    push_up(x); // del(y);
  }
  /*
  int merge(int l, int r, int x, int y) { // new node
    if (!x || !y) return x += y;
    int cur = new_node(), mid = (l+r)>>1;
    if (l == r) return tr[cur] = tr[x]+tr[y], cur;
    lc[cur] = merge(l, mid, lc[x], lc[y]);
    rc[cur] = merge(mid+1, r, rc[x], rc[y]);
    push_up(cur);
    return cur;
  }
  */
  void split(int L, int R, int l, int r, int &x, int &y) { //split x [L, R] to y
    if (!x) return;
    if (L <= l && r <= R) return y = x, x = 0, void();
    if (!y) y = new_node();
    int mid = (l+r)>>1;
    if (L <= mid) split(L, R, l, mid, lc[x], lc[y]);
    if (R >  mid) split(L, R, mid+1, r, rc[x], rc[y]);
    push_up(x); push_up(y);
  }
  T query(int L, int R, int l, int r, int i) {
    if (!i) return 0;
    if (L <= l && r <= R) return tr[i];
    int mid = (l+r)>>1;
    if (R <= mid) return query(L, R, l, mid, lc[i]);
    if (L >  mid) return query(L, R, mid+1, r, rc[i]);
    return giao(query(L, R, l, mid, lc[i]), query(L, R, mid+1, r, rc[i]));
  }
  int query_kth(int k, int l, int r, int i) {
    if (l == r) return l;
    int mid = (l+r)>>1;
    if (k <= tr[lc[i]]) return query_kth(k, l, mid, lc[i]);
    return query_kth(k-tr[lc[i]], mid+1, r, rc[i]);
  }
};

struct Tree {
  struct TreeNode {
    int l, r, mx, se, cnt, tag;
    ll sum;
  } tr[N<<2];
  void push_up(int i) {
    tr[i].sum = tr[i<<1].sum+tr[i<<1|1].sum;
    if (tr[i<<1].mx > tr[i<<1|1].mx) {
      tr[i].mx = tr[i<<1].mx;
      tr[i].cnt = tr[i<<1].cnt;
      tr[i].se = max(tr[i<<1].se, tr[i<<1|1].mx);
    } else if (tr[i<<1].mx < tr[i<<1|1].mx) {
      tr[i].mx = tr[i<<1|1].mx;
      tr[i].cnt = tr[i<<1|1].cnt;
      tr[i].se = max(tr[i<<1|1].se, tr[i<<1].mx);
    } else {
      tr[i].mx = tr[i<<1].mx;
      tr[i].cnt = tr[i<<1].cnt+tr[i<<1|1].cnt;
      tr[i].se = max(tr[i<<1].se, tr[i<<1|1].se);
    }
  }
  void push_tag(int i, int v) {
    if (v >= tr[i].mx) return;
    tr[i].sum -= 1ll*(tr[i].mx-v)*tr[i].cnt;
    tr[i].mx = tr[i].tag = v;
  }
  void push_down(int i) {
    if (tr[i].tag == -1) return;
    push_tag(i<<1, tr[i].tag);
    push_tag(i<<1|1, tr[i].tag);
    tr[i].tag = -1;
  }
  void build(int l, int r, int i = 1) {
    tr[i].l = l; tr[i].r = r; tr[i].tag = -1;
    if (l == r) {
      tr[i].sum = tr[i].mx = a[l];
      tr[i].cnt = 1;
      tr[i].se = -1;
      return;
    }
    int mid = (l+r)>>1;
    build(l, mid, i<<1);
    build(mid+1, r, i<<1|1);
    push_up(i);
  }
  void update_min(int l, int r, int v, int i = 1) {
    if (v >= tr[i].mx) return;
    if (l <= tr[i].l && r >= tr[i].r && v > tr[i].se) return push_tag(i, v);
    push_down(i);
    int mid = (tr[i].l+tr[i].r)>>1;
    if (l <= mid) update_min(l, r, v, i<<1);
    if (r >  mid) update_min(l, r, v, i<<1|1);
    push_up(i);
  }
  int query_max(int l, int r, int i = 1) {
    if (l <= tr[i].l && r >= tr[i].r) return tr[i].mx;
    push_down(i);
    int mid = (tr[i].l+tr[i].r)>>1;
    if (r <= mid) return query_max(l, r, i<<1);
    if (l >  mid) return query_max(l, r, i<<1|1);
    return max(query_max(l, r, i<<1), query_max(l, r, i<<1|1));
  }
  ll query_sum(int l, int r, int i = 1) {
    if (l <= tr[i].l && r >= tr[i].r) return tr[i].sum;
    push_down(i);
    int mid = (tr[i].l+tr[i].r)>>1;
    if (r <= mid) return query_sum(l, r, i<<1);
    if (l >  mid) return query_sum(l, r, i<<1|1);
    return query_sum(l, r, i<<1)+query_sum(l, r, i<<1|1);
  }
};

struct SegmentTree {
#define rt tr[i]
#define ls tr[i<<1]
#define rs tr[i<<1|1]
  typedef int T;
  struct TreeNode {
    int l, r;
    T mn1, mn2, mx1, mx2, cmn, cmx, tag1, tag2, tag3;
    long long sum;
  };
  vector<T> a;
  vector<TreeNode> tr;
  void push_up(int i) {
    rt.sum = ls.sum+rs.sum;
    if (ls.mn1 == rs.mn1) {
      rt.mn1 = ls.mn1;
      rt.cmn = ls.cmn+rs.cmn;
      rt.mn2 = min(ls.mn2, rs.mn2);
    } else if (ls.mn1 < rs.mn1) {
      rt.mn1 = ls.mn1;
      rt.cmn = ls.cmn;
      rt.mn2 = min(ls.mn2, rs.mn1);
    } else if (ls.mn1 > rs.mn1) {
      rt.mn1 = rs.mn1;
      rt.cmn = rs.cmn;
      rt.mn2 = min(ls.mn1, rs.mn2);
    }
    if (ls.mx1 == rs.mx1) {
      rt.mx1 = ls.mx1;
      rt.cmx = ls.cmx+rs.cmx;
      rt.mx2 = max(ls.mx2, rs.mx2);
    } else if (ls.mx1 > rs.mx1) {
      rt.mx1 = ls.mx1;
      rt.cmx = ls.cmx;
      rt.mx2 = max(ls.mx2, rs.mx1);
    } else if (ls.mx1 < rs.mx1) {
      rt.mx1 = rs.mx1;
      rt.cmx = rs.cmx;
      rt.mx2 = max(ls.mx1, rs.mx2);
    }
  }
  // 1 2 3 -> min, max, other
  void push_tag(int i, T add1, T add2, T add3) {
    if (rt.mn1 == rt.mx1) {
      add1 == add3 ? add1 = add2 : add2 = add1; // 不应被其他值的标记作用
      rt.sum += 1ll*rt.cmn*add1;
    } else {
      rt.sum += 1ll*rt.cmn*add1+1ll*rt.cmx*add2
          +(rt.r-rt.l+1ll-rt.cmn-rt.cmx)*add3;
    }
    if (rt.mn2 == rt.mx1) rt.mn2 += add2;
    else if (rt.mn2 != INF) rt.mn2 += add3;
    if (rt.mx2 == rt.mn1) rt.mx2 += add1;
    else if (rt.mx2 != -INF) rt.mx2 += add3;
    rt.mn1 += add1; rt.mx1 += add2;
    rt.tag1 += add1; rt.tag2 += add2; rt.tag3 += add3;
  }
  void push_down(int i) {
    T mn = min(ls.mn1, rs.mn1);
    T mx = max(ls.mx1, rs.mx1);
    push_tag(i<<1  , ls.mn1 == mn ? rt.tag1 : rt.tag3, ls.mx1 == mx ? rt.tag2 : rt.tag3, rt.tag3);
    push_tag(i<<1|1, rs.mn1 == mn ? rt.tag1 : rt.tag3, rs.mx1 == mx ? rt.tag2 : rt.tag3, rt.tag3);
    rt.tag1 = rt.tag2 = rt.tag3 = 0;
  }
  template <typename TT> void build(int n, TT arr[]) {
    a.resize(1);
    a.insert(a.end(), arr+1, arr+n+1);
    tr.resize(n*4+1);
    build(1, n, 1);
  }
  void build(int n, T val = 0) {
    a.resize(n+1, val);
    tr.resize(n*4+1);
    build(1, n, 1);
  }
  void build(int l, int r, int i) {
    rt.l = l; rt.r = r;
    rt.tag1 = rt.tag2 = rt.tag3 = 0;
    if (l == r) {
      rt.sum = rt.mn1 = rt.mx1 = a[l];
      rt.mn2 = INF; rt.mx2 = -INF;
      rt.cmn = rt.cmx = 1;
      return;
    }
    int mid = (l+r)>>1;
    build(l, mid, i<<1); build(mid+1, r, i<<1|1);
    push_up(i);
  }
  void update_add(int l, int r, T v, int i = 1) {
    if (rt.r < l || rt.l > r) return;
    if (rt.l >= l && rt.r <= r)
      return push_tag(i, v, v, v);
    push_down(i);
    update_add(l, r, v, i<<1); update_add(l, r, v, i<<1|1);
    push_up(i);
  }
  void update_max(int l, int r, T v, int i = 1) {
    if (rt.r < l || rt.l > r || rt.mn1 >= v) return;
    if (rt.l >= l && rt.r <= r && rt.mn2 > v)
      return push_tag(i, v-rt.mn1, 0, 0);
    push_down(i);
    update_max(l, r, v, i<<1); update_max(l, r, v, i<<1|1);
    push_up(i);
  }
  void update_min(int l, int r, T v, int i = 1) {
    if (rt.r < l || rt.l > r || rt.mx1 <= v) return;
    if (rt.l >= l && rt.r <= r && rt.mx2 < v)
      return push_tag(i, 0, v-rt.mx1, 0);
    push_down(i);
    update_min(l, r, v, i<<1); update_min(l, r, v, i<<1|1);
    push_up(i);
  }
  long long query_sum(int l, int r, int i = 1) {
    if (rt.r < l || rt.l > r) return 0;
    if (rt.l >= l && rt.r <= r) return rt.sum;
    push_down(i);
    return query_sum(l, r, i<<1)+query_sum(l, r, i<<1|1);
  }
  T query_max(int l, int r, int i = 1) {
    if (rt.r < l || rt.l > r) return -INF;
    if (rt.l >= l && rt.r <= r) return rt.mx1;
    push_down(i);
    return max(query_max(l, r, i<<1), query_max(l, r, i<<1|1));
  }
  T query_min(int l, int r, int i = 1) {
    if (rt.r < l || rt.l > r) return INF;
    if (rt.l >= l && rt.r <= r) return rt.mn1;
    push_down(i);
    return min(query_min(l, r, i<<1), query_min(l, r, i<<1|1));
  }
#undef rt
#undef ls
#undef rs
};

struct SegmentTree {
#define rt tr[i]
#define ls tr[i<<1]
#define rs tr[i<<1|1]
  typedef int T;
  struct TreeNode {
    int l, r;
    bool tag;
    T add, cov, mx, hadd, hcov, hmx;
  } tr[N<<2];
  void push_up(int i) {
    rt.mx = max(ls.mx, rs.mx);
    rt.hmx = max(ls.hmx, rs.hmx);
  }
  void plus(int i, T k, T hk) {
    rt.hmx = max(rt.hmx, rt.mx+hk);
    rt.mx += k;
    rt.tag ? rt.hcov = max(rt.hcov, rt.cov+hk), rt.cov += k
        : rt.hadd = max(rt.hadd, rt.add+hk), rt.add += k;
  }
  void cover(int i, T k, T hk) {
    rt.hmx = max(rt.hmx, hk);
    rt.mx = k;
    rt.hcov = max(rt.hcov, hk);
    rt.cov = k;
    rt.tag = 1;
  }
  void push_down(int i) {
    if (rt.add) {
      plus(i<<1  , rt.add, rt.hadd);
      plus(i<<1|1, rt.add, rt.hadd);
      rt.add = rt.hadd = 0;
    }
    if (rt.tag) {
      cover(i<<1  , rt.cov, rt.hcov);
      cover(i<<1|1, rt.cov, rt.hcov);
      rt.tag = 0; rt.hcov = -INF;
    }
  }
  void build(int l, int r, int i = 1) {
    rt.l = l; rt.r = r; rt.tag = false;
    rt.add = rt.hadd = 0;
    rt.hcov = -INF;
    if (l == r) return rt.hmx = rt.mx = 0, void();
    int mid = (l+r)>>1;
    build(l, mid, i<<1); build(mid+1, r, i<<1|1);
    push_up(i);
  }
  T query_max(int l, int r, int i = 1) {
    if (rt.r < l || rt.l > r) return -INF;
    if (l <= rt.l && rt.r <= r) return rt.mx;
    push_down(i);
    return max(query_max(l, r, i<<1), query_max(l, r, i<<1|1));
  }
  T query_hmax(int l, int r, int i = 1) {
    if (rt.r < l || rt.l > r) return -INF;
    if (l <= rt.l && rt.r <= r) return rt.hmx;
    push_down(i);
    return max(query_hmax(l, r, i<<1), query_hmax(l, r, i<<1|1));
  }
  void update_add(int l, int r, T v, int i = 1) {
    if (rt.r < l || rt.l > r) return;
    if (l <= rt.l && rt.r <= r) return plus(i, v, v);
    push_down(i);
    update_add(l, r, v, i<<1); update_add(l, r, v, i<<1|1);
    push_up(i);
  }
  void update_cov(int l, int r, T v, int i = 1) {
    if (rt.r < l || rt.l > r) return;
    if (l <= rt.l && rt.r <= r) return cover(i, v, v);
    push_down(i);
    update_cov(l, r, v, i<<1); update_cov(l, r, v, i<<1|1);
    push_up(i);
  }
#undef rt
#undef ls
#undef rs
};

struct SegmentTree {
#define rt tr[i]
#define ls tr[i<<1]
#define rs tr[i<<1|1]
  typedef long long T;
  struct Tag {
    T add, mx;
    Tag(T _add = 0, T _mx = -INF) : add(_add), mx(_mx) {}
    Tag operator +(const Tag &t) const { // 合并tag
      return Tag(max(-INF, add+t.add), max(mx+t.add, t.mx));
    }
    Tag operator *(const Tag &t) const { // 取max
      return Tag(max(add, t.add), max(mx, t.mx));
    }
    Tag& operator +=(const Tag &t) { return *this = *this+t; }
    Tag& operator *=(const Tag &t) { return *this = *this*t; }
  };
  struct TreeNode {
    int l, r;
    Tag his, cur;
  } tr[N<<2];
  void push_tag(int i, Tag hk, Tag k) {
    rt.his *= rt.cur+hk;
    rt.cur += k;
  }
  void push_down(int i) {
    push_tag(i<<1  , rt.his, rt.cur);
    push_tag(i<<1|1, rt.his, rt.cur);
    rt.his = rt.cur = Tag();
  }
  void build(int l, int r, int i = 1) {
    rt.l = l; rt.r = r; rt.his = rt.cur = Tag();
    if (l == r) return rt.his = rt.cur = Tag(a[l]), void();
    int mid = (l+r)>>1;
    build(l, mid, i<<1); build(mid+1, r, i<<1|1);
  }
  // add(val, -INF) cov(-INF, val) max(0, val)
  void update(int l, int r, T a, T x = -INF, int i = 1) {
    if (rt.r < l || rt.l > r) return;
    if (l <= rt.l && rt.r <= r) return push_tag(i, Tag(a, x), Tag(a, x));
    push_down(i);
    update(l, r, a, x, i<<1); update(l, r, a, x, i<<1|1);
  }
  T query_max(int x, int i = 1) {
    if (rt.l == rt.r) return max(rt.cur.add, rt.cur.mx);
    push_down(i);
    int mid = (rt.l+rt.r)>>1;
    if (x <= mid) return query_max(x, i<<1);
    else return query_max(x, i<<1|1);
  }
  T query_hmax(int x, int i = 1) {
    if (rt.l == rt.r) return max(rt.his.add, rt.his.mx);
    push_down(i);
    int mid = (rt.l+rt.r)>>1;
    if (x <= mid) return query_hmax(x, i<<1);
    else return query_hmax(x, i<<1|1);
  }
#undef rt
#undef ls
#undef rs
};

struct SegmentTree {
#define rt tr[i]
#define ls tr[i<<1]
#define rs tr[i<<1|1]
  typedef int T;
  struct TreeNode {
    int l, r;
    T mn, hmn, se, tag1, htag1, tag2, htag2;
  } tr[N<<2];
  void push_up(int i) {
    rt.hmn = min(ls.hmn, rs.hmn);
    if (ls.mn == rs.mn) {
      rt.mn = ls.mn;
      rt.se = min(ls.se, rs.se);
    } else if (ls.mn < rs.mn) {
      rt.mn = ls.mn;
      rt.se = min(ls.se, rs.mn);
    } else if (ls.mn > rs.mn) {
      rt.mn = rs.mn;
      rt.se = min(ls.mn, rs.se);
    }
  }
  void push_tag(int i, T add1, T hadd1, T add2, T hadd2) {
    rt.hmn = min(rt.hmn, rt.mn+hadd1);
    rt.htag1 = min(rt.htag1, rt.tag1+hadd1);
    rt.mn += add1; rt.tag1 += add1;
    rt.htag2 = min(rt.htag2, rt.tag2+hadd2);
    if (rt.se != INF) rt.se += add2;
    rt.tag2 += add2;
  }
  void push_down(int i) {
    T mn = min(ls.mn, rs.mn);
    push_tag(i<<1  , ls.mn == mn ? rt.tag1 : rt.tag2,
        ls.mn == mn ? rt.htag1 : rt.htag2, rt.tag2, rt.htag2);
    push_tag(i<<1|1, rs.mn == mn ? rt.tag1 : rt.tag2,
        rs.mn == mn ? rt.htag1 : rt.htag2, rt.tag2, rt.htag2);
    rt.tag1 = rt.htag1 = rt.tag2 = rt.htag2 = 0;
  }
  void build(int l, int r, int i = 1) {
    rt.l = l; rt.r = r;
    rt.tag1 = rt.htag1 = rt.tag2 = rt.htag2 = 0;
    if (l == r) {
      rt.hmn = rt.mn = a[l];
      rt.se = INF;
      return;
    }
    int mid = (l+r)>>1;
    build(l, mid, i<<1); build(mid+1, r, i<<1|1);
    push_up(i);
  }
  void update_add(int l, int r, T v, int i = 1) {
    if (rt.r < l || rt.l > r) return;
    if (l <= rt.l && rt.r <= r) return push_tag(i, v, v, v, v);
    push_down(i);
    update_add(l, r, v, i<<1); update_add(l, r, v, i<<1|1);
    push_up(i);
  }
  void update_max(int l, int r, T v, int i = 1) {
    if (rt.r < l || rt.l > r || v <= rt.mn) return;
    if (l <= rt.l && rt.r <= r && v < rt.se)
      return push_tag(i, v-rt.mn, v-rt.mn, 0, 0);
    push_down(i);
    update_max(l, r, v, i<<1); update_max(l, r, v, i<<1|1);
    push_up(i);
  }
  T query_min(int l, int r, int i = 1) {
    if (rt.r < l || rt.l > r) return INF;
    if (l <= rt.l && rt.r <= r) return rt.mn;
    push_down(i);
    return min(query_min(l, r, i<<1), query_min(l, r, i<<1|1));
  }
  T query_hmin(int l, int r, int i = 1) {
    if (rt.r < l || rt.l > r) return INF;
    if (l <= rt.l && rt.r <= r) return rt.hmn;
    push_down(i);
    return min(query_hmin(l, r, i<<1), query_hmin(l, r, i<<1|1));
  }
#undef rt
#undef ls
#undef rs
};

struct Node {
  int x, y, v;
} s[N];
bool cmpx(int a, int b) { return s[a].x < s[b].x; }
bool cmpy(int a, int b) { return s[a].y < s[b].y; }
struct KDTree {
  double alpha = 0.725;
  int rt, cur, xl, yl, xr, yr; //rt根结点
  int d[N], siz[N], lc[N], rc[N]; //d=1竖着砍，sz子树大小
  int L[N], R[N], D[N], U[N]; //该子树的界线
  int sum[N]; //维护的二维区间信息（二维区间和）
  int g[N], gt;
  void pia(int x) { //将树还原成序列g
    if (!x) return;
    pia(lc[x]);
    g[++gt] = x;
    pia(rc[x]);
  }
  void push_up(int x) { //更新信息
    siz[x] = siz[lc[x]] + siz[rc[x]] + 1;
    sum[x] = sum[lc[x]] + sum[rc[x]] + s[x].v;
    L[x] = R[x] = s[x].x;
    D[x] = U[x] = s[x].y;
    if (lc[x]) {
      L[x] = min(L[x], L[lc[x]]);
      R[x] = max(R[x], R[lc[x]]);
      D[x] = min(D[x], D[lc[x]]);
      U[x] = max(U[x], U[lc[x]]);
    }
    if (rc[x]) {
      L[x] = min(L[x], L[rc[x]]);
      R[x] = max(R[x], R[rc[x]]);
      D[x] = min(D[x], D[rc[x]]);
      U[x] = max(U[x], U[rc[x]]);
    }
  }
  int build(int l, int r) { //以序列g[l..r]为模板重建树，返回根结点
    if (l > r) return 0;
    int mid = (l + r) >> 1;
    double ax = 0, ay = 0, sx = 0, sy = 0;
    for (int i = l; i <= r; i++) ax += s[g[i]].x, ay += s[g[i]].y;
    ax /= (r - l + 1);
    ay /= (r - l + 1);
    for (int i = l; i <= r; i++) {
      sx += (ax - s[g[i]].x) * (ax - s[g[i]].x);
      sy += (ay - s[g[i]].y) * (ay - s[g[i]].y);
    }
    if (sx > sy)
      nth_element(g + l, g + mid, g + r + 1, cmpx), d[g[mid]] = 1;
    else
      nth_element(g + l, g + mid, g + r + 1, cmpy), d[g[mid]] = 2;
    lc[g[mid]] = build(l, mid - 1);
    rc[g[mid]] = build(mid + 1, r);
    push_up(g[mid]);
    return g[mid];
  }
  void rebuild(int &x) {
    gt = 0;
    pia(x);
    x = build(1, gt);
  }
  bool bad(int x) {
    return alpha * siz[x] <= max(siz[lc[x]], siz[rc[x]]);
  }
  void insert(int x, int y, int v) { //在(x,y)处插入元素
    s[++cur] = {x, y, v};
    insert(rt, cur);
  }
  void insert(int &x, int v) {
    if (!x) return push_up(x = v);
    if (d[x]) insert(s[v].x <= s[x].x ? lc[x] : rc[x], v);
    else insert(s[v].y <= s[x].y ? lc[x] : rc[x], v);
    push_up(x);
    if (bad(x)) rebuild(x);
  }
  int query(int xl, int yl, int xr, int yr) { //查询[x1,x2]×[y1,y2]的区间和
    if (xl > xr) swap(xl, xr);
    if (yl > yr) swap(yl, yr);
    this->xl = xl; this->yl = yl; this->xr = xr; this->yr = yr;
    return query(rt);
  }
  int query(int x) {
    if (!x || xr < L[x] || xl > R[x] || yr < D[x] || yl > U[x]) return 0;
    if (xl <= L[x] && R[x] <= xr && yl <= D[x] && U[x] <= yr) return sum[x];
    int res = 0;
    if (xl <= s[x].x && s[x].x <= xr && yl <= s[x].y && s[x].y <= yr)
      res += s[x].v;
    return query(lc[x]) + query(rc[x]) + res;
  }
};

template <typename T>
struct BinaryIndexedTree {
  int n;
  vector<T> tr;
  void init(const int &n) { this->n = n; tr = vector<T>(n+1, 0); }
  void add(const int &x, const T &v) { for (int i = x; i <= n; i += i&-i) tr[i] += v; }
  void add(const int &x, const int &y, const T &v) { add(x, v); add(y+1, -v); }
  T query(const int &x) { T res = 0; for (int i = x ; i; i -= i&-i) res += tr[i]; return res; }
  T query(const int &x, const int &y) { return query(y)-query(x-1); }
};

template <typename TT>
void init(const int &_n, const TT a[]) {
  n = _n; clear();
  for (int i = 1; i <= n; ++i) {
    tr[i] += a[i];
    if (i+(i&-i) <= n) tr[i+(i&-i)] += tr[i];
  }
}

struct BIT{
    static const int SIZE=1e6+5;
    ll bit1[SIZE],bit2[SIZE];
    int limit;
    void init(int n=SIZE-1){
        limit=n;
        for(int i=1;i<=n;i++)bit1[i]=bit2[i]=0;
    }
    BIT(){init();}
    void add(ll *bit,int x,ll v){
        while(x<=limit)bit[x]+=v,x+=x&-x;
    }
    ll query(ll *bit,int x){
        ll res=0;
        while(x)res+=bit[x],x-=x&-x;
        return res;
    }
    void add(int l,int r,ll v){
        add(bit1,l,v);
        add(bit2,l,v*l);
        add(bit1,r+1,-v);
        add(bit2,r+1,-v*(r+1));
    }
    ll query(int l,int r){
        return (r+1)*query(bit1,r)-query(bit2,r)-l*query(bit1,l-1)+query(bit2,l-1);
    }
}bit;

template <typename T>
struct BIT_2D {
  int n, m;
  T a[N][N], tr[N][N];
  BIT_2D() { memset(tr, 0, sizeof tr); }
  void init(const int &_n, const int &_m) {
    n = _n; m = _m;
    memset(a, 0, sizeof a);
    memset(tr, 0, sizeof tr);
  }
  void add(const int &x, const int &y, const T &k) {
    a[x][y] += k;
    for (int i = x; i <= n; i += i&-i)
      for (int j = y; j <= m; j += j&-j)
        tr[i][j] += k;
  }
  T query(const int &x, const int &y) {
    return a[x][y];
    // return query(x, y, x, y);
  }
  T query(int r1, int c1, int r2, int c2) {
    if (r1 > r2) swap(r1, r2);
    if (c1 > c2) swap(c1, c2);
    return _query(r2, c2)-_query(r1-1, c2)-_query(r2, c1-1)+_query(r1-1, c1-1);
  }
  T _query(const int &x, const int &y) {
    T res = 0;
    for (int i = x; i; i -= i&-i)
      for (int j = y; j; j -= j&-j)
        res += tr[i][j];
    return res;
  }
};

template <typename T>
struct PersistantArray {
  static const int NN = N*(log2(N)+3);
  int rt[N], ls[NN], rs[NN], val[NN], tot, n;
  void build(const int &n) {
    this->n = n;
    tot = 0;
    rt[0] = build(1, n);
  }
  int build(const int &l, const int &r) {
    int cur = ++tot; assert(tot < NN);
    if (l == r) return val[cur] = a[l], cur;
    int mid = (l+r)>>1;
    ls[cur] = build(l, mid);
    rs[cur] = build(mid+1, r);
    return cur;
  }
  void update(const int &cur, const int &pre, const int &x, const T &k) {
    rt[cur] = update(rt[pre], x, k, 1, n);
  }
  int update(const int &pre, const int &x, const T &k, const int &l, const int &r) {
    int cur = ++tot; assert(tot < NN);
    if (l == x && r == x) return val[cur] = k, cur;
    ls[cur] = ls[pre]; rs[cur] = rs[pre];
    int mid = (l+r)>>1;
    if (x <= mid) ls[cur] = update(ls[pre], x, k, l, mid);
    else rs[cur] = update(rs[pre], x, k, mid+1, r);
    return cur;
  }
  T query(const int &cur, const int &x) {
    return query(rt[cur], x, 1, n);
  }
  T query(const int &cur, const int &x, const int &l, const int &r) {
    if (l == x && r == x) return val[cur];
    int mid = (l+r)>>1;
    if (x <= mid) return query(ls[cur], x, l, mid);
    return query(rs[cur], x, mid+1, r);
  }
};

template <typename T>
struct PersistantSegmentTree {
  static const int NN = N*(log2(N)+5);
  int rt[N], sum[NN], ls[NN], rs[NN], tot, sz;
  vector<T> des;
  void build(const T a[], const int &n) {
    vector<T>(a+1, a+n+1).swap(des);
    sort(des.begin(), des.end());
    des.erase(unique(des.begin(), des.end()), des.end());
    sz = des.size();
    tot = 0;
    rt[0] = _build(1, sz);
    for (int i = 1; i <= n; ++i) {
      int t = lower_bound(des.begin(), des.end(), a[i])-des.begin()+1;
      rt[i] = _update(rt[i-1], 1, sz, t);
    }
  }
  void update(const int &id, const T &k) {
    int t = lower_bound(des.begin(), des.end(), k)-des.begin()+1;
    rt[id] = _update(rt[id-1], 1, sz, t);
  }
  T query(const int &l, const int &r, const int &k) {
    return des[_query(rt[l-1], rt[r], 1, sz, k)-1];
  }
private:
  int _build(const int &l, const int &r) {
    int cur = ++tot;
    sum[cur] = 0;
    if (l >= r) return cur;
    int mid = (l+r)>>1;
    ls[cur] = _build(l, mid);
    rs[cur] = _build(mid+1, r);
    return cur;
  }
  int _update(const int &pre, const int &l, const int &r, const int &k) {
    int cur = ++tot;
    ls[cur] = ls[pre]; rs[cur] = rs[pre]; sum[cur] = sum[pre]+1;
    if (l >= r) return cur;
    int mid = (l+r)>>1;
    if (k <= mid) ls[cur] = _update(ls[pre], l, mid, k);
    else rs[cur] = _update(rs[pre], mid+1, r, k);
    return cur;
  }
  int _query(const int &u, const int &v, const int &l, const int &r, const int &k) {
    if (l >= r) return l;
    int num = sum[ls[v]]-sum[ls[u]], mid = (l+r)>>1;
    if (num >= k) return _query(ls[u], ls[v], l, mid, k);
    else return _query(rs[u], rs[v], mid+1, r, k-num);
  }
};

template <typename T>
struct PersistantSegmentTree {
  static const int NN = N*(log2(N)+5);
  int rt[N], sum[NN], ls[NN], rs[NN], tot, n;
  void build(const int &n) {
    this->n = n;
    tot = 0;
    rt[0] = _build(1, n);
  }
  void update(const int &cur, const int &pre, const T &k) {
    rt[cur] = _update(rt[pre], 1, n, k);
  }
  T query(const int &l, const int &r, const int &k) {
    return _query(rt[l-1], rt[r], 1, n, k);
  }
private:
  int _build(const int &l, const int &r) {
    int cur = ++tot;
    sum[cur] = 0;
    if (l >= r) return cur;
    int mid = (l+r)>>1;
    ls[cur] = _build(l, mid);
    rs[cur] = _build(mid+1, r);
    return cur;
  }
  int _update(const int &pre, const int &l, const int &r, const int &k) {
    int cur = ++tot;
    ls[cur] = ls[pre]; rs[cur] = rs[pre]; sum[cur] = sum[pre]+1;
    if (l >= r) return cur;
    int mid = (l+r)>>1;
    if (k <= mid) ls[cur] = _update(ls[pre], l, mid, k);
    else rs[cur] = _update(rs[pre], mid+1, r, k);
    return cur;
  }
  int _query(const int &u, const int &v, const int &l, const int &r, const int &k) {
    if (l >= r) return l;
    int num = sum[ls[v]]-sum[ls[u]], mid = (l+r)>>1;
    if (num >= k) return _query(ls[u], ls[v], l, mid, k);
    else return _query(rs[u], rs[v], mid+1, r, k-num);
  }
};

template <class T>
class PersistantSegmentTree {
 public:
  void init(int n) {
    tot = 0;
    this->n = n;
    rt = vector<int>(1, 0);
    tr = vector<TreeNode>(1, TreeNode{0, 0, 0});
  }
  void update(int cur, int pre, int k, T v = 1) {
    rt.resize(cur+1); // assert rt.size()+1 <= cur
    rt[cur] = update(rt[pre], 1, n, k, v);
  }
  int update(int pre, int l, int r, int k, T v) {
    int cur = ++tot; // assert tot == tr.size()
    tr.emplace_back(tr[pre]);
    tr[cur].sum += v;
    if (l == r) return cur;
    int mid = (l+r)>>1;
    if (k <= mid) tr[cur].lc = update(tr[pre].lc, l, mid, k, v);
    else tr[cur].rc = update(tr[pre].rc, mid+1, r, k, v);
    return cur;
  }
  T query(int l, int r, int ql, int qr) {
    return query(rt[l-1], rt[r], 1, n, ql, qr);
  }
  // [u, v] 段 [ql, qr] 区间和
  T query(int u, int v, int l, int r, int ql, int qr) {
    if (!u && !v) return 0;
    if (l >= ql && r <= qr) return tr[v].sum-tr[u].sum;
    int mid = (l+r)>>1;
    if (qr <= mid) return query(tr[u].lc, tr[v].lc, l, mid, ql, qr);
    if (ql >  mid) return query(tr[u].rc, tr[v].rc, mid+1, r, ql, qr);
    return query(tr[u].lc, tr[v].lc, l, mid, ql, qr)+query(tr[u].rc, tr[v].rc, mid+1, r, ql, qr);
  }
 private:
  struct TreeNode {
    int lc, rc;
    T sum;
  };
  int tot, n;
  vector<int> rt;
  vector<TreeNode> tr;
};

template <typename T>
struct PersistantSegmentTree {
  static const int NN = N*(log2(N)+5);
  int rt[N], ls[NN], rs[NN], tot, n;
  T sum[NN];
  void build(const int &n) {
    this->n = n;
    tot = 0;
    rt[0] = _build(1, n);
  }
  void update(const int &cur, const int &pre, const int &k, const T &v) {
    rt[cur] = _update(rt[pre], 1, n, k, v);
  }
  T query(const int &l, const int &r, const int &ql, const int &qr) {
    return _query(rt[l-1], rt[r], 1, n, ql, qr);
  }
private:
  int _build(const int &l, const int &r) {
    int cur = ++tot;
    sum[cur] = 0;
    if (l >= r) return cur;
    int mid = (l+r)>>1;
    ls[cur] = _build(l, mid);
    rs[cur] = _build(mid+1, r);
    return cur;
  }
  int _update(const int &pre, const int &l, const int &r, const int &k, const T &v) {
    int cur = ++tot;
    ls[cur] = ls[pre]; rs[cur] = rs[pre]; sum[cur] = sum[pre]+v;
    if (l >= r) return cur;
    int mid = (l+r)>>1;
    if (k <= mid) ls[cur] = _update(ls[pre], l, mid, k, v);
    else rs[cur] = _update(rs[pre], mid+1, r, k, v);
    return cur;
  }
  // [u, v] 段 [ql, qr] 区间和
  T _query(const int &u, const int &v, const int &l, const int &r, const int &ql, const int &qr) {
    if (l >= ql && r <= qr) return sum[v]-sum[u];
    int mid = (l+r)>>1;
    if (qr <= mid) return _query(ls[u], ls[v], l, mid, ql, qr);
    if (ql >  mid) return _query(rs[u], rs[v], mid+1, r, ql, qr);
    return _query(ls[u], ls[v], l, mid, ql, qr)+_query(rs[u], rs[v], mid+1, r, ql, qr);
  }
};

struct FenKuai {
  typedef long long T;
  int t; // 每组大小
  static const int NN = static_cast<int>(sqrt(N))+7;
  T a[N], sum[NN], add[NN];
  FenKuai() {
    memset(a, 0, sizeof a);
    memset(sum, 0, sizeof sum);
    memset(add, 0, sizeof add);
  }
  void init() {
    t = static_cast<int>(sqrt(n)+0.5);
    for (int i = 0; i < n; ++i) sum[i/t] += a[i];
  }
  void update(int x, T k) { a[x] += k; sum[x/t] += k; }
  void update(int x, int y, T k) {
    for ( ; x <= y && x%t; ++x) a[x] += k, sum[x/t] += k;
    for ( ; x+t-1 <= y; x += t) sum[x/t] += k*t, add[x/t] += k;
    for ( ; x <= y; ++x) a[x] += k, sum[x/t] += k;
  }
  T query(int x) { return a[x]+add[x/t]; }
  T query(int x, int y) {
    T res = 0;
    for ( ; x <= y && x%t; ++x) res += a[x]+add[x/t];
    for ( ; x+t-1 <= y; x += t) res += sum[x/t];
    for ( ; x <= y; ++x) res += a[x]+add[x/t];
    return res;
  }
} B;

struct FenKuai {
  typedef int T;
  int t; // 每组大小
  T a[N], b[N], add[N];
  FenKuai() {
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    memset(add, 0, sizeof add);
  }
  void build(int x) {
    for (int i = x*t; i < min(x*t+t, n); ++i) b[i] = a[i];
    sort(b+x*t, b+min(x*t+t, n));
  }
  void init() {
    t = static_cast<int>(sqrt(n)+0.5);
    for (int i = 0; i*t < n; ++i) build(i);
  }
  void update(int x, int y, T c) {
    int i = x;
    for ( ; i <= y && i%t; ++i) a[i] += c;
    build(x/t);
    for ( ; i+t-1 <= y; i += t) add[i/t] += c;
    for ( ; i <= y; ++i) a[i] += c;
    build(y/t);
  }
  T query(int x, int y, long long c) {
    T res = 0; int i = x;
    for ( ; i <= y && i%t; ++i) res += (a[i]+add[i/t] < c*c);
    for ( ; i+t-1 <= y; i += t) res += lower_bound(b+i, b+i+t, c*c-add[i/t])-(b+i);
    for ( ; i <= y; ++i) res += (a[i]+add[i/t] < c*c);
    return res;
  }
} B;

struct FenKuai {
  typedef int T;
  int t, sz;
  static const int NN = static_cast<int>(sqrt(N))+7;
  T a[N];
  deque<int> q[NN];
  void init(int _n) {
    sz = _n;
    t = static_cast<int>(sqrt(sz*1.5)+0.5);
    for (int i = 0; i < sz; ++i) q[i/t].push_back(a[i]);
  }
  void update(int x, int k) {
    stack<int> tmp;
    for (int i = 0; i != x%t; ++i) {
      tmp.push(q[x/t].front());
      q[x/t].pop_front();
    }
    q[x/t].push_front(k);
    while (tmp.size()) {
      q[x/t].push_front(tmp.top());
      tmp.pop();
    }
    ++sz;
    if (sz/t == x/t) return;
    for (int i = x/t, val; i < sz/t; ++i) {
      val = q[i].back();
      q[i].pop_back();
      q[i+1].push_front(val);
    }
  }
  T query(int x) {
    stack<int> tmp;
    for (int i = 0; i != x%t; ++i) {
      tmp.push(q[x/t].front());
      q[x/t].pop_front();
    }
    int res = q[x/t].front();
    while (tmp.size()) {
      q[x/t].push_front(tmp.top());
      tmp.pop();
    }
    return res;
  }
} B;

template <typename T> bool cmp(const T &q1, const T &q2) {
  return q1.l/block != q2.l/block ? q1.l < q2.l :
      (q1.l/block)&1 ? q1.r < q2.r : q1.r > q2.r;
}

template <typename T> bool cmp(const T &q1, const T &q2) {
  return q1.l/block != q2.l/block ? q1.l < q2.l :
      q1.r/block != q2.r/block ? q1.r < q2.r : q1.t < q2.t;
}

template <typename T>
struct PreSum {
  int n, block;
  T s[N], t[(int)sqrt(N)+3];
  void init(int n) {
    this->n = n;
    block = sqrt(n);
  }
  void add(int x, T k) {
    for (int i = x; i/block == x/block && i <= n; ++i) s[i] += k;
    for (int i = x/block+1; i <= n/block; ++i) t[i] += k;
  }
  T query(int x) {
    return t[x/block]+s[x];
  }
};

template <typename T>
struct SufSum {
  int n, block;
  T s[N], t[(int)sqrt(N)+3];
  void init(int n) {
    this->n = n;
    block = sqrt(n);
  }
  void add(int x, T k) {
    for (int i = x; i/block == x/block && i >= 1; --i) s[i] += k;
    for (int i = x/block-1; i >= 0; --i) t[i] += k;
  }
  T query(int x) {
    return t[x/block]+s[x];
  }
};

struct Query {
  int id, l, r;
  Query() {}
  Query(int i, int _l, int _r) : id(i), l(_l), r(_r) {}
};

int n, m, block;
int a[N];
long long res[N], sumil[N], sumir[N], ans[N];
Query q[N];
SufSum<int> suml;
PreSum<int> sumr;
vector<Query> ql[N], qr[N];

inline void calc_sumi() {
  static BinaryIndexedTree<int> tree;
  tree.init(n);
  for (int i = 1; i <= n; ++i) {
    sumil[i] = sumil[i-1]+i-1-tree.query(a[i]);
    tree.add(a[i], 1);
  }
  tree.clear();
  for (int i = n; i; --i) {
    sumir[i] = sumir[i+1]+tree.query(a[i]-1);
    tree.add(a[i], 1);
  }
}

signed main() {
  read(n); read(m);
  for (int i = 1; i <= n; ++i) read(a[i]);
  discrete();
  block = n/sqrt(m);
  for (int i = 1; i <= m; ++i) {
    q[i].id = i;
    read(q[i].l);
    read(q[i].r);
  }
  sort(q+1, q+m+1, cmp);
  calc_sumi();
  q[0] = Query(0, 1, 0);
  for (int i = 1, ul, vl, ur, vr; i <= m; ++i) {
    ul = q[i-1].l; ur = q[i-1].r;
    vl = q[i].l; vr = q[i].r;
    res[i] = sumil[vr]-sumil[ur]+sumir[vl]-sumir[ul];
    if (vl < ul) qr[vr+1].emplace_back(-i, vl, ul-1);
    if (vl > ul) qr[vr+1].emplace_back(+i, ul, vl-1);
    if (vr < ur) ql[ul-1].emplace_back(+i, vr+1, ur);
    if (vr > ur) ql[ul-1].emplace_back(-i, ur+1, vr);
  }
  suml.init(n+1);
  for (int i = 1; i <= n; ++i) {
    suml.add(a[i], 1);
    for (auto &qq : ql[i]) {
      for (int j = qq.l; j <= qq.r; ++j) {
        if (qq.id > 0) res[qq.id] += suml.query(a[j]+1);
        else res[-qq.id] -= suml.query(a[j]+1);
      }
    }
  }
  sumr.init(n);
  for (int i = n; i; --i) {
    sumr.add(a[i], 1);
    for (auto &qq : qr[i]) {
      for (int j = qq.l; j <= qq.r; ++j) {
        if (qq.id > 0) res[qq.id] += sumr.query(a[j]-1);
        else res[-qq.id] -= sumr.query(a[j]-1);
      }
    }
  }
  for (int i = 1; i <= m; ++i) {
    res[i] += res[i-1];
    ans[q[i].id] = res[i];
  }
  for (int i = 1; i <= m; ++i) write(ans[i]), putchar('\n');
  return 0;
}

template <typename T, typename U = std::greater<T>>
struct ST {
  static const int NN = 31-__builtin_clz(N)+3;
  static const T INF = 1e9;
  int lg2[N];
  U cmp = U();
  T rmq[N][NN];
  ST() {
    fill(rmq[0], rmq[0]+N*NN, cmp(-INF, +INF) ? INF : -INF);
    for (int i = 2; i < N; ++i) lg2[i] = lg2[i>>1]+1;
  }
  T& operator [] (const int &i) { return rmq[i][0]; }
  void init(const T &val = 0) { fill(rmq[0], rmq[0]+N*NN, val); }
  T mv(const T &x, const T &y) { return cmp(x, y) ? x : y; }
  // rmq[i][j] ==> [i, i+2^j-1]
  void build(T a[], const int &n) {
    for (int i = n; i; --i) {
      rmq[i][0] = a[i];
      for (int j = 1; j <= lg2[n-i+1]; ++j)
        rmq[i][j] =  mv(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
    }
  }
  T query(const int &l, const int &r) {
    if (l > r) return query(r, l);
    int k = lg2[r-l+1];
    return mv(rmq[l][k], rmq[r-(1<<k)+1][k]);
  }
};
  /* rmq[i][j] ==> [i-2^j+1, i]
  void build(T a[], const int &n) {
    for (int i = 1; i <= n; ++i) {
      rmq[i][0] = a[i];
      for (int j = 1; j <= lg2[i]; ++j)
        rmq[i][j] =  mv(rmq[i][j-1], rmq[i-(1<<(j-1))][j-1]);
    }
  }
  T query(const int &l, const int &r) {
    if (l > r) return query(r, l);
    int k = lg2[r-l+1];
    return mv(rmq[r][k], rmq[l+(1<<k)-1][k]);
  }
  */

template <typename T, typename U = std::greater<T>>
struct ST {
  static const int NN = (int)log2(N)+3;
  static const T INF = 1e9;
  U cmp = U();
  T rmq[N][N][NN][NN]; // rmq[i][j][k][l] [i, j] [i+2^k-1, j+2^l-1]
  ST() { init(); }
  ST(const T &val) { init(val); }
  T& operator [] (const int &i) { return rmq[i][0]; }
  void init(){ fill(rmq[0][0][0], rmq[0][0][0]+N*N*NN*NN, cmp(-INF, +INF) ? INF : -INF); }
  void init(const T &val) { fill(rmq[0][0][0], rmq[0][0][0]+N*N*NN*NN, val); }
  T mv(const T &x, const T &y) { return cmp(x, y) ? x : y; }
  void build(T a[N][N], const int &n, const int &m) {
    for (int k = 0; k <= log_2[n]; ++k)
    for (int l = 0; l <= log_2[m]; ++l)
    for (int i = 1; i+(1<<k)-1 <= n; ++i)
    for (int j = 1; j+(1<<l)-1 <= m; ++j) {
      T &cur = rmq[i][j][k][l];
      if (!k && !l) cur = a[i][j];
      else if (!l) cur = mv(rmq[i][j][k-1][l], rmq[i+(1<<(k-1))][j][k-1][l]);
      else cur = mv(rmq[i][j][k][l-1], rmq[i][j+(1<<(l-1))][k][l-1]);
    }
  }
  T query(const int &r1, const int &c1, const int &r2, const int &c2) {
    int k = log_2[r2-r1+1], l = log_2[c2-c1+1];
    return mv(mv(rmq[r1][c1][k][l], rmq[r2-(1<<k)+1][c2-(1<<l)+1][k][l]),
          mv(rmq[r2-(1<<k)+1][c1][k][l], rmq[r1][c2-(1<<l)+1][k][l]));
  }
};

template <typename T, typename U = std::greater<T>>
struct rST {
  static const int NN = (int)log2(N)+3;
  static const T INF = 1e9;
  int n;
  int lg2[N];
  U cmp = U();
  T rmq[N][NN]; // rmq[i][j] ==> [i, i+2^j-1]
  rST() { for (int i = 2; i < N; ++i) lg2[i] = lg2[i>>1]+1; }
  T& operator [] (const int &i) { return rmq[i][0]; }
  T mv(const T &x, const T &y) { return cmp(x, y) ? x : y; }
  void init(const int &_n, const T &val = 0) { 
    n = _n;
    for (int i = 1; i <= n; ++i) fill(rmq[i], rmq[i]+NN, val);
  }
  void update(const int &l, const int &r, const T &k) {
    if (l > r) return void(update(r, l, k));
    int b = lg2[r-l+1];
    rmq[l][b] = mv(rmq[l][b], k);
    rmq[r-(1<<b)+1][b] = mv(rmq[r-(1<<b)+1][b], k);
  }
  void build() {
    for (int i = lg2[n]; i >= 0; --i) {
      for (int l = 1, r; l <= n; ++l) {
        r = l+(1<<i);
        if (r <= n) rmq[r][i] = mv(rmq[r][i], rmq[l][i+1]);
        rmq[l][i] = mv(rmq[l][i], rmq[l][i+1]);
      }
    }
  }
  T query(const int &l, const int &r) {
    if (l > r) return query(r, l);
    int b = lg2[r-l+1];
    return mv(rmq[l][b], rmq[r-(1<<b)+1][b]);
  }
};

struct DSU {
  vector<int> fa;
  void init(int n) { fa = vector<int>(n+1); iota(fa.begin(), fa.end(), 0); }
  int get(int s) { return s == fa[s] ? s : fa[s] = get(fa[s]); }
  int& operator [] (int i) { return fa[get(i)]; }
  bool merge(int x, int y) { // merge x to y
    x = get(x); y = get(y);
    return x == y ? false : (fa[x] = y, true);
  }
};

struct DSU {
  vector<int> fa, rk;
  void init(int n) { fa = rk = vector<int>(n+1, 0); iota(fa.begin(), fa.end(), 0); }
  int get(int s) { return s == fa[s] ? s : get(fa[s]); }
  int operator [](int i) { return get(i); }
  bool merge(int x, int y) {
    x = get(x); y = get(y);
    if (x == y) return false;
    if (rk[x] < rk[y]) fa[x] = y;
    else fa[y] = x, rk[x] += rk[x] == rk[y];
    return true;
  }
};

template <typename T = int> struct DSU {
  vector<int> fa;
  vector<T> w;
  void init(int n, T v = 1) {
    fa = vector<int>(n+1);
    iota(fa.begin(), fa.end(), 0);
    w = vector<T>(n+1, v);
  }
  void init(int n, T a[]) {
    fa = vector<int>(n+1);
    iota(fa.begin(), fa.end(), 0);
    w = vector<T>(a, a+n+1);
  }
  int get(int s) { return s == fa[s] ? s : fa[s] = get(fa[s]); }
  int& operator [] (int i) { return fa[get(i)]; }
  bool merge(int x, int y) { // merge x to y
    x = get(x); y = get(y);
    return x == y ? false : (w[y] += w[x], fa[x] = y, true);
  }
};

struct DSU {
  int n;
  vector<int> fa; // [1, n] partner, [n+1, 2n] enemy
  void init(int n) {
    this->n = n;
    fa = vector<int>(2*n+1, 0);
    iota(fa.begin(), fa.end(), 0);
  }
  int get(int s) { return s == fa[s] ? s : fa[s] = get(fa[s]); }
  int& operator [] (int i) { return fa[get(i)]; }
  void merge(int x, int y) { fa[get(x)] = get(y); }
  bool update(int x, int y) {
    if (get(x) == get(y)) return false;
    merge(x+n, y);
    merge(x, y+n);
    return true;
  }
};

struct DSU {
  vector<int> fa, rk;
  stack<pair<int&, int>> stk;
  void init(int n) {
    stk = stack<pair<int&, int>>();
    fa = rk = vector<int>(n+1, 0);
    iota(fa.begin(), fa.end(), 0);
  }
  int get(int s) { while (s != fa[s]) s = fa[s]; return s; }
  int& operator [](int i) { return fa[get(i)]; }
  int merge(int x, int y) { // return the number push in stack
    x = get(x); y = get(y);
    if (x == y) return 0;
    if (rk[x] > rk[y]) swap(x, y);
    stk.push({fa[x], fa[x]});
    fa[x] = y;
    return rk[x] == rk[y] ? stk.push({rk[y], rk[y]++}), 2 : 1;
  }
  bool undo() {
    if (stk.empty()) return false;
    stk.top().first = stk.top().second;
    stk.pop();
    return true;
  }
};

struct DSU {
  vector<int> fa, sz;
  stack<pair<int, int>> stk;
  void init(int n) {
    stk = stack<pair<int, int>>();
    fa = sz = vector<int>(n+1, 1);
    iota(fa.begin(), fa.end(), 0);
  }
  int get(int s) { while (s != fa[s]) s = fa[s]; return s; }
  int& operator [](int i) { return fa[get(i)]; }
  int merge(int x, int y) {
    x = get(x); y = get(y);
    if (x == y) return 0;
    if (sz[x] > sz[y]) swap(x, y);
    stk.push({x, y});
    fa[x] = y;
    sz[y] += sz[x];
    return 1;
  }
  bool undo() {
    if (stk.empty()) return false;
    int x = stk.top().first, y = stk.top().y;
    stk.pop();
    fa[x] = x;
    sz[y] -= sz[x];
    return true;
  }
}

struct DSU {
  int n;
  vector<int> fa, rk; // [1, n] partner, [n+1, 2n] enemy
  stack<pair<int&, int>> stk;
  void init(int n) {
    this->n = n;
    stk = stack<pair<int&, int>>();
    fa = rk = vector<int>(2*n+1, 0);
    iota(fa.begin(), fa.end(), 0);
  }
  int& operator [] (int i) { return fa[get(i)]; }
  int get(int s) { while (s != fa[s]) s = fa[s]; return s; }
  void undo() { stk.top().first = stk.top().second; stk.pop(); }
  void merge(int x, int y) {
    x = get(x); y = get(y);
    if (x == y) return;
    if (rk[x] > rk[y]) swap(x, y);
    stk.push({fa[x], fa[x]});
    stk.push({rk[y], rk[y]});
    fa[x] = y;
    rk[y] += rk[x] == rk[y];
  }
  bool update(int x, int y) {
    if (get(x) == get(y)) return false;
    merge(x+n, y);
    merge(x, y+n);
    return true;
  }
};

struct PersistantUnionSet {
  static const int NN = N*(log2(N)+3);
  int rt[N], ls[NN], rs[NN], fa[NN], dep[NN], n, tot;
  void build(const int &n) {
    this->n = n;
    tot = 0;
    rt[0] = build(1, n);
  }
  int build(const int &l, const int &r) {
    int cur = ++tot; assert(tot < NN);
    if (l == r) return fa[cur] = l, dep[cur] = 0, cur;
    int mid = (l+r)>>1;
    ls[cur] = build(l, mid);
    rs[cur] = build(mid+1, r);
    return cur;
  }
  bool query(const int &cur, const int &x, const int &y) {
    return fa[getf(rt[cur], x)] == fa[getf(rt[cur], y)];
  }
  // return the id of fa[], dep[]
  int query(const int &cur, const int &x, const int &l, const int &r) {
    if (l == r) return cur;
    int mid = (l+r)>>1;
    if (x <= mid) return query(ls[cur], x, l, mid);
    else return query(rs[cur], x, mid+1, r);
  }
  // return the id of fa[], dep[]
  int getf(const int &cur, int x) {
    int fi;
    while (fa[(fi = query(cur, x, 1, n))] != x) x = fa[fi];
    return fi;
  }
  void merge(const int &cur, const int &pre, const int &x, const int &y) {
    rt[cur] = rt[pre];
    int fx = getf(rt[cur], x), fy = getf(rt[cur], y);
    if (fa[fx] == fa[fy]) return;
    if (dep[fx] > dep[fy]) swap(fx, fy);
    rt[cur] = update(rt[pre], fa[fx], fa[fy], 1, n);
    if (dep[fx] == dep[fy]) add(rt[cur], fa[fy], 1, n);
  }
  // update fa, merge x to y
  int update(const int &pre, const int &x, const int &y, const int &l, const int &r) {
    int cur = ++tot; assert(tot < NN);
    if (l == r) return fa[cur] = y, dep[cur] = dep[pre], cur;
    ls[cur] = ls[pre]; rs[cur] = rs[pre];
    int mid = (l+r)>>1;
    if (x <= mid) ls[cur] = update(ls[pre], x, y, l, mid);
    else rs[cur] = update(rs[pre], x, y, mid+1, r);
    return cur;
  }
  // add dep
  void add(const int &cur, const int &x, const int &l, const int &r) {
    if (l == r) return ++dep[cur], void();
    int mid = (l+r)>>1;
    if (x <= mid) add(ls[cur], x, l, mid);
    else add(rs[cur], x, mid+1, r);
  }
};

template <typename T>
struct MonotonousQueue {
  unsigned head;
  vector<T> q;
  MonotonousQueue() { clear(); }
  T& operator [](const int &i) { return q[head+i];}
  void clear() { head = 0; q.clear(); }
  size_t size() { return q.size()-head; }
  bool empty() { return head == q.size(); }
  T front() { return q[head]; }
  T back() { return q.back(); }
  void push_front(const T &x) {/*unsupported*/}
  void push_back(const T &x) { q.push_back(x); }
  void pop_front() { ++head; }
  void pop_back() { q.pop_back(); }
};

template <typename T> struct Tree { // 左偏树|可并堆
#define ls tr[x].son[0]
#define rs tr[x].son[1]
  struct TreeNode {
    T val;
    int dis, rt, son[2];
  };
  vector<TreeNode> tr;
  template <typename TT> void build(TT a[], int n) {
    tr.resize(n+1);
    tr[0].dis = -1;
    for (int i = 1; i <= n; ++i) {
      tr[i].val = a[i];
      tr[i].rt = i;
    }
  }
  int get(int x) {
    return tr[x].rt == x ? x : tr[x].rt = get(tr[x].rt);
  }
  void merge(int x, int y) {
    if (tr[x].val == -1 || tr[y].val == -1) return;
    x = get(x); y = get(y);
    if (x != y) tr[x].rt = tr[y].rt = _merge(x, y);
  }
  int _merge(int x, int y) {
    if (!x || !y) return x+y;
    if (tr[x].val > tr[y].val || (tr[x].val == tr[y].val && x > y)) swap(x, y);
    rs = _merge(rs, y);
    if(tr[ls].dis < tr[rs].dis) swap(ls, rs);
    tr[ls].rt = tr[rs].rt = tr[x].rt = x;
    tr[x].dis = tr[rs].dis+1;
    return x;
  }
  T pop(int x) {
    if (tr[x].val == -1) return -1;
    x = get(x);
    T res = tr[x].val;
    tr[x].val = -1;
    tr[ls].rt = ls;
    tr[rs].rt = rs;
    tr[x].rt = _merge(ls, rs);
    return res;
  }
#undef ls
#undef rs
};

inline int manacher(const char *str, char *buf, int *p) {
  int str_len = strlen(str), buf_len = 2;
  buf[0] = buf[1] = '#';
  for(int i = 0; i < str_len; ++i)
    buf[buf_len++] = str[i], buf[buf_len++] = '#';

  int mx = 0, id, ans = 0;
  for(int i = 1; i < buf_len; ++i) {
    if(i <= mx) p[i] = min(p[id*2-i], mx-i);
    else p[i] = 1;
    while(buf[i-p[i]] == buf[i+p[i]]) p[i]++;
    if(i+p[i] > mx) mx = i+p[i], id = i;
    ans = max(ans, p[i]-1);
  }
  return ans;
}

p[l+r+2]-1 >= r-l+1

inline void get_next(const string &s, int nex[]) { get_next(s.c_str(), nex); }
inline void get_next(const char *s, int nex[]) {
  nex[0] = nex[1] = 0;
  for (int i = 1, j = 0, l = strlen(s); i < l; ++i) {
    while (j && s[i] != s[j]) j = nex[j];
    nex[i+1] = s[i] == s[j] ? ++j : 0;
  }
}

inline void kmp(const string &s1, const string &s2, int nex[]) { kmp(s1.c_str(), s2.c_str(), nex); }
inline void kmp(const char *s1, const char *s2, int nex[]) {
  for (int i = 0, j = 0, l1 = strlen(s1), l2 = strlen(s2); i < l1; ++i){
    while (j && s1[i] != s2[j]) j = nex[j];
    if (s1[i] == s2[j]) ++j;
    if (j == l2) {
      cout << i-l2+2 << endl;
      j = nex[j];
    }
  }
}

inline void get_next(const string &s, int nex[]) {
  nex[0] = nex[1] = 0;
  for (int i = 1, j = 0; i < (int)s.size(); ++i) {
    while (j && s[i] != s[j]) j = nex[j];
    nex[i+1] = s[i] == s[j] ? ++j : 0;
  }
}

inline void kmp(const string &s1, const string &s2, int nex[]) {
  for (int i = 0, j = 0; i < (int)s1.size(); ++i) {
    while (j && s1[i] != s2[j]) j = nex[j];
    if (s1[i] == s2[j]) ++j;
    if (j == (int)s2.size()) {
      cout << i-s2.size()+2 << endl;
      j = nex[j];
    }
  }
}

vector<int> z_function(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r && z[i - l] < r - i + 1) {
      z[i] = z[i - l];
    } else {
      z[i] = max(0, r - i + 1);
      while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    }
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}

string max_pre_suf(const string &s1, const string &s2) {
  static const int M1 = 805306457, M2 = 1000173169, P = 31;
  static pii pre[N], suf[N], pwp[N];
  int l1 = s1.size(), l2 = s2.size();
  pre[0] = {0, 0};
  for (int i = 1; i <= l1; ++i) {
    pre[i] = {static_cast<int>((1ll*pre[i-1].first*P+s1[i-1]-'a')%M1),
          static_cast<int>((1ll*pre[i-1].second*P+s1[i-1]-'a')%M2)};
  }
  pwp[0] = {1, 1};
  for (int i = 1; i <= l2; ++i) {
    pwp[i] = {static_cast<int>(1ll*pwp[i-1].first*P%M1),
          static_cast<int>(1ll*pwp[i-1].second*P%M2)};
  }
  suf[l2+1] = {0, 0}; 
  for (int i = l2; i; --i) {
    suf[i] = {static_cast<int>((1ll*(s2[i-1]-'a')*pwp[l2-i].first+suf[i+1].first)%M1),
          static_cast<int>((1ll*(s2[i-1]-'a')*pwp[l2-i].second+suf[i+1].second)%M2)};
  }
  for (int i = min(l1, l2); i; --i)
    if (pre[i] == suf[l2-i+1]) return s1.substr(0, i);
  return "";
}

struct StringHash {
  static const int M1 = 1e9+7;
  static const int M2 = 998244353;
  static const int P1 = 31;
  static const int P2 = 29;
  int ha1[N], ha2[N], pw1[N], pw2[N];
  StringHash() {
    pw1[0] = pw2[0] = 1;
    for (int i = 1; i < N; ++i) {
      pw1[i] = 1ll*pw1[i-1]*P1%M1;
      pw2[i] = 1ll*pw2[i-1]*P2%M2;
    }
  }
  void init(char *s, int len) {
    for (int i = 0; i < len; ++i) {
      ha1[i+1] = (1ll*ha1[i]*P1+s[i]-'a'+1)%M1;
      ha2[i+1] = (1ll*ha2[i]*P2+s[i]-'a'+1)%M2;
    }
  }
  pair<int, int> get(int l, int r) {
    return {(ha1[r]-1ll*ha1[l-1]*pw1[r-l+1]%M1+M1)%M1,
            (ha2[r]-1ll*ha2[l-1]*pw2[r-l+1]%M2+M2)%M2};
  }
};

struct TireTree {
  static const int NN = 5e5+7;
  static const int SZ = 26;
  char beg;
  int nex[NN][SZ], num[NN], cnt;
  bool exist[NN];
  TireTree(char _beg = 'a') : beg(_beg) { clear(); }
  void clear() {
    memset(nex, 0, sizeof(nex[0])*(cnt+1));
    memset(num, 0, sizeof(int)*(cnt+1));
    memset(exist, 0, sizeof(bool)*(cnt+1));
    cnt = 0;
  }
  void insert(const char *s) {
    int len = strlen(s), p = 0;
    for (int i = 0, c; i < len; ++i) {
      c = s[i]-beg;
      if (!nex[p][c]) nex[p][c] = ++cnt;
      p = nex[p][c];
      ++num[p];
    }
    exist[p] = true;
  }
  bool find(const char *s) {
    int len = strlen(s), p = 0;
    for (int i = 0, c; i < len; ++i) {
      c = s[i]-beg;
      if (!nex[p][c]) return false;
      p = nex[p][c];
    }
    return exist[p];
  }
  int count(const char *s) {
    int len = strlen(s), p = 0;
    for (int i = 0, c; i < len; ++i) {
      c = s[i]-beg;
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return num[p];
  }
  void insert(const string &s) { insert(s.c_str()); }
  bool find(const string &s) { return find(s.c_str()); }
  int count(const string &s) { return count(s.c_str()); }
};

struct TireTree {
  static const int SZ = 2;
  static const int B = 30;
  static const int NN = N*B;
  int nex[NN][SZ], cnt;
  void init() { clear(); }
  void clear() {
    memset(nex, 0, sizeof(int)*(cnt+1)*SZ);
    cnt = 0;
  }
  void insert(int x) {
    for (int i = B, c, p = 0; i >= 0; --i) {
      c = (x>>i)&1;
      if (!nex[p][c]) nex[p][c] = ++cnt;
      p = nex[p][c];
    }
  }
  int max_xor(int x) const {
    int ans = 0;
    for (int i = B, c, p = 0; i >= 0; --i) {
      c = (x>>i)&1;
      if (!nex[p][c^1]) p = nex[p][c];
      else p = nex[p][c^1], ans |= 1<<i;
    }
    return ans;
  }
};

struct TireTree {
  static const int SZ = 2;
  static const int B = 30;
  typedef array<int, SZ> T;
  vector<T> nex;
  TireTree() { init(); }
  void init() { nex.assign(1, T()); /* nex.reserve(N); */ }
  void clear() { nex = vector<T>(); }
  size_t size() const { return nex.size(); }
  void extend(int &x) {
    if (x != 0) return;
    x = nex.size();
    nex.emplace_back(T());
  }
  void insert(int x) {
    for (int i = B, c, p = 0; i >= 0; --i) {
      c = (x>>i)&1;
      extend(nex[p][c]);
      p = nex[p][c];
    }
  }
  int max_xor(int x) const {
    int ans = 0;
    for (int i = B, c, p = 0; i >= 0; --i) {
      c = (x>>i)&1;
      if (!nex[p][c^1]) p = nex[p][c];
      else p = nex[p][c^1], ans |= 1<<i;
    }
    return ans;
  }
  void dfs(const TireTree &t, int p = 0, int pt = 0) {
    for (int c = 0; c < SZ; ++c) {
      if (t.nex[pt][c] == 0) continue;
      extend(nex[p][c]);
      dfs(t, nex[p][c], t.nex[pt][c]);
    }
  }
  void join(TireTree &t) {
    if (t.size() < size()) swap(*this, t);
    dfs(t);
    t.clear();
  }
};

struct Aho_Corasick_Automaton {
  static const int NN = 5e6+7;
  static const int SZ = 26;
  char beg;
  int nex[NN][SZ], num[NN], fail[NN], cnt;
  Aho_Corasick_Automaton(const char &_beg = 'a') : beg(_beg) {}
  void clear() {
    memset(nex, 0, sizeof(nex[0])*(cnt+1));
    memset(num, 0, sizeof(int)*(cnt+1));
    memset(fail, 0, sizeof(int)*(cnt+1));
    cnt = 0;
  }
  void insert(const char *s) {
    int len = strlen(s), p = 0;
    for (int i = 0, c; i < len; ++i) {
      c = s[i]-beg;
      if (!nex[p][c]) nex[p][c] = ++cnt;
      p = nex[p][c];
    }
    ++num[p];
  }
  void build() {
    static queue<int> q;
    for (int i = 0; i < SZ; ++i) if (nex[0][i]) q.push(nex[0][i]);
    while (q.size()) {
      int u = q.front();
      q.pop();
      for (int i = 0; i < SZ; ++i) {
        if (nex[u][i]) {
          fail[nex[u][i]] = nex[fail[u]][i];
          q.push(nex[u][i]);
        } else {
          nex[u][i] = nex[fail[u]][i];
        }
      }
    }
  }
  int query(const char *s) {
    int len = strlen(s), p = 0, res = 0;
    for (int i = 0; i < len; ++i) {
      p = nex[p][s[i]-beg];
      for (int t = p; t && ~num[t]; t = fail[t]) {
        res += num[t];
        num[t] = -1;
      }
    }
    return res;
  }
};

struct Aho_Corasick_Automaton {
  static const int NN = 2e5+7;
  static const int SZ = 26;
  char beg;
  int cnt;
  int nex[NN][SZ], fail[NN], vis[NN];
  Aho_Corasick_Automaton(const char &_beg = 'a') : beg(_beg) {}
  void clear() {
    memset(nex, 0, sizeof(nex[0])*(cnt+1));
    memset(fail, 0, sizeof(int)*(cnt+1));
    memset(vis, 0, sizeof(int)*(cnt+1));
    cnt = 0;
  }
  int insert(const char *s) {
    int len = strlen(s), p = 0;
    for (int i = 0, c; i < len; ++i) {
      c = s[i]-beg;
      if (!nex[p][c]) nex[p][c] = ++cnt;
      p = nex[p][c];
    }
    return p;
  }
  void build() {
    static queue<int> q;
    for (int i = 0; i < SZ; ++i) if (nex[0][i]) q.push(nex[0][i]);
    while (q.size()) {
      int u = q.front();
      q.pop();
      for (int i = 0; i < SZ; ++i) {
        if (nex[u][i]) {
          fail[nex[u][i]] = nex[fail[u]][i];
          q.push(nex[u][i]);
        } else {
          nex[u][i] = nex[fail[u]][i];
        }
      }
    }
  }
  void query(char *s) {
    static int deg[NN];
    static queue<int> q;
    int len = strlen(s);
    for (int i = 0, p = 0; i < len; ++i) {
      p = nex[p][s[i]-beg];
      ++vis[p];
      // for (int t = p; t; t = fail[t]) ++vis[t];
    }
    for (int i = 1; i <= cnt; ++i) ++deg[fail[i]];
    for (int i = 1; i <= cnt; ++i) if (!deg[i]) q.push(i);
    while (q.size()) {
      int u = q.front();
      q.pop();
      vis[fail[u]] += vis[u];
      if (--deg[fail[u]] == 0) q.push(fail[u]);
    }
  }
} ac;

int sa[N], rk[N<<1], height[N];
template <typename T> // s start from 1
inline void SA(const T *s, const int &n) {
  static int oldrk[N<<1];
  memset(rk+n+1, 0, sizeof(int)*n);
  for (int i = 1; i <= n; ++i) rk[i] = s[i];
  for (int w = 1; w <= n; w <<= 1) {
    iota(sa+1, sa+n+1, 1);
    sort(sa+1, sa+n+1, [&](const int &x, const int &y) {
      return rk[x] == rk[y] ? rk[x+w] < rk[y+w] : rk[x] < rk[y];
    });
    memcpy(oldrk+1, rk+1, sizeof(int)*2*n);
    for (int p = 0, i = 1; i <= n; ++i) {
      if (oldrk[sa[i]] == oldrk[sa[i-1]] &&
        oldrk[sa[i]+w] == oldrk[sa[i-1]+w]) {
        rk[sa[i]] = p;
      } else {
        rk[sa[i]] = ++p;
      }
    }
  }
  for (int i = 1, k = 0; i <= n; ++i) {
    if (k) --k;
    while (s[i+k] == s[sa[rk[i]-1]+k]) ++k;
    height[rk[i]] = k;
  }
}

int sa[N], rk[N<<1], height[N];
template <typename T> // s start from 1
inline void SA(const T *s, const int &n) {
#define cmp(x, y, w) oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w]
  static int oldrk[N<<1], id[N], px[N], cnt[N], m;
  // memset(oldrk+n+1, 0, sizeof(int)*n); // multi testcase
  memset(cnt, 0, sizeof(int) * (m = 128));
  for (int i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
  for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i; --i) sa[cnt[rk[i]]--] = i;
  for (int w = 1, p, i; w <= n; w <<= 1, m = p) {
    for (p = 0, i = n; i > n - w; --i) id[++p] = i;
    for (i = 1; i <= n; ++i) if (sa[i] > w) id[++p] = sa[i] - w;
    memset(cnt + 1, 0, sizeof(int) * m);
    for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i; --i) sa[cnt[px[i]]--] = id[i];
    swap(oldrk, rk); // memcpy(oldrk+1, rk+1, sizeof(int)*n);
    for (p = 0, i = 1; i <= n; ++i) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }
  for (int i = 1, k = 0; i <= n; ++i) {
    if (k) --k;
    while (s[i+k] == s[sa[rk[i]-1]+k]) ++k;
    height[rk[i]] = k;
  }
#undef cmp
}

namespace SuffixArray {

int sa[N], rk[N], ht[N];
bool t[N << 1];

inline bool islms(const int i, const bool *t) { return i > 0 && t[i] && !t[i - 1]; }

template <class T>
inline void sort(T s, int *sa, const int len, const int sz, const int sigma, bool *t, int *b, int *cb, int *p) {
  memset(b, 0, sizeof(int) * sigma);
  memset(sa, -1, sizeof(int) * len);
  for (register int i = 0; i < len; i++) b[static_cast<int>(s[i])]++;
  cb[0] = b[0];
  for (register int i = 1; i < sigma; i++) cb[i] = cb[i - 1] + b[i];
  for (register int i = sz - 1; i >= 0; i--) sa[--cb[static_cast<int>(s[p[i]])]] = p[i];
  for (register int i = 1; i < sigma; i++) cb[i] = cb[i - 1] + b[i - 1];
  for (register int i = 0; i < len; i++)
    if (sa[i] > 0 && !t[sa[i] - 1])
      sa[cb[static_cast<int>(s[sa[i] - 1])]++] = sa[i] - 1;
  cb[0] = b[0];
  for (register int i = 1; i < sigma; i++) cb[i] = cb[i - 1] + b[i];
  for (register int i = len - 1; i >= 0; i--)
    if (sa[i] > 0 && t[sa[i] - 1])
      sa[--cb[static_cast<int>(s[sa[i] - 1])]] = sa[i] - 1;
}

template <class T>
inline void sais(T s, int *sa, const int len, bool *t, int *b, int *b1, const int sigma) {
  register int i, j, x, p = -1, cnt = 0, sz = 0, *cb = b + sigma;
  for (t[len - 1] = 1, i = len - 2; i >= 0; i--) t[i] = s[i] < s[i + 1] || (s[i] == s[i + 1] && t[i + 1]);
  for (i = 1; i < len; i++)
    if (t[i] && !t[i - 1])
      b1[sz++] = i;
  sort(s, sa, len, sz, sigma, t, b, cb, b1);
  for (i = sz = 0; i < len; i++)
    if (islms(sa[i], t))
      sa[sz++] = sa[i];
  for (i = sz; i < len; i++) sa[i] = -1;
  for (i = 0; i < sz; i++) {
    for (x = sa[i], j = 0; j < len; j++) {
      if (p == -1 || s[x + j] != s[p + j] || t[x + j] != t[p + j]) {
        cnt++, p = x;
        break;
      } else if (j > 0 && (islms(x + j, t) || islms(p + j, t))) {
        break;
      }
    }
    sa[sz + (x >>= 1)] = cnt - 1;
  }
  for (i = j = len - 1; i >= sz; i--)
    if (sa[i] >= 0)
      sa[j--] = sa[i];
  register int *s1 = sa + len - sz, *b2 = b1 + sz;
  if (cnt < sz)
    sais(s1, sa, sz, t + len, b, b1 + sz, cnt);
  else
    for (i = 0; i < sz; i++) sa[s1[i]] = i;
  for (i = 0; i < sz; i++) b2[i] = b1[sa[i]];
  sort(s, sa, len, sz, sigma, t, b, cb, b2);
}

template <class T>
inline void getHeight(T s, int n) {
  for (register int i = 1; i <= n; i++) rk[sa[i]] = i;
  register int j = 0, k = 0;
  for (register int i = 0; i < n; ht[rk[i++]] = k)
    for (k ? k-- : 0, j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++)
      ;
}

template <class T>  // s start from 0
inline void init(T s, const int len, const int sigma = 128) {
  sais(s, sa, len + 1, t, rk, ht, sigma);
  getHeight(s, len);
  for (int i = 1; i <= len; ++i) ++sa[i];
  for (int i = len; i; --i) rk[i] = rk[i-1];
}

}  // namespace SuffixArray

struct SAonTree {
  int n, d[N], cnt[N], sa[N], rk[N<<1], _rk[N<<1], _oldrk[N<<1], tp[N<<1];
  template <typename T>
  void tsort(int *sa, T *rk, int *tp, int m) {
    memset(cnt, 0, sizeof(int)*(m+1));
    for (int i = 1; i <= n; ++i) ++cnt[rk[i]];
    for (int i = 1; i <= m; ++i) cnt[i] += cnt[i-1];
    for (int i = n; i; --i) sa[cnt[rk[tp[i]]]--] = tp[i];
  }
  template <typename T>
  void build(int *f, const T *a, const int n) {
    this->n = n;
    int p = 128, i; // p = n
    iota(tp+1, tp+n+1, 1);
    tsort(sa, a, tp, p);
    for (i = 1, p = 0; i <= n; ++i) {
      _rk[sa[i]] = a[sa[i-1]] == a[sa[i]] ? p : ++p;
      rk[sa[i]] = i;
    }
    for (int w = 1, t = 0; w < n; w <<= 1, ++t) {
      for (i = 1; i <= n; ++i) _oldrk[i] = rk[f[i]];
      tsort(tp, _oldrk, sa, n);
      tsort(sa, _rk, tp, p);
      swap(_rk, tp);
      for (i = 1, p = 0; i <= n; ++i) {
        _rk[sa[i]] = tp[sa[i-1]] == tp[sa[i]]
            && tp[f[sa[i-1]]] == tp[f[sa[i]]] ? p : ++p;
        rk[sa[i]] = i;
      }
      for (int i = n; i; --i) f[i] = f[f[i]]; // attention special tree
    }
  }
};

struct SAM { // root 0
  static const int A = 26;
  static const int M = N<<1;
  static const char C = 'a';
  int sz, last, len[M], link[M], nex[M][A];
  void init() {
    memset(nex, 0, sizeof(int)*A*sz);
    link[0] = -1; sz = 1; last = 0;
  }
  int extend(int c) {
    int cur = sz++, p = last;
    len[cur] = len[last]+1;
    for (; ~p && !nex[p][c]; p = link[p]) nex[p][c] = cur;
    if (p == -1) return link[cur] = 0, cur;
    int q = nex[p][c];
    if (len[p]+1 == len[q]) return link[cur] = q, cur;
    int clone = sz++;
    memcpy(nex[clone], nex[q], sizeof nex[q]);
    link[clone] = link[q];
    len[clone] = len[p]+1;
    for (; ~p && nex[p][c] == q; p = link[p]) nex[p][c] = clone;
    link[q] = link[cur] = clone;
    return cur;
  }
  void insert(const string &s) {
    init(); for (char ch : s) last = extend(ch-C);
  }
};

template <typename T>
struct SAM { // root 0
  struct State {
    int len, link;
    map<T, int> nex;
  } st[N<<1];
  int sz, last;
  SAM() { init(); }
  void init() {
    st[0].len = 0;
    st[0].link = -1;
    sz = 1;
    last = 0;
  }
  void extend(T c) {
    int cur = sz++;
    st[cur].len = st[last].len+1;
    int p = last;
    while (~p && !st[p].nex.count(c)) {
      st[p].nex[c] = cur;
      p = st[p].link;
    }
    if (p == -1) {
      st[cur].link = 0;
    } else {
      int q = st[p].nex[c];
      if (st[p].len+1 == st[q].len) {
        st[cur].link = q;
      } else {
        int clone = sz++;
        st[clone].len = st[p].len+1;
        st[clone].nex = st[q].nex;
        st[clone].link = st[q].link;
        while (~p && st[p].nex[c] == q) {
          st[p].nex[c] = clone;
          p = st[p].link;
        }
        st[q].link = st[cur].link = clone;
      }
    }
    last = cur;
  }
};