#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"


#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/library/cpp-dump.hpp"
#ifndef ONLINE_JUDGE



#else
#define dump(...)
#define CPP_DUMP_SET_OPTION(...)
#define CPP_DUMP_SET_OPTION_GLOBAL(...)
#define CPP_DUMP_DEFINE_EXPORT_OBJECT(...)
#define CPP_DUMP_DEFINE_EXPORT_ENUM(...)
#define CPP_DUMP_DEFINE_EXPORT_OBJECT_GENERIC(...)
#endif

void init_cpp_dump() {
  // ログのラベルを行番号にする
  CPP_DUMP_SET_OPTION(log_label_func, cp::log_label::filename());

  // 記号に色を付ける
  CPP_DUMP_SET_OPTION(es_value,
                      (cp::types::es_value_t{
                          "\x1b[02m",       // log: 灰色
                          "\x1b[34m",       // expression: 青
                          "\x1b[38;5;39m",  // reserved: 明るい青
                          "\x1b[38;5;150m", // number: 明るい緑
                          "\x1b[38;5;172m", // character: オレンジ
                          "\x1b[38;5;220m", // escaped_char: 明るいオレンジ
                          "\x1b[02m",       // op: 灰色
                          "\x1b[32m",       // identifier:  緑
                          "\x1b[96m",       // member: 明るいシアン
                          "\x1b[31m",       // unsupported: 赤
                          {
                              "\x1b[33m", // bracket_by_depth[0]: 黄色
                              "\x1b[35m", // bracket_by_depth[1]: マゼンタ
                              "\x1b[36m", // bracket_by_depth[2]: シアン
                          },
                          "\x1b[02m", // class_op: 灰色
                          "\x1b[02m", // member_op: 灰色
                          "",         // number_op: デフォルト
                      }));
  CPP_DUMP_SET_OPTION(detailed_class_es, true);
  CPP_DUMP_SET_OPTION(detailed_member_es, true);
  CPP_DUMP_SET_OPTION(detailed_number_es, true);
  CPP_DUMP_SET_OPTION(es_style, cp::types::es_style_t::by_syntax);
}

#line 7 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"

#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/alias.hpp"


#include <boost/multiprecision/cpp_int.hpp>

// #include <bits/stdc++.h>
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/bits/stdc++.h"
// C++ includes used for precompiling -*- C++ -*-

// Copyright (C) 2003-2022 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file stdc++.h
 *  This is an implementation file for a precompiled header.
 */

// 17.4.1.2 Headers

// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cuchar>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

#if __cplusplus >= 201402L
#include <shared_mutex>
#endif

#if __cplusplus >= 201703L
#include <any>
#include <charconv>
// #include <execution>
#include <filesystem>
#include <optional>
#include <memory_resource>
#include <string_view>
#include <variant>
#endif

#if __cplusplus >= 202002L
#include <barrier>
#include <bit>
#include <compare>
#include <concepts>
#if __cpp_impl_coroutine
# include <coroutine>
#endif
#include <latch>
#include <numbers>
#include <ranges>
#include <span>
#include <stop_token>
#include <semaphore>
#include <source_location>
#include <syncstream>
#include <version>
#endif

#if __cplusplus > 202002L
#include <expected>
#include <spanstream>
#if __has_include(<stacktrace>)
# include <stacktrace>
#endif
#include <stdatomic.h>
#endif

#line 7 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/alias.hpp"
using namespace std;
// using namespace std::views;
// using namespace boost::multiprecision;

// --- 型エイリアス ---
using ll = long long;
using ull = unsigned long long;
template <typename T> using vec = vector<T>;
template <typename T> using vvec = vector<vector<T>>;
template <typename T> using vvvec = vector<vector<vector<T>>>;
template <typename T> using p_queue = priority_queue<T>;
template <typename T> using rp_queue = priority_queue<T, vec<T>, greater<T>>;
using bint = boost::multiprecision::cpp_int;

// --- 黒魔術 ---
#define int ll

// --- 制御マクロ ---
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define all(v) begin(v), end(v)
// #define BIT(n) (1LL << (n))
#define MAX(type) numeric_limits<type>::max()
#define MIN(type) numeric_limits<type>::min()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pb push_back
#define mp make_pair
#define fir first
#define sec second

// --- 定数 ---
constexpr ll INF = 1LL << 60;
// constexpr ll INF = numeric_limits<ll>::max();

inline signed bit_width(ll x) { return bit_width((ull)x); }
inline ull bit_ceil(ll x) { return bit_ceil((ull)x); }

#line 9 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/concepts.hpp"




template <class T>
concept addable = requires(T a, T b) {
  { a + b } -> convertible_to<T>;
};

#line 10 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/debug.hpp"




// --- デバッグ ---
#ifndef ONLINE_JUDGE















#else

#define line_debug() ;
#define coutd(x) ;
#define printd(x) ;

#endif

#line 11 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/int128_t.hpp"




using int128_t = __int128_t;
using uint128_t = __uint128_t;
using lll = int128_t;
using ulll = uint128_t;

// https://kenkoooo.hatenablog.com/entry/2016/11/30/163533

ostream &operator<<(ostream &dest, lll value) {
  ostream::sentry s(dest);
  if (s) {
    lll tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(ios_base::badbit);
    }
  }
  return dest;
}

lll string_to_lll(string &s) {
  lll ret = 0;
  for (int i = 0; i < s.length(); i++)
    if ('0' <= s[i] && s[i] <= '9')
      ret = 10 * ret + s[i] - '0';
  return ret;
}

istream &operator>>(istream &src, lll &value) {
  string s;
  src >> s;
  value = string_to_lll(s);
  return src;
}

#line 12 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/print.hpp"




// ---------------
// ----- TOC -----
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p);
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p);
template <typename T> ostream &operator<<(ostream &os, const vector<T> &v);
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v);
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v);
template <typename T> istream &operator>>(istream &is, vector<T> &v);
template <typename T, typename S>
ostream &operator<<(ostream &os, const map<T, S> &mp);
template <typename T> ostream &operator<<(ostream &os, const set<T> &st);
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st);
template <typename T> ostream &operator<<(ostream &os, queue<T> q);
template <typename T> ostream &operator<<(ostream &os, deque<T> q);
template <typename T> ostream &operator<<(ostream &os, stack<T> st);
template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq);
// --- END TOC ---
// ---------------

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "[";
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i] << (i + 1 != (int)v.size() ? ", " : "]");
  }
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i] << endl;
  }
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << "i = " << i << endl;
    os << v[i];
  }
  return os;
}

template <typename T> istream &operator>>(istream &is, vector<T> &v) {
  for (T &in : v)
    is >> in;
  return is;
}

template <typename T, typename S>
ostream &operator<<(ostream &os, const map<T, S> &mp) {
  for (auto &[key, val] : mp) {
    os << key << ":" << val << " ";
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, const set<T> &st) {
  os << "{";
  auto itr = st.begin();
  for (int i = 0; i < (int)st.size(); i++) {
    os << *itr << (i + 1 != (int)st.size() ? ", " : "}");
    itr++;
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st) {
  auto itr = st.begin();
  for (int i = 0; i < (int)st.size(); i++) {
    os << *itr << (i + 1 != (int)st.size() ? " " : "");
    itr++;
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, queue<T> q) {
  while (q.size()) {
    os << q.front() << " ";
    q.pop();
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, deque<T> q) {
  while (q.size()) {
    os << q.front() << " ";
    q.pop_front();
  }
  return os;
}

template <typename T> ostream &operator<<(ostream &os, stack<T> st) {
  while (st.size()) {
    os << st.top() << " ";
    st.pop();
  }
  return os;
}

template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) {
  while (pq.size()) {
    os << pq.top() << " ";
    pq.pop();
  }
  return os;
}

#line 13 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/util.hpp"





// --- Utils ---

// 二分探索
template <typename T>
inline T bin_search(T ok, T ng, const function<bool(T)> is_ok) {
  assert(is_ok(ok));
  assert(!is_ok(ng));
  assert(ok < ng);
  while (abs(ok - ng) > 1) {
    T mid = (ok + ng) / 2;
    if (is_ok(mid))
      ok = mid;
    else
      ng = mid;
  }
  return ok;
}

// 順列全探索
inline void rep_perm(int n, function<void(vec<int> &)> f) {
  vec<int> v(n);
  iota(v.begin(), v.end(), 0);
  do {
    f(v);
  } while (next_permutation(v.begin(), v.end()));
}

inline void rep_bit(int n, function<void(int)> f) { rep(i, 1LL << n) f(i); }

// 配列 to string
template <typename T> inline string join(const vec<T> &v, string sep = " ") {
  string res = "";
  rep(i, v.size()) res += to_string(v[i]) + (i == v.size() - 1 ? "" : sep);
  return res;
}
template <typename T>
inline void join_out(ostream &os, const vec<T> &v, string sep = " ",
                     string end = "\n") {
  int n = v.size();
  rep(i, n) os << v[i] << (i == n - 1 ? end : sep);
}

template <typename T>
inline void transform(vec<T> &src, function<void(T &)> f) {
  for (auto &val : src)
    f(val);
}

// ベース指定ceil
inline ll ceil(ll x, ll base) { return (x + base - 1) / base * base; }
// ベース指定floor
inline ll floor(ll x, ll base) { return x / base * base; }

// 合計値を求める
// ll sum(const vec<ll> &v) { return accumulate(all(v), 0LL); }
template <addable T> T sum(const vec<T> &v) { return accumulate(all(v), T()); }

// 可変引数min
template <class... T> auto min(T... a) {
  return min(initializer_list<common_type_t<T...>>{a...});
}

// 可変引数max
template <class... T> auto max(T... a) {
  return max(initializer_list<common_type_t<T...>>{a...});
}

template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}

// 3項間不等式
// 広義単調増加
inline bool is_increasing(int x, int y, int z) { return x <= y && y <= z; }

// 半開区間[x, z)にyが含まれるか?
inline bool is_contained(int x, int y, int z) { return x <= y && y < z; }

// 頂点(x, y)が範囲に含まれるか
inline bool is_contained(int H, int W, int x, int y) {
  return is_contained(0, x, H) && is_contained(0, y, W);
}

// rootに対し、aとbが同じ側にあるか (=は含まない)
inline bool is_same_side(int root, int a, int b) {
  return (root < a) == (root < b);
}

// vector継承にする?
template <typename T> struct vec_accumulate : public vec<T> {
  explicit vec_accumulate(vec<T> &v) : vec<T>(v.size()) {
    assert(v.size() > 0);
    this->at(0) = v[0];
    for (int i = 1; i < v.size(); ++i)
      this->at(i) = this->at(i - 1) + v[i];
  }

  // [0, i]の和
  // なので、-1 <= i < size()
  T operator[](int i) {
    assert(is_contained(-1, i, this->size()));
    if (i == -1)
      return T();
    return this->at(i);
  }
};

// vector func
template <typename T> inline void unique_erase(vec<T> &v) {
  sort(all(v));
  v.erase(unique(all(v)), v.end());
}

// view
struct to_vec_adoptor {
  friend constexpr auto operator|(std::ranges::viewable_range auto &&r,
                                  to_vec_adoptor self) {
    auto r_common = r | std::views::common;
    return std::vector(r_common.begin(), r_common.end());
  }
};
inline constexpr to_vec_adoptor to_vec;

void io_setup() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << std::fixed << std::setprecision(15);
}

#line 14 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"

#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/pow.hpp"





// 繰り返し2乗法
template <integral T, integral F> constexpr T powi(T a, F n) {
  T ans = 1;
  while (n > 0) {
    if (n & 1)
      ans *= a;
    a *= a;
    n >>= 1;
  }
  return ans;
}
template <integral T, integral F> constexpr T pow(T a, F n) {
  return powi(a, n);
}

constexpr ll powm(ll a, ll n, const ll mod) {
  lll ans = 1;
  while (n > 0) {
    if (n & 1)
      ans = ans * a % mod;
    a = ((lll)a) * a % mod;
    n >>= 1;
  }
  return ans;
}

#line 16 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"

#line 2 "/home/zoi/document/kyopro/under_greeen_3/main.cpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp"


#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/all.hpp"


#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/area.hpp"


#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/point.hpp"




class Point {
public:
  int x, y;
  Point() : x(0), y(0) {}
  Point(int x, int y) : x(x), y(y) {}

  Point up() const { return Point(x - 1, y); }
  Point down() const { return Point(x + 1, y); }
  Point left() const { return Point(x, y - 1); }
  Point right() const { return Point(x, y + 1); }
  Point upper_left() const { return Point(x - 1, y - 1); }
  Point upper_right() const { return Point(x - 1, y + 1); }
  Point lower_left() const { return Point(x + 1, y - 1); }
  Point lower_right() const { return Point(x + 1, y + 1); }

  vec<Point> around4() const { return {up(), down(), left(), right()}; }
  vec<Point> around8() const {
    return {up(),   up().right(),  right(), right().down(),
            down(), down().left(), left(),  left().up()};
  }

  int manhattan() const { return std::abs(x) + std::abs(y); }
  int eucurid2() const { return x * x + y * y; }

  bool operator==(const Point &p) const { return x == p.x && y == p.y; }
  bool operator!=(const Point &p) const { return !(*this == p); }
  void operator+=(const Point &p) {
    x += p.x;
    y += p.y;
  }
  void operator-=(const Point &p) {
    x -= p.x;
    y -= p.y;
  }

  Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }
  Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }

  bool operator<(const Point &p) const { return x == p.x ? y < p.y : x < p.x; }
  bool operator>(const Point &p) const { return x == p.x ? y > p.y : x > p.x; }
};
ostream &operator<<(ostream &os, const Point &p) {
  os << p.x << p.y;
  return os;
}
istream &operator>>(istream &is, Point &p) {
  is >> p.x >> p.y;
  return is;
}

inline bool is_contained(int H, int W, Point p) {
  return is_contained(H, W, p.x, p.y);
}

#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/area.hpp"

class Area {
public:
  int H, W;
  bool allow_outside = false;
  char out_val;
  Area(int H, int W) : H(H), W(W), data(vector(H, string(W, '.'))) {}
  Area(int H, int W, char out_val)
      : H(H), W(W), data(vector(H, string(W, '.'))), allow_outside(true),
        out_val(out_val) {}
  string &operator[](int i) { return data[i]; }
  // 時計回りで90度回転
  Area rotated90() const {
    Area ret(W, H);
    rep(i, H) rep(j, W) ret[j][H - i - 1] = data[i][j];
    return ret;
  }
  void rotate90() {
    assert(H == W);
    data = rotated90().data;
  }
  char at(int x, int y) {
    if (is_contained(H, W, x, y))
      return data[x][y];
    else if (allow_outside)
      return out_val;
    else {
      cerr << "[Area::at] out of range" << endl;
      assert(false);
    }
  }
  void set(int x, int y, char val) {
    if (is_contained(H, W, x, y))
      data[x][y] = val;
    else if (allow_outside)
      return;
    else {
      cerr << "[Area::set] out of range" << endl;
      assert(false);
    }
  }

  bool contains(int x, int y) const { return is_contained(H, W, x, y); }
  bool contains(Point p) const { return is_contained(H, W, p.x, p.y); }

private:
  vec<string> data;
};
ostream &operator<<(ostream &os, Area &a) {
  rep(i, a.H) os << a[i] << endl;
  return os;
}
istream &operator>>(istream &is, Area &a) {
  rep(i, a.H) is >> a[i];
  return is;
}

#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/all.hpp"

#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/rect.hpp"


class Rect {
public:
  int x, y, w, h;
  Rect(int x, int y, int w, int h) : x(x), y(y), w(w), h(h) {}
  int area() const { return w * h; }
};

#line 6 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/all.hpp"

#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp"
// #include "3d/all.hpp"
// #include "convolution/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"


#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/comp.hpp"




// https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/4/DSL_4_A

template <typename T> struct comp {
private:
  const int _n;
  int _cmp_n;
  vec<T> _raw, _comp;

public:
  explicit comp(const vec<T> &src)
      : _n(src.size()), _cmp_n(0), _raw(src), _comp(_n, 0) {
    sort(_raw.begin(), _raw.end());
    _raw.erase(unique(_raw.begin(), _raw.end()), _raw.end());
    _cmp_n = _raw.size();
    rep(i, _n) _comp[i] =
        lower_bound(_raw.begin(), _raw.end(), src[i]) - _raw.begin();
  }
  inline int size() const { return _n; }
  inline int cmp_size() const { return _cmp_n; }
  inline T get_raw(int complessed) {
    assert(0 <= complessed && complessed < _cmp_n);
    return _raw[complessed];
  }
  inline T operator[](int i) {
    assert(0 <= i && i < _n);
    return _comp[i];
  }
  inline T get_comp(int raw) {
    return lower_bound(_raw.begin(), _raw.end(), raw) - _raw.begin();
  }
};

#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/dynamic-segment-tree.hpp"




/**
 * @brief セグメント木
 *
 * @tparam T ノードの型
 */
template <typename T> struct DynamicSegmentTree {

private:
  /// 単位元
  T e;
  /// 演算
  function<T(T, T)> op;

  /// 要素数
  int n;

  /// ノードの構造体
  struct Node {

    /// ノードの値
    T val;

    /// 初期化用の値
    T e;

    /// 親ノード, 左の子ノード, 右の子ノード
    Node *p, *l_child, *r_child;

    /// ノードの範囲
    int l, r;

    Node(T val, T e, int l, int r)
        : val(val), e(e), p(nullptr), l_child(nullptr), r_child(nullptr), l(l),
          r(r) {}

    Node(T val, Node *p, bool child_index)
        : val(val), e(p->e), p(p), l_child(nullptr), r_child(nullptr),
          l(!child_index ? p->l : p->mid()), r(!child_index ? p->mid() : p->r) {
    }

    /// ノードの範囲の中央
    int mid() const { return (l + r) / 2; }

    /// 子ノードを取得する
    Node *child(bool child_index) {
      if (child_index == 0) {
        if (l_child == nullptr)
          l_child = new Node(e, this, 0);
        return l_child;
      } else {
        if (r_child == nullptr)
          r_child = new Node(e, this, 1);
        return r_child;
      }
    }

    /// 子ノードの情報からvalを更新する
    void update(auto &op) {
      T l_val = l_child == nullptr ? e : l_child->val;
      T r_val = r_child == nullptr ? e : r_child->val;
      val = op(l_val, r_val);
    }
  };

  Node *root;

public:
  /**
   * @brief 個数から空のSegmentTreeを生成する O(1)
   *
   * @param length 要素数
   * @param e 単位元
   * @param op 演算
   */
  inline explicit DynamicSegmentTree(int length, T e, function<T(T, T)> op)
      : e(e), op(op), n(bit_ceil(length)), root(new Node(e, e, 0, n)) {}

  /**
   * @brief i番目の要素を取得する O(log n)
   */
  inline Node *get_node(int i) const {
    Node *node = root;
    while (node->l + 1 < node->r) {
      node = node->child(node->mid() <= i);
    }
    return node;
  }

  /**
   * @brief i番目の要素を変更する O(log n) * op
   *
   * @param i インデックス (0-indexed)
   * @param a 更新後の要素
   */
  inline void set(int i, T a) {
    Node *node = get_node(i);
    node->val = a;
    while (node->p != nullptr) {
      node = node->p;
      node->update(op);
    }
  }

  /**
   * @brief i番目の要素を取得する O(log n)
   *
   * @param i インデックス (0-indexed)
   * @return i番目の要素
   */
  inline T get(int i) const { return get_node(i)->val; }

  /**
   * @brief [l, r)の範囲に対するクエリを行う O(log n) * op
   *
   * @param l クエリの左端 (0-indexed)
   * @param r クエリの右端 (0-indexed)
   * @return クエリの結果
   */
  inline T query(int l, int r) const { return _query(root, l, r); }

private:
  /**
   * @brief 特定のノードに対し、[l, r)の範囲に対するクエリを行う O(log n) * op
   *
   * @param node クエリを行うノード
   * @param l クエリの左端 (0-indexed)
   * @param r クエリの右端 (0-indexed)
   * @return クエリの結果
   */
  inline T _query(Node *node, int l, int r) const {
    if (r <= node->l || node->r <= l)
      return e;
    if (l <= node->l && node->r <= r)
      return node->val;
    return op(_query(node->child(0), l, r), _query(node->child(1), l, r));
  }
};

#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/fenwick-tree.hpp"




template <typename T> struct FenwickTree {
private:
  T _n;
  vec<T> _data;

public:
  explicit FenwickTree(T n) : _n(n), _data(n + 1, 0) {}
  explicit FenwickTree(const vec<T> &src) : _n(src.size()), _data(_n + 1, 0) {
    rep(i, _n) add(i, src[i]);
  }

  void add(int i, T val) {
    i++;
    while (i <= _n) {
      _data[i] += val;
      i += i & -i;
    }
  }
  // [0, i]
  int sum(int i) const {
    i++;
    T ans = 0;
    while (i > 0) {
      ans += _data[i];
      i -= i & -i;
    }
    return ans;
  }
  // [l, r)
  int sum(int l, int r) const { return sum(r - 1) - sum(l - 1); }
};

#line 6 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos.hpp"




template <typename T> struct imos {
private:
  const int _n;
  vec<T> _data;
  bool _is_build = false;

public:
  explicit imos(int n) : _n(n), _data(_n + 1, 0) {}
  explicit imos(vec<T> src) : _n(src.size()), _data(_n + 1, 0) {
    rep(i, _n) add(i, src[i]);
  }
  inline int size() const { return _n; }
  inline void add(int l, int r, T x) {
    assert(!_is_build);
    assert(l < r);
    assert(0 <= l && r <= _n);
    _data[l] += x;
    _data[r] -= x;
  }
  inline void add(int i, T x) {
    assert(!_is_build);
    assert(0 <= i && i < _n);
    add(i, i + 1, x);
  }
  inline void build() {
    rep(i, _n) _data[i + 1] += _data[i];
    _is_build = true;
  }
  inline T get(int i) {
    assert(0 <= i && i < _n);
    if (!_is_build)
      build();
    return _data[i];
  }

  friend ostream &operator<<(ostream &os, const imos<T> &a) {
    if (!a._is_build) {
      os << "not builded";
      return os;
    }
    os << a._data;
    return os;
  }
};

#line 7 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos2d.hpp"





template <typename T> struct imos2d {
private:
  const int _H, _W;
  vvec<T> _data;
  bool _is_build = false;

public:
  explicit imos2d(int H, int W)
      : _H(H), _W(W), _data(_H + 1, vec<T>(_W + 1, 0)) {}
  explicit imos2d(vvec<T> src)
      : _H(src.size()), _W(src[0].size()), _data(_H + 1, vec<T>(_W + 1, 0)) {
    rep(x, _H) rep(y, _W) add({x, y}, src[x][y]);
  }
  inline pair<int, int> size() const { return {_H, _W}; }
  // 半開区間
  inline void add(Point a, Point b, T x) {
    assert(!_is_build);
    assert(a.x < b.x && a.y < b.y);
    assert(is_contained(_H, _W, a) && is_contained(_H, _W, b.upper_left()));
    _data[a.x][a.y] += x;
    _data[a.x][b.y] -= x;
    _data[b.x][a.y] -= x;
    _data[b.x][b.y] += x;
  }
  inline void add(Point a, T x) {
    assert(!_is_build);
    assert(is_contained(_H, _W, a));
    add(a, a.lower_right(), x);
  }
  inline void build() {
    rep(x, _H) rep(y, _W) _data[x][y + 1] += _data[x][y];
    rep(y, _W) rep(x, _H) _data[x + 1][y] += _data[x][y];
    _is_build = true;
  }
  inline T get(Point p) const {
    assert(is_contained(_H, _W, p));
    assert(_is_build);
    return _data[p.x][p.y];
  }
};

template <typename T> ostream &operator<<(ostream &os, const imos2d<T> &im) {
  rep(x, im.size().first) {
    rep(y, im.size().second) { os << im.get({x, y}) << " "; }
    os << endl;
  }
  return os;
}

#line 8 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/lazy-segment-tree.hpp"




// 参考 https://qiita.com/ningenMe/items/bf66de877e3b97d35862

/**
 * @brief 遅延セグメント木
 *
 * @tparam T ノードの型
 * @tparam F 操作情報の型
 */
template <typename T, typename F> struct LazySegmentTree {
private:
  /// データの単位元
  const T e;
  /// 操作の単位元
  const F id;

  /// データの演算(ノードのマージ)
  const function<T(T, T)> op;
  /// ノードの更新 (操作の適用)
  const function<T(F, T)> apply;
  /// 操作のマージ
  const function<F(F, F)> merge;

  // 要素数
  int32_t _n;
  int32_t _height;

  /// セグ木のノード情報
  vec<T> _data;
  /// セグ木の遅延情報
  vec<F> _lazy;

  /// 左の子のインデックスを返す
#define L(i) (i << 1)
  /// 右の子のインデックスを返す
#define R(i) (i << 1 | 1)
  /// 親のインデックスを返す
#define P(i) (i >> 1)

  /**
   * @brief k番目のノードの遅延情報を解消し、子ノードに伝搬する O(log N) * merge
   *
   * @param k ノード番号 (1-indexed, seg-index)
   */
  inline void eval(int32_t k) {
    if (_lazy[k] == id)
      return;
    _data[k] = apply(_lazy[k], _data[k]);
    if (k < _n) {
      _lazy[L(k)] = merge(_lazy[L(k)], _lazy[k]);
      _lazy[R(k)] = merge(_lazy[R(k)], _lazy[k]);
    }
    _lazy[k] = id;
  }

public:
  // n: 要素数, e: 単位元, id: 操作情報の単位元, op: 演算, update:
  // ノードの更新(fn,val->val), merge:
  // 操作aがすでに行われている状態に操作bを適用したときの操作
  // TODO: 2つの実装が別れているのをどうにかする

  /**
   * @brief 要素数から空のLazySegmentTreeを生成する O(length)
   *
   * @param length 要素数
   * @param e 単位元
   * @param id 操作情報の単位元
   * @param op ノードのマージ
   * @param apply 操作の適用
   * @param merge 操作のマージ
   */
  explicit inline LazySegmentTree(const int32_t length, const T e, const F id,
                                  const function<T(T, T)> op,
                                  const function<T(F, T)> apply,
                                  const function<F(F, F)> merge)
      : e(e), id(id), op(op), apply(apply), merge(merge), _n(bit_ceil(length)),
        _height(bit_width(_n) - 1), _data(2 * _n, e), _lazy(2 * _n, id) {}

  /**
   * @brief 既存のベクトルからLazySegmentTreeを生成する O(length) * op
   *
   * @param data データ
   * @param e 単位元
   * @param id 操作情報の単位元
   * @param op ノードのマージ
   * @param apply 操作の適用
   * @param merge 操作のマージ
   */
  explicit inline LazySegmentTree(vec<T> &data, const T e, const F id,
                                  const function<T(T, T)> op,
                                  const function<T(F, T)> apply,
                                  const function<F(F, F)> merge)
      : e(e), id(id), op(op), apply(apply), merge(merge),
        _n(bit_ceil(data.size())), _height(bit_width(_n) - 1), _data(2 * _n, e),
        _lazy(2 * _n, id) {
    rep(i, data.size()) _data[i + _n] = data[i];
    for (int i = _n - 1; i > 0; --i)
      _data[i] = op(_data[L(i)], _data[R(i)]);
  }

  /**
   * @brief [l, r)の区間に対して操作fを適用する O(log N) * op
   *
   * @param l 左端 (0-indexed)
   * @param r 右端 (0-indexed)
   * @param f 操作
   */
  inline void set(int32_t l, int32_t r, F f) {
    // a, bはseg-index [a,b]
    int32_t a = l + _n, b = r + _n - 1;

    // 上から下へとlazyを伝搬させる
    for (int32_t i = _height; 0 < i; --i)
      eval(a >> i), eval(b >> i);
    // bを [a, b]から[a, b)にする
    for (b++; a < b; a >>= 1, b >>= 1) {
      if (a & 1)
        _lazy[a] = merge(_lazy[a], f), eval(a), a++;
      if (b & 1)
        --b, _lazy[b] = merge(_lazy[b], f), eval(b);
    }
    // a, bをseg-index [a,b]に戻す
    a = l + _n, b = r + _n - 1;
    // a,bを親に移しつつ、aが実在頂点の間
    while ((a >>= 1), (b >>= 1), a) {
      if (_lazy[a] == id) {
        _data[a] = op(apply(_lazy[(a << 1) | 0], _data[(a << 1) | 0]),
                      apply(_lazy[(a << 1) | 1], _data[(a << 1) | 1]));
      }
      if (_lazy[b] == id) {
        _data[b] = op(apply(_lazy[(b << 1) | 0], _data[(b << 1) | 0]),
                      apply(_lazy[(b << 1) | 1], _data[(b << 1) | 1]));
      }
    }
  }

  /**
   * @brief [l, r)の区間に対するクエリを処理する
   *
   * @param l 左端 (0-indexed)
   * @param r 右端 (0-indexed)
   * @return T クエリの結果
   */
  inline T query(int32_t l, int32_t r) {
    // a, bはseg-index [a,b]
    int32_t a = l + _n, b = r + _n - 1;
    // 上から下へとlazyを伝搬させる
    for (int32_t i = _height; 0 <= i; --i)
      eval(a >> i), eval(b >> i);
    T vl = e, vr = e;
    // bを [a, b]から[a, b)にする
    for (b++; a < b; a >>= 1, b >>= 1) {
      if (a & 1)
        vl = op(vl, apply(_lazy[a], _data[a])), a++;
      if (b & 1)
        b--, vr = op(apply(_lazy[b], _data[b]), vr);
    }
    return op(vl, vr);
  }

  /**
   * @brief i番目の要素を取得する
   *
   * @param i インデックス (0-indexed)
   * @return T i番目の要素
   */
  inline T get(int32_t i) { return query(i, i + 1); }

#undef L
#undef R
#undef P
};

#line 9 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/rbst-multiset.hpp"


#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/rbst.hpp"




template <typename T> struct RBST {
private:
  /// 乱数シード生成器
  random_device rd;
  /// 乱数生成器
  mt19937 mt;
  /// 単位元
  T e;
  /// 演算
  function<T(T, T)> F;

public:
  /// ノード
  struct node_t {
    /// ノードの値
    T val;
    /// 部分木の大きさ
    size_t size;
    /// 部分木の総積
    T sum;
    /// 左右の子
    node_t *lch, *rch;
    /// 値のみによるノードの生成
    node_t(T val) : val(val), size(1), sum(val), lch(nullptr), rch(nullptr) {}
    /// 値と子によるノードの生成
    node_t(T val, node_t *lch, node_t *rch)
        : val(val), size(1), sum(val), lch(lch), rch(rch) {}
  };
  /// ノードの値を取得
  inline T val(const node_t *const t) const { return t ? t->val : e; }
  inline size_t size(const node_t *const t) const { return t ? t->size : 0; }
  inline T sum(const node_t *const t) const { return t ? t->sum : e; }
  inline node_t *update(node_t *const t) const {
    t->size = size(t->lch) + size(t->rch) + 1;
    t->sum = F(F(sum(t->lch), val(t)), sum(t->rch));
    return t;
  }

  RBST(T e, function<T(T, T)> F) : mt(rd()), e(e), F(F) {}

  node_t *root = nullptr;
  inline node_t *merge(node_t *const l, node_t *const r) {
    if (!l || !r)
      return l ? l : r;
    if (mt() % (l->size + r->size) < l->size) {
      l->rch = merge(l->rch, r);
      return update(l);
    } else {
      r->lch = merge(l, r->lch);
      return update(r);
    }
  }
  inline pair<node_t *, node_t *> split(node_t *const t, const size_t k) {
    if (!t)
      return {nullptr, nullptr};
    if (k <= size(t->lch)) {
      auto p = split(t->lch, k);
      t->lch = p.second;
      return {p.first, update(t)};
    } else {
      auto p = split(t->rch, k - size(t->lch) - 1);
      t->rch = p.first;
      return {update(t), p.second};
    }
  }
  inline node_t *insert_at(node_t *t, const size_t k, T val) {
    auto [l, r] = split(t, k);
    return t = merge(merge(l, new node_t(val)), r);
  }
  inline void insert_at(const size_t k, T val) {
    if (!root)
      root = new node_t(val);
    else
      root = insert_at(root, k, val);
  }
  inline node_t *erase_at(node_t *t, const size_t k) {
    auto [l, r] = split(t, k);
    auto [ll, lr] = split(r, 1);
    return t = merge(l, lr);
  }
  inline void erase_at(const size_t k) {
    assert(root);
    assert(0 <= k);
    assert(k < root->size);
    if (root->size == 1) {
      delete root;
      root = nullptr;
      return;
    }
    root = erase_at(root, k);
  }
  inline T get_at(const node_t *const t, const size_t k) const {
    assert(t);
    assert(0 <= k);
    assert(k < t->size);
    if (k < size(t->lch))
      return get_at(t->lch, k);
    if (k == size(t->lch))
      return t->val;
    return get_at(t->rch, k - size(t->lch) - 1);
  }

  inline T get_at(const size_t k) const { return get_at(root, k); }
  inline T query(node_t *&t, const size_t l, const size_t r) {
    auto [left, mid_right] = split(t, l);
    auto [mid, right] = split(mid_right, r - l);
    T res = sum(mid);
    t = merge(merge(left, mid), right);
    return res;
  }
  inline T query(const size_t l, const size_t r) { return query(root, l, r); }
  inline size_t size() const { return size(root); }
};

template <typename T> ostream &operator<<(ostream &os, const RBST<T> &t) {
  using node_t = typename RBST<T>::node_t;
  auto dump = [&os](auto fn, node_t *t) {
    if (!t)
      return;
    fn(fn, t->lch);
    os << t->val << " ";
    fn(fn, t->rch);
  };
  os << "RBST[ ";
  dump(dump, t.root);
  os << "]";
  return os;
}

#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/rbst-multiset.hpp"

template <typename T> struct RBSTMultiSet : public RBST<T> {
private:
  using node_t = typename RBST<T>::node_t;

public:
  inline RBSTMultiSet() : RBST<T>(0, [](T a, T b) { return a; }) {}

  inline size_t lower_bound(const node_t *const t, T val) const {
    if (!t)
      return 0;
    if (val <= this->val(t))
      return lower_bound(t->lch, val);
    return this->size(t->lch) + 1 + lower_bound(t->rch, val);
  }
  inline size_t lower_bound(const T val) const {
    return lower_bound(this->root, val);
  }
  inline size_t upper_bound(const node_t *const t, const T val) const {
    if (!t)
      return 0;
    if (val < t->val)
      return upper_bound(t->lch, val);
    return this->size(t->lch) + 1 + upper_bound(t->rch, val);
  }
  inline size_t upper_bound(const T val) const {
    return upper_bound(this->root, val);
  }
  inline void insert(const T val) { this->insert_at(lower_bound(val), val); }
  inline size_t count(const T val) const {
    return upper_bound(val) - lower_bound(val);
  }
  inline bool contains(const T val) const {
    int idx = lower_bound(val);
    return idx < this->root->size && this->get_at(idx)->val == val;
  }
  inline void erase(const T val) {
    int idx = lower_bound(val);
    if (idx < this->root->size && this->get_at(idx)->val == val) {
      this->erase_at(idx);
    }
  }
};

#line 10 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/rbst-set.hpp"




template <typename T> struct RBSTSet : public RBSTMultiSet<T> {
public:
  inline RBSTSet() : RBSTMultiSet<T>() {}
  inline void insert(const T val) {
    if (contains(val))
      return;
    this->insert(val, lower_bound(val));
  }
};

#line 11 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"

#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/segment-tree.hpp"




// 参考: https://qiita.com/ningenMe/items/bf66de877e3b97d35862

/**
 * @brief セグメント木
 *
 * @tparam T ノードの型
 */
template <typename T> struct SegmentTree {

private:
  /// 単位元
  T e;
  /// 演算
  function<T(T, T)> op;

  /// 要素数
  int n;
  /// SegTreeのノード上のデータ
  vec<T> data;

  /// 左の子のインデックスを返す
#define L(i) (i << 1)
  /// 右の子のインデックスを返す
#define R(i) (i << 1 | 1)
  /// 親のインデックスを返す
#define P(i) (i >> 1)

public:
  /**
   * @brief 個数から空のSegmentTreeを生成する O(n)
   *
   * @param length 要素数
   * @param e 単位元
   * @param op 演算
   */
  inline explicit SegmentTree(int length, T e, function<T(T, T)> op)
      : e(e), op(op), n(bit_ceil(length)), data(2 * n, e) {}

  /**
   * @brief 既存のベクトルからSegmentTreeを生成する O(n) * op
   *
   * @param v データ
   * @param e 単位元
   * @param op 演算
   */
  inline explicit SegmentTree(const vec<T> &v, T e, function<T(T, T)> op)
      : e(e), op(op), n(bit_ceil(v.size())), data(2 * n, e) {
    rep(i, v.size()) data[i + n] = v[i];
    for (int i = n - 1; i > 0; --i)
      data[i] = op(data[L(i)], data[R(i)]);
  }

  /**
   * @brief i番目の要素を変更する O(log n) * op
   *
   * @param i インデックス (0-indexed)
   * @param a 更新後の要素
   */
  inline void set(int i, T a) {
    i += n;
    data[i] = a;
    while (i = P(i), i > 0)
      data[i] = op(data[L(i)], data[R(i)]);
  }

  /**
   * @brief i番目の要素を取得する O(1)
   *
   * @param i インデックス (0-indexed)
   * @return i番目の要素
   */
  inline T get(int i) const { return data[i + n]; }

  /**
   * @brief [l, r)の範囲に対するクエリを行う O(log n) * op
   *
   * @param l クエリの左端 (0-indexed)
   * @param r クエリの右端 (0-indexed)
   * @return クエリの結果
   */
  inline T query(int l, int r) const {
    T l_val = e, r_val = e;
    l += n, r += n;
    while (l < r) {
      if (l & 1)
        l_val = op(l_val, data[l++]);
      if (r & 1)
        r_val = op(data[--r], r_val);
      l = P(l), r = P(r);
    }
    return op(l_val, r_val);
  }

#undef L
#undef R
#undef P
};

#line 13 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/union-find.hpp"




struct UnionFind {
private:
  int _n;
  vec<int> _parents;
  vec<int> _size;

public:
  explicit UnionFind(int n) : _n(n), _parents(n), _size(n, 1) {
    iota(all(_parents), 0);
  }
  int find(int a) {
    if (_parents[a] == a)
      return a;
    else
      return _parents[a] = find(_parents[a]);
  }
  void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
      // merge後の親はa
      if (_size[a] < _size[b])
        swap(a, b);
      _size[a] += _size[b];
      _size[b] = 0;
      _parents[b] = a;
    }
  }
  int size(int a) { return _size[find(a)]; }
  bool same(int a, int b) { return find(a) == find(b); }
  vec<vec<int>> groups() {
    vec<int> leaders(_n);
    rep(i, _n) { leaders[i] = find(i); }
    vec<vec<int>> res(_n);
    rep(i, _n) res[i].reserve(_size[i]);
    rep(i, _n) res[leaders[i]].push_back(i);
    res.erase(remove_if(all(res), [&](const vec<int> &v) { return v.empty(); }),
              res.end());
    return res;
  }
};
using UF = UnionFind;

#line 14 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/weighted-union-find.hpp"





template <addable T> struct WeightedUnionFind {
private:
  int _n;
  vec<int> _parents;
  vec<int> _size;
  vec<T> _weight;

  T weight(int i) {
    find(i);
    return _weight[i];
  }

public:
  explicit WeightedUnionFind(int n)
      : _n(n), _parents(n), _size(n, 1), _weight(n) {
    iota(all(_parents), 0);
  }

  int find(int i) {
    if (_parents[i] == i)
      return i;
    const int root = find(_parents[i]);
    _weight[i] += _weight[_parents[i]];
    return _parents[i] = root;
  }

  void merge(int a, int b, T w) {
    w += weight(a);
    w -= weight(b);
    a = find(a);
    b = find(b);
    if (a != b) {
      // merge後の親はa
      if (_size[a] < _size[b])
        swap(a, b), w = -w;
      _size[a] += _size[b];
      _size[b] = 0;
      _parents[b] = a;
      _weight[b] = w;
    }
  }

  T diff(int a, int b) { return weight(b) - weight(a); }

  int size(int a) { return _size[find(a)]; }

  bool same(int a, int b) { return find(a) == find(b); }
};

template <addable T> using WUF = WeightedUnionFind<T>;

#line 15 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"

#line 7 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/cycle.hpp"


#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/template.hpp"




// Node
template <class T = ll> struct WeightedNode {
  int id;
  T cost = numeric_limits<T>::max();
  WeightedNode(int id, T cost) : id(id), cost(cost) {}
};

template <class T = ll> struct WeightState {
public:
  int location;
  T used_cost;
  WeightState(int location, T used_cost)
      : location(location), used_cost(used_cost) {}
  bool operator<(const WeightState &n) const { return used_cost < n.used_cost; }
  bool operator>(const WeightState &n) const { return used_cost > n.used_cost; }
};

// Graph
struct Graph {
private:
  const int n;
  const bool directed;
  vec<vec<int>> edges;

public:
  explicit Graph(int n, bool directed = false)
      : n(n), directed(directed), edges(n) {}
  inline void add_edge(int u, int v) {
    edges[u].emplace_back(v);
    if (!directed)
      edges[v].emplace_back(u);
  }
  inline vec<int> &operator[](int i) { return edges[i]; }
  inline int size() const { return n; }
};

template <class T = ll> struct WeightedGraph {
private:
  const int n;
  const bool directed;

public:
  vec<vec<WeightedNode<T>>> edges;
  explicit WeightedGraph(int n, bool directed = false)
      : n(n), directed(directed), edges(n) {}
  inline void add_edge(int u, int v, T w) {
    edges[u].emplace_back(WeightedNode(v, w));
    if (!directed)
      edges[v].emplace_back(WeightedNode(u, w));
  }
  inline vec<WeightedNode<T>> &operator[](int i) { return edges[i]; }
  inline int size() const { return n; }
};

// template <class T = ll> using WeightedGraph = vec<vec<WeightedNode<T>>>;

template <class T = ll> using WGraph = WeightedGraph<T>;

#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/cycle.hpp"

bool has_cycle(Graph &g, int start = 0) {
  vec<int> seen(g.size(), 0);
  vec<int> finished(g.size(), 0);
  auto dfs = [&](auto fn, int index) {
    seen[index] = 1;
    for (auto next : g[index]) {
      if (finished[next])
        continue;
      if (seen[next] && !finished[next])
        return true;
      if (fn(fn, next))
        return true;
    }
    finished[index] = 1;
    return false;
  };
  return dfs(dfs, start);
}

#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/depth.hpp"




struct TreeNodeInfo {
public:
  TreeNodeInfo(int parent, int depth) : parent(parent), depth(depth) {}
  int parent;
  int depth;
};

vec<TreeNodeInfo> depth(Graph &graph, int root = 0) {
  vec<TreeNodeInfo> result(graph.size(), TreeNodeInfo(-1, -1));
  stack<int> st;
  st.push(root);
  result[root] = TreeNodeInfo(root, 0);
  while (!st.empty()) {
    int index = st.top();
    st.pop();
    for (auto next : graph[index]) {
      if (result[next].depth != -1)
        continue;
      result[next] = TreeNodeInfo(index, result[index].depth + 1);
      st.push(next);
    }
  }
  return result;
}

#line 3 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/diameter.hpp"




int diameter(Graph &graph, int start = 0) {
  vec<int> seen(graph.size(), 0);
  auto dfs = [&](auto fn, int index) -> pair<int, int> {
    // max-cost, index
    pair<int, int> result = {0, index};

    seen[index] = 1;

    for (auto next : graph[index]) {
      if (seen[next])
        continue;
      auto next_result = fn(fn, next);
      next_result.first += 1;
      result = max(result, next_result);
    }
    seen[index] = 0;
    return result;
  };
  auto result = dfs(dfs, start);
  result = dfs(dfs, result.second);
  return result.first;
}

template <typename T = ll> int diameter(WGraph<T> &graph, int start = 0) {
  auto dfs = [&](int index) -> pair<T, int> {
    vec<T> result(graph.size(), -1);

    T mx = 0;
    int mx_index = index;
    stack<int> st;
    st.push(index);
    result[index] = 0;
    while (!st.empty()) {
      int current = st.top();
      st.pop();
      for (auto next : graph[current]) {
        if (result[next.id] >= 0)
          continue;
        st.push(next.id);
        result[next.id] = result[current] + next.cost;
        if (chmax(mx, result[next.id])) {
          mx_index = next.id;
        }
      }
    }
    return {mx, mx_index};
  };
  auto result = dfs(start);
  result = dfs(result.second);
  return result.first;
}

#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/dijkstra.hpp"




template <typename T = ll> vec<T> dijkstra(WGraph<T> &graph, int start) {
  vec<T> way(graph.size(), INF);
  rp_queue<WeightState<T>> q;
  q.push(WeightState<T>(start, 0));
  way[start] = 0;
  while (!q.empty()) {
    WeightState current = q.top();
    q.pop();
    for (auto &next : graph[current.location]) {
      T next_cost = current.used_cost + next.cost;
      if (way[next.id] <= next_cost)
        continue;
      way[next.id] = next_cost;
      q.push(WeightState<T>(next.id, way[next.id]));
    }
  }
  return way;
}

#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/lca.hpp"


struct LCA {
private:
  Graph graph;
  int root;
  // parent[k][v] := vの2^k先の親
  vec<vec<int>> parent;
  vec<TreeNodeInfo> depth_data;

public:
  explicit LCA(Graph &graph, int root = 0)
      : graph(graph), root(root), depth_data(depth(graph, root)) {
    int n = graph.size();
    int logn = 1;
    while ((1 << logn) < n)
      logn++;
    parent = vector(logn, vector(n, -1LL));
    for (int i = 0; i < n; i++)
      parent[0][i] = depth_data[i].parent;
    // ダブリング
    for (int k = 0; k + 1 < logn; k++) {
      for (int i = 0; i < n; i++) {
        if (parent[k][i] < 0)
          parent[k + 1][i] = -1;
        else
          parent[k + 1][i] = parent[k][parent[k][i]];
      }
    }
  }

  int query(int u, int v) const {
    if (depth_data[u].depth > depth_data[v].depth)
      swap(u, v);
    int logn = parent.size();
    // uとvの深さが同じになるまで親を辿る
    rep(k, logn) {
      if ((depth_data[v].depth - depth_data[u].depth) >> k & 1) {
        v = parent[k][v];
      }
    }
    // にぶたん
    if (u == v)
      return u;
    for (int k = logn - 1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
};

#line 6 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp"

#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/topological-sort.hpp"




vec<int> topological_sort(Graph &graph) {
  vec<int> result;
  vec<int> deleted(graph.size(), false);

  vec<int> in_count(graph.size());
  rep(i, graph.size()) {
    for (auto next : graph[i]) {
      in_count[next]++;
    }
  }
  queue<int> q;
  rep(i, graph.size()) {
    if (in_count[i] == 0) {
      q.push(i);
    }
  }

  while (!q.empty()) {
    int now = q.front();
    q.pop();
    result.emplace_back(now);
    deleted[now] = true;
    for (auto next : graph[now]) {
      if (deleted[next])
        continue;
      in_count[next]--;
      if (in_count[next] == 0) {
        q.push(next);
      }
    }
  }

  return result;
}

#line 8 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/all.hpp"

#line 8 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/all.hpp"


// #include "combination.hpp"
// #include "factorial.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/modint.hpp"





namespace modint_utils {
constexpr inline int32_t normalize(int val, int32_t mod) {
  return (val % mod + mod) % mod;
}
constexpr inline int32_t inv(int32_t a, int32_t mod) {
  int32_t b = mod, u = 1, v = 0;
  while (b) {
    int32_t t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= mod;
  if (u < 0)
    u += mod;
  return u;
  // return mod_pow(val, mod - 2, mod);
}
} // namespace modint_utils

template <int MOD> struct dynamic_modint {
private:
  int _val;

public:
  dynamic_modint() : dynamic_modint(0) {}
  dynamic_modint(int val) : _val(modint_utils::normalize(val, MOD)) {}

  // logic
  int val() const { return _val; }
  inline dynamic_modint inv() const {
    return dynamic_modint(modint_utils::inv(_val, MOD));
  }
  inline dynamic_modint pow(const int n) const {
    return dynamic_modint(powm(_val, n, MOD));
  }
  inline static constexpr dynamic_modint pow(const dynamic_modint &a,
                                             const int n) {
    return dynamic_modint(mod_pow(a._val, n, a.MOD));
  }

  // op
  inline dynamic_modint &operator++() { return *this += 1; }
  inline dynamic_modint &operator--() { return *this -= 1; }
  inline dynamic_modint operator++(int32_t) const {
    dynamic_modint tmp = *this;
    ++*this;
    return tmp;
  }
  inline dynamic_modint operator--(int32_t) {
    dynamic_modint tmp = *this;
    --*this;
    return tmp;
  }
  inline dynamic_modint operator+(const dynamic_modint &a) const {
    return dynamic_modint(_val) += a;
  }
  inline dynamic_modint operator-(const dynamic_modint &a) const {
    return dynamic_modint(_val) -= a;
  }
  inline dynamic_modint operator*(const dynamic_modint &a) const {
    return dynamic_modint(_val) *= a;
  }
  inline dynamic_modint operator/(const dynamic_modint &a) const {
    return dynamic_modint(_val) /= a;
  }
  inline bool operator==(const dynamic_modint &a) { return _val == a._val; }
  inline bool operator!=(const dynamic_modint &a) { return _val != a._val; }
  inline dynamic_modint &operator+=(const dynamic_modint &a) {
    _val += a.val();
    if (_val >= MOD)
      _val -= MOD;
    return *this;
  }
  inline dynamic_modint &operator-=(const dynamic_modint &a) {
    _val -= a.val();
    if (_val < 0)
      _val += MOD;
    return *this;
  }
  inline dynamic_modint &operator*=(const dynamic_modint &a) {
    _val = _val * a.val() % MOD;
    return *this;
  }
  inline dynamic_modint &operator/=(const dynamic_modint &a) {
    *this *= modint_utils::inv(a.val(), MOD);
    return *this;
  }

  explicit operator int() const { return _val; }

  // io
  friend ostream &operator<<(ostream &os, const dynamic_modint &a) {
    return os << a._val;
  }
  friend istream &operator>>(istream &os, dynamic_modint &a) {
    os >> a._val;
    a._val = modint_utils::normalize(a._val, MOD);
    return os;
  }
};

// using modint998 = modint<998244353>;

template <int MOD>
ostream &operator<<(ostream &os, const dynamic_modint<MOD> &i) {
  os << i.val();
  return os;
}

template <int MOD>
ostream &operator<<(ostream &os, const vector<dynamic_modint<MOD>> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i].val() << (i + 1 != (int)v.size() ? " " : "");
  }
  return os;
}

template <const int32_t MOD> struct modint {
private:
  using i32 = int32_t;
  i32 _val;

public:
  consteval inline modint() noexcept : _val(0) {}
  constexpr inline modint(int val) noexcept
      : _val(modint_utils::normalize(val, MOD)) {}
  constexpr inline modint(modint const &val) noexcept : _val(val._val) {}

  // logic
  constexpr i32 val() const noexcept { return _val; }
  constexpr modint pow(const int n) const { return modint(powm(_val, n, MOD)); }
  constexpr inline static modint pow(const modint &a, const int n) noexcept {
    return modint(mod_pow(a._val, n, a.MOD));
  }
  constexpr inline modint inv() const noexcept {
    return modint(modint_utils::inv(_val, MOD));
  }

  // op
  constexpr inline modint &operator++() noexcept { return *this += 1; }
  constexpr inline modint &operator--() noexcept { return *this -= 1; }
  constexpr inline modint operator++(int32_t) noexcept {
    modint tmp = *this;
    ++*this;
    return tmp;
  }
  constexpr inline modint operator--(int32_t) noexcept {
    modint tmp = *this;
    --*this;
    return tmp;
  }
  constexpr inline modint operator+(const modint &a) const noexcept {
    return modint(*this) += a;
  }
  constexpr inline modint operator-(const modint &a) const noexcept {
    return modint(*this) -= a;
  }
  constexpr inline modint operator*(const modint &a) const noexcept {
    return modint(*this) *= a;
  }
  constexpr inline modint operator/(const modint &a) const noexcept {
    return modint(*this) /= a;
  }
  constexpr inline bool operator==(const modint &a) const noexcept {
    return _val == a.val();
  }
  constexpr inline bool operator!=(const modint &a) const noexcept {
    return _val != a.val();
  }
  constexpr inline modint &operator+=(const modint &a) noexcept {
    _val += a._val;
    if (_val >= MOD)
      _val -= MOD;
    return *this;
  }
  constexpr inline modint &operator-=(const modint &a) noexcept {
    _val -= a._val;
    if (_val < 0)
      _val += MOD;
    return *this;
  }
  constexpr inline modint &operator*=(const modint &a) noexcept {
    _val = (ll)_val * a._val % MOD;
    return *this;
  }
  constexpr inline modint &operator/=(const modint &a) noexcept {
    *this *= modint_utils::inv(a.val(), MOD);
    return *this;
  }

  explicit operator int() const noexcept { return _val; }

  // io
  friend ostream &operator<<(ostream &os, const modint &a) noexcept {
    return os << a._val;
  }
  friend istream &operator>>(istream &os, modint &a) noexcept {
    os >> a._val;
    a._val = modint_utils::normalize(a._val, MOD);
    return os;
  }
};
using mint998 = modint<998244353>;

#line 6 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/all.hpp"

#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/prime.hpp"





// ミラーラビン素数判定法
// O(k log^3 n)
// https://drken1215.hatenablog.com/entry/2023/05/23/233000
bool MillerRabin(long long N, vector<long long> A) {
  long long s = 0, d = N - 1;
  while (d % 2 == 0) {
    ++s;
    d >>= 1;
  }
  for (auto a : A) {
    if (N <= a)
      return true;
    long long t, x = powm(a, d, N);
    if (x != 1) {
      for (t = 0; t < s; ++t) {
        if (x == N - 1)
          break;
        x = __int128_t(x) * x % N;
      }
      if (t == s)
        return false;
    }
  }
  return true;
}

bool is_prime(long long N) {
  if (N <= 1)
    return false;
  if (N == 2)
    return true;
  if (N % 2 == 0)
    return false;
  if (N < 4759123141LL)
    return MillerRabin(N, {2, 7, 61});
  else
    return MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}

// ポラード・ロー素因数分解法
// 値が大きい場合に有効、ちゃんと調べる!
// O(n^(1/4))
// https://lpha-z.hatenablog.com/entry/2023/01/15/231500
// https://algo-method.com/tasks/553/editorial
uint64_t pollard_rho(uint64_t N) {
  if (N % 2 == 0)
    return 2;
  if (is_prime(N))
    return N;

  uint64_t step = 0;
  auto f = [&](uint64_t x) -> uint64_t {
    return (__int128_t(x) * x + step) % N;
  };
  while (true) {
    ++step;
    uint64_t x = step, y = f(x);
    while (true) {
      uint64_t p = gcd(y - x + N, N);
      if (p == 0 || p == N)
        break;
      if (p != 1)
        return p;
      x = f(x);
      y = f(f(y));
    }
  }
}

// 素因数分解
// https://algo-method.com/tasks/553/editorial
struct PrimeFactor {
  uint64_t prime;
  uint64_t exp;
};
vec<PrimeFactor> prime_factorize(uint64_t N) {
  if (N == 1)
    return {};
  uint64_t p = pollard_rho(N);
  if (p == N)
    return {{p, 1}};
  auto left = prime_factorize(p);
  auto right = prime_factorize(N / p);
  left.insert(left.end(), all(right));
  sort(all(left), [](const PrimeFactor &a, const PrimeFactor &b) {
    return a.prime < b.prime;
  });
  vec<PrimeFactor> ans;
  rep(i, left.size()) {
    if (i == 0 || left[i].prime != left[i - 1].prime)
      ans.emplace_back(left[i]);
    else
      ans.back().exp += left[i].exp;
  }
  return ans;
}

#line 8 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/rational.hpp"


template <typename T = ll> struct Rational {
  T num, den;
  Rational(T num) : num(num), den(1) {}
  Rational(T num, T den) : num(num), den(den) {
    T g = gcd(num, den);
    this->num /= g;
    this->den /= g;
  }
  Rational operator+(const Rational &rhs) const {
    return Rational(num * rhs.den + rhs.num * den, den * rhs.den);
  }
  Rational operator-(const Rational &rhs) const {
    return Rational(num * rhs.den - rhs.num * den, den * rhs.den);
  }
  Rational operator*(const Rational &rhs) const {
    return Rational(num * rhs.num, den * rhs.den);
  }
  Rational operator/(const Rational &rhs) const {
    return Rational(num * rhs.den, den * rhs.num);
  }

  bool operator<(const Rational &rhs) const {
    return num * rhs.den < rhs.num * den;
  }
  bool operator>(const Rational &rhs) const {
    return num * rhs.den > rhs.num * den;
  }
  bool operator==(const Rational &rhs) const {
    return num * rhs.den == rhs.num * den;
  }
  bool operator!=(const Rational &rhs) const { return !(*this == rhs); }
  bool operator<=(const Rational &rhs) const {
    return (*this < rhs) || (*this == rhs);
  }
  bool operator>=(const Rational &rhs) const {
    return (*this > rhs) || (*this == rhs);
  }
  friend ostream &operator<<(ostream &os, const Rational &r) {
    return os << r.num << "/" << r.den;
  }
  void operator+=(const Rational &rhs) { *this = *this + rhs; }
  void operator-=(const Rational &rhs) { *this = *this - rhs; }
  void operator*=(const Rational &rhs) { *this = *this * rhs; }
  void operator/=(const Rational &rhs) { *this = *this / rhs; }

  double val() const { return (double)num / den; }
  // operator double() const { return val(); }
  // operator string() const { return to_string(num) + "/" + to_string(den); }
  Rational pow(ll n) const {
    if (n == 0) {
      return Rational(1);
    } else if (n < 0) {
      return Rational(den, num).pow(-n);
    } else {
      Rational res = pow(n / 2);
      res *= res;
      if (n % 2 == 1) {
        res *= *this;
      }
      return res;
    }
  }
};

#line 9 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/all.hpp"

#line 9 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp"
// #include "string/all.hpp"
#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/util/all.hpp"


#line 1 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/util/inversion-num.hpp"





int inversion_num(const vec<int> &a) {
  comp<int> c(a);

  int n = a.size();
  FenwickTree<int> bit(n);
  int ans = 0;
  rep(i, n) {
    ans += i - bit.sum(c[i]);
    bit.add(c[i], 1);
  }
  return ans;
}

#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/util/all.hpp"

#line 11 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp"

#line 3 "/home/zoi/document/kyopro/under_greeen_3/main.cpp"

using mint = modint<998'244'353>;

void solve() {
  string s;
  cin >> s;
  deque<int> starts;
  int current_removes = 0;
  int removes = 0;
  rep(i, s.size()) {
    if(s[i] == '<') {
      starts.push_back(i);
    }
    else if(s[i] == '>') {
      bool ok = false;
      if(!starts.empty()){
        int from = starts.back();
        if(from + 1 < i) {
          removes += i - from + 1 - current_removes;
          current_removes += i - from + 1;
          // dump("remove", from, i);
          ok = true;
        }
      }
      if(!starts.empty()) {
        starts.pop_back();
      }
      if(!ok) {
        starts.clear();
        current_removes = 0;
      }
    }
  }
  // dump(s.size(), removes);
  cout << s.size() - removes << endl;
}

void test() {
}

signed main() {
  io_setup();
  init_cpp_dump();
  // input

  solve();
  // test();
}