icpclib - arosh/arosh.github.com GitHub Wiki

template <class T, class U>
T lexical_cast(const U& from) {
    T to;
    stringstream ss;
    ss << from; ss >> to;
    return to;
}

// iostreamが遅いときは std::ios::sync_with_stdio(false); を設定し
// std::endl の代わりに '\n' を使う (#define endl '\n')
// std::cin.tie(nullptr); はあまり効果がないようが気がする

printf("%0*d", 4, 123); // => 0123
cout << setw(4) << setfill('0') << 123 << endl; // => 0123

cout.setf(ios::fixed); cout.precision(10);

// remove, unique, rotate
vector<int> v = { 1, 1, 2, 3, 5 };
v.erase(remove(v.begin(), v.end(), 3), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
v.erase(v.begin() + 2); // v[2]だけ消す (v.end()不要)
rotate(v.begin(), v.begin() + 2, v.end()); // v[2]が最初に来る

// mapやsetの比較関数
struct Node {
    int fst, snd;
    Node(int f, int s) : fst(f), snd(s) { }
};

struct NodeCmp {
    bool operator()(const Node& a, const Node& b) {
        if(a.fst != b.fst) return a.fst < b.fst;
        return a.snd < b.snd;
    }
};

set<Node, NodeCmp> s;

// map#[]にmap#sizeはダメ。ゼッタイ。
std::map<int, int> dict;
dict[123] = dict.size(); // dict[123] = 0 or 1

vector<string> splitAll(string s, string t) {
  vector<string> v;
  for(int p = 0; (p = s.find(t)) != string::npos; ) {
    v.push_back(s.substr(0, p));
    s = s.substr(p + t.size());
  }
  v.push_back(s);
  return v;
}

string replaceAll(string s, string f, string t) {
  string r;
  for(int p = 0; (p = s.find(f)) != string::npos; ) {
    r += s.substr(0, p) + t;
    s = s.substr(p + f.size());
  }
  return r + s;
}

__builtin_popcount(b); // (1 << 1) | (1 << 3) => 2
// 0を入れるとキケン！！！
__builtin_ctz(b);      // (1 << 1) | (1 << 3) => 1
31 - __builtin_clz(b); // (1 << 1) | (1 << 3) => 3

// unsigned long long な場合は
__builtin_popcountll();
__builtin_ctzll();
__builtin_clzll();

// 左シフトの穴埋めは0であることが保証される
// unsignedの右シフトの穴埋めは0であることが保証される
// signedの右シフトの穴埋めは0であることが保証されない

S = S & ~(1 << k); // k番目のビットの消去
S = S & -S; // 最も右の1ビット
S = -S & (S + 1); // 最も右の0ビット

// 集合の部分集合の列挙、サイズkの集合の列挙 → 蟻本のp.144に載ってるけどよく分からん

int search_max() {
  int lb = 0, ub = N;
  while(ub - lb > 1) {
    int mid = (lb + ub) / 2;
    (check(mid) ? lb : ub) = mid;
  }
  return lb;
}
int search_min() {
  int lb = -1, ub = N - 1;
  while(ub - lb > 1) {
    int mid = (lb + ub) / 2;
    (check(mid) ? ub : lb) = mid;
  }
  return ub;
}

struct UnionFind {
  vector<int> data;
  UnionFind(int v) : data(v, -1) {}
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return -data[root(x)];
  }
  void merge(int x, int y) {
    x = root(x), y = root(y);
    if (x != y) {
      if (size(y) > size(x))
        swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }
};

struct BIT {
  int N;
  vector<int> data;
  BIT(int n) : N(n), data(n + 1, 0) { }
  void add(int a, int w) {
    ++a;
    for(int x = a; x <= N; x += x & -x) {
      data[x] += w;
    }
  }
  int sum(int a) {
    int ret = 0;
    for(int x = a; x > 0; x -= x & -x) {
      ret += data[x];
    }
    return ret;
  }
};

bit0.add(l, -x * l);
bit1.add(l, x);
bit0.add(r, x * r);
bit1.add(r, -x);

bit0.sum(r) + r*bit1.sum(r) - bit0.sum(l) - l*bit1.sum(l);

const int INF = (int)1e9;
struct RMQ {
    vector<int> data;
    int N;
    RMQ(int size) {
        N = 1;
        while(N < size) N *= 2;
        data.assign(2*N - 1, INF);
    }
    // 0オリジンでk番目の要素をaに変更する
    void update(int k, int a) {
        k += N - 1; // 葉に移動
        data[k] = a;
        while(k > 0) {
            k = (k - 1)/2;
            data[k] = min(data[2*k + 1], data[2*k + 2]);
        }
    }
    // minimum [a, b)
    int minimum(int a, int b) {
        return minimum_sub(a, b, 0, 0, N);
    }
    int minimum_sub(int a, int b, int k, int l, int r) {
        if(r <= a || b <= l) return INF;
        if(a <= l && r <= b) return data[k];
        
        return min(minimum_sub(a, b, 2*k + 1, l, (l + r)/2),
                   minimum_sub(a, b, 2*k + 2, (l + r)/2, r));
    }
};

struct SegTree {
    int N;
    vector<ll> data_add;
    vector<ll> data_min;
    SegTree(int size) {
        N = 1;
        while(N < size) N *= 2;
        data_add.assign(2*N - 1, 0LL);
        data_min.assign(2*N - 1, 0LL);
    }
    void add(int a, int b, ll x, int k, int l, int r) {
        if(r <= a || b <= l) return;
        if(a <= l && r <= b) {
            data_add[k] += x;
            while(k > 0) {
                k = (k - 1) / 2;
                data_min[k] = min(data_min[2*k + 1] + data_add[2*k + 1],
                                  data_min[2*k + 2] + data_add[2*k + 2]);
            }
        }
        else {
            add(a, b, x, 2*k + 1, l, (l + r)/2);
            add(a, b, x, 2*k + 2, (l + r)/2, r);
        }
    }
    ll minimum(int a, int b, int k, int l, int r) {
        if(r <= a || b <= l) return INF;
        if(a <= l && r <= b) {
            return data_min[k] + data_add[k];
        }
        else {
            return min(minimum(a, b, 2*k + 1, l, (l + r)/2),
                       minimum(a, b, 2*k + 2, (l + r)/2, r)) + data_add[k];
        }
    }
};

const int sqrtN = 400;
struct SqrtDecomposition {
  int N, K;
  vector<int> data;
  vector<int> addpart;
  vector<int> addall;
  SqrtDecomposition(int n) : N(n) {
    K = (N + sqrtN - 1) / sqrtN;
    data.assign(K * sqrtN, 0);
    addpart.assign(K, 0);
    addall.assign(K, 0);
  }
  void put(int a, int b, int value) {
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= a || b <= l) continue;
      if(a <= l && r <= b) {
        addall[k] += value;
      }
      else {
        for(int i = max(a, l); i < min(b, r); ++i) {
          data[i] += value;
          addpart[k] += value;
        }
      }
    }
  }
  int get(int a, int b) {
    int ret = 0;
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= a || b <= l) continue;
      if(a <= l && r <= b) {
        ret += addall[k] * sqrtN + addpart[k];
      }
      else {
        for(int i = max(a, l); i < min(b, r); ++i) {
          ret += data[i] + addall[k];
        }
      }
    }
    return ret;
  }
};

struct Edge {
  int to, cost;
  Edge(int to_, int cost_) : to(to_), cost(cost_) { }
};
struct State {
  int pos, cost;
  State(int pos_, int cost_) : pos(pos_), cost(cost_) { }
  bool operator <(const State &s) const {
    return cost > s.cost;
  }
};
vector<int> shortest_path(const vector<vector<Edge>> &G, const int src) {
  const int n = G.size();
  vector<int> d(n, INF);
  priority_queue<State> Q;
  Q.emplace(src, 0);
  d[src] = 0;
  while(!Q.empty()) {
    State s = Q.top(); Q.pop();
    if(s.cost > d[s.pos]) continue;
    for(Edge e : G[s.pos]) {
      if(d[e.to] > s.cost + e.cost) {
        d[e.to] = s.cost + e.cost;
        Q.emplace(e.to, d[e.to]);
      }
    }
  }
  return d;
}

const int MAX_N = 16;
const int INF = (int)1e9;

int d[MAX_N][MAX_N];
int dp[MAX_N][1 << MAX_N];

int tsp(int v, int b) {
    if(dp[v][b] != -1) return dp[v][b];
    // 全ての頂点を経由し、戻ってきた
    if(b == (1 << N) - 1 && v == 0) return 0;

    int res = INF;
    for(int i = 0; i < N; i++) {
        if(b & (1 << i)) continue;
        res = min(res, tsp(i, b | (1 << i)) + d[v][i]);
    }
    return dp[v][b] = res;
}

int solve() {
    memset(dp, -1, sizeof(dp));
    return tsp(0, 0); // 呼び出し注意！
}

struct Scc {
    const int V; // 頂点数
    vector<vector<int> > G, revG; // グラフの隣接リスト表現と、その逆グラフ
    vector<int> order; // scc()を呼ぶと、トポロジカル順序が入る
    vector<int> vs; // 帰りがけ順序
    vector<bool> used; // STL注意

    Scc(int v) : V(v), G(v), revG(v), order(v), used(v) { }

    void add_edge(int from, int to) {
        G[from].push_back(to);
        revG[to].push_back(from);
    }
    void dfs(int v) {
        used[v] = true;
        for(int to : G[v]) {
            if(used[to] == false) dfs(to);
        }
        vs.push_back(v);
    }
    void rdfs(int v, int k) {
        used[v] = true;
        order[v] = k;
        for(int to : revG[v]) {
            if(used[to] == false) rdfs(to, k);
        }
    }
    // @return 強連結成分を潰してDAGを作ったときの頂点数
    int compute() {
        vs.clear();
        used.assign(V, false);
        for(int i = 0; i < V; i++) {
            if(used[i] == false) dfs(i);
        }
        int k = 0;
        reverse(vs.begin(), vs.end());
        used.assign(V, false);
        for(int v : vs) {
            if(used[v] == false) rdfs(v, k++);
        }
        return k;
    }
};

vector<int> topological_sort(const vector<vector<int>> &G) {
  const int N = G.size();
  vector<int> indeg(N, 0);
  for(auto &&vs : G) {
    for(int v : vs) {
      indeg[v]++;
    }
  }
  queue<int> Q;
  for(int i = 0; i < N; ++i) {
    if(indeg[i] == 0) Q.push(i);
  }
  vector<int> ret;
  while(!Q.empty()) {
    int v = Q.front(); Q.pop();
    ret.push_back(v);
    for(int u : G[v]) {
      indeg[u]--;
      if(indeg[u] == 0) Q.push(u);
    }
  }
  return ret;
}

struct LCA {
  int N, logN; // logN == ceil(lg(N))
  vector<vector<int>> G;
  vector<int> depth;
  // vから根の方向に2^k回登ったときのノード parent[k][v]
  vector<vector<int>> parent;

  LCA(int size) : N(size), G(size), depth(size) {
    logN = 0;
    for(int x = 1; x < N; x *= 2) logN++;
    parent.assign(max(logN, 1), vector<int>(N));
  }
  // どちらが根であってもOK
  void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
  }
  void dfs(int v, int par, int dep) {
    depth[v] = dep;
    parent[0][v] = par;
    for(int next : G[v]) {
      if(next != par) dfs(next, v, dep + 1);
    }
  }
  void build(int root) {
    dfs(root, -1, 0);
    for(int k = 1; k < logN; k++) {
      for(int v = 0; v < N; v++) {
        if(parent[k - 1][v] == -1) parent[k][v] = -1;
        else parent[k][v] = parent[k - 1][parent[k - 1][v]];
      }
    }
  }
  int lca(int u, int v) {
    if(depth[u] > depth[v]) swap(u, v); // vのほうが深くなる
    // uとvの深さが同じになるまでvを根の方向に移動する
    for(int k = 0; k < logN; k++) {
      if(((depth[v] - depth[u]) >> 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];
  }
};

struct LowLink {
  const int N;
  vector<vector<int>> G;
  vector<bool> vis;
  vector<int> ord, parent, low;
  LowLink(int size) : N(size), G(size), vis(size, false), ord(size), parent(size), low(size) { }
  void add(int a, int b) {
    G[a].push_back(b); G[b].push_back(a);
  }
  void dfs(int v, int &k) {
    ord[v] = low[v] = k++;
    vis[v] = true;
    for(int u : G[v]) {
      if(!vis[u]) {
        parent[u] = v;
        dfs(u, k);
        low[v] = min(low[v], low[u]);
      }
      else if(u != parent[v]) {
        low[v] = min(low[v], ord[u]);
      }
    }
  }
  void compute() {
    int k = 0;
    dfs(0, k);
  }
  vector<pair<int, int>> bridge() {
    compute();
    vector<pair<int, int>> ret;
    for(int i = 0; i < N; ++i) {
      if(ord[parent[i]] < low[i]) ret.emplace_back(parent[i], low[i]);
    }
    return ret;
  }
  vector<int> articulation() {
    compute();
    vector<int> ret;
    int c = 0;
    for(int i = 1; i < N; ++i) {
      int p = parent[i];
      if(p == 0) ++c;
      else if(ord[p] <= low[i]) ret.push_back(p);
    }
    if(c >= 2) ret.push_back(0);
    sort(ret.begin(), ret.end());
    ret.erase(unique(ret.begin(), ret.end()), ret.end());
    return ret;
  }
};

const int INF = (int)1e9;

struct Edge {
  int to, cap, rev;
  Edge(int to_, int cap_, int rev_) :
    to(to_), cap(cap_), rev(rev_) { }
};

struct FordFulkerson {
  const int V;
  vector<vector<Edge> > G;
  vector<bool> used;
  FordFulkerson(int v) : V(v), G(v), used(v) { }
  void add_edge(int from, int to, int cap) {
    G[from].emplace_back(to, cap, G[to].size());
    G[to].emplace_back(from, 0, G[from].size() - 1);
  }
  int find_flow(int v, int t, int f) {
    if(v == t) return f;
    used[v] = true;
    for(Edge &e : G[v]) {
      if(used[e.to] == false && e.cap > 0) {
        int d = find_flow(e.to, t, min(f, e.cap));
        if(d > 0) {
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
  int max_flow(int s, int t) {
    int flow = 0;
    while(true) {
      used.assign(V, false);
      int f = find_flow(s, t, INF);
      if(f == 0) return flow;
      flow += f;
    }
  }
};

struct Matching {
  int N, M;
  vector<vector<int>> G;
  vector<int> match;
  vector<bool> used;
  Matching(int n, int m) : N(n), M(m), G(n + m) {}
  void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
  }
  bool dfs(int v) {
    used[v] = true;
    for (int u : G[v]) {
      int w = match[u];
      if (w < 0 || (!used[w] && dfs(w))) {
        match[v] = u;
        match[u] = v;
        return true;
      }
    }
    return false;
  }
  int max_match() {
    int res = 0;
    match.assign(N + M, -1);
    for (int v = 0; v < N + M; ++v) {
      if (match[v] < 0) {
        used.assign(N + M, false);
        if (dfs(v)) res++;
      }
    }
    return res;
  }
};

typedef string::const_iterator iter;
int expr(iter& p);
int term(iter& p);
int factor(iter& p);
int number(iter& p);
int expr(iter& p) {
    int r = term(p);
    while(true) {
        if(*p == '+') {
            ++p;
            int rs = term(p);
            r += rs;
        }
        else if(*p == '-') {
            ++p;
            int rs = term(p);
            r -= rs;
        }
        else {
            break;
        }
    }
    return r;
}
int term(iter& p) {
    int r = factor(p);
    while(true) {
        if(*p == '*') {
            p++;
            int rs = factor(p);
            r *= rs;
        }
        else if(*p == '/') {
            p++;
            int rs = factor(p);
            r /= rs;
        }
        else {
            break;
        }
    }
    return r;
}
int factor(iter& p) {
    if(*p == '(') {
        ++p; // skip (
        int r = expr(p);
        ++p; // skip )
        return r;
    }
    return number(p);
}
int number(iter& p) {
    int r = 0;
    while(isdigit(*p)) {
        r *= 10;
        r += *p -'0';
        p++;
    }
    return r;
}

enum FACE { TOP, FRONT, RIGHT, LEFT, BACK, BOTTOM }; // 1..6
typedef array<int, 6> Dice;
FACE tbl[6][4] = {
  { TOP, BACK, BOTTOM, FRONT },
  { TOP, RIGHT, BOTTOM, LEFT },
  { TOP, FRONT, BOTTOM, BACK },
  { TOP, LEFT, BOTTOM, RIGHT },
  { FRONT, RIGHT, BACK, LEFT },
  { FRONT, LEFT, BACK, RIGHT }
};
enum MOVE { TOP_TO_BACK, TOP_TO_RIGHT, TOP_TO_FRONT,
            TOP_TO_LEFT, FRONT_TO_RIGHT, FRONT_TO_LEFT };
void rotate(Dice &d, FACE t[4]) {
  int tmp = d[t[3]];
  d[t[3]] = d[t[2]]; d[t[2]] = d[t[1]]; d[t[1]] = d[t[0]]; d[t[0]] = tmp;
}
vector<Dice> generate_all(Dice dice) {
  vector<Dice> res;
  for(int i = 0; i < 6; ++i) {
    for(int j = 0; j < 4; ++j) {
      res.emplace_back(dice);
      rotate(dice, tbl[FRONT_TO_RIGHT]);
    }
    if(i % 2 == 0) rotate(dice, tbl[TOP_TO_BACK]);
    else rotate(dice, tbl[TOP_TO_RIGHT]);
  }
  return res;
}

bool EQ(double a, double b) { return abs(a - b) < 1e-8; }
typedef vector<double> Vec;
typedef vector<Vec> Mat;

bool solve_mat(Mat B, Vec& x) {
    const int N = B.size();

    for(int i = 0; i < N; i++) {
        int pivot = i;
        for(int r = i + 1; r < N; r++) {
            if(abs(B[r][i]) > abs(B[pivot][i])) pivot = r;
        }
        B[i].swap(B[pivot]);

        if(EQ(B[i][i], 0)) return false;
        // 本来ならば0や1になる要素の計算をサボる
        for(int j = i + 1; j < N + 1; j++) B[i][j] /= B[i][i];
        for(int r = 0; r < N; r++) {
            if(r == i) continue;
            double mul = B[r][i];
            for(int j = i + 1; j < N + 1; j++) {
                B[r][j] -= B[i][j] * mul;
            }
        }
    }

    x.resize(N);
    for(int i = 0; i < N; i++) x[i] = B[i][N];
    return true;
}

double simpson(double L, double R, int div = 1) {
  const double h = (R - L) / (2 * div);
  double s = 0.0, t = 0.0;
  for(int i = 1; i <= 2 * div - 3; i += 2) {
    s += f(L + h*i); t += f(L + h*(i + 1));
  }
  return h / 3 * (f(L) + f(R) + 4*(s + f(R - h)) + 2*t);
}

int extgcd(int a, int b, int &x, int &y) {
  int d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1; y = 0;
  }
  return d;
}

int mod_inv(int a, int m) {
  int x, y;
  extgcd(a, m, x, y);
  return (m + x % m) % m;
}

vector<int> euler(int n) {
    vector<int> res(++n);
    for(int i = 0; i < n; i++) res[i] = i;
    for(int i = 2; i < n; i++) {
        if(res[i] == i) {
            for(int j = i; j < n; j += i)
                res[j] = res[j]/i*(i-1);
        }
    }
    return res;
}

ll pow_mod(ll x, ll y) {
  ll res = 1;
  for(; y > 0; y >>= 1, (x *= x) %= MOD) {
    if(y & 1) (res *= x) %= MOD;
  }
  return res;
}

ll lcm_many(const vector<ll> &v) {
  vector<int> maxexp(MAX + 1, 0);
  for(ll item : v) {
    ll s = item;
    for(ll d = 2; d * d <= s; d++) {
      int k = 0;
      while (s % d == 0) {
        s /= d;
        k++;
      }
      maxexp[d] = max(maxexp[d], k);
    }
    maxexp[s] = max(maxexp[s], 1);
  }
  ll lcm = 1;
  for (ll i = 2; i <= MAX; ++i) {
    lcm *= pow_mod(i, maxexp[i]);
    lcm %= MOD;
  }
  return lcm;
}

ll lcm1ton(const int n) {
  ll lcm = 1;
  vector<bool> vis(n + 1, false);
  for(int i = 2; i <= n; ++i) {
    if(vis[i]) continue;
    ll num = i;
    while(num * i <= n) num *= i;
    for(int j = i * i; j <= n; j += i)
      vis[j] = true;
    (lcm *= num) %= MOD;
  }
  return lcm;
}

const int MAX_N = 10;
const int MAX_K = 10;
int dp[MAX_N][MAX_K];

int comb(int n, int k) {
    if(k < 0 || k > n) return 0;
    if(n == 0) return 1;
    if(dp[n][k] > 0) return dp[n][k];

    return dp[n][k] = comb(n-1, k-1) + comb(n-1, k);
}

int main() {
    memset(dp, 0, sizeof(dp));
}

void stern_brocot(int ax = 0, int ay = 1, int bx = 1, int by = 0) {
    int mx = ax + bx; // 分子
    int my = ay + by; // 分母
    // 何らかの制限をかける
    stern_brocot(ax, ay, mx, my);
    // 何かする
    stern_brocot(mx, my, bx, by);
}