#include<bits/stdc++.h>
#include<atcoder/all>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define rep(i,n) for(ll i = 0LL; i < (ll)n; ++i)
#define rep1(i,n) for(ll i = 1LL; i <= (ll)n; ++i)
#define rep2(i,m,n) for(ll i = (ll)m; i < (ll)n; ++i)
#define rrep(i,n) for(ll i = (ll)n - 1; i >= 0LL; --i)
#define rrep1(i,n) for(ll i = (ll)n; i > 0LL; --i)
#define rrep2(i,m,n) for(ll i = (ll)m; i > (ll)n; --i)
#define lb(a,x) static_cast<ll>(lower_bound(all(a), x) - a.begin())
#define ub(a,x) static_cast<ll>(upper_bound(all(a), x) - a.begin())
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define SORT(a) sort(all(a));
#define RSORT(a) sort(rall(a));
#define REV(a) reverse(all(a));
#define CEIL(x,y) (x + y - 1) / y
#define pb push_back
#define eb emplace_back
#define _GLIBCXX_DEBUG
#define _CRT_SECURE_NO_WARNINGS
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)

using namespace std;
using namespace atcoder;
using namespace chrono;

using ld = long double;
using ll = long long;
using ull = unsigned long long;

using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;

using vvi = vector<vi>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using vvb = vector<vb>;
using vvs = vector<vs>;


using pii = pair<int, int>;
using pll = pair<ll, ll>;

using si = set<int>;
using sl = set<ll>;

using mii = map<int, int>;
using mll = map<ll, ll>;

//in
void in(){}
template<class T>void in(vector<T> &v){
    for(T &t : v)cin >> t;
}
template<class T>void in(vector<vector<T>> &v){
    for(auto &row : v)for(T&element : row)cin >> element;
}
template<class Head, class... Tail>void in(Head &head, Tail &...tail){
    cin >> head; in(tail...);
}

//out
void out(){}
template<class T>void out(const T &t){
    cout << t << endl;
}
template<class T>void out(vector<T> &v){
    for(T &t : v)cout << t << ' ';
    cout << endl;
}
template<class T>void out(vector<vector<T>> &v){
    for(vector<T> &row : v){
        for(T &element : row){
            cout << element << ' ';
        }
        cout << endl;
    }
}
template<class Head, class...Tail>void out(const Head &head, const Tail &...tail){
    cout << head; out(tail...);
}

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

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

//min
template<typename T>T MIN(vector<T> &v){
    T mn = numeric_limits<T>::max();
    for(T &e : v){
        mn = min(mn, e);
    }
    return mn;
}

//max
template<typename T>T MAX(vector<T> &v){
    T mx = numeric_limits<T>::min();
    for(T &e : v){
        mx = max(mx, e);
    }
    return mx;
}

//sum
template<typename T>T SUM(vector<T> &v){
    T sum = 0;
    for(T &e : v){
        sum += e;
    }
    return sum;
}

//l_sort
template<typename T>void l_sort(vector<T> &l, vector<T> &r){
    assert(l.size() == r.size());
    long long n = l.size();
    vector<pair<T, T>> p;
    for(ll i = 0; i < n; i++){
        p.emplace_back(l[i], r[i]);
    }
    sort(p.begin(), p.end());
    for(ll i = 0; i < n; i++){
        l[i] = p[i].first;
        r[i] = p[i].second;
    }
}

//r_sort
template<typename T>void r_sort(vector<T> &l, vector<T> &r){
    assert(l.size() == r.size());
    long long n = l.size();
    vector<pair<T, T>> p;
    for(ll i = 0; i < n; i++){
        p.emplace_back(r[i], l[i]);
    }
    sort(p.begin(), p.end());
    for(ll i = 0; i < n; i++){
        l[i] = p[i].second;
        r[i] = p[i].first;
    }
}
//-----------------------array-----------------------//
//cumulative_sum
struct cumulative_sum{
    vector<long long> res;
    ll n;
    cumulative_sum(vector<long long> &a){
        n = a.size();
        res.resize(n + 1);
        res[0] = 0;
        for(ll i = 0; i < n; i++){
            res[i + 1] = a[i] + res[i];
        }
    }
    long long get(long long from, long long to){
        return res[to + 1] - res[from];
    }
};

//LCS
ll LCS(string s, string t){
    vector dp(s.size() + 1,vector<ll>(t.size() + 1));
    rep(i,s.size()){
        rep(j,t.size()){
            if(s[i] == t[j]){
                dp[i + 1][j + 1] = max({dp[i][j + 1], dp[i + 1][j], dp[i][j] + 1});
            }else{
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
    }
    return dp[s.size()][t.size()];
}

//LIS
template<typename T>ll LIS(vector<T> &a){
    vector<T> dp;
	for (T &e : a){
		auto it = lower_bound(dp.begin(), dp.end(), e);
		if (it == dp.end()){
			dp.push_back(e);
		}else{
			*it = e;
		}
	}
	return (ll)dp.size();
}

template< typename T > struct Compress {
    vector<T> xs;

    Compress() = default;

    Compress(const vector< T > &vs) {
        add(vs);
    }

    Compress(const initializer_list< vector< T > > &vs) {
        for(auto &p : vs) add(p);
    }

    void add(const vector< T > &vs) {
        copy(begin(vs), end(vs), back_inserter(xs));
    }

    void add(const T &x) {
        xs.emplace_back(x);
    }

    void build() {
        sort(begin(xs), end(xs));
        xs.erase(unique(begin(xs), end(xs)), end(xs));
    }

    vector< ll > get(const vector< T > &vs) const {
        vector<ll> ret;
        transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x) {
            return lower_bound(begin(xs), end(xs), x) - begin(xs);
        });
        return ret;
    }

    ll get(const T &x) const {
        return lower_bound(begin(xs), end(xs), x) - begin(xs);
    }

    const T &operator[](ll k) const {
        return xs[k];
    }
};

//編集距離
ll edit_distance(string &s, string &t){
    ll n = s.size(), m = t.size();
    vector dp(n + 1, vector<ll>(m + 1));
    for(ll i = 1; i <= n; i++)dp[i][0] = i;
    for(ll j = 1; j <= m; j++)dp[0][j] = j;
    for(ll i = 1; i <= n; i++)for(ll j = 1; j <= m; j++){
        dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (s[i - 1] == t[j - 1]? 0 : 1)});
    }
    return dp[n][m];
}

//エラトステネスの篩
vector<bool> sieve(ll N) {
    vector<bool> isprime(N+1, true);
    isprime[0] = false;
    isprime[1] = false;
    for (ll p = 2; p <= N; ++p){
        if (!isprime[p]) continue;
        for (ll q = p * 2; q <= N; q += p){
            isprime[q] = false;
        }
    }
    return isprime;
}
//--------------------data_structure-----------------//
//suffix_array
struct suffix_array{
    vector<ll> sa, rank, tmp;
    ll n;
    string base;

    //suffix_arrayを構築
    suffix_array(const string s){
        n = s.size();
        base = s;
        sa.resize(n);
        rank.resize(n);
        tmp.resize(n);

        for(ll i = 0; i < n; i++){
            sa[i] = i;
            rank[i] = s[i];
        }

        for(ll k = 1; k < n; k *= 2){
            auto compare_sa = [&](ll i, ll j){
                if(rank[i] != rank[j])return rank[i] < rank[j];
                ll ri = (i + k < n) ? rank[i + k] : -1;
                ll rj = (j + k < n) ? rank[j + k] : -1;
                return ri < rj;
            };
            sort(sa.begin(), sa.end(), compare_sa);

            tmp[sa[0]] = 0;
            for(ll i = 1; i < n; i++){
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i])? 1 : 0);
            }
            rank = tmp;
        }
    }

    //部分文字列の個数を求める
    ll counts(string t){
        string u = t + "彁";
        ll num1, num2;
        {
            ll m = t.size();
            ll ng = -1, ok = n;
            while(ok - ng > 1){
                ll mid = (ng + ok) / 2;
                ll l = sa[mid];
                if(base.substr(l, m) >= t){
                    ok = mid;
                }else{
                    ng = mid;
                }
            }
            num1 = ok;
        }
        {
            ll m = u.size();
            ll ng = -1, ok = n;
            while(ok - ng > 1){
                ll mid = (ng + ok) / 2;
                ll l = sa[mid];
                if(base.substr(l, m) >= u){
                    ok = mid;
                }else{
                    ng = mid;
                }
            }
            num2 = ok;
        }
        return num2 - num1;
    }
};
//-----------------------check-----------------------//
//is_prime
template<typename T> bool is_prime(T n){
    if(n <= 1)return false;
    T m = sqrt(n);
    for(ll i = 2; i <= m; ++i){
        if(n % i == 0)return false;
    }
    return true;
}

//is_square
template<typename T> bool is_square(T n){
    if(n < 0)return false;
    T m = sqrt(n);
    if(n == m * m){
        return true;
    }else{
        return false;
    }
}

//is_substring
bool is_substring(const string& s, const string& t){
    const ll n = s.size(), m = t.size();
    for(ll i = 0; i + m <= n; ++i){
        if(s.substr(i, m) == t)return true;
    }
    return false;
}
//-----------------------math------------------------//
//gcd(faster)
ll GCD(ll A, ll B){
    if(B == 0){
        return A;
    }else{
        return GCD(B, A % B);
    }
}

//lcm(faster)
ll LCM(ll A, ll B){
    return A / GCD(A, B) * B;
}

//comb
ll comb(ll n, ll r){
    assert(n >= 2);
    vector dp(n + 1, vector<ll>(r + 1));
    for(ll i = 0; i < n + 1; ++i){
        dp[i][0] = 1;
    }
    for(ll i = 0; i < r + 1; ++i){
        dp[i][i] = 1;
    }
    for(ll i = 1; i < n + 1; ++i){
        for(ll j = 1; j < min(i, r + 1); ++j){
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }
    return dp[n][r];
}

// comb_mod
using mint_comb = atcoder::static_modint<1000000007>;

vector<mint_comb> fac, finv, inv;

// テーブルを作る前処理
void init_comb_mod(ll size) {
    size += 109;
    fac.resize(size);
    finv.resize(size);
    inv.resize(size);
    const ll MOD = mint_comb::mod();
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < size; i++){
        fac[i] = fac[i - 1] * i;
        inv[i] = MOD - inv[MOD%i] * (MOD / i);
        finv[i] = finv[i - 1] * inv[i];
    }
}

// 二項係数計算
mint_comb comb_mod(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * finv[k] * finv[n - k];
}

//make_random
//long long
ll rand_ll(ll l, ll r){
    if(l > r)swap(l, r);
    random_device rd;
    mt19937_64 gen(rd());
    uniform_int_distribution<ll>dis(l, r);
    return dis(gen);
}

//int
int rand_int(int l, int r){
    if(l > r)swap(l, r);
    return l + rand() % (r - l + 1);
}

//double
ld rand_double(){
    return (ld)1.0 * rand() / RAND_MAX;
}

//base_conversion
ll ntodec(const char c){
    if(c >= '0' && c <= '9'){
        return (ll)c - '0';
    }else{
        return (ll)c - 55;
    }
}
char decton(const ll n){
    if(n >= 0 && n <= 9){
        return (char)'0' + n;
    }else{
        return (char)55 + n;
    }
}
inline ll pow_ll(ll x,ll n){
    ll ret = 1;
    rep(i,n){
        ret *= x;
    }
    return ret;
}
string base_conversion(string str, ll n, ll m){
    ull tmp = 0;
    string ret;
    rep(i,str.size()){
        tmp += (ull)ntodec(str[str.size() - 1 - i]) * pow_ll(n, i);
    }
    if(tmp == 0){
        return "0";
    }
    while(tmp != 0){
        ret = decton(tmp % m) + ret;
        tmp /= m;
    }
    return ret;
}

//calc_triangle
long double calc_triangle(long double x1,long double y1,long double x2,long double y2,long double x3,long double y3){
    return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0);
}

//文字列の最小周期
vector<ll> computeLPSArray(const string& pattern){
    ll m = pattern.length();
    vector<ll> lps(m);
    ll len = 0;
    lps[0] = 0;
    ll i = 1;
    while (i < m){
        if(pattern[i] == pattern[len]){
            len++;
            lps[i] = len;
            i++;
        }else{
            if(len != 0){
                len = lps[len - 1];
            }else{
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}
ll findMinimumPeriod(const string& str){
    ll n = str.length();
    vector<ll> lps = computeLPSArray(str);
    ll len = lps[n - 1];
    ll period = n - len;
    if (n % period == 0) {
        return period;
    } else {
        return n;
    }
}

//rolling hash
const ull rh_mod = 0x1fffffffffffffff, rh_base = chrono::duration_cast<chrono::microseconds>(chrono::system_clock::now().time_since_epoch()).count() % rh_mod;
struct RollingHash {
    vector<ull> hashed, power;
    
    static constexpr ull mask(ll a){ return (1ULL << a) - 1; }
    
    inline ull mul(ull a, ull b) const {
        //*
        __uint128_t ans = __uint128_t(a) * b;
        /*/
         // without __uint128_t
         ull a31 = a >> 31, b31 = b >> 31;
         a &= mask(31);
         b &= mask(31);
         ull x = a * b31 + b * a31;
         ull ans = (a31 * b31 << 1) + (x >> 30) + ((x & mask(30)) << 31) + a * b;
         //*/
        ans = (ans >> 61) + (ans & rh_mod);
        if(ans >= rh_mod) ans -= rh_mod;
        return ans;
    }
    
    
    RollingHash(const string &s) {
        ll n = s.size();
        hashed.assign(n + 1, 0);
        power.assign(n + 1, 0);
        power[0] = 1;
        for(ll i = 0; i < n; i++) {
            power[i + 1] = mul(power[i], rh_base);
            hashed[i + 1] = mul(hashed[i], rh_base) + s[i];
            if(hashed[i + 1] >= rh_mod) hashed[i + 1] -= rh_mod;
        }
    }
    
    ull get(ll l, ll r) const {
        ull ret = hashed[r] + rh_mod - mul(hashed[l], power[r - l]);
        if(ret >= rh_mod) ret -= rh_mod;
        return ret;
    }
    
    ull connect(ull h1, ull h2, ll h2len) const {
        ull ret = mul(h1, power[h2len]) + h2;
        if(ret >= rh_mod) ret -= rh_mod;
        return ret;
    }
    
    void connect(const string &s){
        ll n = hashed.size() - 1, m = s.size();
        hashed.resize(n + m + 1);
        power.resize(n + m + 1);
        for(ll i = n; i < n + m; i++) {
            power[i + 1] = mul(power[i], rh_base);
            hashed[i + 1] = mul(hashed[i], rh_base) + s[i - n];
            if(hashed[i + 1] >= rh_mod) hashed[i + 1] -= rh_mod;
        }
    }
    
    ll LCP(const RollingHash &b, ll l1, ll r1, ll l2, ll r2) {
        ll len = min(r1 - l1, r2 - l2);
        ll low = -1, high = len + 1;
        while(high - low > 1) {
            ll mid = (low + high) / 2;
            if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
            else high = mid;
        }
        return low;
    }
};
//-----------------------graph-----------------------//
//graph_template
struct Edge{
    ll to;
    ll cost;
    Edge(ll to, ll cost) : to(to), cost(cost) {}
    bool operator>(const Edge &e) const{
        return cost > e.cost;
    }
    bool operator<(const Edge &e) const{
        return cost < e.cost;
    }
};

struct Edge2{
    ll from;
    ll to;
    ll cost;
    Edge2(ll from, ll to, ll cost) : from(from), to(to), cost(cost) {}
    bool operator>(const Edge2 &e) const{
        return cost > e.cost;
    }
    bool operator<(const Edge2 &e) const{
        return cost < e.cost;
    }
};

struct Edge3 {
    ll to;
    Edge3(ll to) : to(to) {}
};

struct Graph{
    Graph() = default;
    vector<vector<Edge>> G;

    Graph(ll n){
        G.resize(n);
    }

    ll size(){
        return G.size();
    }

    void add(ll from, ll to, ll cost = 1){
        G[from].push_back(Edge(to, cost));
        G[to].push_back(Edge(from, cost));
    }

    void add_di(ll from, ll to, ll cost = 1){
        G[from].push_back(Edge(to, cost));
    }

    vector<Edge> operator[](ll v){
        return G[v];
    }
};

//bfs1(単一始点最短経路)
struct bfs1{
    vector<bool> visited;
    vector<ll> dist;
    vector<ll> parent;

    //bfs1(単一始点最短経路)を構築
    bfs1(Graph &g, ll s){
        ll n = g.size();
        visited.assign(n, false);
        dist.assign(n, -1);
        parent.assign(n, -1);
        visited[s] = true;
        dist[s] = 0;
        parent[s] = -1;
        queue<ll> que;
        que.push(s);
        while(!que.empty()){
            ll cur = que.front();
            que.pop();
            for(auto nxt : g[cur]){
                if(!visited[nxt.to]){
                    que.push(nxt.to);
                    visited[nxt.to] = true;
                    dist[nxt.to] = dist[cur] + 1;
                    parent[nxt.to] = cur;
                }
            }
        }
    }

    //最小コストを求める
    ll cost(ll to){
        return dist[to];
    }

    //最短経路を求める
    vector<ll> path(ll to){
        vector<ll> path;
        if(!visited[to]){
            return path;
        }
        for(ll i = to; i != -1; i = parent[i]){
            path.push_back(i);
        }
        reverse(path.begin(), path.end());
        return path;
    }

    //到達可能か調べる
    bool cango(ll to){
        return visited[to];
    }
};

//bfs2(全点対最短経路)
struct bfs2{
    vector<vector<bool>> visited;
    vector<vector<ll>> dist;
    vector<vector<ll>> parent;
    bfs2(Graph &g){
        ll n = g.size();
        visited.assign(n, vector<bool>(n, false));
        dist.assign(n, vector<ll>(n, -1));
        parent.assign(n, vector<ll>(n, -1));
        for(ll s = 0; s < n; s++){
            visited[s][s] = true;
            dist[s][s] = 0;
            parent[0][0] = -1;
            queue<ll> que;
            que.push(s);
            while(!que.empty()){
                ll cur = que.front();
                que.pop();
                for(auto nxt : g[cur]){
                    if(!visited[s][nxt.to]){
                        que.push(nxt.to);
                        visited[s][nxt.to] = true;
                        dist[s][nxt.to] = dist[s][cur] + 1;
                        parent[s][nxt.to] = cur;
                    }
                }
            }
        }
    }

    //最小コストを求める
    ll cost(ll from, ll to){
        return dist[from][to];
    }

    //最短経路を求める
    vector<ll> path(ll from, ll to){
        vector<ll> path;
        if(!visited[from][to]){
            return path;
        }
        for(ll i = to; i != -1; i = parent[from][i]){
            path.push_back(i);
        }
        reverse(path.begin(), path.end());
        return path;
    }

    //到達可能か調べる
    bool cango(ll from, ll to){
        return visited[from][to];
    }
};

//dijkstra
struct dijkstra{
    vector<ll> dist;
    vector<ll> prev;

    //dijkstraを構築
    dijkstra(Graph &G, ll s){
        ll N = G.size();
        dist.assign(N, 1LL << 60);
        prev.assign(N, -1);
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
        dist[s] = 0;
        pq.emplace(dist[s], s);
        while (!pq.empty()){
            auto p = pq.top();
            pq.pop();
            ll v = p.second;
            if(dist[v] < p.first)continue;
            for (auto &e : G[v]){
                if (dist[e.to] > dist[v] + e.cost){
                    dist[e.to] = dist[v] + e.cost;
                    prev[e.to] = v;
                    pq.emplace(dist[e.to], e.to);
                }
            }
        }
    }

    //最小コストを求める
    ll cost(ll to){
        return dist[to];
    }

    //最短経路を求める
    vector<ll> path(ll to){
        vector<ll> get_path;
        for (ll i = to; i != -1; i = prev[i]){
            get_path.push_back(i);
        }
        reverse(get_path.begin(), get_path.end());
        return get_path;
    }

    //到達可能か調べる
    bool cango(ll to){
        return dist[to] != 1LL << 60;
    }
};

//bellman_ford
struct bellman_ford{
    vector<ll> dist;
    vector<ll> prev;
    ll start;
    ll n;
    bool cl = false;

    //bellman_fordを構築
    bellman_ford(Graph &g, ll s){
        start = s;
        n = g.size();
        dist.assign(n, 1LL << 60);
        prev.assign(n, -1);
        vector<ll> counts(n);
        vector<bool> inqueue(n);

        queue<ll> q;
        dist[s] = 0;
        q.push(s);
        inqueue[s] = true;

        while(!q.empty()){
            ll from = q.front();
            q.pop();
            inqueue[from] = false;

            for(auto &e : g[from]){
                ll d = dist[from] + e.cost;
                if(d < dist[e.to]){
                    dist[e.to] = d;
                    prev[e.to] = from;
                    if(!inqueue[e.to]){
                        q.push(e.to);
                        inqueue[e.to] = true;
                        ++counts[e.to];

                        if(n < counts[e.to])cl = true;
                    }
                }
            }
        }
    }

    //最小コストを求める
    ll cost(ll to){
        return dist[to];
    }

    //最短経路を求める
    vector<ll> path(ll to){
        vector<ll> path;
        if(dist[to] != 1LL << 60){
            for(ll i = to; i != -1; i = prev[i]){
                path.push_back(i);
            }
            reverse(path.begin(), path.end());
        }
        return path;
    }

    //到達可能か調べる
    bool cango(ll to){
        return (dist[to] != 1LL << 60);
    }

    //負の閉路の有無を調べる
    bool closed(){
        return cl;
    }
};

//warshall_floyd
struct warshall_floyd{
    vector<vector<ll>> d;
    vector<vector<ll>> next;
    bool cl = false;

    //warshall_floydを構築
    warshall_floyd(Graph &g){
        ll n = g.size();
        d.resize(n, vector<ll>(n, 1LL << 60));
        next.resize(n, vector<ll>(n, -1));

        for(ll i = 0; i < n; i++){
            d[i][i] = 0;
        }

        for(ll i = 0; i < n; i++){
            for(auto e : g[i]){
                d[i][e.to] = e.cost;
                next[i][e.to] = e.to;
            }
        }

        for(ll k = 0; k < n; ++k){
            for(ll i = 0; i < n; ++i){
                for(ll j = 0; j < n; ++j){
                    if(d[i][k] == 1LL << 60 || d[k][j] == 1LL << 60)continue;
                    if(d[i][j] > d[i][k] + d[k][j]){
                        d[i][j] = d[i][k] + d[k][j];
                        next[i][j] = next[i][k];
                    }
                }
            }
        }

        for(ll i = 0; i < n; i++){
            if(d[i][i] < 0){
                cl = true;
                break;
            }
        }
    }

    //最小コストを求める
    ll cost(ll from, ll to){
        return d[from][to];
    }

    //最短経路を求める
    vector<ll> path(ll from, ll to) {
        if (d[from][to] == 1LL << 60) return {};
        vector<ll> path;
        for(ll at = from; at != to; at = next[at][to]){
            if (at == -1) return {};
            path.push_back(at);
        }
        path.push_back(to);
        return path;
    }

    //到達可能か調べる
    bool cango(ll from, ll to){
        return d[from][to] != 1LL << 60;
    }

    //負の閉路の有無を調べる
    bool closed(){
        return cl;
    }
};

//DSU
struct DSU{
    vector<ll>par, rank, siz;
    DSU(ll n):par(n, -1), rank(n, 0), siz(n, 1){}

    //根を求める
    ll leader(ll x){
        if(par[x] == -1){
            return x;
        }else{
            return par[x] = leader(par[x]);
        }
    }

    //連結判定
    bool same(ll x, ll y){
        return leader(x) == leader(y);
    }

    //連結
    bool merge(ll x, ll y){
        ll rx = leader(x), ry = leader(y);
        if(rx == ry){
            return false;
        }
        if(rank[rx] < rank[ry]){
            swap(rx, ry);
        }
        par[ry] = rx;
        if(rank[rx] == rank[ry]){
            rank[rx]++;
        }
        siz[rx] += siz[ry];
        return true;
    }

    //集合の大きさを求める
    ll size(ll x){
        return siz[leader(x)];
    }
};

template<class Abel>struct Weighted_UnionFind{
    vector<ll> par;
    vector<ll> rank;
    vector<Abel> diff_weight;

    Weighted_UnionFind(ll n = 1, Abel SUM_UNITY = 0){
        init(n, SUM_UNITY);
    }

    void init(ll n = 1, Abel SUM_UNITY = 0){
        par.resize(n);
        rank.resize(n);
        diff_weight.resize(n);
        for(ll i = 0; i < n; ++i)par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
    }

    ll root(ll x){
        if(par[x] == x){
            return x;
        }else{
            ll r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }

    Abel weight(ll x){
        root(x);
        return diff_weight[x];
    }

    bool issame(ll x, ll y){
        return root(x) == root(y);
    }

    //x + w = y
    bool unite(ll x, ll y, Abel w){
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if(x==y)return false;
        if(rank[x] < rank[y])swap(x, y), w = -w;
        if(rank[x]==rank[y])++rank[x];
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }

    Abel diff(ll x, ll y){
        return weight(y) - weight(x);
    }
};

struct kruskal{
    ll n;
    vector<Edge2> edges;
    bool mn_finish = false, mx_finish = false;
    ll mn, mx;
    set<ll> mn_node, mx_node;
    set<ll> mn_path, mx_path;
    //kruskalの構築
    kruskal(Graph &g){
        n = g.size();
        for(ll i = 0; i < n; i++){
            for(auto e : g[i]){
                edges.emplace_back(i, e.to, e.cost);
            }
        }
    }

    //最小全域木のコストを求める
    ll min_cost(){
        if(mn_finish){
            return mn;
        }
        sort(edges.begin(), edges.end());
        DSU dsu(n);
        ll ret = 0;
        for(auto e : edges){
            if(dsu.merge(e.from, e.to)){
                ret += e.cost;
                mn_node.insert(e.from);
                mn_node.insert(e.to);
            }
        }
        return mn = ret;
    }

    //最大全域木のコストを求める
    ll max_cost(){
        if(mx_finish){
            return mx;
        }
        sort(edges.rbegin(), edges.rend());
        DSU dsu(n);
        ll ret = 0;
        for(auto e : edges){
            if(dsu.merge(e.from, e.to)){
                ret += e.cost;
                mx_node.insert(e.from);
                mx_node.insert(e.to);
            }
        }
        return mx = ret;
    }

    //最小全域木のノードをsetで求める
    set<ll> min_node(){
        if(mn_finish){
            return mn_node;
        }
        sort(edges.begin(), edges.end());
        DSU dsu(n);
        ll ret = 0;
        for(auto e : edges){
            if(dsu.merge(e.from, e.to)){
                ret += e.cost;
                mn_node.insert(e.from);
                mn_node.insert(e.to);
            }
        }
        return mn_node;
    }

    //最大全域木のノードをsetで求める
    set<ll> max_node(){
        if(mx_finish){
            return mx_node;
        }
        sort(edges.rbegin(), edges.rend());
        DSU dsu(n);
        ll ret = 0;
        for(auto e : edges){
            if(dsu.merge(e.from, e.to)){
                ret += e.cost;
                mx_node.insert(e.from);
                mx_node.insert(e.to);
            }
        }
        return mx_node;
    }
};

//LCA
struct LCA {
    vector<vector<ll>> parent;
    vector<ll> dist;

    LCA(Graph &g, ll root = 0){
        vector<vector<Edge3>> G(g.size());
        for(ll i = 0; i < g.size(); i++){
            for(auto e : g[i]){
                G[i].emplace_back(e.to);
            }
        }
        ll V = G.size();
        ll K = 1;
        while ((1 << K) < V) K++;
        parent.assign(K, vector<ll>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (ll k = 0; k + 1 < K; k++) {
            for (ll v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                } else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    void dfs(const vector<vector<Edge3>> &G, ll v, ll p, ll d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e.to != p) dfs(G, e.to, v, d + 1);
        }
    }

    //最小共通祖先を求める
    ll query(ll u, ll v) {
        if (dist[u] < dist[v]) swap(u, v);
        ll K = parent.size();
        for (ll k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        if (u == v) return u;
        for (ll k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }

    //最短距離を求める
    ll get_dist(ll u, ll v){
        return dist[u] + dist[v] - 2 * dist[query(u, v)];
    }

    //aがuとvのpath上にあるか
    bool is_on_path(ll u, ll v, ll a){
        return get_dist(u, a) + get_dist(a, v) == get_dist(u, v);
    }
};

//動的セグ木
template <class S, S (*op)(S, S), S (*e)()> class dynamic_segtree {
public:
    dynamic_segtree(size_t n) : n(n), root(nullptr) {}

    void set(size_t p, S x) {
        assert(p < n);
        set(root, 0, n, p, x);
    }

    S get(size_t p) const {
        assert(p < n);
        return get(root, 0, n, p);
    }

    S prod(size_t l, size_t r) const {
        assert(l <= r && r <= n);
        return prod(root, 0, n, l, r);
    }

    S all_prod() const { return root ? root->product : e(); }

    void reset(size_t l, size_t r) {
        assert(l <= r && r <= n);
        return reset(root, 0, n, l, r);
    }

    template <bool (*f)(S)> size_t max_right(size_t l) const {
        return max_right(l, [](S x) { return f(x); });
    }

    template <class F> size_t max_right(size_t l, const F& f) const {
        assert(l <= n);
        S product = e();
        assert(f(product));
        return max_right(root, 0, n, l, f, product);
    }

    template <bool (*f)(S)> size_t min_left(size_t r) const {
        return min_left(r, [](S x) { return f(x); });
    }

    template <class F> size_t min_left(size_t r, const F& f) const {
        assert(r <= n);
        S product = e();
        assert(f(product));
        return min_left(root, 0, n, r, f, product);
    }

private:
    struct node;
    using node_ptr = std::unique_ptr<node>;

    struct node {
        size_t index;
        S value, product;
        node_ptr left, right;

        node(size_t index, S value)
            : index(index),
              value(value),
              product(value),
              left(nullptr),
              right(nullptr) {}

        void update() {
            product = op(op(left ? left->product : e(), value),
                         right ? right->product : e());
        }
    };

    const size_t n;
    node_ptr root;

    void set(node_ptr& t, size_t a, size_t b, size_t p, S x) const {
        if (!t) {
            t = std::make_unique<node>(p, x);
            return;
        }
        if (t->index == p) {
            t->value = x;
            t->update();
            return;
        }
        size_t c = (a + b) >> 1;
        if (p < c) {
            if (t->index < p) std::swap(t->index, p), std::swap(t->value, x);
            set(t->left, a, c, p, x);
        } else {
            if (p < t->index) std::swap(p, t->index), std::swap(x, t->value);
            set(t->right, c, b, p, x);
        }
        t->update();
    }

    S get(const node_ptr& t, size_t a, size_t b, size_t p) const {
        if (!t) return e();
        if (t->index == p) return t->value;
        size_t c = (a + b) >> 1;
        if (p < c) return get(t->left, a, c, p);
        else return get(t->right, c, b, p);
    }

    S prod(const node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {
        if (!t || b <= l || r <= a) return e();
        if (l <= a && b <= r) return t->product;
        size_t c = (a + b) >> 1;
        S result = prod(t->left, a, c, l, r);
        if (l <= t->index && t->index < r) result = op(result, t->value);
        return op(result, prod(t->right, c, b, l, r));
    }

    void reset(node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {
        if (!t || b <= l || r <= a) return;
        if (l <= a && b <= r) {
            t.reset();
            return;
        }
        size_t c = (a + b) >> 1;
        reset(t->left, a, c, l, r);
        reset(t->right, c, b, l, r);
        t->update();
    }

    template <class F>
    size_t max_right(const node_ptr& t, size_t a, size_t b,
                     size_t l, const F& f, S& product) const {
        if (!t || b <= l) return n;
        if (f(op(product, t->product))) {
            product = op(product, t->product);
            return n;
        }
        size_t c = (a + b) >> 1;
        size_t result = max_right(t->left, a, c, l, f, product);
        if (result != n) return result;
        if (l <= t->index) {
            product = op(product, t->value);
            if (!f(product)) return t->index;
        }
        return max_right(t->right, c, b, l, f, product);
    }

    template <class F>
    size_t min_left(const node_ptr& t, size_t a, size_t b,
                    size_t r, const F& f, S& product) const {
        if (!t || r <= a) return 0;
        if (f(op(t->product, product))) {
            product = op(t->product, product);
            return 0;
        }
        size_t c = (a + b) >> 1;
        size_t result = min_left(t->right, c, b, r, f, product);
        if (result != 0) return result;
        if (t->index < r) {
            product = op(t->value, product);
            if (!f(product)) return t->index + 1;
        }
        return min_left(t->left, a, c, r, f, product);
    }
};

//centroid_decomposition
//Graph構造体は使わず、二次元配列（隣接行列ではない）を渡す
template <typename G>
class CentroidDecomposition {
    const G &g;
    
    vector<vector<long long>> to;
    vector<bool> used;
    vector<long long> size;
    long long first;
    
    void dfs(long long v, long long p) {
        size[v] = 1;
        for (long long u : g[v]) {
            if (u == p || used[u]) {
                continue;
            }
            dfs(u, v);
            size[v] += size[u];
        }
    }
    
    long long find_centroid(long long v) {
        dfs(v, v);
        long long sz = size[v];
        long long p = v;
        while (true) {
            bool ok = true;
            for (long long u : g[v]) {
                if (u == p || used[u]) {
                    continue;
                }
                if (size[u] > sz / 2) {
                    p = v;
                    v = u;
                    ok = false;
                    break;
                }
            }
            if (ok) {
                break;
            }
        }
        return v;
    }
    
    long long decomposite(long long v) {
        long long cent = find_centroid(v);
        used[cent] = true;
        for (long long u : g[cent]) {
            if (used[u]) {
                continue;
            }
            to[cent].push_back(decomposite(u));
        }
        return cent;
    }
    
public:
    CentroidDecomposition(const G &_g) :
    g(_g),
    to((long long) g.size()),
    used((long long) g.size(), false),
    size((long long) g.size(), 0) {
        first = decomposite(0);
    }
    
    long long first_centroid() const {
        return first;
    }
    
    const vector<long long> &next_centroids(long long v) const {
        assert(v >= 0 && v < (long long) g.size());
        return to[v];
    }
};
//----------------------normal-----------------------//
const ld PI = 3.1415926535897932;

const ll mod = 998244353;
const ll MOD = 1000000007;

const ll LINF = 1001001001001001001;
const ll INF = 1001001001;

const ll dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
const ll dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

const string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alpha = "abcdefghijklmnopqrstuvwxyz";

//using mint = atcoder::modint;
//using mint = atcoder::static_modint<1000000021>;
using mint = atcoder::modint998244353;
//using mint = atcoder::modint1000000007;

/*-----------------------function------------------------*/
/*------------------------solve--------------------------*/
void solve(){
    string s; cin >> s;
    stack<pair<char, ll>> st;
    ll n = s.size();
    ll ans = n;
    rep(i,n){
        if(s[i] == '<'){
            st.push({'<', i});
        }else if(s[i] == '>'){
            if(st.empty()){
                st.push({'>', i});
            }else{
                auto[c, idx] = st.top();
                if(c == '<' && idx != i - 1){
                    st.pop();
                    ans -= (i - idx + 1 - (n - ans));
                }else{
                    st.push({'>', i});
                }
            }
        }
    }
    cout << ans << endl;
}
int main(){
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    srand((unsigned)time(NULL));
    //ll T; cin >> T;
    ll T = 1;
    while(T--){
        solve();
    }
    return 0;
}