結果

問題 No.927 Second Permutation
ユーザー ituse10ituse10
提出日時 2020-03-08 16:01:19
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 24,137 bytes
コンパイル時間 2,267 ms
コンパイル使用メモリ 148,164 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-07 07:43:27
合計ジャッジ時間 3,446 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 3 ms
5,248 KB
testcase_25 AC 3 ms
5,248 KB
testcase_26 AC 3 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 3 ms
5,248 KB
testcase_29 AC 3 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'll bfs(ll, ll, std::vector<std::vector<std::pair<long long int, long long int> > >)':
main.cpp:691:1: warning: no return statement in function returning non-void [-Wreturn-type]
  691 | }
      | ^

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <numeric>
#include <functional>
#include <cmath>
#include <cassert>
#include <string>
#include <iostream>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, ll> PL;
const ll mod = 1000000007;
const ll MOD = 1000000007;
const ll INF = 1LL << 60;
#define PI (acos(-1))
#define ALL(c) (c).begin(), (c).end()

template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
    for (auto &v : vec)
        is >> v;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
    os << "[";
    for (auto v : vec)
        os << v << ",";
    os << "]";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &vec)
{
    os << "deq[";
    for (auto v : vec)
        os << v << ",";
    os << "]";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &vec)
{
    os << "{";
    for (auto v : vec)
        os << v << ",";
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &vec)
{
    os << "{";
    for (auto v : vec)
        os << v << ",";
    os << "}";
    return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{
    os << "(" << pa.first << "," << pa.second << ")";
    return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const map<TK, TV> &mp)
{
    os << "{";
    for (auto v : mp)
        os << v.first << "=>" << v.second << ",";
    os << "}";
    return os;
}

#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
// template <typename A, size_t N, typename T>

template <typename T>
inline string toString(const T &a)
{
    ostringstream oss;
    oss << a;
    return oss.str();
};

template <int mod>
struct ModInt
{
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p)
    {
        if ((x += p.x) >= mod)
            x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &p)
    {
        if ((x += mod - p.x) >= mod)
            x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p)
    {
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p)
    {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const
    {
        int a = x, b = mod, u = 1, v = 0, t;
        while (b > 0)
        {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const
    {
        ModInt ret(1), mul(x);
        while (n > 0)
        {
            if (n & 1)
                ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p)
    {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a)
    {
        int64_t t;
        is >> t;
        a = ModInt<mod>(t);
        return (is);
    }

    static int get_mod() { return mod; }
};

using modint = ModInt<mod>;

template <typename T>
struct Combination
{
    vector<T> _fact, _rfact, _inv;

    Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1)
    {
        _fact[0] = _rfact[sz] = _inv[0] = 1;
        for (int i = 1; i <= sz; i++)
            _fact[i] = _fact[i - 1] * i;
        _rfact[sz] /= _fact[sz];
        for (int i = sz - 1; i >= 0; i--)
            _rfact[i] = _rfact[i + 1] * (i + 1);
        for (int i = 1; i <= sz; i++)
            _inv[i] = _rfact[i] * _fact[i - 1];
    }

    inline T fact(int k) const { return _fact[k]; }

    inline T rfact(int k) const { return _rfact[k]; }

    inline T inv(int k) const { return _inv[k]; }

    T P(int n, int r) const
    {
        if (r < 0 || n < r)
            return 0;
        return fact(n) * rfact(n - r);
    }

    T C(int p, int q) const
    {
        if (q < 0 || p < q)
            return 0;
        return fact(p) * rfact(q) * rfact(p - q);
    }

    T H(int n, int r) const
    {
        if (n < 0 || r < 0)
            return (0);
        return r == 0 ? 1 : C(n + r - 1, r);
    }

    T NC(int p, int q) const
    {
        modint ret = 1;
        for (int i = 1; i <= q; i += 1)
        {
            ret = ret * p / i;
            p--;
        }
        return ret;
    }
};

ll lcm(ll a, ll b)
{
    return a / __gcd(a, b) * b;
}

bool is_prime(ll x)
{
    if (x == 1)
    {
        return false;
    }
    for (ll i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}

map<int64_t, int> prime_factor(int64_t n)
{
    map<int64_t, int> ret;
    for (int64_t i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

vector<ll> divisor(ll n)
{
    vector<ll> ret;
    for (ll i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ret.push_back(i);
            if (i * i != n)
                ret.push_back(n / i);
        }
    }
    sort(begin(ret), end(ret));
    return (ret);
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod)
{
    return modpow(a, mod - 2, mod);
}

const ll MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];

void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll COM(ll n, ll k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

struct UnionFind
{
    vector<int> par;

    UnionFind(int n) : par(n, -1) {}
    void init(int n) { par.assign(n, -1); }

    int root(int x)
    {
        if (par[x] < 0)
            return x;
        else
            return par[x] = root(par[x]);
    }

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

    bool merge(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (par[x] > par[y])
            swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

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

struct BIT
{
    //1-indexed!!!
    int n;
    vector<int> bit;
    BIT()
    {
        init();
    }
    BIT(int n) : n(n)
    {
        init();
    }
    void init()
    {
        bit.clear();
        bit.resize(n + 1, 0);
    }
    int sum(int i)
    {
        int s = 0;
        while (i > 0)
        {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    int sum(int x, int y)
    {
        return sum(y) - sum(x - 1);
    }
    void add(int i, int x)
    {
        while (i <= n)
        {
            bit[i] += x;
            i += i & -i;
        }
    }
    int lower_bound(int w)
    {
        if (w <= 0)
            return 0;
        int x = 0, r = 1;
        while (r < n)
            r <<= 1;
        for (int k = r; k > 0; k >>= 1)
        {
            if (x + k <= n && bit[x + k] < w)
            {
                w -= bit[x + k];
                x += k;
            }
        }
        return x + 1;
    }
};

struct LazySegmentTree
{
    // private:
    ll n;
    vector<ll> node, lazy;

    // public:
    LazySegmentTree(vector<ll> v)
    {
        int sz = (int)v.size();
        n = 1;
        while (n < sz)
            n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);

        for (int i = 0; i < sz; i++)
            node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--)
            node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }

    void eval(int k, int l, int r)
    {
        if (lazy[k] != 0)
        {
            node[k] += lazy[k];
            if (r - l > 1)
            {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, ll x, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        eval(k, l, r);
        if (b <= l || r <= a)
            return;
        if (a <= l && r <= b)
        {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else
        {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }

    ll getsum(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        eval(k, l, r);
        if (b <= l || r <= a)
            return 0;
        if (a <= l && r <= b)
            return node[k];
        ll vl = getsum(a, b, 2 * k + 1, l, (l + r) / 2);
        ll vr = getsum(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;
    }
};

ll digit_sum(ll v)
{
    ll ret = 0;
    while (v)
    {
        ret += (v % 10);
        v /= 10;
    }
    return ret;
}

template <typename T>
struct Kruskal
{

    struct edge
    {
        ll from, to;
        T cost;
        ll used;
        edge() {}
        edge(ll from, ll to, T cost) : from(from), to(to), cost(cost), used(0) {}
        bool operator<(const edge &e) const
        {
            return cost < e.cost;
        }
    };

    ll n;
    vector<ll> p, r;
    vector<edge> edges;

    Kruskal() {}
    Kruskal(ll n) : n(n) {}

    void init(ll n)
    {
        r.assign(n, 1);
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    ll find(ll x)
    {
        return (x == p[x] ? x : p[x] = find(p[x]));
    }

    bool same(ll x, ll y)
    {
        return find(x) == find(y);
    }

    void unite(ll x, ll y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (r[x] < r[y])
            swap(x, y);
        r[x] += r[y];
        p[y] = x;
    }

    void add_edge(ll u, ll v, T c)
    {
        edges.emplace_back(u, v, c);
    }

    T build()
    {
        sort(edges.begin(), edges.end());
        init(n);
        T res = 0;
        for (auto &e : edges)
        {
            if (!same(e.from, e.to))
            {
                res += e.cost;
                unite(e.from, e.to);
                e.used = 1;
            }
        }
        return res;
    }

    T build(ll k)
    {
        sort(edges.begin(), edges.end());
        init(n);
        T res = 0;
        ll cnt = 0;
        for (auto &e : edges)
        {
            if (!same(e.from, e.to))
            {
                res += e.cost;
                unite(e.from, e.to);
                e.used = 1;
                cnt++;
            }
            if (cnt == k)
            {
                break;
            }
        }
        return res;
    }
};

int LIS(int a[], int n)
{
    vector<int> A(n, 0x3f3f3f3f);
    for (int i = 0; i < n; i++)
        *lower_bound(A.begin(), A.end(), a[i]) = a[i];
    return find(A.begin(), A.end(), 0x3f3f3f3f) - A.begin();
}

// string maze[1010];
ll maze[100][100];
ll grid_bfs(ll H, ll W, ll sx, ll sy, ll gx, ll gy)
{

    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    vector<vector<ll>> dist(H, vector<ll>(W, -1));
    dist[sy][sx] = 0;

    queue<PL> q;
    q.push({sy, sx});
    while (!q.empty())
    {
        ll x, y;
        tie(y, x) = q.front();
        q.pop();
        if (y == gy && x == gx)
        {
            break;
        }
        for (int t = 0; t < 4; t++)
        {
            ll nx = x + dx[t], ny = y + dy[t];
            if (nx < 0 || ny < 0 || nx >= W || ny >= H || dist[ny][nx] != -1 || maze[ny][nx] == '#')
            {
                continue;
            }

            dist[ny][nx] = dist[y][x] + 1;
            q.push({ny, nx});
        }
    }

    return dist[gy][gx];
}

// no verify
ll bfs(ll n, ll start, vector<vector<PL>> Edges)
{

    vector<ll> dist(n + 1, -1);
    dist[start] = 0;
    queue<PL> q;
    q.push({start, 0});

    while (!q.empty())
    {
        ll node, cost;
        tie(cost, node) = q.front();
        q.pop();
        for (auto p : Edges[node])
        {
            ll v = p.first, cost = p.second;
            if (dist[v] == -1)
            {
                dist[v] = dist[node] + cost;
                q.push({v, cost});
            }
        }
    }
}

vector<vector<ll>> warshall_floyd(ll n, vector<vector<ll>> g, ll INF)
{
    //init vector<vector<ll>> c(10,vector<ll>(10,0));

    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (g[i][k] == INF || g[k][j] == INF)
                    continue;
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }

    return g;
}

struct Dijkstra
{

    ll n;
    vector<vector<pair<ll, ll>>> Edges;
    vector<ll> Dist;
    vector<ll> Prev;
    vector<ll> PathNum;

    Dijkstra(ll n) : n(n), Edges(n), Dist(n), Prev(n), PathNum(n)
    {
        Prev.assign(n, -1);
    };

    void add_edge(ll a, ll b, ll c, bool directed = true)
    {
        if (directed)
        {
            Edges[a].emplace_back(make_pair(b, c));
        }
        else
        {
            Edges[a].emplace_back(make_pair(b, c));
            Edges[b].emplace_back(make_pair(a, c));
        }
    }
    // O((E+V)logV)
    void build(int start)
    {
        priority_queue<P, vector<P>, greater<P>> queue;
        fill(Dist.begin(), Dist.end(), 1e+18); //1e18 !?!?
        fill(Prev.begin(), Prev.end(), -1);    //1e18 !?!?
        Dist[start] = 0;
        PathNum[start] = 1;
        queue.push(PL(0, start));

        while (!queue.empty())
        {
            PL p = queue.top();
            queue.pop();
            int v = p.second;
            if (Dist[v] < p.first)
                continue;

            for (int i = 0; i < Edges[v].size(); i++)
            {
                PL e = Edges[v][i];
                if (Dist[e.first] > Dist[v] + e.second)
                {
                    Dist[e.first] = Dist[v] + e.second;
                    queue.push(P(Dist[e.first], e.first));

                    Prev[e.first] = v;

                    PathNum[e.first] = PathNum[v];
                }
                else if (Dist[e.first] == Dist[v] + e.second)
                {
                    PathNum[e.first] += PathNum[v];
                    PathNum[e.first] %= MOD;
                }
            }
        }
    }

    ll dist(ll t)
    {
        return Dist[t];
    }

    vector<ll> get_path(ll t)
    {
        vector<ll> path;
        for (; t != -1; t = Prev[t])
        {
            path.push_back(t);
        }
        reverse(path.begin(), path.end());
        return path;
    }

    ll get_path_num(ll t)
    {
        return PathNum[t];
    }

    // int solve()
    // {
    //    ll v, e, r;
    //    cin >> v >> e >> r;
    //    Dijkstra dij(v);
    //    for (int i = 0; i < e; i++)
    //    {
    //       ll a, b, c;
    //       cin >> a >> b >> c;
    //       dij.add_edge(a, b, c);
    //    }
    //    dij.build(r);
    //    for (int i = 0; i < v; i++)
    //    {
    //       if (dij.dist(i) == 1e18)
    //       {
    //          cout << "INF" << endl;
    //       }
    //       else
    //       {
    //          cout << dij.dist(i) << endl;
    //          cout << dij.get_path(i) << endl;
    //          cout << dij.get_path_num(i) << endl;
    //       }
    //    }
    //    return 0;
    // }
};

struct CumulativeSum2D
{
    int H;
    int W;
    vector<vector<ll>> data;

    CumulativeSum2D(int H, int W) : H(H), W(W), data(H + 1, vector<ll>(W + 1, 0LL)) {}

    void add(int x, int y, ll z)
    {
        data[x + 1][y + 1] += z;
    }

    void build()
    {
        for (int i = 1; i < data.size(); i++)
        {
            for (int j = 1; j < data[i].size(); j++)
            {
                data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
            }
        }
    }

    void print()
    {

        for (int i = 0; i <= H; i++)
        {
            for (int j = 0; j <= W; j++)
            {
                cout << data[i][j] << " ";
            }
            cout << endl;
        }
    }

    ll query(int sx, int sy, int gx, int gy)
    {
        return (data[gy][gx] - data[sy - 1][gx] - data[gy][sx - 1] + data[sy - 1][sx - 1]);
    }
};

struct LCA
{
    int n, h;
    vector<vector<int>> par;
    vector<vector<pair<int, int>>> v;
    vector<ll> depth, dis;
    LCA(int sz) : n(sz), v(n), depth(n), dis(n)
    {
        h = 1;
        while ((1 << h) < n)
            h++;
        par.assign(h, vector<int>(n, -1));
    }

    void add_edge(int x, int y, int z)
    {
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }

    void dfs(int x, int p, int d, ll di)
    {
        par[0][x] = p;
        depth[x] = d;
        dis[x] = di;
        for (auto to : v[x])
            if (to.first != p)
                dfs(to.first, x, d + 1, di + to.second);
    }

    void build()
    {
        dfs(0, -1, 0, 0);
        for (int i = 0; i < h - 1; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (par[i][j] < 0)
                    par[i + 1][j] = -1;
                else
                    par[i + 1][j] = par[i][par[i][j]];
            }
        }
    }

    int lca(int u, int v)
    {
        if (depth[u] > depth[v])
            swap(u, v);
        for (int i = 0; i < h; i++)
            if ((depth[v] - depth[u]) >> i & 1)
                v = par[i][v];
        if (u == v)
            return u;
        for (int i = h - 1; i >= 0; i--)
        {
            if (par[i][u] != par[i][v])
            {
                u = par[i][u];
                v = par[i][v];
            }
        }
        return par[0][u];
    }

    ll dist(int u, int v)
    {
        return dis[u] + dis[v] - 2 * dis[lca(u, v)];
    }

    // int solve()
    // {
    //    ll n;
    //    cin >> n;
    //    LCA lca(n);
    //    for (int i = 0; i < n - 1; i++)
    //    {
    //       ll u, v, w;
    //       cin >> u >> v >> w;
    //       lca.add_edge(u, v, w);
    //    }
    //    lca.build();
    //    ll q;
    //    cin >> q;
    //    while (q--)
    //    {
    //       ll a, b, c;
    //       cin >> a >> b >> c;
    //       cout << (lca.dist(a, b) + lca.dist(b, c) + lca.dist(c, a)) / 2 << endl;
    //    }

    //    return 0;
    // }
};

vector<ll> compress(vector<ll> r)
{
    //1-indexed
    set<ll> se;
    for (int i = 0; i < r.size(); i++)
    {
        se.insert(r[i]);
    }

    map<ll, ll> m;
    ll cnt = 1;
    for (auto t : se)
    {
        m[t] = cnt;
        cnt++;
    }

    for (int i = 0; i < r.size(); i++)
    {
        r[i] = m[r[i]];
    }

    return r;
}

/*------------------------------*/

void YES()
{
    cout << "YES" << endl;
    exit(0);
}
void NO()
{
    cout << "NO" << endl;
    exit(0);
}

void Yes()
{
    cout << "Yes" << endl;
    exit(0);
}
void No()
{
    cout << "No" << endl;
    exit(0);
}

void m1()
{
    cout << -1 << endl;
    exit(0);
}

void solve()
{
    string x;
    cin >> x;
    sort(ALL(x));
    reverse(ALL(x));
    ll v = x[x.size() - 1];
    ll c = 0;
    for(int i=0; i < x.size(); i++){
        if(x[i] == v){
            c++;
        }
        if(c >= x.size()-1){
            m1();
        }
    }
    

    for(int i=x.size() -2; i > -1; i--){
        if(v != x[i]){
            swap(x[x.size() - 1], x[i]);
            cout << x << endl;
            exit(0);
        }
    }
    cout << -1 << endl;
}

int main()
{
    cout.precision(10);
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();
    return 0;
}

//IMOS
//https://imoz.jp/algorithms/imos_method.html

/*名前
bitcount    __builtin_popcountll
二次元累積和 CumulativeSum2D
10進数の桁和 digit_sum
(b*b+c*c)**0.5 hypot
        cout << fixed << setprecision(10) << ans.x << " " << ans.y << endl;

// 文字列t　->整数　atoi(t.c_str());
// 文字列t　->long long整数　stoll(t); ローカルではつかえない
*/

/*実装例

**********
DP
**********
・ナップサックDP

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_C
個数制限なしナップサック　N<=100,W<=10000,v<=1000

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_B
01ナップサック　N<=100,W<=10000,v<=1000
https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_F
01ナップサック　N<=100,W<=10^9,v<=100

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_H
巨大ナップザック N=40 w<10^15 , v<10^15
半分全列挙して、wi > wj かつvi < vj となるようなiを除いて、二分探索

・部分文字列DP 
https://www.hackerrank.com/contests/bbc003/challenges/bbc003-e/submissions/code/1321355726
（部分文字列の中で＋の個数の偶奇によって、カウントするか決める）

・桁DP
１
https://atcoder.jp/contests/abc029/tasks/abc029_d
n以下の数字の中で現れた１の数を求める
dp[i][j][k]:i桁目まで見たときに１の個数がk個の数字の個数

S - Digit Sum
https://atcoder.jp/contests/dp/tasks/dp_s
n以下の数字の中で、各桁の総和がDの倍数となるものを数える

E - Almost Everywhere Zero
https://atcoder.jp/contests/abc154/tasks/abc154_e
n以下の数字の中で,0でない数字が丁度K個あるものの数を数える

*************
組み合わせ
*************
https://codeforces.com/contest/888/problem/D
少なくともn-k個がpi=iとなるような順列の組の数え上げ
→pi≠iとなる順列をモンモール数という。n-k~n個をpi=iと固定したときに、他の要素がpi≠iとなるような組み合わせの数（モンモール数）の積をとる

https://codeforces.com/problemset/problem/322/B
赤・青・緑の花束が存在し、ある色を３本or全ての色を１本ずつ使ったときに、できる花束の最大数

https://atcoder.jp/contests/abc021/tasks/abc021_d
https://codeforces.com/problemset/problem/1288/C
1 <=a1 <= a2 <= ... <= ak <= n となる（a1,a2..ak)の組の数
→等号がなければ単純にn個の要素の中からk個を選べばよい　－＞　C(n,k)
→等号がある場合は重複を許してk個選べばよい　　　　　　－＞　H(n,k)

*************
最短経路
*************
https://atcoder.jp/contests/joi2014yo/tasks/joi2014yo_e
移動できるノード数に制限がある場合の最短経路問題
→事前に幅優先探索でノード毎に移動できるノードを求めて、ダイクストラ

*************
遅延セグ木
*************
https://atcoder.jp/contests/abc153/submissions/10165699

***********
BIT
***********
https://atcoder.jp/contests/abc157/tasks/abc157_e(アルファベット毎にBITもつやつ)
https://hoj.hamako-ths.ed.jp/onlinejudge/problems/1276（中央値求めるやつ）

*/
0