#858351 (C++17) No.1106 🦉 何事もバランスが大事

提出ソース
結果

問題	No.1106 🦉 何事もバランスが大事
ユーザー	hashiryo
提出日時	2023-04-10 23:22:59
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	4 ms / 2,000 ms
コード長	33,012 bytes
コンパイル時間	9,318 ms
コンパイル使用メモリ	383,364 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-10-06 10:41:57
合計ジャッジ時間	11,455 ms
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	3 ms 6,816 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,816 KB
testcase_13	AC	2 ms 6,820 KB
testcase_14	AC	3 ms 6,816 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	2 ms 6,816 KB
testcase_17	AC	2 ms 6,820 KB
testcase_18	AC	2 ms 6,820 KB
testcase_19	AC	2 ms 6,816 KB
testcase_20	AC	2 ms 6,816 KB
testcase_21	AC	2 ms 6,816 KB
testcase_22	AC	2 ms 6,820 KB
testcase_23	AC	3 ms 6,820 KB
testcase_24	AC	2 ms 6,820 KB
testcase_25	AC	2 ms 6,816 KB
testcase_26	AC	3 ms 6,816 KB
testcase_27	AC	3 ms 6,816 KB
testcase_28	AC	3 ms 6,816 KB
testcase_29	AC	3 ms 6,816 KB
testcase_30	AC	3 ms 6,816 KB
testcase_31	AC	3 ms 6,820 KB
testcase_32	AC	3 ms 6,816 KB
testcase_33	AC	3 ms 6,816 KB
testcase_34	AC	3 ms 6,816 KB
testcase_35	AC	3 ms 6,820 KB
testcase_36	AC	3 ms 6,820 KB
testcase_37	AC	3 ms 6,816 KB
testcase_38	AC	3 ms 6,816 KB
testcase_39	AC	3 ms 6,816 KB
testcase_40	AC	3 ms 6,820 KB
testcase_41	AC	3 ms 6,824 KB
testcase_42	AC	3 ms 6,820 KB
testcase_43	AC	3 ms 6,820 KB
testcase_44	AC	3 ms 6,816 KB
testcase_45	AC	4 ms 6,816 KB
testcase_46	AC	3 ms 6,816 KB
testcase_47	AC	3 ms 6,820 KB
testcase_48	AC	3 ms 6,820 KB
testcase_49	AC	3 ms 6,820 KB
testcase_50	AC	3 ms 6,816 KB
testcase_51	AC	3 ms 6,820 KB
testcase_52	AC	3 ms 6,816 KB
testcase_53	AC	3 ms 6,816 KB
testcase_54	AC	3 ms 6,816 KB
testcase_55	AC	3 ms 6,816 KB
testcase_56	AC	3 ms 6,820 KB
testcase_57	AC	3 ms 6,816 KB
testcase_58	AC	3 ms 6,820 KB
testcase_59	AC	4 ms 6,816 KB
testcase_60	AC	3 ms 6,816 KB
testcase_61	AC	3 ms 6,820 KB
testcase_62	AC	4 ms 6,816 KB
testcase_63	AC	3 ms 6,816 KB
testcase_64	AC	3 ms 6,816 KB
testcase_65	AC	2 ms 6,816 KB
testcase_66	AC	3 ms 6,816 KB
testcase_67	AC	3 ms 6,816 KB
testcase_68	AC	4 ms 6,816 KB
testcase_69	AC	3 ms 6,816 KB
testcase_70	AC	4 ms 6,816 KB
testcase_71	AC	4 ms 6,820 KB
testcase_72	AC	3 ms 6,816 KB
testcase_73	AC	3 ms 6,816 KB
testcase_74	AC	4 ms 6,820 KB
testcase_75	AC	3 ms 6,816 KB
testcase_76	AC	3 ms 6,816 KB
testcase_77	AC	3 ms 6,820 KB
testcase_78	AC	3 ms 6,820 KB
testcase_79	AC	3 ms 6,816 KB
testcase_80	AC	3 ms 6,820 KB
testcase_81	AC	2 ms 6,816 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}

#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
#ifdef __LOCAL
// clang-format off
#undef checkpoint
#undef debug
#undef debugArray
#undef debugMatrix
template<class T, class U>std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&x){return os<<"("<<x.first<<", "<<x.second<<")";}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::vector<T>&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<<vec[_];return os<<']';}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::set<T>&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<<x; return os << '}';}
template<typename T,std::size_t _Nm>std::ostream&operator<<(std::ostream &os,const std::array<T, _Nm> &arr) {os<<'['<<arr[0];for(std::size_t _=1;_<_Nm;++_)os<<", "<<arr[_];return os<<']';}
template<class Tup,std::size_t... I>void print(std::ostream&os,const Tup &x,std::index_sequence<I...>){(void)(int[]){(os<<std::get<I>(x)<<", ",0)...};}
template<class... Args>std::ostream &operator<<(std::ostream&os,const std::tuple<Args...> &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence<N-1>());return os<<std::get<N-1>(x)<<")";}
const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m";
#define func_LINE_FILE  NORMAL_FAINT<<" in "<<BOLD<<__func__<<NORMAL_FAINT<<ITALIC<<" (L"<<__LINE__<<") "<< __FILE__<<COLOR_RESET
#define checkpoint() std::cerr<<BRIGHT_RED<<"< check point! >"<<func_LINE_FILE<<'\n'
#define debug(x) std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<func_LINE_FILE<<'\n'
#define debugArray(x, n) do{std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = ["<<x[0];for(int _=1;_<(int)(n);++_)std::cerr<<", "<<x[_];std::cerr<<"]"<<func_LINE_FILE<<'\n';}while(0)
#define debugMatrix(x, h, w) do{std::cerr<<BRIGHT_CYAN<<#x<<"\n"<<COLOR_RESET<<"= ";for(int _=0;(_)<(int)(h);++_){std::cerr<<((_?"   [":"[["));for(int __=0;__<(int)(w);++__)std::cerr<<((__?", ":""))<<x[_][__];std::cerr<<"]"<<(_+1==(int)(h)?"]":",\n");}std::cerr<<func_LINE_FILE<<'\n';}while(0)
#endif
// clang-format on

#include <type_traits>
#include <cassert>
template <class Int> constexpr inline Int mod_inv(Int a, Int mod) {
 static_assert(std::is_signed_v<Int>);
 Int x= 1, y= 0, b= mod;
 for (Int q= 0, z= 0, c= 0; b;) z= x, c= a, x= y, y= z - y * (q= a / b), a= b, b= c - b * q;
 return assert(a == 1), x < 0 ? mod - (-x) % mod : x % mod;
}
namespace math_internal {
using namespace std;
using u8= uint8_t;
using u32= uint32_t;
using u64= uint64_t;
using i64= int64_t;
using u128= __uint128_t;
#define CE constexpr
#define IL inline
#define NORM \
 if (n >= mod) n-= mod; \
 return n
#define PLUS(U, M) \
 CE IL U plus(U l, U r) const { \
  if (l+= r; l >= M) l-= M; \
  return l; \
 }
#define DIFF(U, C, M) \
 CE IL U diff(U l, U r) const { \
  if (l-= r; l >> C) l+= M; \
  return l; \
 }
#define SGN(U) \
 static CE IL U set(U n) { return n; } \
 static CE IL U get(U n) { return n; } \
 static CE IL U norm(U n) { return n; }
template <class u_t, class du_t, u8 B, u8 A> struct MP_Mo {
 u_t mod;
 CE MP_Mo(): mod(0), iv(0), r2(0) {}
 CE MP_Mo(u_t m): mod(m), iv(inv(m)), r2(-du_t(mod) % mod) {}
 CE IL u_t mul(u_t l, u_t r) const { return reduce(du_t(l) * r); }
 PLUS(u_t, mod << 1)
 DIFF(u_t, A, mod << 1)
 CE IL u_t set(u_t n) const { return mul(n, r2); }
 CE IL u_t get(u_t n) const {
  n= reduce(n);
  NORM;
 }
 CE IL u_t norm(u_t n) const { NORM; }
private:
 u_t iv, r2;
 static CE u_t inv(u_t n, int e= 6, u_t x= 1) { return e ? inv(n, e - 1, x * (2 - x * n)) : x; }
 CE IL u_t reduce(const du_t &w) const { return u_t(w >> B) + mod - ((du_t(u_t(w) * iv) * mod) >> B); }
};
struct MP_Na {
 u32 mod;
 CE MP_Na(): mod(0){};
 CE MP_Na(u32 m): mod(m) {}
 CE IL u32 mul(u32 l, u32 r) const { return u64(l) * r % mod; }
 PLUS(u32, mod) DIFF(u32, 31, mod) SGN(u32)
};
struct MP_Br {  // mod < 2^31
 u32 mod;
 CE MP_Br(): mod(0), s(0), x(0) {}
 CE MP_Br(u32 m): mod(m), s(31 - __builtin_clz(m - 1) + 64), x(((u128(1) << s) + m - 1) / m) {}
 CE IL u32 mul(u32 l, u32 r) const { return rem(u64(l) * r); }
 PLUS(u32, mod) DIFF(u32, 31, mod) SGN(u32) private: u8 s;
 u64 x;
 CE IL u64 quo(u64 n) const { return (u128(x) * n) >> s; }
 CE IL u32 rem(u64 n) const { return n - quo(n) * mod; }
};
struct MP_Br2 {  // 2^20 < mod <= 2^41
 u64 mod;
 CE MP_Br2(): mod(0), x(0) {}
 CE MP_Br2(u64 m): mod(m), x((u128(1) << 84) / m) {}
 CE IL u64 mul(u64 l, u64 r) const { return rem(u128(l) * r); }
 PLUS(u64, mod << 1)
 DIFF(u64, 63, mod << 1)
 static CE IL u64 set(u64 n) { return n; }
 CE IL u64 get(u64 n) const { NORM; }
 CE IL u64 norm(u64 n) const { NORM; }
private:
 u64 x;
 CE IL u128 quo(const u128 &n) const { return (n * x) >> 84; }
 CE IL u64 rem(const u128 &n) const { return n - quo(n) * mod; }
};
struct MP_D2B1 {
 u8 s;
 u64 mod, d, v;
 CE MP_D2B1(): s(0), mod(0), d(0), v(0) {}
 CE MP_D2B1(u64 m): s(__builtin_clzll(m)), mod(m), d(m << s), v(u128(-1) / d) {}
 CE IL u64 mul(u64 l, u64 r) const { return rem((u128(l) * r) << s) >> s; }
 PLUS(u64, mod) DIFF(u64, 63, mod) SGN(u64) private: CE IL u64 rem(const u128 &u) const {
  u128 q= (u >> 64) * v + u;
  u64 r= u64(u) - (q >> 64) * d - d;
  if (r > u64(q)) r+= d;
  if (r >= d) r-= d;
  return r;
 }
};
template <class u_t, class MP> CE u_t pow(u_t x, u64 k, const MP &md) {
 for (u_t ret= md.set(1);; x= md.mul(x, x))
  if (k & 1 ? ret= md.mul(ret, x) : 0; !(k>>= 1)) return ret;
}
#undef NORM
#undef PLUS
#undef DIFF
#undef SGN
#undef CE
}
namespace math_internal {
#define CE constexpr
struct m_b {};
struct s_b: m_b {};
template <class mod_t> CE bool is_modint_v= is_base_of_v<m_b, mod_t>;
template <class mod_t> CE bool is_staticmodint_v= is_base_of_v<s_b, mod_t>;
template <class MP, u64 MOD> struct SB: s_b {
protected:
 static CE MP md= MP(MOD);
};
template <class Int, class U, class B> struct MInt: public B {
 using Uint= U;
 static CE inline auto mod() { return B::md.mod; }
 CE MInt(): x(0) {}
 CE MInt(const MInt &r): x(r.x) {}
 template <class T, enable_if_t<is_modint_v<T>, nullptr_t> = nullptr> CE MInt(T v): x(B::md.set(v.val() % B::md.mod)) {}
 template <class T, enable_if_t<is_convertible_v<T, __int128_t>, nullptr_t> = nullptr> CE MInt(T n): x(B::md.set((n < 0 ? ((n= (-n) % B::md.mod) ? B::md.mod - n : n) : n % B::md.mod))) {}
 CE MInt operator-() const { return MInt() - *this; }
#define FUNC(name, op) \
 CE MInt name const { \
  MInt ret; \
  ret.x= op; \
  return ret; \
 }
 FUNC(operator+(const MInt &r), B::md.plus(x, r.x))
 FUNC(operator-(const MInt &r), B::md.diff(x, r.x))
 FUNC(operator*(const MInt &r), B::md.mul(x, r.x))
 FUNC(pow(u64 k), math_internal::pow(x, k, B::md))
#undef FUNC
 CE MInt operator/(const MInt &r) const { return *this * r.inv(); }
 CE MInt &operator+=(const MInt &r) { return *this= *this + r; }
 CE MInt &operator-=(const MInt &r) { return *this= *this - r; }
 CE MInt &operator*=(const MInt &r) { return *this= *this * r; }
 CE MInt &operator/=(const MInt &r) { return *this= *this / r; }
 CE bool operator==(const MInt &r) const { return B::md.norm(x) == B::md.norm(r.x); }
 CE bool operator!=(const MInt &r) const { return !(*this == r); }
 CE bool operator<(const MInt &r) const { return B::md.norm(x) < B::md.norm(r.x); }
 CE inline MInt inv() const { return mod_inv<Int>(val(), B::md.mod); }
 CE inline Uint val() const { return B::md.get(x); }
 friend ostream &operator<<(ostream &os, const MInt &r) { return os << r.val(); }
 friend istream &operator>>(istream &is, MInt &r) {
  i64 v;
  return is >> v, r= MInt(v), is;
 }
private:
 Uint x;
};
template <u64 MOD> using ModInt= conditional_t < (MOD < (1 << 30)) & MOD, MInt<int, u32, SB<MP_Mo<u32, u64, 32, 31>, MOD>>, conditional_t < (MOD < (1ull << 62)) & MOD, MInt<i64, u64, SB<MP_Mo<u64, u128, 64, 63>, MOD>>, conditional_t<MOD<(1u << 31), MInt<int, u32, SB<MP_Na, MOD>>, conditional_t<MOD<(1ull << 32), MInt<i64, u32, SB<MP_Na, MOD>>, conditional_t<MOD <= (1ull << 41), MInt<i64, u64, SB<MP_Br2, MOD>>, MInt<i64, u64, SB<MP_D2B1, MOD>>>>>>>;
#undef CE
}
using math_internal::ModInt, math_internal::is_modint_v, math_internal::is_staticmodint_v;
template <class mod_t, size_t LM> mod_t get_inv(int n) {
 static_assert(is_modint_v<mod_t>);
 static const auto m= mod_t::mod();
 static mod_t dat[LM];
 static int l= 1;
 if (l == 1) dat[l++]= 1;
 while (l <= n) dat[l++]= dat[m % l] * (m - m / l);
 return dat[n];
}
template <class symbol_t> class Automaton {
 std::vector<int> table;
 std::vector<int8_t> info;
 std::vector<symbol_t> alph;
 const int m;
 template <template <class, class> class Map, class state_t, class F, class G, class H> void build(const state_t &initial_state, const F &transition, const G &is_accept, const H &abs_reject) {
  static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);
  static_assert(std::is_same_v<bool, std::invoke_result_t<H, state_t>>);
  Map<state_t, int> encode;
  std::vector<state_t> decode;
  int ts= 0;
  decode.push_back(initial_state), encode.emplace(initial_state, ts++);
  for (int i= 0, k= 0; i < ts; ++i) {
   auto s= decode[i];
   table.resize(table.size() + m);
   for (int j= 0; j < m; ++j) {
    if (auto t= transition(s, j); abs_reject(t)) table[k++]= -1;
    else if (auto it= encode.find(t); it != encode.end()) table[k++]= it->second;
    else table[k++]= ts, decode.push_back(t), encode.emplace(t, ts++);
   }
  }
  info.resize(ts);
  for (int i= ts; i--;) info[i]= is_accept(decode[i]);
 }
 Automaton(const std::vector<symbol_t> &alphabet): alph(alphabet), m(alph.size()) {}
public:
 template <class state_t, class F, class G, std::enable_if_t<std::is_same_v<state_t, std::invoke_result_t<F, state_t, symbol_t>>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept): alph(alphabet), m(alph.size()) {
  std::sort(alph.begin(), alph.end());
  auto tr= [&](const state_t &s, int i) { return transition(s, alph[i]); };
  if constexpr (std::is_integral_v<state_t>) build<std::unordered_map>(initial_state, tr, is_accept, [](const state_t &) { return false; });
  else build<std::map>(initial_state, tr, is_accept, [](const state_t &) { return false; });
 }
 template <class state_t, class F, class G, std::enable_if_t<std::is_same_v<state_t, std::invoke_result_t<F, state_t, symbol_t>>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept, const state_t &abs_rej_state): alph(alphabet), m(alph.size()) {
  std::sort(alph.begin(), alph.end());
  auto tr= [&](const state_t &s, int i) { return transition(s, alph[i]); };
  if constexpr (std::is_integral_v<state_t>) build<std::unordered_map>(initial_state, tr, is_accept, [abs_rej_state](const state_t &s) { return s == abs_rej_state; });
  else build<std::map>(initial_state, tr, is_accept, [abs_rej_state](const state_t &s) { return s == abs_rej_state; });
 }
 template <class state_t, class F, class G, std::enable_if_t<std::is_same_v<std::set<state_t>, std::invoke_result_t<F, state_t, symbol_t>>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept): alph(alphabet), m(alph.size()) {
  static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);
  std::sort(alph.begin(), alph.end());
  auto tr= [&](const std::set<state_t> &s, int i) {
   std::set<state_t> ret;
   for (const auto &x: s) {
    auto ys= transition(x, alph[i]);
    ret.insert(ys.begin(), ys.end());
   }
   return ret;
  };
  auto ac= [&](const std::set<state_t> &s) { return std::any_of(s.begin(), s.end(), is_accept); };
  build<std::map>(std::set<state_t>({initial_state}), tr, ac, [](const std::set<state_t> &s) { return s == std::set<state_t>(); });
 }
 template <class state_t, class F, class G, class H, std::enable_if_t<std::is_same_v<std::set<state_t>, std::invoke_result_t<F, state_t, symbol_t>>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept, const H &eps_trans): alph(alphabet), m(alph.size()) {
  static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);
  static_assert(std::is_same_v<std::set<state_t>, std::invoke_result_t<H, state_t>>);
  std::sort(alph.begin(), alph.end());
  auto eps_closure= [&](std::set<state_t> s) {
   for (std::set<state_t> t; s != t;) {
    t= s;
    for (const auto &x: t) {
     auto ys= eps_trans(x);
     s.insert(ys.begin(), ys.end());
    }
   }
   return s;
  };
  auto tr= [&](const std::set<state_t> &s, int i) {
   std::set<state_t> ret;
   for (const auto &x: s) {
    auto ys= transition(x, alph[i]);
    ret.insert(ys.begin(), ys.end());
   }
   return eps_closure(ret);
  };
  auto ac= [&](const std::set<state_t> &s) { return std::any_of(s.begin(), s.end(), is_accept); };
  build<std::map>(eps_closure({initial_state}), tr, ac, [](const std::set<state_t> &s) { return s == std::set<state_t>(); });
 }
 size_t alphabet_size() const { return m; }
 Automaton operator&(const Automaton &r) const {
  assert(alph == r.alph);
  const int S= info.size();
  auto tr= [&](int s, int q) {
   auto [s1, s0]= std::div(s, S);
   int t1= r.table[s1 * m + q], t0= table[s0 * m + q];
   return t0 == -1 || t1 == -1 ? -1 : t1 * S + t0;
  };
  auto ac= [&](int s) {
   auto [s1, s0]= std::div(s, S);
   return info[s0] == 1 && r.info[s1] == 1;
  };
  Automaton ret(alph);
  return ret.build<std::unordered_map>(0, tr, ac, [](int s) { return s == -1; }), ret;
 }
 template <class T, class A, class F> T dp_run(int n, const A &op, const T &ti, const F &f, const T &init) const {
  static_assert(std::is_same_v<T, std::invoke_result_t<A, T, T>>);
  static_assert(std::is_same_v<T, std::invoke_result_t<F, T, symbol_t, int>>);
  const size_t S= info.size();
  std::queue<std::pair<int, int>> que;
  T dp[2][S], ret= ti;
  bool in[2][S];
  for (std::fill_n(dp[0], S, ti), std::fill_n(dp[1], S, ti), std::fill_n(in[0], S, 0), std::fill_n(in[1], S, 0), dp[0][0]= init, que.emplace(0, 0), in[0][0]= 1; que.size();) {
   auto [s, i]= que.front();
   bool b= i & 1;
   T tmp= dp[b][s];
   if (que.pop(), in[b][s]= 0, dp[b][s]= ti; i == n) {
    if (info[s] == 1) ret= op(ret, tmp);
    continue;
   }
   auto l= table.cbegin() + s * m;
   for (int j= m; j--;)
    if (int t= l[j]; t != -1)
     if (dp[!b][t]= op(dp[!b][t], f(tmp, alph[j], i)); !in[!b][t]) que.emplace(t, i + 1), in[!b][t]= 1;
  }
  return ret;
 }
 template <class T> T num(int n) const {
  return dp_run(
      n, [](const T &l, const T &r) { return l + r; }, T(), [](const T &x, const auto &, auto) { return x; }, T(1));
 }
};
using namespace std;
// https://atcoder.jp/contests/abc235/tasks/abc235_f
namespace ABC235F {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using Mint= ModInt<998244353>;
 string N;
 int M;
 cin >> N >> M;
 int n= N.length();
 int c= 0;
 for (int i= 0; i < M; i++) {
  int C;
  cin >> C, c|= 1 << C;
 }
 std::vector<int> alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 auto tr0= [&](int s, int q) {
  if (s >= n) return s;
  int c= N[s] - '0';
  if (q > c) return n + 1;
  if (q < c) return n;
  return s + 1;
 };
 auto ac0= [&](int s) { return s == n; };
 Automaton dfa_le(alp, 0, tr0, ac0, n + 1);
 auto tr1= [&](int s, int q) { return s | ((q || s) << q); };
 auto ac1= [&](int s) { return (s & c) == c; };
 Automaton dfa_variety(alp, 0, tr1, ac1);
 auto dfa= dfa_le & dfa_variety;
 using T= array<Mint, 2>;
 auto op= [](const T &l, const T &r) { return T{l[0] + r[0], l[1] + r[1]}; };
 auto f= [](const T &v, int a, int) { return T{v[0] * 10 + v[1] * a, v[1]}; };
 cout << dfa.dp_run(n, op, T{0, 0}, f, T{0, 1})[0] << '\n';
 return 0;
}
}  // namespace ABC235F
// https://atcoder.jp/contests/agc015/tasks/agc015_d
namespace AGC015D {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 vector alphabet= {0, 1};
 using state_t= set<pair<int64_t, int64_t>>;
 auto tr= [&](const state_t &S, int c) -> set<state_t> {
  set<state_t> ret;
  if (c == 0) {
   state_t T;
   bool isok= true;
   for (auto [a, b]: S) {
    if (a= (a + 1) / 2, b/= 2; a > b) {
     isok= false;
     break;
    }
    T.emplace(a, b);
   }
   if (isok) ret.insert(T);
  } else {
   int sz= S.size();
   for (int s= 1 << sz; --s;)
    for (int t= s;; --t&= s) {
     state_t T;
     bool isok= true;
     auto it= S.cbegin();
     for (int j= sz; j--; ++it) {
      auto [a, b]= *it;
      auto a0= (a + 1) / 2, b0= b / 2;
      auto a1= a / 2, b1= (b + 1) / 2 - 1;
      if ((t >> j) & 1) {
       if (a0 > b0 || a1 > b1) {
        isok= false;
        break;
       }
       T.emplace(a0, b0), T.emplace(a1, b1);
      } else if ((s >> j) & 1) {
       if (a1 > b1) {
        isok= false;
        break;
       }
       T.emplace(a1, b1);
      } else {
       if (a0 > b0) {
        isok= false;
        break;
       }
       T.emplace(a0, b0);
      }
     }
     if (isok) ret.insert(T);
     if (!t) break;
    }
  }
  return ret;
 };
 int64_t A, B;
 cin >> A >> B;
 Automaton nfa(alphabet, state_t({{A, B}}), tr, [](const auto &) { return true; });
 cout << nfa.num<int64_t>(60) << '\n';
 return 0;
}
}  // namespace AGC015D
// https://atcoder.jp/contests/abc050/tasks/arc066_b
namespace ARC066B {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Mint= ModInt<int(1e9 + 7)>;
 using symbol_t= array<bool, 2>;
 vector<symbol_t> alp= {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
 using state_t= int64_t;
 auto tr0= [&](state_t s, symbol_t c) {
  if (c[0] == 0) return s / 2;
  else return (s + 1) / 2 - 1;
 };
 auto tr1= [&](state_t s, symbol_t c) {
  if (c[1] == 0) return s / 2;
  else return (s + 1) / 2 - 1;
 };
 int64_t N;
 cin >> N;
 Automaton dfa_le0(
     alp, N, tr0, [&](int64_t) { return true; }, state_t(-1));
 Automaton dfa_le1(
     alp, N, tr1, [&](int64_t) { return true; }, state_t(-1));
 auto tr= [&](int s, symbol_t c) {
  set<int> ret;
  for (int a= 2; a--;)
   for (int b= 2; b--;)
    if ((a ^ b) == c[0] && ((a + b + s) & 1) == c[1]) ret.insert((a + b + s) / 2);
  return ret;
 };
 Automaton nfa(alp, 0, tr, [&](int s) { return s == 0; });
 auto dfa= dfa_le0 & dfa_le1 & nfa;
 cout << dfa.num<Mint>(60) << '\n';
 return 0;
}
}
// https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Prelim/2587
namespace AOJ_2587 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N;
 vector<int> low, high;
 vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 while (cin >> N && N != 0) {
  low.resize(N), high.resize(N);
  for (int i= 0; i < N; ++i) cin >> low[i] >> high[i];
  using state_t= array<int, 2>;
  auto tr= [&](state_t s, int c) -> set<state_t> {
   auto [i, j]= s;
   if (i >= N) return {};
   auto [l1, l0]= div(low[i], 10);
   auto [h1, h0]= div(high[i], 10);
   if (j == 1) {
    if (l0 <= c) return {{i + 1, 0}};
   } else if (j == 2) return {{i + 1, 0}};
   else if (j == 3) {
    if (c <= h0) return {{i + 1, 0}};
   } else if (j == 4) {
    if (l0 <= c && c <= h0) return {{i + 1, 0}};
   } else {
    if (c == 0) return {};
    if (l1 == h1) {
     if (c == l1) return {{i, 4}};
    } else {
     if (c == l1) return {{i, 1}};
     if (l1 < c && c < h1) return {{i, 2}};
     if (c == h1) return {{i, 3}};
    }
   }
   return {};
  };
  auto eps= [&](state_t s) -> set<state_t> {
   auto [i, j]= s;
   if (i >= N) return {};
   if (j == 0 && (low[i] / 10) == 0) {
    if ((high[i] / 10) == 0) return {{i, 4}};
    else return {{i, 1}};
   }
   return {};
  };
  auto ac= [&](state_t s) { return s[0] == N && s[1] == 0; };
  Automaton nfa(alp, state_t{0, 0}, tr, ac, eps);
  int64_t ans= 0;
  for (int i= N; i <= 2 * N; ++i) ans+= nfa.num<int64_t>(i);
  cout << ans << '\n';
 }
 return 0;
}
}  // namespace AOJ_2587
// https://onlinejudge.u-aizu.ac.jp/problems/0570
namespace AOJ_0570 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Mint= ModInt<10000>;
 string A, B;
 cin >> A >> B;
 int M;
 cin >> M;
 int n= B.length();
 A= string(n - A.length(), '0') + A;
 vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 auto tr_a= [&](int s, int c) {
  if (s >= n) return s;
  int d= A[s] - '0';
  if (c < d) return n + 1;
  if (c > d) return n;
  return s + 1;
 };
 auto tr_b= [&](int s, int c) {
  if (s >= n) return s;
  int d= B[s] - '0';
  if (c > d) return n + 1;
  if (c < d) return n;
  return s + 1;
 };
 auto ac0= [&](int s) { return s == n; };
 Automaton dfa_a(alp, 0, tr_a, ac0, n + 1), dfa_b(alp, 0, tr_b, ac0, n + 1);
 auto tr_m= [&](int s, int c) { return (s * 10 + c) % M; };
 Automaton dfa_m(alp, 0, tr_m, [](int s) { return s == 0; });
 using state_t= array<int, 2>;
 auto tr_zz= [&](state_t s, int c) -> state_t {
  auto [d, t]= s;
  if (d == -2) {
   if (c == 0) return {-2, -2};
   else return {c, -2};
  }
  if (d == c) return {-1, -1};
  if (t == -2) return {c, d < c};
  if (d < c) {
   if (t == 1) return {-1, -1};
   else return {c, 1};
  } else {
   if (t == 0) return {-1, -1};
   else return {c, 0};
  }
  return {-1, -1};
 };
 Automaton dfa_zz(
     alp, state_t{-2, -2}, tr_zz, [](state_t) { return true; }, state_t{-1, -1});

 debug(dfa_zz.num<Mint>(n));
 debug((dfa_a & dfa_b).num<Mint>(n));
 debug((dfa_a & dfa_b & dfa_m).num<Mint>(n));
 auto dfa= dfa_a & dfa_b & dfa_m & dfa_zz;
 cout << dfa.num<Mint>(n) << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/315
namespace yukicoder_315 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Mint= ModInt<int(1e9 + 7)>;
 string A, B;
 cin >> A >> B;
 int P;
 cin >> P;
 vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 int n_a= A.length(), n_b= B.length();
 for (int i= n_a; i--;) {
  if (A[i] > '0') {
   --A[i];
   break;
  }
  A[i]= '9';
 }
 auto tr_a= [&](int s, int c) {
  if (s >= n_a) return s;
  int d= A[s] - '0';
  if (c < d) return n_a;
  if (c > d) return n_a + 1;
  return s + 1;
 };
 auto tr_b= [&](int s, int c) {
  if (s >= n_b) return s;
  int d= B[s] - '0';
  if (c < d) return n_b;
  if (c > d) return n_b + 1;
  return s + 1;
 };
 auto ac_a= [&](int s) { return s == n_a; };
 auto ac_b= [&](int s) { return s == n_b; };
 Automaton dfa_a(alp, 0, tr_a, ac_a, n_a + 1), dfa_b(alp, 0, tr_b, ac_b, n_b + 1);
 auto tr_3= [&](int s, int c) {
  if (s == -1 || c == 3) return -1;
  return (s + c) % 3;
 };
 Automaton dfa_3(alp, 0, tr_3, [](int s) { return s <= 0; });
 auto dfa1= dfa_a & dfa_3;
 auto dfa2= dfa_b & dfa_3;
 Mint ans= dfa2.num<Mint>(n_b) - dfa1.num<Mint>(n_a);
 while (P % 10 == 0) P/= 10, --n_a, --n_b;
 Automaton dfa_a2(alp, 0, tr_a, ac_a, n_a + 1), dfa_b2(alp, 0, tr_b, ac_b, n_b + 1);
 auto tr_P= [&](int s, int c) { return (s * 10 + c) % P; };
 Automaton dfa_P(alp, 0, tr_P, [](int s) { return s == 0; });
 auto dfa3= dfa_a2 & dfa_3 & dfa_P;
 auto dfa4= dfa_b2 & dfa_3 & dfa_P;
 ans-= dfa4.num<Mint>(n_b) - dfa3.num<Mint>(n_a);
 cout << ans << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/1417
namespace yukicode_1417 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using Mint= ModInt<int(1e9 + 7)>;
 vector alp= {1, 2, 3, 4, 5, 6, 7, 8, 9};
 string N;
 cin >> N;
 int n= N.length();
 auto tr_le= [&](int s, int c) {
  if (s >= n) return s;
  int d= N[s] - '0';
  if (c < d) return n;
  if (c > d) return n + 1;
  return s + 1;
 };
 Automaton dfa_le(
     alp, 0, tr_le, [&](int s) { return s == n; }, n + 1);
 auto tr_prod= [](int s, int c) { return s * c % 100; };
 Automaton dfa_prod(alp, 1, tr_prod, [](int s) { return s == 0; });
 Mint ans= 0;
 for (int i= 1; i < n; ++i) ans+= dfa_prod.num<Mint>(i);
 auto dfa= dfa_le & dfa_prod;
 ans+= dfa.num<Mint>(n);
 cout << ans << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/685
namespace yukicoder_685 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using Mint= ModInt<int(1e9 + 7)>;
 using symbol_t= array<int, 2>;
 vector<symbol_t> alp= {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
 int64_t N;
 cin >> N;
 auto tr_le= [&](int64_t s, symbol_t c) {
  if (c[1]) return (s + 1) / 2 - 1;
  else return s / 2;
 };
 Automaton dfa_le(
     alp, N, tr_le, [](int64_t) { return true; }, int64_t(-1));
 auto tr_xy= [&](bool s, symbol_t c) {
  if (c[0] < c[1]) s= 1;
  else if (c[0] > c[1]) s= 0;
  return s;
 };
 Automaton dfa_xy(alp, false, tr_xy, [](bool s) { return s; });
 auto tr_ax= [&](bool s, symbol_t c) {
  bool a= c[0] & c[1], x= c[0] ^ c[1];
  if (a < x) s= 1;
  else if (a > x) s= 0;
  return s;
 };
 Automaton dfa_ax(alp, false, tr_ax, [](bool s) { return s; });
 auto tr_xo= [&](bool s, symbol_t c) {
  bool x= c[0] ^ c[1], o= c[0] | c[1];
  if (x < o) s= 1;
  else if (x > o) s= 0;
  return s;
 };
 Automaton dfa_xo(alp, false, tr_xo, [](bool s) { return s; });
 auto dfa= dfa_le & dfa_xy & dfa_ax & dfa_xo;
 cout << dfa.num<Mint>(60) << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/737
namespace yukicoder_737 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using Mint= ModInt<int(1e9 + 7)>;
 vector alp= {0, 1};
 int64_t N;
 cin >> N;
 auto tr= [&](int s, int c) {
  if (s <= -1) return s;
  int d= (N >> s) & 1;
  if (c < d) return -1;
  if (c > d) return -2;
  return s - 1;
 };
 Automaton dfa(
     alp, 59, tr, [&](int s) { return s == -1; }, -2);
 using T= array<Mint, 4>;
 auto op= [&](const T &l, const T &r) {
  T ret;
  for (int i= 4; i--;) ret[i]= l[i] + r[i];
  return ret;
 };
 auto f= [&](T x, int c, int) {
  x[0]+= x[0], x[1]+= x[1];
  if (c) {
   x[0]+= x[1] + x[2] + x[3];
   x[1]+= x[3];
   x[2]+= x[3];
  }
  return x;
 };
 cout << dfa.dp_run(60, op, T{0, 0, 0, 0}, f, T{0, 0, 0, 1})[0] << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/911
namespace yukicoder_911 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 int64_t L, R;
 cin >> L >> R;
 vector<int64_t> A(N);
 for (int i= 0; i < N; ++i) cin >> A[i];
 vector alp= {0, 1};
 auto tr_l= [&](int s, int c) {
  if (s <= -1) return s;
  int d= (L >> s) & 1;
  if (c < d) return -2;
  if (c > d) return -1;
  return s - 1;
 };
 auto tr_r= [&](int s, int c) {
  if (s <= -1) return s;
  int d= (R >> s) & 1;
  if (c < d) return -1;
  if (c > d) return -2;
  return s - 1;
 };
 auto ac0= [&](int s) { return s == -1; };
 Automaton dfa_l(alp, 60, tr_l, ac0, -2), dfa_r(alp, 60, tr_r, ac0, -2);
 using state_t= pair<vector<int>, int>;
 state_t rej= make_pair(vector<int>(), -1);
 state_t init= make_pair(vector<int>{0, N}, 60);
 auto tr_x= [&](const state_t &s, int c) -> state_t {
  const auto &[sep, i]= s;
  if (i <= -1) return s;
  const int n= sep.size();
  vector<int> nsep{0};
  for (int j= 0; j + 1 < n; ++j) {
   int bg= sep[j], ed= sep[j + 1];
   for (int k= bg; k + 1 < ed; ++k) {
    int l= ((A[k] >> i) & 1) ^ c, r= ((A[k + 1] >> i) & 1) ^ c;
    if (l > r) return rej;
    if (l < r) nsep.push_back(k + 1);
   }
   nsep.push_back(ed);
  }
  return {nsep, i - 1};
 };
 auto ac_x= [&](const state_t &s) {
  const auto &[sep, i]= s;
  return sep.size() == N + 1;
 };
 Automaton dfa_x(alp, init, tr_x, ac_x, rej);
 auto dfa= dfa_l & dfa_r & dfa_x;
 cout << dfa.num<int64_t>(61) << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/1953
// sp judge
namespace yukicoder_1953 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 auto tr_le= [&](int64_t s, int c) { return (s - c + 10) / 10 - 1; };
 auto ac_le= [&](int64_t) { return true; };
 auto tr_0= [&](bool, int c) -> bool { return c; };
 auto ac_0= [&](bool s) { return s; };
 Automaton dfa_0(alp, false, tr_0, ac_0);
 using T= array<int64_t, 2>;
 auto op= [&](T l, T r) {
  T ret;
  ret[0]= l[0] + r[0], ret[1]= l[1] + r[1];
  return ret;
 };
 auto f= [&](T x, int c, int) {
  if (c == 4 || c == 6 || c == 9 || c == 0) x[0]+= x[1];
  else if (c == 8) x[0]+= 2 * x[1];
  return x;
 };
 int64_t K;
 cin >> K;
 int64_t l= 0, h= 1ll << 60;
 while (h - l > 1) {
  int64_t N= (h + l) / 2;
  int n= 0;
  for (auto m= N; m; m/= 10) ++n;
  Automaton dfa_le(alp, N, tr_le, ac_le, int64_t(-1));
  auto dfa= dfa_le & dfa_0;
  int64_t x= dfa.dp_run(n, op, T{0, 0}, f, T{0, 1})[0];
  for (int i= 1; i < n; ++i) x+= dfa_0.dp_run(i, op, T{0, 0}, f, T{0, 1})[0];
  if (x == K) {
   cout << N << '\n';
   return 0;
  }
  if (x < K) l= N;
  else h= N;
 }
 cout << -1 << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/1740
namespace yukicoder_1740 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using Mint= ModInt<998244353>;
 vector<char> alp(26);
 for (int i= 0; i < 26; ++i) alp[i]= 'a' + i;
 int N;
 cin >> N;
 string S;
 cin >> S;
 auto tr_le= [&](int s, char c) {
  if (s >= N) return s;
  if (c < S[s]) return N + 1;
  if (c > S[s]) return N;
  return s + 1;
 };
 Automaton dfa_le(
     alp, 0, tr_le, [&](int s) { return s == N + 1; }, N);
 auto tr_a= [&](int s, char c) {
  if (c == 'a') ++s;
  return s;
 };
 Automaton dfa_1(
     alp, 0, tr_a, [](int s) { return s == 1; }, 2);
 auto dfa= dfa_le & dfa_1;
 cout << dfa.num<Mint>(N) << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/362
namespace yukicoder_362 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 auto tr_le= [&](int64_t s, int c) { return (s - c + 10) / 10 - 1; };
 auto ac_le= [&](int64_t) { return true; };
 using state_t= array<int, 2>;
 auto tr_kado= [&](state_t s, int c) -> state_t {
  if (s[0] == -1) {
   if (s[1] == c) return {-2, -2};
   else return {s[1], c};
  }
  if (s[0] == c || s[1] == c) return {-2, -2};
  auto [mi, mx]= minmax({s[0], s[1], c});
  if (s[1] == mi || s[1] == mx) return {s[1], c};
  return {-2, -2};
 };
 auto ac_kado= [&](state_t s) { return true; };
 Automaton dfa_kado(alp, state_t{-1, -1}, tr_kado, ac_kado, state_t{-2, -2});
 auto tr_0= [&](bool, int c) -> bool { return c; };
 Automaton dfa_0(alp, false, tr_0, [](bool s) { return s; });
 auto dfa1= dfa_kado & dfa_0;
 int T;
 cin >> T;
 while (T--) {
  int64_t K;
  cin >> K;
  int64_t l= 101, h= 37294859064823;
  while (h - l > 1) {
   int64_t X= (h + l) / 2;
   int n= 0;
   for (auto m= X; m; m/= 10) ++n;
   Automaton dfa_le(alp, X, tr_le, ac_le, int64_t(-1));
   auto dfa= dfa1 & dfa_le;
   int64_t sum= dfa.num<int64_t>(n);
   for (int i= 3; i < n; ++i) sum+= dfa1.num<int64_t>(i);
   if (sum < K) l= X;
   else h= X;
  }
  cout << h << '\n';
 }
 return 0;
}
}
// https://atcoder.jp/contests/abc155/tasks/abc155_e
namespace ABC155E {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 vector<int> alp(19);
 for (int i= 0; i < 19; ++i) alp[i]= i - 9;
 string N;
 cin >> N;
 N= "0" + N;
 int n= N.length();
 using state_t= array<int, 2>;
 auto tr= [&](state_t s, int c) -> state_t {
  auto [i, b]= s;
  if (i < 0) return {-1, -1};
  int d= (N[i] - '0' + b) % 10;
  if (c == d || 10 + c == d) return {i - 1, (N[i] - '0' + b - c) / 10};
  return {-1, -1};
 };
 auto ac= [&](state_t s) { return s[1] == 0; };
 Automaton dfa(alp, state_t{n - 1, 0}, tr, ac, state_t{-1, -1});
 auto op= [&](int l, int r) { return min(l, r); };
 auto f= [&](int x, int c, int) { return x + abs(c); };
 cout << dfa.dp_run(n, op, 1 << 30, f, 0) << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/1106
namespace yukicoder_1106 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 vector alp= {-2, -1, 0, 1, 2};
 int64_t N;
 cin >> N;
 auto tr_le= [&](int64_t s, int c) { return (s - c + 5) / 5 - 1; };
 Automaton dfa_le(
     alp, N, tr_le, [](int64_t) { return true; }, int64_t(-1));
 auto tr_pos= [&](bool s, int c) {
  if (c > 0) s= 1;
  else if (c < 0) s= 0;
  return s;
 };
 Automaton dfa_pos(alp, false, tr_pos, [](bool s) { return s; });
 auto tr_eq= [&](int s, int c) {
  if (abs(s) > 100) return s;
  return s + c;
 };
 Automaton dfa_eq(alp, 0, tr_eq, [](int s) { return s == 0; });
 auto dfa= dfa_le & dfa_pos & dfa_eq;
 cout << dfa.num<int64_t>(60) << '\n';
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 // ABC235F::main();
 // AGC015D::main();
 // ARC066B::main();
 // AOJ_2587::main();
 // AOJ_0570::main();
 // yukicoder_315::main();
 // yukicode_1417::main();
 // yukicoder_685::main();
 // yukicoder_737::main();
 // yukicoder_911::main();
 // yukicoder_1953::main();
 // yukicoder_1740::main();
 // yukicoder_362::main();
 // ABC155E::main();
 yukicoder_1106::main();
 return 0;
}