QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#878276#8591. Shopskaichou24355 432ms90328kbC++2030.9kb2025-02-01 14:31:272025-02-01 14:31:27

Judging History

This is the latest submission verdict.

  • [2025-02-01 14:31:27]
  • Judged
  • Verdict: 55
  • Time: 432ms
  • Memory: 90328kb
  • [2025-02-01 14:31:27]
  • Submitted

answer

#include<bits/stdc++.h>
#include <immintrin.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll=long long;
using P = pair<ll,ll>;
const long double PI=acos(-1);
const ll INF=1e18;
const int inf=1e9;
struct Edge {
    ll to;
    ll cost;
};
using Graph=vector<vector<Edge>>;
template <typename T>
bool chmax(T &a,const T& b){
  if (a<b){
    a=b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a,const T& b){
  if (a>b){
    a=b;
    return true;
  }
  return false;
}
template<int MOD> struct Fp{
  ll val;
  constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
    if (val < 0) val += MOD;
  }
  static constexpr int getmod() { return MOD; }
  constexpr Fp operator - () const noexcept {
    return val ? MOD - val : 0;
  }
  constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
  constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
  constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
  constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
  constexpr Fp& operator += (const Fp& r) noexcept {
    val += r.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  constexpr Fp& operator -= (const Fp& r) noexcept {
    val -= r.val;
    if (val < 0) val += MOD;
    return *this;
  }
  constexpr Fp& operator *= (const Fp& r) noexcept {
    val = val * r.val % MOD;
    return *this;
  }
  constexpr Fp& operator /= (const Fp& r) noexcept {
    ll a = r.val, b = MOD, u = 1, v = 0;
    while (b) {
      ll t = a / b;
      a -= t * b, swap(a, b);
      u -= t * v, swap(u, v);
    }
    val = val * u % MOD;
    if (val < 0) val += MOD;
    return *this;
  }
  constexpr bool operator == (const Fp& r) const noexcept {
    return this->val == r.val;
  }
  constexpr bool operator != (const Fp& r) const noexcept {
    return this->val != r.val;
  }
  constexpr bool operator < (const Fp& r) const noexcept {
    return this->val < r.val;
  }
  friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {
    is >> x.val;
    x.val %= MOD;
    if (x.val < 0) x.val += MOD;
    return is;
  }
  friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {
    return os << x.val;
  }
  friend constexpr Fp<MOD> modpow(const Fp<MOD>& a, long long n) noexcept {
    Fp<MOD> res=1,r=a;
    while(n){
      if(n&1) res*=r;
      r*=r;
      n>>=1;
    }
    return res;
  }
  friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Fp<MOD>(u);
  }
  ll get(){
      return val;
  }
  explicit operator bool()const{
		return val;
  }
};
template< uint32_t mod, bool fast = false >
struct MontgomeryModInt {
  using mint = MontgomeryModInt;
  using i32 = int32_t;
  using i64 = int64_t;
  using u32 = uint32_t;
  using u64 = uint64_t;
 
  static constexpr u32 get_r() {
    u32 ret = mod;
    for(i32 i = 0; i < 4; i++) ret *= 2 - mod * ret;
    return ret;
  }
 
  static constexpr u32 r = get_r();
  static constexpr u32 n2 = -u64(mod) % mod;
 
  static_assert(r * mod == 1, "invalid, r * mod != 1");
  static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
  static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
 
  u32 a;
 
  MontgomeryModInt() : a{} {}
 
  MontgomeryModInt(const i64 &x)
      : a(reduce(u64(fast ? x : (x % mod + mod)) * n2)) {}
 
  static constexpr u32 reduce(const u64 &b) {
    return u32(b >> 32) + mod - u32((u64(u32(b) * r) * mod) >> 32);
  }
 
  constexpr mint& operator+=(const mint &p) {
    if(i32(a += p.a - 2 * mod) < 0) a += 2 * mod;
    return *this;
  }
 
  constexpr mint& operator-=(const mint &p) {
    if(i32(a -= p.a) < 0) a += 2 * mod;
    return *this;
  }
 
  constexpr mint& operator*=(const mint &p) {
    a = reduce(u64(a) * p.a);
    return *this;
  }
 
  constexpr mint& operator/=(const mint &p) {
    *this *= modinv(p);
    return *this;
  }
 
  constexpr mint operator-() const { return mint() - *this; }
 
  constexpr mint operator+(const mint &p) const { return mint(*this) += p; }
 
  constexpr mint operator-(const mint &p) const { return mint(*this) -= p; }
 
  constexpr mint operator*(const mint &p) const { return mint(*this) *= p; }
 
  constexpr mint operator/(const mint &p) const { return mint(*this) /= p; }
 
  constexpr bool operator==(const mint &p) const { return (a >= mod ? a - mod : a) == (p.a >= mod ? p.a - mod : p.a); }
 
  constexpr bool operator!=(const mint &p) const { return (a >= mod ? a - mod : a) != (p.a >= mod ? p.a - mod : p.a); }
 
  u32 get() const {
    u32 ret = reduce(a);
    return ret >= mod ? ret - mod : ret;
  }
 
  friend constexpr MontgomeryModInt<mod> modpow(const MontgomeryModInt<mod> &x,u64 n) noexcept {
    MontgomeryModInt<mod> ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
 
  friend constexpr MontgomeryModInt<mod> modinv(const MontgomeryModInt<mod> &r) noexcept {
        u64 a = r.get(), b = mod, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return MontgomeryModInt<mod>(u);
  }
 
  friend ostream &operator<<(ostream &os, const mint &p) {
    return os << p.get();
  }
 
  friend istream &operator>>(istream &is, mint &a) {
    i64 t;
    is >> t;
    a = mint(t);
    return is;
  }
  static constexpr u32 getmod() { return mod; }
};
struct SCCgraph{
  // input
  vector<vector<int>> G, rG;
  // result
  vector<vector<int>> scc;
  vector<int> cmp;
  vector<vector<int>> dag;
  // constructor
  SCCgraph(int N) : G(N), rG(N) {}
  // add edge
  void add_edge(int u, int v) {
    G[u].push_back(v);
    rG[v].push_back(u);
  }
  // decomp
  vector<bool> seen;
  vector<int> vs, rvs;
  void dfs(int v) {
    seen[v] = true;
    for (auto e : G[v]) if (!seen[e]) dfs(e);
    vs.push_back(v);
  }
  void rdfs(int v, int k) {
    seen[v] = true;
    cmp[v] = k;
    for (auto e : rG[v]) if (!seen[e]) rdfs(e, k);
    rvs.push_back(v);
  }
  // reconstruct
  set<pair<int,int>> newEdges;
  void reconstruct() {
    int N = (int)G.size();
    int dV = (int)scc.size();
    dag.resize(dV);
    newEdges.clear();
    for (int i = 0; i < N; ++i) {
      int u = cmp[i];
      for (auto e : G[i]) {
        int v = cmp[e];
        if (u == v) continue;
        if (!newEdges.count({u, v})) {
          dag[u].push_back(v);
          newEdges.insert({u, v});
        }
      }
    }
  }
  void solve() {
    // first dfs
    int N = (int)G.size();
    seen.assign(N, false);
    vs.clear();
    for (int v = 0; v < N; ++v) if (!seen[v]) dfs(v);
    // back dfs
    int k = 0;
    scc.clear();
    cmp.assign(N, -1);
    seen.assign(N, false);
    for (int i = N - 1; i >= 0; --i) {
      if (!seen[vs[i]]) {
        rvs.clear();
        rdfs(vs[i], k++);
        scc.push_back(rvs);
      }
    }
    // reconstruct
    reconstruct();
  }
};
template<class T,T (*op)(T,T),T (*e)()> struct SegmentTree{
  int n;
  vector<T> dat;
  SegmentTree(int N){
    n=1;
    while(n<N)n*=2;
    dat.assign(2*n,e());
  }
  void add(int k,T x){
    k+=n;
    dat[k]+=x;
    while(k){
      k>>=1;
      dat[k]=op(dat[k*2],dat[k*2+1]);
    }
  }
  void apply(int k,T x){
    k+=n;
    dat[k]=op(dat[k],x);
    while(k){
      k>>=1;
      dat[k]=op(dat[k*2],dat[k*2+1]);
    }
  }
  void set(int k,T x){
    k+=n;
    dat[k]=x;
    while(k){
      k>>=1;
      dat[k]=op(dat[k*2],dat[k*2+1]);
    }
  }
  T query(int l,int r){
    T prodl=e(),prodr=e();
    l+=n;
    r+=n;
    while(l<r){
      if(l&1) prodl=op(prodl,dat[l++]);
      if(r&1) prodr=op(dat[--r],prodr);
      l>>=1;
      r>>=1;
    }
    return op(prodl,prodr);
  }
};
struct FenwickTree{
    int n;
    vector<ll> dat;
    FenwickTree(int N) : n(N+1), dat(n,0ll) {}
    void add(int k,ll x){
      k+=1;
      while(k<n){
          dat[k]+=x;
          k+=k&-k;
      }
    }
  //sum[0,k)
  ll sum(int k){
    ll ans=0;
    while(k){
      ans+=dat[k];
      k-=k&-k;
    }
    return ans;
  }
  //sum[l,r)
  ll sum(int l,int r){
    return sum(r)-sum(l);
  }
};
template<class S,S (*op)(S,S),S (*e)(),class F,S (*mapping)(F,S),F (*composition)(F,F),F (*id)()>
struct LazySegTree{
  private:
  int _n,size=1,idx=0;
  vector<S>seq;
  vector<F>lazy;
  void update(int k){seq[k]=op(seq[2*k],seq[2*k+1]);}
  void all_apply(int k,F f){
    seq[k]=mapping(f,seq[k]);
    if(k<size)lazy[k]=composition(f,lazy[k]);
  }
  void eval(int k){
    all_apply(2*k,lazy[k]);
    all_apply(2*k+1,lazy[k]);
    lazy[k]=id();
  }
  public:
  LazySegTree(int n):LazySegTree(vector<S>(n,e())){}
  LazySegTree(const vector<S>&v):_n(int(v.size())){
    while(size<_n)size<<=1,idx++;
    seq=vector<S>(2*size,e());
    lazy=vector<F>(2*size,id());
    for(int i=0;i<_n;i++)seq[size+i]=v[i];
    for(int i=size-1;i>=1;i--)update(i);
  }
  void set(int p,S x){
    p+=size;
    for(int i=idx;i>=1;i--)eval(p>>i);
    seq[p]=x;
    for(int i=1;i<=idx;i++)update(p>>i);
  }
  void add(int p,S x){
    p+=size;
    for(int i=idx;i>=1;i--)eval(p>>i);
    seq[p]+=x;
    for(int i=1;i<=idx;i++)update(p>>i);
  }
  S operator[](int p){
    p+=size;
    for(int i=idx;i>=1;i--)eval(p>>i);
    return seq[p];
  }
  S query(int l,int r){
    if(l==r)return e();
    S sml=e(),smr=e();
    l+=size,r+=size;
    for(int i=idx;i>=1;i--){
      if(((l>>i)<<i)!=l)eval(l>>i);
      if(((r>>i)<<i)!=r)eval(r>>i);
    }
    while(l<r){
      if(l&1)sml=op(sml,seq[l++]);
      if(r&1)smr=op(seq[--r],smr);
      l>>=1,r>>=1;
    }
    return op(sml,smr);
  }
  S all_query()const{return seq[1];}
  void apply(int p,F f){
    p+=size;
    for(int i=idx;i>=1;i--)eval(p>>i);
    seq[p]=mapping(f,seq[p]);
    for(int i=1;i<=idx;i++)update(p>>i);
  }
  void apply(int l,int r,F f){
    if(l==r)return ;
    l+=size;
    r+=size;
    for(int i=idx;i>=1;i--){
      if(((l>>i)<<i)!=l)eval(l>>i);
      if(((r>>i)<<i)!=r)eval((r-1)>>i);
    }
    int l2=l,r2=r;
    while(l<r){
      if(l&1)all_apply(l++,f);
      if(r&1)all_apply(--r,f);
      l>>=1;
      r>>=1;
    }
    l=l2,r=r2;
    for(int i=1;i<=idx;i++){
      if(((l>>i)<<i)!=l)update(l>>i);
      if(((r>>i)<<i)!=r)update((r-1)>>i);
    }
  }
};
struct UnionFind{
  int n;
  vector<int> data;
  vector<int> edge_num;
  UnionFind(int N) : n(N) , data(N,-1) , edge_num(N,0){}
  int root(int x){ // データxが属する木の根を再帰で得る:root(x) = {xの木の根}
    return data[x]<0?x:data[x]=root(data[x]);
  }
  void unite(int x, int y) {
    x=root(x);
    y=root(y);
    if(x!=y){
      if (data[x]>data[y]) swap(x, y);
      data[x]+=data[y];
      data[y]=x;
    }
    if(x!=y){
      edge_num[x]+=edge_num[y];
      edge_num[y]=0;
    }
    edge_num[x]+=1;
  }
  bool same(int x, int y){ // 2つのデータx, yが属する木が同じならtrueを返す
    return root(x)==root(y);
  }
  int size(int x){
    return -data[root(x)];
  }
  int edge(int x){
    return edge_num[root(x)];
  }
  vector<int> get_roots(){
    vector<int> res;
    for(int i=0;i<n;i++){
      if(data[i]<0) res.push_back(i);
    }
    return res;
  }
};
template< typename T >
struct WeightedUnionFind{
  vector<int> data;
  vector<T> we;
  WeightedUnionFind(int n) : data(n, -1), we(n) {}
  int root(int k) {
    if(data[k] < 0) return k;
    int par = root(data[k]);
    we[k] += we[data[k]];
    return data[k] = par;
  }
  T weight(int t) {
    root(t);
    return we[t];
  }
  bool unite(int x, int y, T w) {
    w += weight(x);
    w -= weight(y);
    x = root(x), y = root(y);
    if(x == y) return false;
    if(data[x] > data[y]) {
      swap(x, y);
      w *= -1;
    }
    data[x] += data[y];
    data[y] = x;
    we[y] = w;
    return true;
  }
  bool same(int x,int y){
    return root(x)==root(y);
  }
  int size(int x){
    return -data[root(x)];
  }
  T diff(int x, int y) {
    return weight(y) - weight(x);
  }
};
template< typename flow_t >
struct MFGraph{
  static_assert(is_integral< flow_t >::value, "template parameter flow_t must be integral type");
  const flow_t INF;
  struct edge {
    int to;
    flow_t cap;
    int rev;
    bool isrev;
    int idx;
  };

  vector< vector< edge > > graph;
  vector< int > min_cost, iter;
  flow_t max_cap;
  int SZ;

  explicit MFGraph(int V) : INF(numeric_limits< flow_t >::max()), graph(V), max_cap(0), SZ(V) {}

  void add_edge(int from, int to, flow_t cap, int idx = -1) {
    max_cap = max(max_cap, cap);
    graph[from].emplace_back((edge) {to, cap, (int) graph[to].size(), false, idx});
    graph[to].emplace_back((edge) {from, 0, (int) graph[from].size() - 1, true, idx});
  }

  bool build_augment_path(int s, int t, const flow_t &base) {
    min_cost.assign(graph.size(), -1);
    queue< int > que;
    min_cost[s] = 0;
    que.push(s);
    while(!que.empty() && min_cost[t] == -1) {
      int p = que.front();
      que.pop();
      for(auto &e : graph[p]) {
        if(e.cap >= base && min_cost[e.to] == -1) {
          min_cost[e.to] = min_cost[p] + 1;
          que.push(e.to);
        }
      }
    }
    return min_cost[t] != -1;
  }

  flow_t find_augment_path(int idx, const int t, flow_t base, flow_t flow) {
    if(idx == t) return flow;
    flow_t sum = 0;
    for(int &i = iter[idx]; i < (int)graph[idx].size(); i++) {
      edge &e = graph[idx][i];
      if(e.cap >= base && min_cost[idx] < min_cost[e.to]) {
        flow_t d = find_augment_path(e.to, t, base, min(flow - sum, e.cap));
        if(d > 0) {
          e.cap -= d;
          graph[e.to][e.rev].cap += d;
          sum += d;
          if(flow - sum < base) break;
        }
      }
    }
    return sum;
  }

  flow_t max_flow(int s, int t) {
    if(max_cap == flow_t(0)) return flow_t(0);
    flow_t flow = 0;
    for(int i = 63 - __builtin_clzll(max_cap); i >= 0; i--) {
      flow_t now = flow_t(1) << i;
      while(build_augment_path(s, t, now)) {
        iter.assign(graph.size(), 0);
        flow += find_augment_path(s, t, now, INF);
      }
    }
    return flow;
  }

  //after max_flow(s,t)
  vector<bool> min_cut(int s) {
        vector<bool> visited(SZ);
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            visited[p] = true;
            for (auto e : graph[p]) {
                if (e.cap && !visited[e.to]) {
                    visited[e.to] = true;
                    que.push(e.to);
                }
            }
        }
        return visited;
    }
  
  void output() {
    for(int i = 0; i < graph.size(); i++) {
      for(auto &e : graph[i]) {
        if(e.isrev) continue;
        auto &rev_e = graph[e.to][e.rev];
        cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
      }
    }
  }
};
template< typename flow_t, typename cost_t >
struct MCFGraph{
  struct edge {
    int to;
    flow_t cap;
    cost_t cost;
    int rev;
    bool isrev;
  };

  vector< vector< edge > > graph;
  vector< cost_t > potential, min_cost;
  vector< int > prevv, preve;
  const cost_t INF;

  MCFGraph(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {}

  void add_edge(int from, int to, flow_t cap, cost_t cost) {
    graph[from].emplace_back((edge) {to, cap, cost, (int) graph[to].size(), false});
    graph[to].emplace_back((edge) {from, 0, -cost, (int) graph[from].size() - 1, true});
  }

  cost_t min_cost_flow(int s, int t, flow_t f) {
    int V = (int) graph.size();
    cost_t ret = 0;
    using Pi = pair< cost_t, int >;
    priority_queue< Pi, vector< Pi >, greater< Pi > > que;
    potential.assign(V, 0);
    preve.assign(V, -1);
    prevv.assign(V, -1);

    while(f > 0) {
      min_cost.assign(V, INF);
      que.emplace(0, s);
      min_cost[s] = 0;
      while(!que.empty()) {
        Pi p = que.top();
        que.pop();
        if(min_cost[p.second] < p.first) continue;
        for(int i = 0; i < (int)graph[p.second].size(); i++) {
          edge &e = graph[p.second][i];
          cost_t nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to];
          if(e.cap > 0 && min_cost[e.to] > nextCost) {
            min_cost[e.to] = nextCost;
            prevv[e.to] = p.second, preve[e.to] = i;
            que.emplace(min_cost[e.to], e.to);
          }
        }
      }
      if(min_cost[t] == INF) return -1;
      for(int v = 0; v < V; v++) potential[v] += min_cost[v];
      flow_t addflow = f;
      for(int v = t; v != s; v = prevv[v]) {
        addflow = min(addflow, graph[prevv[v]][preve[v]].cap);
      }
      f -= addflow;
      ret += addflow * potential[t];
      for(int v = t; v != s; v = prevv[v]) {
        edge &e = graph[prevv[v]][preve[v]];
        e.cap -= addflow;
        graph[v][e.rev].cap += addflow;
      }
    }
    return ret;
  }

  void output() {
    for(int i = 0; i < graph.size(); i++) {
      for(auto &e : graph[i]) {
        if(e.isrev) continue;
        auto &rev_e = graph[e.to][e.rev];
        cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << rev_e.cap + e.cap << ")" << endl;
      }
    }
  }
};
struct MST{
  struct MSTEdge{
    ll u,v;
    ll cost;
    bool used;
    bool operator<(const MSTEdge& o) const {
      return cost < o.cost;
    }
  };
  int n;
  vector<MSTEdge> edges;
  MST(int sz) : n(sz){}
  void add_edge(int u,int v,ll c){
    edges.push_back({u,v,c,false});
  }
  ll kruskal(){
    UnionFind uf(n);
    sort(all(edges));
    ll min_cost=0;
    for(int i=0;i<sz(edges);i++){
      auto& [u,v,c,used]=edges[i];
      if(!uf.same(u,v)){
        uf.unite(u,v);
        used=true;
        min_cost+=c;
      }else{
          used=false;
      }
    }
    return min_cost;
  }
  Graph Tree(){
    kruskal();
    Graph G(n);
    for(int i=0;i<sz(edges);i++){
      if(edges[i].used){
        G[edges[i].u].push_back({edges[i].v,edges[i].cost});
        G[edges[i].v].push_back({edges[i].u,edges[i].cost});
      }
    }
    return G;
  }
};
void Dijkstra(const Graph &G, int s, vector<long long> &dis, vector<int> &prev) {
    int N = G.size();
    dis.assign(N, INF);
    prev.assign(N, -1); // 初期化
    priority_queue<P, vector<P>, greater<P>> pq; 
    dis[s] = 0;
    pq.emplace(dis[s], s);
    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        int v = p.second;
        if (dis[v] < p.first) {
            continue;
        }
        for (auto &e : G[v]) {
            if (dis[e.to] > dis[v] + e.cost) {
                dis[e.to] = dis[v] + e.cost;
                prev[e.to] = v; // 頂点 v を通って e.to にたどり着いた
                pq.emplace(dis[e.to], e.to);
            }
        }
    }
}
//fast Input by yosupo
#include <unistd.h>
#include <algorithm>
#include <array>
#include <cassert>
#include <cctype>
#include <cstring>
#include <sstream>
#include <string>
#include <type_traits>
#include <vector>
namespace fastio{
/*
  quote from yosupo's submission in Library Checker
*/
int bsr(unsigned int n) {
    return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(n);
}
// @param n `1 <= n`
// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned long n) {
    return 8 * (int)sizeof(unsigned long) - 1 - __builtin_clzl(n);
}
// @param n `1 <= n`
// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned long long n) {
    return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(n);
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned __int128 n) {
    unsigned long long low = (unsigned long long)(n);
    unsigned long long high = (unsigned long long)(n >> 64);
    return high ? 127 - __builtin_clzll(high) : 63 - __builtin_ctzll(low);
}
 
namespace internal {
 
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;
 
template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;
 
template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;
 
template <class T>
using is_integral =
    typename std::conditional<std::is_integral<T>::value ||
                                  internal::is_signed_int128<T>::value ||
                                  internal::is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;
 
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;
 
template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;
 
template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;
 
template <class T>
using is_integral_t = std::enable_if_t<is_integral<T>::value>;
 
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
 
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
 
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
 
}  // namespace internal
struct Scanner {
  public:
    Scanner(const Scanner&) = delete;
    Scanner& operator=(const Scanner&) = delete;
 
    Scanner(FILE* fp) : fd(fileno(fp)) {}
 
    void read() {}
    template <class H, class... T> void read(H& h, T&... t) {
        bool f = read_single(h);
        assert(f);
        read(t...);
    }
 
    int read_unsafe() { return 0; }
    template <class H, class... T> int read_unsafe(H& h, T&... t) {
        bool f = read_single(h);
        if (!f) return 0;
        return 1 + read_unsafe(t...);
    }
 
    int close() { return ::close(fd); }
 
  private:
    static constexpr int SIZE = 1 << 15;
 
    int fd = -1;
    std::array<char, SIZE + 1> line;
    int st = 0, ed = 0;
    bool eof = false;
 
    bool read_single(std::string& ref) {
        if (!skip_space()) return false;
        ref = "";
        while (true) {
            char c = top();
            if (c <= ' ') break;
            ref += c;
            st++;
        }
        return true;
    }
    bool read_single(double& ref) {
        std::string s;
        if (!read_single(s)) return false;
        ref = std::stod(s);
        return true;
    }
 
    template <class T,
              std::enable_if_t<std::is_same<T, char>::value>* = nullptr>
    bool read_single(T& ref) {
        if (!skip_space<50>()) return false;
        ref = top();
        st++;
        return true;
    }
 
    template <class T,
              internal::is_signed_int_t<T>* = nullptr,
              std::enable_if_t<!std::is_same<T, char>::value>* = nullptr>
    bool read_single(T& sref) {
        using U = internal::to_unsigned_t<T>;
        if (!skip_space<50>()) return false;
        bool neg = false;
        if (line[st] == '-') {
            neg = true;
            st++;
        }
        U ref = 0;
        do {
            ref = 10 * ref + (line[st++] & 0x0f);
        } while (line[st] >= '0');
        sref = neg ? -ref : ref;
        return true;
    }
    template <class U,
              internal::is_unsigned_int_t<U>* = nullptr,
              std::enable_if_t<!std::is_same<U, char>::value>* = nullptr>
    bool read_single(U& ref) {
        if (!skip_space<50>()) return false;
        ref = 0;
        do {
            ref = 10 * ref + (line[st++] & 0x0f);
        } while (line[st] >= '0');
        return true;
    }
 
    bool reread() {
        if (ed - st >= 50) return true;
        if (st > SIZE / 2) {
            std::memmove(line.data(), line.data() + st, ed - st);
            ed -= st;
            st = 0;
        }
        if (eof) return false;
        auto u = ::read(fd, line.data() + ed, SIZE - ed);
        if (u == 0) {
            eof = true;
            line[ed] = '\0';
            u = 1;
        }
        ed += int(u);
        line[ed] = char(127);
        return true;
    }
 
    char top() {
        if (st == ed) {
            bool f = reread();
            assert(f);
        }
        return line[st];
    }
 
    template <int TOKEN_LEN = 0>
    bool skip_space() {
        while (true) {
            while (line[st] <= ' ') st++;   
            if (ed - st > TOKEN_LEN) return true;
            if (st > ed) st = ed;
            for (auto i = st; i < ed; i++) {
                if (line[i] <= ' ') return true;
            }
            if (!reread()) return false;
        }
    }
};

//fast Output by ei1333
/**
 * @brief Printer(高速出力)
 */
struct Printer {
public:
  explicit Printer(FILE *fp) : fp(fp) {}

  ~Printer() { flush(); }

  template< bool f = false, typename T, typename... E >
  void write(const T &t, const E &... e) {
    if(f) write_single(' ');
    write_single(t);
    write< true >(e...);
  }

  template< typename... T >
  void writeln(const T &...t) {
    write(t...);
    write_single('\n');
  }

  void flush() {
    fwrite(line, 1, st - line, fp);
    st = line;
  }

private:
  FILE *fp = nullptr;
  static constexpr size_t line_size = 1 << 16;
  static constexpr size_t int_digits = 20;
  char line[line_size + 1] = {};
  char small[32] = {};
  char *st = line;

  template< bool f = false >
  void write() {}

  void write_single(const char &t) {
    if(st + 1 >= line + line_size) flush();
    *st++ = t;
  }

  template< typename T, enable_if_t< is_integral< T >::value, int > = 0 >
  void write_single(T s) {
    if(st + int_digits >= line + line_size) flush();
    if(s == 0) {
      write_single('0');
      return;
    }
    if(s < 0) {
      write_single('-');
      s = -s;
    }
    char *mp = small + sizeof(small);
    typename make_unsigned< T >::type y = s;
    size_t len = 0;
    while(y > 0) {
      *--mp = y % 10 + '0';
      y /= 10;
      ++len;
    }
    memmove(st, mp, len);
    st += len;
  }

  void write_single(const string &s) {
    for(auto &c : s) write_single(c);
  }

  void write_single(const char *s) {
    while(*s != 0) write_single(*s++);
  }

  template< typename T >
  void write_single(const vector< T > &s) {
    for(size_t i = 0; i < s.size(); i++) {
      if(i) write_single(' ');
      write_single(s[i]);
    }
  }
};

}; //namespace fastio
using mint=MontgomeryModInt<998244353>;
int main(){
    fastio::Scanner sc(stdin);
    fastio::Printer pr(stdout);
    #define in(...) sc.read(__VA_ARGS__)
    #define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
    #define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
    #define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
    #define out(...) pr.write(__VA_ARGS__)
    #define outln(...) pr.writeln(__VA_ARGS__)
    #define outspace(...) pr.write(__VA_ARGS__),pr.write(' ')
    #define rall(v) (v).rbegin(), (v).rend()
    #define fi first
    #define se second
    /*
         
    */
    INT(n,m);
    //自明な下界として、一番近い頂点の最大値がある
    //これを達成したい
    //例えばパスグラフなら、交互にやれば簡単に達成できる
    //ウニなら、真ん中でBにして残りはDとか
    //uから一番遠い頂点がvで、距離がmaxの時、uがBでvがDか、その逆
    //でも他でも基本的に交互を崩したくない
    //最小全域木上で交互に配置すれば、okじゃない?(適当がすぎるが、まあ実装もそこまでなのでやろう)
    //最短経路木と、どっちだ?うーん、どっちでも良さそうだしどっちも提出しよ。
    ll mx=0;
    Graph g(n);
    //MST G(n);
    FOR(i,m){
        LL(u,v,w);
        g[--u].push_back({--v,w});
        g[v].push_back({u,w});
        //G.add_edge(u,v,w);
    }
    FOR(v,n){
        ll tmp=INF;
        for(auto& [nv,cost]:g[v]){
            chmin(tmp,cost);
        }
        chmax(mx,tmp);
    }
    outln(mx);
    vector<ll> dist;
    vector<int> prev;
    Dijkstra(g,0,dist,prev);
    //FOR(i,n) outln(dist[i]);
    vector<vector<int>> t(n);
    FOR(i,n){
        if(prev[i]!=-1){
            t[i].push_back(prev[i]);
            t[prev[i]].push_back(i);
        }
        //outln(prev[i]);
    }
    vector<int> ans(n);
    auto slv=[&](auto rec,int v,int p,int cur)->void{
        ans[v]=cur;
        for(auto& nv:t[v]){
            if(nv==p) continue;
            rec(rec,nv,v,cur^1);
        }
    };
    slv(slv,0,-1,0);
    string Ans;
    FOR(i,n) if(ans[i]){
        Ans.push_back('B');
    }else{
        Ans.push_back('D');
    }
    outln(Ans);
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3712kb

input:

3 3
1 2 3
2 3 1
1 3 2

output:

2
DBB

result:

wrong answer your claimed answer is 2, but the inconveniences of your plan is actually 3

Subtask #2:

score: 13
Accepted

Test #11:

score: 13
Accepted
time: 72ms
memory: 90328kb

input:

500000 499999
1 2 776715136
2 3 406881694
3 4 265792290
4 5 507607272
5 6 182246639
6 7 997847597
7 8 164130256
8 9 278962226
9 10 411194641
10 11 363646402
11 12 672225656
12 13 494629089
13 14 717664153
14 15 121619271
15 16 476857704
16 17 301215244
17 18 810217743
18 19 850722975
19 20 10710274
...

output:

998789691
DBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDB...

result:

ok inconveniences = 998789691

Test #12:

score: 13
Accepted
time: 77ms
memory: 90328kb

input:

500000 499999
1 2 919029898
2 3 967926553
3 4 537841283
4 5 789574589
5 6 84356111
6 7 262979300
7 8 81760204
8 9 934833222
9 10 815362560
10 11 765318578
11 12 133878729
12 13 42184040
13 14 683417496
14 15 330426787
15 16 252037344
16 17 246808442
17 18 218647305
18 19 390164712
19 20 304437162
20...

output:

998086576
DBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDB...

result:

ok inconveniences = 998086576

Test #13:

score: 13
Accepted
time: 76ms
memory: 90328kb

input:

500000 499999
1 2 495717169
2 3 2736566
3 4 246490731
4 5 676348793
5 6 433656165
6 7 300871636
7 8 877832205
8 9 24348676
9 10 904055276
10 11 110426018
11 12 943185526
12 13 820883221
13 14 622560418
14 15 960692040
15 16 630347197
16 17 390849180
17 18 366668667
18 19 919683360
19 20 161247567
20...

output:

999027362
DBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDB...

result:

ok inconveniences = 999027362

Test #14:

score: 13
Accepted
time: 73ms
memory: 90320kb

input:

500000 499999
1 2 881926628
2 3 878365295
3 4 189444416
4 5 196764012
5 6 937066345
6 7 492929211
7 8 404162136
8 9 294189704
9 10 648590434
10 11 205708308
11 12 917107337
12 13 430038581
13 14 988914191
14 15 996853504
15 16 766772044
16 17 551967939
17 18 98588609
18 19 726003769
19 20 770678124
...

output:

998870338
DBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDB...

result:

ok inconveniences = 998870338

Test #15:

score: 13
Accepted
time: 68ms
memory: 90324kb

input:

500000 499999
1 2 275555710
2 3 928907994
3 4 351852867
4 5 739735339
5 6 757618705
6 7 186440113
7 8 817785536
8 9 958144538
9 10 65474464
10 11 881281553
11 12 537108380
12 13 419150600
13 14 786449308
14 15 645606967
15 16 757995051
16 17 9350371
17 18 413220186
18 19 856401635
19 20 774467299
20...

output:

998341670
DBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDB...

result:

ok inconveniences = 998341670

Test #16:

score: 13
Accepted
time: 78ms
memory: 90324kb

input:

500000 499999
1 2 2726164
2 3 814453419
3 4 77779202
4 5 212522091
5 6 575026293
6 7 111411302
7 8 671949780
8 9 598712779
9 10 513069672
10 11 622002136
11 12 606394125
12 13 554104755
13 14 693830694
14 15 464592249
15 16 176186577
16 17 170141847
17 18 84481371
18 19 18806105
19 20 887306486
20 2...

output:

998639500
DBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDB...

result:

ok inconveniences = 998639500

Test #17:

score: 13
Accepted
time: 69ms
memory: 90324kb

input:

500000 499999
1 2 699534547
2 3 756875816
3 4 650330256
4 5 385184303
5 6 252347359
6 7 572617046
7 8 54010889
8 9 947248022
9 10 691017140
10 11 281775875
11 12 804678960
12 13 796483137
13 14 721881104
14 15 799196727
15 16 932579324
16 17 778572034
17 18 156714181
18 19 173646893
19 20 854532026
...

output:

998386205
DBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDB...

result:

ok inconveniences = 998386205

Test #18:

score: 13
Accepted
time: 71ms
memory: 90296kb

input:

500000 499999
1 2 528281229
2 3 544813983
3 4 970327172
4 5 223929886
5 6 297537831
6 7 701582097
7 8 321477324
8 9 508501108
9 10 187475004
10 11 847549963
11 12 25037993
12 13 730505330
13 14 934227167
14 15 42350450
15 16 716244922
16 17 577182613
17 18 47412695
18 19 403130619
19 20 783335054
20...

output:

998268275
DBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDB...

result:

ok inconveniences = 998268275

Test #19:

score: 13
Accepted
time: 73ms
memory: 90324kb

input:

500000 499999
1 2 176647181
2 3 430435019
3 4 142683460
4 5 760806099
5 6 691983032
6 7 640928945
7 8 564806640
8 9 587621269
9 10 656576849
10 11 810001387
11 12 295415472
12 13 676473367
13 14 495893801
14 15 236356194
15 16 896384046
16 17 853257263
17 18 531811298
18 19 914837617
19 20 540207783...

output:

998100668
DBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDB...

result:

ok inconveniences = 998100668

Test #20:

score: 13
Accepted
time: 74ms
memory: 90128kb

input:

500000 499999
1 2 459441093
2 3 712179264
3 4 462698877
4 5 428755230
5 6 140982872
6 7 333359430
7 8 145590701
8 9 605794157
9 10 885201977
10 11 992315213
11 12 787968819
12 13 693140189
13 14 777613982
14 15 486848706
15 16 417423069
16 17 904399877
17 18 169733516
18 19 650464517
19 20 956947852...

output:

998576988
DBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBDB...

result:

ok inconveniences = 998576988

Subtask #3:

score: 18
Accepted

Dependency #2:

100%
Accepted

Test #21:

score: 18
Accepted
time: 378ms
memory: 76748kb

input:

500000 499999
1 498191 98644113
4 407741 285960522
9 2593 142219271
10 231716 692978475
11 281544 395541063
12 425498 656170589
13 383980 504747359
19 160252 266870005
21 153907 259282410
23 150872 408664227
24 364918 305130116
29 206272 807953223
32 114552 837969530
33 446658 296132297
34 445587 53...

output:

999999634
DDBDDDDDBDBBBBDBDBDBDBDBBBDBBDDBBDBBBDDBDDDDDDDDDDBBBDDDDBDDBDBDBBBDDBBBBDDDBDBBBDBDBDDDDBDBBBBDBBBDBBBBBDDDDDDBDBBBBDBDDDDDBBBDDBDDDDDBBBDDDDDDBBBDDBBBDDDDDBDDBDDDBBBBBDBDDBBDDBBDBBBDDBBDBBDDDDDBBDBDBDBDDBDDDDDDDBBDDBDBBBDDBDDBDDBBDBDBDBDDBDDBBBBBDBDDBDDBDBDBDBDBDDDDBBBBDBDDBBBBBBBBDBBBBD...

result:

ok inconveniences = 999999634

Test #22:

score: 18
Accepted
time: 379ms
memory: 76696kb

input:

500000 499999
1 298047 486034323
3 302455 15380870
10 112586 384710444
12 461380 106460032
15 400629 477739108
16 122191 944242040
19 140395 876468438
20 474471 54926698
21 247975 99912702
27 311759 304963895
29 201874 604590096
32 50134 964818840
34 52048 182700548
35 250795 19874383
38 296918 1736...

output:

999996272
DBBDDBDBBBDBDDBDBBBBDBDDDBBBDBBDBBDDBDDDBBDBBBDBBBBBBBDDBDBBDBBBBDDDDBDDBBDDDBBDDBDBBDDBDBDBBBDBDDDBDBDDBBDBDBBDBDDDDBDBBDDBDDDDBBBDDBBDBBBBBDDBBDBBDBBBBBDDDDDBBBBBDBDBBDBDDBBBBDDDBBBDDDBBDDBBBDBDBBDDDBDBBDDDBBDBDDDDDDDDBBBDBDBBBBDBDDBDDDBBBDDDBDDBDBDDBDDDDDDBDDDDBDBBBBBBBBBDDDBDBBDBBDBBDB...

result:

ok inconveniences = 999996272

Test #23:

score: 18
Accepted
time: 370ms
memory: 76744kb

input:

500000 499999
2 226958 733592075
3 282387 995489009
5 3289 914063619
7 440129 319619170
10 232251 411769136
15 43628 596243869
16 52374 374810745
24 21798 520964509
34 187883 248720052
35 17991 51962919
37 359348 832609079
42 101340 397779335
43 208881 996145582
44 4415 606734719
45 65727 142440494
...

output:

999998286
DBDBBDDDDBDDBDBBBBBBDDBBDBDDBBBBDDDDBDBBDBDBBDDBDDDBBBDBBDDDDBDBDDDBBDBDBDDBDBBDBDDDBBDDBDDBBBBDBDDDDDDDBDBBBBDBBDDBBBBDBBDBBBDDDDDDBBBDDBBDBDBBBDDBDBDBBBDBDDDDDBDBBDBBDDBBDBDBBDDBDBBBDDBDDDDDDBDBBBDBBDDBBBDBDBBBDDDBBBDDDDBDBBBBDDDDDDBDBBDDDDDBDBBDDBBDDDDBDBBDDBDBDBDBDBDDBDBDBDBBDDBDDBBDDB...

result:

ok inconveniences = 999998286

Test #24:

score: 18
Accepted
time: 380ms
memory: 76744kb

input:

500000 499999
1 195861 482944530
4 253474 607504910
6 499057 183478116
7 270968 191239
9 218955 878650354
11 395347 639963581
18 131956 561652195
20 83456 418951767
21 52587 414052939
26 293651 163591780
32 174307 880729517
34 443184 781843198
36 99016 683958976
40 405900 433342252
43 379684 4646270...

output:

999999321
DBBDDBBBDDBBBDDBDBBDBDDBBBDBBBDBDDBDDDBDDBBBDDDBBDBBDBDBDBDBDBDDDDDBBDDBBDBDBDDBBDBDDDDBBDDDBDDDDDDBDDBDBDDDBBBDBBDDBBBDDDBDDDBDDBBBBDBDBDBDDBBBDBDBDBDBBBDBDDDDDDDBBDDBBBDBDBDDBDBBDDDDDBDBDBDBBDDDDBBBBDBDDDDDBDDDDBBDDBDDBDDDDDDBDBBDBDBBBDBDDDDDBDBDDDDDDBDBBBBBBDBDBBBDBBBBBDBDBBDBBBBBBBBBBD...

result:

ok inconveniences = 999999321

Test #25:

score: 18
Accepted
time: 377ms
memory: 76756kb

input:

500000 499999
1 393184 586613362
4 340302 191769755
6 454461 697663107
8 116487 763378035
10 311098 323331823
11 271655 814032559
12 449238 759661861
13 489535 331502823
16 25411 976732072
23 180097 559693743
25 25359 850249966
26 352864 542643997
28 16841 296031371
30 472953 998957448
31 128349 210...

output:

999991572
DDBBDBBDDDDBDBBDDDDDBBBDBDDDBBBBBDDDDBDBDBBBDBBBBBDDDBDBBDDBDBDBBDBDDBBBDDBBDDDBBDBDDDDBDBBBDDDDDDDBDBBDDDBBDBDDBBBDBDBDBDBBBDBBDDBBBBDDDBDBDDBDBBBDDBBBBBDDBBBDDBBDDDBDDDDBBDBDDDDBBBBBDDBDDDBDDDDDDBDDDBBDBDBDDBBDDDDDDBDBBBBBDDBDDDDBBDBBDDDBBDBBDBBBDBDBBBBDBDBDDDBDBDDBDDBDDDDDBDBDBDDDDDBBBB...

result:

ok inconveniences = 999991572

Test #26:

score: 18
Accepted
time: 376ms
memory: 76740kb

input:

500000 499999
3 100372 223541239
4 428911 979162540
8 389796 555207091
9 18026 175154280
13 83459 757629595
14 318242 562687038
16 186332 56015539
19 450513 687421132
23 363524 355955464
28 19737 665996432
30 324384 78021621
33 82309 139756751
36 302313 309431714
37 25550 234897335
38 15923 59162388...

output:

999997771
DDBDDDDDBDBDDDBBBBBBBBDBDDBBBDDDDDBBDDDBBBDDBBBDDDDDDBBBBDBDBBBBBBBBDDBBBDDDBDBDDBBDDBDBBDBDBBBBDDBDBBDDDDBDBBBDBDDDBBDDDDBDBDDBBBDDDBBBDDDDDBDBBDBDBBDDDDBDBBBBBDDBBBDBBDBDBBBDDBBBBDBDBBDDDDBBBDDDBBDDDBDBDDBDBDBDBDDDDDDBBDDDBBBBBBBBBBBDDBBDBBDBDDBDDDBBDBBBDDDDDBDDBBDDDBDBBDBBBBDBBBBDDDBBDB...

result:

ok inconveniences = 999997771

Test #27:

score: 18
Accepted
time: 397ms
memory: 76760kb

input:

500000 499999
3 322399 938467174
5 294668 997432634
9 140349 749403173
13 156326 230666059
15 176904 584148575
18 462527 661616347
19 115932 915236576
20 40100 537230519
21 360684 923335513
22 478700 447133025
25 299737 154218322
28 413164 457095459
31 459296 293271135
32 200585 898724710
36 129428 ...

output:

999995080
DDDBDDDDBBBBDDDBDBDBBBBBBBDBDBBBBDDDDDBDBDDDBBBDDDDBBDDBDDBBDDDDDDBDBDDDBDBDDDDBDDDBBBDDDDBBBDBDBDDDDBDBDDDDDBDBDBDBBBBDBDBDDDDBDDDBDDBDDBBDBBDDBBDBDBDDDDDDBDBDDDBDDDBDDDDBBBDBDBBDBDBBDBBDBDDDDDDDDBBBBDDBDBDDBDBBBDBBBDDBBBBBBBDBBDBBDBDDDBBBDBDDDBDBDDDDBBDBDBBDDDDDDBBDDDDDBDDBDBBDDBBDBDDDBD...

result:

ok inconveniences = 999995080

Test #28:

score: 18
Accepted
time: 393ms
memory: 76720kb

input:

500000 499999
1 349448 695258814
3 413276 280795333
5 321286 908037219
13 407009 915549351
17 386773 804890068
21 39914 951119699
22 480150 163314795
25 134419 514390297
27 432990 814259581
29 335885 139743148
35 28324 612519155
36 43885 372504270
42 344828 8498457
48 449031 890534986
51 362532 6223...

output:

999998911
DDDDBDDBDDBDDBDDBDBDDDBBBDDDBDDDBBDDDDBBDBBDBDBBBBBDDBDBBBDDDBBBDDBDDDBDDDBBDDDBDBBBBBBBBBDDDBBDBBBBBDDDDDDBDDBDDDBBDDBBDBDDDDDBBBBBBBDBDBDBDDBBBBBDDDBDBBBDBDBBDBDBDDDBDBDBBDBDBBDDBDDDBDDDBBDDBBBDBDBDBBDDDBBDBDDDBBBDBBDBBDBDBDBBBDBDBDBDDBDDDBBBBDDDDDDDBBBBDDBBDBDDDDDDDBBBDBBBBDDDBDDDDBDDDD...

result:

ok inconveniences = 999998911

Test #29:

score: 18
Accepted
time: 397ms
memory: 76748kb

input:

500000 499999
2 10921 246329059
5 470731 878985801
7 160878 180062960
8 58099 756069772
10 475544 658632747
15 476775 199595606
21 95867 218826447
28 293838 603911187
29 268431 782740038
33 408755 673720382
37 490718 552334523
38 362775 747272214
40 283199 889096173
43 455689 72912274
50 213988 5215...

output:

999996361
DBBDDBBDDBDBDDBBBBDDDBDBDDDDDDDBBBDDDDBDDDDBBBDDDDBDDDDDBDDBBDDBDDDBDBDBDDBDBDDDDBDDDBDDBDBBBBBBBBBDDBDDDDDDDDDDDBBBBDDDDBDDBDDBBDBDDDDDBDBDBBBBBDDBBBDBBDDDBDBBBBBDBBBDBDDBBDBDBBDDBBDBBDDDBDBBDBDDDBBBDDDDDBBBDBDBDBDDDBDDBDBBBDBDBDBDDBBDDDBDDDBDDDDBBDDBBDDBDDDBBDDDBBDDBBDBBBDBDBDDBBBDBBBDBD...

result:

ok inconveniences = 999996361

Test #30:

score: 18
Accepted
time: 384ms
memory: 76764kb

input:

500000 499999
1 143758 557958489
4 395896 134647479
5 223284 982837565
6 152064 270356505
7 49367 458751900
12 408086 415638934
13 281677 430784294
17 199713 516686210
21 126232 368019079
24 121546 763498777
26 261239 623535252
32 460231 602594775
38 405662 735358912
40 122229 589490694
42 253737 23...

output:

999999181
DDBDDBBBDDDDBBBBBDBBBBDDBDBDDDBDDDDBBDBDBDDDDBBBDDDBDBBBDBBDDBBDBDDBBDBDDDDDDBDBDDDBDBBDBBBDBBDDBBDDBBBDBBDBDBBDBDBDBDBBDDDBBDBDDBDBDBDDDDBDBBDBBDBBDBBDDDDDBDDBDBBDDBBBBDBDBDBBBBDBDDBBDBDBBDBBBDBBDDDDDDBDBBDBDDDDBBBBDDDDBBBDBDBDDBBBBDDBDBDBBDBBBBBDBDDBBDDDDDBDBDDDDBBBDBDDBDBBBDBDDBBBBDBBBB...

result:

ok inconveniences = 999999181

Subtask #4:

score: 24
Accepted

Test #31:

score: 24
Accepted
time: 322ms
memory: 58380kb

input:

366489 397001
2 127909 1
7 171229 1
8 158597 1
11 282213 1
14 356007 1
15 286102 1
16 93205 1
17 260111 1
18 138962 1
20 359938 1
29 223905 1
31 357684 1
32 259968 1
34 65205 1
37 200276 1
41 83195 1
43 159858 1
48 332277 1
50 320322 1
51 338467 1
53 262785 1
55 83815 1
56 173198 1
58 169473 1
63 19...

output:

1
DBBBDBDDBDDBDBDDDBDBDDBBDBDBDDDDDDBDBDBDBDBBDBDBDDDBDDDDBDDDDDDBDDDDBDDBBDBDBDDBBBBBDBBBDDDBBDBBBDDDDBDDDDDBBBBDBBBBDBDDDDBDDDBBDBBDDDDDBDDDDBBDBBDDDBDDBBBBDBBDDBDBBBDDDDDBBBBDBDDBBBDBDDBBDDBDBDBBDDDBDBDBBDDBDDDBDDBBDDBDBDBDBDDBDBBDDDDDBDBDDDDBBDBDDDDDBDBBDBDDBDBDDDDDBBBBBBDDBBBBBBDDBBBDDDDBDDDBDB...

result:

ok inconveniences = 1

Test #32:

score: 24
Accepted
time: 432ms
memory: 73616kb

input:

475552 488952
2 161263 1
3 312211 1
5 41910 1
6 421865 1
7 340911 1
9 419906 1
10 468773 1
13 17837 1
18 465833 1
19 297766 1
21 234125 1
26 218984 1
28 296050 1
29 411520 1
30 38207 1
33 370786 1
34 21620 1
35 467168 1
40 136766 1
42 353240 1
44 194443 1
46 119022 1
48 23233 1
54 380603 1
60 99339 ...

output:

1
DBDDDDDDBBDBBDDDDBBBBDDBDDBBBBDDBBBDBBBDDBDDDBBDDBBDBDBDBDDDBDBBDBBBBBDBDBBDDBDDDDBDBDDDDBBBDDBBDDBBDBBBBDDDBDDDBBBDDBBBDBBDBBBBDDBBBBBBDDDBDDDBBBDBBBDDBBDDBDBBDBDDBBBDDDDDDBDDBDDBDDDBDDBDDBBDDBBBBBBDBBDDBBDDBBDBDDBBBDBDDBBDDDBDBBDDDBDDDDDDBDDDDBDDBBBBDBDBDDBBDDBBDDBDBBBBDDDDDBBDDBBDDBDDBDDDDDDBBD...

result:

ok inconveniences = 1

Test #33:

score: 24
Accepted
time: 80ms
memory: 22772kb

input:

128817 140020
2 53427 1
5 86824 1
6 33490 1
11 63864 1
14 109608 1
15 12909 1
16 45790 1
19 27271 1
22 54044 1
24 11063 1
32 53692 1
35 70034 1
38 84224 1
39 64068 1
43 72895 1
44 51948 1
45 40428 1
49 127824 1
50 52852 1
60 25795 1
61 105666 1
65 41013 1
67 97450 1
69 49349 1
71 47569 1
72 70751 1
...

output:

1
DDBDBBDDDBDDDBDDDDBBBBDBBDDBDBDDBDDDDDDDDDBBDDDDDDBDBDDBDBBDDDBBBDDBDBBDBDDBBDDDBDDBDDBDDDBDDBBBDDBBBDDDBBDBDBBDDDBBDBBDDDBBBDBDDDBBBDDDBBBBDDDDDBBDDDBDBDBBBDBBBDDDDBDBBBBDBDDBBDDBDDBDDBDBDDBDBDDDBDDDBBBBBBDBBBDDDBBDBBDBDBDBBDDDDDDBBDBDBBDBDBDDDDDDBBDBDDBBBBBDDBBBBDBBBDBBDBDDDDBDBBDDDBDDBDDDDDBBDD...

result:

ok inconveniences = 1

Test #34:

score: 24
Accepted
time: 252ms
memory: 48848kb

input:

299635 331829
5 197808 1
11 67054 1
12 84275 1
15 287112 1
16 274955 1
24 40825 1
30 266299 1
34 81379 1
35 99815 1
38 219853 1
42 189961 1
47 107895 1
48 137516 1
50 80614 1
54 264232 1
55 93625 1
62 143056 1
63 70844 1
64 72811 1
65 164091 1
68 248158 1
70 9821 1
72 156352 1
77 215022 1
81 270025 ...

output:

1
DBDBBBBDBBBDDDDDBBBDDBDDBBBBBDBBDDDDDBBBDBBDBBDBDBDBBDDDDBBDDBBDBBBDBBDBDDBDDDBBBDBDBBBBBBBDBDDDDDBBBBDDDBBBDBDDBBDDDDBBBDDDBBDDDDBBDDBBBBDDDDDDDBBBDBDDDBBBDBDDDBDDDBBDDBDBDDBDDDDDDDBBBDBDDDBBDDDBBBDDBDBDDDBBDBDBDBBBDDDBBDBBBDDDBBBBBBDDDBBBDBBBDDBDDDBDBDDBBDBDDDBDBDDBBDBBDBBBDBDBBBBBBDDDBDDBBBDBDD...

result:

ok inconveniences = 1

Test #35:

score: 24
Accepted
time: 335ms
memory: 61204kb

input:

369927 447544
1 150509 1
5 250257 1
6 149327 1
7 201307 1
15 330381 1
16 158914 1
18 99391 1
24 90164 1
25 199087 1
28 306199 1
32 83429 1
35 212184 1
36 29977 1
37 261629 1
44 99341 1
45 48378 1
51 130523 1
53 148929 1
58 77382 1
71 211093 1
72 305907 1
73 227420 1
75 188876 1
76 71437 1
79 354402 ...

output:

1
DBDDDBBBDDDDDBBDDBBDBBDBDDBBBDBDDDDDDDDDDDDDDDDDDBBDDDDBBBBBDBDDDBDDBBDDBBBDBDDDDDDBBBBDDBDBBDBBBDDDBDDDDBDBDBDBDDBBBDBBDBDDDBDDDDDBDDBDBBBBDDDDBBDBBDDBBDBDDBDBBDBBDBDBDBBDBBBDBDBBDBDBDBDBDBBDDDDBDBBBBBDDDBDBDBDDDDBDBDDDDBDDDBDBDBBDDBDDBBDBDBDBBBBDDBDBBBBBDDDBBBDBDDBDDDBDBBBBDBBBDBBDBBBDDDBBBBDBBB...

result:

ok inconveniences = 1

Test #36:

score: 24
Accepted
time: 389ms
memory: 76752kb

input:

500000 500000
4 319400 1
12 186157 1
13 443669 1
15 227339 1
19 101284 1
20 183604 1
23 273179 1
26 236933 1
27 79090 1
28 826 1
29 7574 1
31 370188 1
32 48463 1
34 113530 1
35 209157 1
46 13739 1
47 188127 1
48 97203 1
51 251724 1
52 469749 1
53 451782 1
56 249224 1
58 262324 1
60 380990 1
61 82320...

output:

1
DDDDBDDBDDBDDDDBDDBDDBBBDDDBDBDDBBBBDDDDBDDDBBBDBDDBBDDBDDDBDDDBBBDBDDBDDBDBBBBDBBDBBDBBBDBDDDBDDDBDBBDDDDDBDDBDBBDDBDBBDBDBBBDDDBBDBBBBBDBBDDBDDBBDBDBBDBBDBBDDBBBBBDDDDDDBBDBBBBBDBDDDBDDDBBBDDDBBDBDDDDBBDDBBDBDBBBBDDDBDBBDBBBDBBDBBBBDBBBDBBDDBBDDDDDBDDDBDBDBDDBBDDBBBDDDDBBDBDBBBBBBDBDBBDDBDBBDBDB...

result:

ok inconveniences = 1

Test #37:

score: 24
Accepted
time: 390ms
memory: 76616kb

input:

500000 500000
2 182927 1
5 313016 1
9 438269 1
10 97892 1
11 373266 1
13 314494 1
14 318813 1
20 102513 1
23 304478 1
24 162451 1
27 207273 1
30 182950 1
34 133161 1
35 62401 1
37 102023 1
38 19183 1
41 96619 1
42 264471 1
45 339682 1
46 60188 1
51 134306 1
53 85702 1
54 170539 1
55 74017 1
73 14900...

output:

1
DDDDBDDDDBBBBBDBDBDDDBDBDDBBDBBBDBBDDBBBDDBBBBBDBDDBDBBBDBDDDBBDDBBDBDBDBDDDBDBBDBBDBBBDDBDBBDDBDBBBDDBBDBDDDDBDBBDBBDDBDDBDBDBDBBBDDBBBDBDDDDBDBDBBDBDBDDDDDBBDBDBBDBBBDDBDDDBDDDDDDBBDDBBDDDBBDBBDBDBBBBDDDDBBDBBDBDBBBDBBDDBDBBDDDBBBBBDDBBBBBDBBDBDBBDBBDBDDDDDBBDDBBBDDDBBDBDDBBBBDBDBDBDDDDDDDBBBBDD...

result:

ok inconveniences = 1

Test #38:

score: 24
Accepted
time: 401ms
memory: 76740kb

input:

500000 500000
4 490349 1
5 377743 1
7 261998 1
14 410844 1
17 106150 1
20 477772 1
22 48037 1
24 388329 1
26 328805 1
28 248860 1
30 216330 1
34 479575 1
37 303722 1
38 392533 1
40 191119 1
42 177919 1
44 322555 1
45 306160 1
50 129452 1
51 215260 1
53 146880 1
56 441549 1
64 249852 1
69 422318 1
70...

output:

1
DBBBDBDBBDDBBBDBBBDBBDDDBDBBDDBDDBDDBDDBBDDDBBDDBBDDDDBBDDBDBBDBBDBDBBBBDDDBBBDBDDBBDBDDBBDBBDDBDBBDBBBDDDBDDBBBDBDDDBBDDDBDBDBBDDBBBBDDBDDDDDBBBBDDDBDBBDDBDDDBBBDBDDDBBBBBBBDBDDDDBDBDDDDDDBDBBDBDDDDBDBBBDBDDBBDBBDDDDBBBBBBDBDDDBBDDBDDBDBBBDDBDDDBDDBBDBDDDBBDBBDDDDBBBBBDBBDBDDBDBBBDBBBBBBBBBDBDBBD...

result:

ok inconveniences = 1

Test #39:

score: 24
Accepted
time: 386ms
memory: 76776kb

input:

500000 500000
9 213713 1
13 307012 1
14 327287 1
16 103990 1
23 409412 1
24 80587 1
25 91210 1
26 413674 1
28 167751 1
29 223056 1
31 395367 1
34 70127 1
38 344870 1
39 499865 1
40 91257 1
41 443805 1
43 109678 1
47 387825 1
49 328529 1
53 186674 1
59 197682 1
60 27560 1
61 402852 1
64 380750 1
66 1...

output:

1
DBBBBDDBBBDDBDDBBDDBBBBDBDDDDBDBDDDDBDBDDDBDBDDBBDBBDBDDBDBDDBBDBBBBBDBDBDBDDDDBDBBBDDBBDDDBBDBDDBBBBBDBBDDBBDDBBBBDBBDBDDBDBBDBBDDBBDDDDDBDBDDBDDBDDDBBDBDDDDBBBDBBBBDBBBDDBDBBDDBBBBBDBDBBBBBDDBDBBDDBBBBDDBBBBBBBBBDDDDDDBDBBBDBDDBDBBDDDDDDDDBDDBDDDBBBDBBBDBBBDDDDDDDBDBDDDBBBDDBDBBBBDBDBBBBDBBBDBDB...

result:

ok inconveniences = 1

Test #40:

score: 24
Accepted
time: 385ms
memory: 76652kb

input:

500000 500000
1 420147 1
2 70976 1
5 354943 1
6 261427 1
9 317379 1
11 31032 1
15 419781 1
16 155356 1
19 459807 1
25 72438 1
28 385731 1
30 19123 1
34 18208 1
35 332853 1
39 338723 1
41 356728 1
42 114047 1
44 389270 1
47 112208 1
48 23788 1
52 312381 1
57 317756 1
60 311741 1
61 218196 1
62 182171...

output:

1
DBDDBBBBBBDBDBDDDBBBDBBDDBBBDBBDBBDBDDDDBBDBBDBDBDBBDDDDBBDDBBBBBDBBBBDBBBDBDDDDBBBDBDBBBBDDDDDDDDDBDDBDDBDDDDBDBDBDBBDDDDBDDDBDBDBBBBBDBBBDDBBBBBDDDDDBBBBBBDDBDBDDDBDBDBBBBDBBBBDDDDDDDDDDDDDDDDDDDDBBBBBBBBBDDDBDDDBDDDBDDBDBDBDDDDBDBBDDDBDDDBDBBDDDBDDBDDBDDBBDDDBBDDBBBDDBDDBBBDDDDBDBDDDBBDDDBBBBDD...

result:

ok inconveniences = 1

Subtask #5:

score: 0
Skipped

Dependency #1:

0%