/** * */ // header {{{ #include using namespace std; #define CPP_STR(x) CPP_STR_I(x) #define CPP_CAT(x,y) CPP_CAT_I(x,y) #define CPP_STR_I(args...) #args #define CPP_CAT_I(x,y) x ## y #define SFINAE(pred...) std::enable_if_t<(pred), std::nullptr_t> = nullptr #define ASSERT(expr...) assert((expr)) using i8 = int8_t; using u8 = uint8_t; using i16 = int16_t; using u16 = uint16_t; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; using f32 = float; using f64 = double; using f80 = __float80; // }}} constexpr i64 INF = INT64_C(1'010'000'000'000'000'017); constexpr f64 FINF = 1e100; constexpr i64 MOD = INT64_C(1'000'000'007); //constexpr i64 MOD = INT64_C(998'244'353); constexpr f64 EPS = 1e-12; constexpr f64 PI = 3.14159265358979323846; // util {{{ #define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c)) #define LIFT(f) ([](auto&&... args) -> decltype(auto) { return (f)(std::forward(args)...); }) template constexpr i64 SIZE(const C& c) noexcept { return static_cast(c.size()); } template constexpr i64 SIZE(const T (&)[N]) noexcept { return static_cast(N); } template::value)> constexpr T ABS(T x) noexcept { return x < 0 ? -x : x; } template constexpr i64 CMP(T x, T y) noexcept { return (y constexpr i64 SGN(T x) noexcept { return CMP(x,T(0)); } template> constexpr bool chmax(T& xmax, const U& x, Comp comp={}) noexcept { if(comp(xmax, x)) { xmax = x; return true; } return false; } template> constexpr bool chmin(T& xmin, const U& x, Comp comp={}) noexcept { if(comp(x, xmin)) { xmin = x; return true; } return false; } template auto ON(BinaryFunc&& bf, UnaryFunc&& uf) { return [bf=forward(bf),uf=forward(uf)](const auto& x, const auto& y) { return bf(uf(x), uf(y)); }; } template auto LT_ON(F&& f) { return ON(less<>{}, forward(f)); } template auto GT_ON(F&& f) { return ON(greater<>{}, forward(f)); } template auto EQ_ON(F&& f) { return ON(equal_to<>{}, forward(f)); } template auto NE_ON(F&& f) { return ON(not_equal_to<>{}, forward(f)); } // tuple {{{ template void tuple_enumerate(tuple&, F&&) {} template I)> void tuple_enumerate(tuple& t, F&& f) { f(I, get(t)); tuple_enumerate(t, forward(f)); } template void tuple_enumerate(const tuple&, F&&) {} template I)> void tuple_enumerate(const tuple& t, F&& f) { f(I, get(t)); tuple_enumerate(t, forward(f)); } // }}} // container {{{ template struct is_container : false_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct is_container> : true_type {}; template struct ProconHash { size_t operator()(const T& x) const noexcept { return hash{}(x); } }; template size_t procon_hash_value(const T& x) noexcept { return ProconHash{}(x); } size_t procon_hash_combine(size_t h1, size_t h2) noexcept { constexpr size_t M = UINT64_C(0xc6a4a7935bd1e995); constexpr int R = 47; h2 *= M; h2 ^= h2 >> R; h2 *= M; h1 ^= h2; h1 *= M; h1 += 0xe6546b64; return h1; } template struct ProconHash> { size_t operator()(const pair& p) const noexcept { size_t h1 = procon_hash_value(p.first); size_t h2 = procon_hash_value(p.second); return procon_hash_combine(h1, h2); } }; template struct ProconHash> { size_t operator()(const tuple& t) const noexcept { size_t h = 0; tuple_enumerate(t, [&h](i64, const auto& e) { h = procon_hash_combine(h, procon_hash_value(e)); }); return h; } }; template struct ProconHash::value>> { size_t operator()(const C& c) const noexcept { size_t h = 0; for(const auto& e : c) h = procon_hash_combine(h, procon_hash_value(e)); return h; } }; template, typename Eq=equal_to> using HashSet = unordered_set; template, typename Eq=equal_to> using HashMap = unordered_map; template, typename Eq=equal_to> using HashMultiset = unordered_multiset; template, typename Eq=equal_to> using HashMultimap = unordered_multimap; template auto vec_make(i64 n, T x) { return vector(n, x); } template= 2)> auto vec_make(i64 n, Args... args) { auto inner = vec_make(args...); return vector(n, inner); } template auto vec_reserve(i64 cap) { vector res; res.reserve(cap); return res; } template auto vec_iota(i64 n, T init={}) { vector res(n); ALL(iota, res, init); return res; } template> auto priority_queue_make(const Comp& comp, Cont&& cont={}) { return priority_queue,Comp>(comp, forward(cont)); } template auto priority_queue_reserve(const Comp& comp, i64 cap) { return priority_queue,Comp>(comp, vec_reserve(cap)); } template struct ArrayType { using type = array::type,N>; }; template struct ArrayType { using type = array; }; template using Array = typename ArrayType::type; template T& array_at(Array& ary, i64 i) { return ary[i]; } template T& array_at(Array& ary, i64 i, Args... args) { return array_at(ary[i], args...); } template const T& array_at(const Array& ary, i64 i) { return ary[i]; } template const T& array_at(const Array& ary, i64 i, Args... args) { return array_at(ary[i], args...); } template T POP(stack& stk) { T x = stk.top(); stk.pop(); return x; } template T POP(queue& que) { T x = que.front(); que.pop(); return x; } template T POP(priority_queue& que) { T x = que.top(); que.pop(); return x; } // }}} // fixpoint {{{ template class FixPoint { public: explicit constexpr FixPoint(F&& f) : f_(forward(f)) {} template constexpr decltype(auto) operator()(Args&&... args) const { return f_(*this, forward(args)...); } private: F f_; }; template constexpr decltype(auto) FIX(F&& f) { return FixPoint(forward(f)); } template class FixPointMemo { public: explicit FixPointMemo(F&& f) : f_(forward(f)) {} template decltype(auto) operator()(Args... args) const { using R = decltype(f_(*this,args...)); static Array done {}; static Array memo; if(!array_at(done,args...)) { array_at(memo,args...) = f_(*this,args...); array_at(done,args...) = true; } return array_at(memo,args...); } private: F f_; }; template decltype(auto) FIXMEMO(F&& f) { return FixPointMemo(forward(f)); } // }}} // math {{{ /*constexpr*/ i64 GCD(i64 a, i64 b) noexcept { /*constexpr*/ auto f_gcd = FIX([](auto&& self, i64 aa, i64 bb) { if(bb == 0) return aa; return self(bb, aa%bb); }); return f_gcd(ABS(a), ABS(b)); } /*constexpr*/ i64 LCM(i64 a, i64 b) noexcept { ASSERT(a != 0 && b != 0); /*constexpr*/ auto f_gcd = FIX([](auto&& self, i64 aa, i64 bb) { if(bb == 0) return aa; return self(bb, aa%bb); }); a = ABS(a); b = ABS(b); return a / f_gcd(a,b) * b; } /*constexpr*/ tuple EXTGCD(i64 a, i64 b) noexcept { /*constexpr*/ auto impl = FIX([](auto&& self, i64 aa, i64 bb) -> tuple { if(bb == 0) return make_tuple(aa, 1, 0); i64 g,x,y; tie(g,x,y) = self(bb, aa%bb); return make_tuple(g, y, x-(aa/bb)*y); }); i64 g,x,y; tie(g,x,y) = impl(ABS(a), ABS(b)); x *= SGN(a); y *= SGN(b); return make_tuple(g, x, y); } // }}} // string {{{ auto str_reserve(i64 cap) { string res; res.reserve(cap); return res; } // }}} // input {{{ template struct Scan { static T scan(istream& in) { T res; in >> res; return res; } }; template struct Scan1; template struct Scan1::value && !is_same::value>> { static T scan1(istream& in) { return Scan::scan(in) - 1; } }; template struct Scan> { static pair scan(istream& in) { T1 x = Scan::scan(in); T2 y = Scan::scan(in); return {x,y}; } }; template struct Scan1> { static pair scan1(istream& in) { T1 x = Scan1::scan1(in); T2 y = Scan1::scan1(in); return {x,y}; } }; template tuple tuple_scan_impl(istream& in) { return make_tuple(Scan::scan(in)); } template 0)> tuple tuple_scan_impl(istream& in) { auto head = make_tuple(Scan::scan(in)); return tuple_cat(head, tuple_scan_impl(in)); } template struct Scan> { static tuple scan(istream& in) { return tuple_scan_impl(in); } }; template tuple tuple_scan1_impl(istream& in) { return make_tuple(Scan1::scan1(in)); } template 0)> tuple tuple_scan1_impl(istream& in) { auto head = make_tuple(Scan1::scan1(in)); return tuple_cat(head, tuple_scan1_impl(in)); } template struct Scan1> { static tuple scan1(istream& in) { return tuple_scan1_impl(in); } }; template T RD() { return Scan::scan(cin); } template T RD1() { return Scan1::scan1(cin); } template auto RD_VEC(i64 n) { auto res = vec_reserve(n); REP(_, n) { res.emplace_back(RD()); } return res; } template auto RD1_VEC(i64 n) { auto res = vec_reserve(n); REP(_, n) { res.emplace_back(RD1()); } return res; } template auto RD_VEC2(i64 h, i64 w) { auto res = vec_reserve>(h); REP(_, h) { res.emplace_back(RD_VEC(w)); } return res; } template auto RD1_VEC2(i64 h, i64 w) { auto res = vec_reserve>(h); REP(_, h) { res.emplace_back(RD1_VEC(w)); } return res; } // }}} // output {{{ template struct Fmt { static void fmt(ostream& out, const T& x) { out << x; } }; template void fmt_write(ostream& out, const T& x) { Fmt::fmt(out, x); } template struct Fmt> { static void fmt(ostream& out, const tuple& t) { tuple_enumerate(t, [&out](i64 i, const auto& e) { if(i != 0) out << ' '; fmt_write(out, e); }); } }; template struct Fmt> { static void fmt(ostream& out, const pair& p) { return fmt_write(out, make_tuple(p.first,p.second)); } }; template struct Fmt::value>> { static void fmt(ostream& out, const C& c) { for(auto it = begin(c); it != end(c); ++it) { if(it != begin(c)) out << ' '; fmt_write(out, *it); } } }; void PRINT() {} template void PRINT(const T& x, const TS&... args) { fmt_write(cout, x); if(sizeof...(args) > 0) { cout << ' '; PRINT(args...); } } template void PRINTLN(const TS&... args) { PRINT(args...); cout << '\n'; } // }}} // debug {{{ template struct Dbg { static void dbg(ostream& out, const T& x) { out << x; } }; template void dbg_write(ostream& out, const T& x) { Dbg::dbg(out, x); } template<> struct Dbg { static void dbg(ostream& out, i64 x) { if(x == INF) out << "INF"; else if(x == -INF) out << "-INF"; else out << x; } }; template<> struct Dbg { static void dbg(ostream& out, f64 x) { #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wfloat-equal" if(x == FINF) out << "FINF"; else if(x == -FINF) out << "-FINF"; else out << x; #pragma GCC diagnostic pop } }; template struct Dbg { static void dbg(ostream& out, const T (&ary)[N]) { out << "["; REP(i, N) { if(i != 0) out << ","; dbg_write(out, ary[i]); } out << "]"; } }; template struct Dbg { static void dbg(ostream& out, const char (&s)[N]) { out << s; } }; template struct Dbg> { static void dbg(ostream& out, const tuple& t) { out << "("; tuple_enumerate(t, [&out](i64 i, const auto& e) { if(i != 0) out << ","; dbg_write(out, e); }); out << ")"; } }; template struct Dbg> { static void dbg(ostream& out, const pair& p) { return dbg_write(out, make_tuple(p.first,p.second)); } }; template struct Dbg::value>> { static void dbg(ostream& out, const C& c) { out << "["; for(auto it = begin(c); it != end(c); ++it) { if(it != begin(c)) out << ","; dbg_write(out, *it); } out << "]"; } }; template struct Dbg> { static void dbg(ostream& out, stack stk) { out << "["; while(!stk.empty()) { dbg_write(out,stk.top()); stk.pop(); if(!stk.empty()) out << ","; } out << "]"; } }; template struct Dbg> { static void dbg(ostream& out, queue que) { out << "["; while(!que.empty()) { dbg_write(out,que.front()); que.pop(); if(!que.empty()) out << ","; } out << "]"; } }; template struct Dbg> { static void dbg(ostream& out, priority_queue que) { out << "["; while(!que.empty()) { dbg_write(out,que.top()); que.pop(); if(!que.empty()) out << ","; } out << "]"; } }; template void DBG_IMPL(i64 line, const char* expr, const T& value) { cerr << "[L " << line << "]: "; cerr << expr << " = "; dbg_write(cerr, value); cerr << "\n"; } void DBG_IMPL_HELPER() {} template void DBG_IMPL_HELPER(const T& x, const TS&... args) { dbg_write(cerr, x); if(sizeof...(args) > 0) { cerr << ","; DBG_IMPL_HELPER(args...); } } template void DBG_IMPL(i64 line, const char* expr, const TS&... value) { cerr << "[L " << line << "]: "; cerr << "(" << expr << ") = ("; DBG_IMPL_HELPER(value...); cerr << ")\n"; } template::value == 0)> void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array&, const array&) { dbg_write(out, x); } template::value > 0)> void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array& sizes, const array& offs) { i64 k = N - rank::value; i64 off = offs[k]; i64 siz = sizes[k]; if(siz == 0) siz = extent::value - off; out << "["; FOR(i, off, off+siz) { if(i != off) out << ","; DBG_DP_IMPL_HELPER(out, x[i], sizes, offs); } out << "]"; } template::value > 0)> void DBG_DP_IMPL(i64 line, const char* expr, const T& dp, const array::value>& sizes={}, const array::value>& offs={}) { cerr << "[L " << line << "]: "; cerr << expr << " = "; DBG_DP_IMPL_HELPER::value>(cerr, dp, sizes, offs); cerr << "\n"; } template void DBG_GRID_IMPL(i64 line, const char* expr, const vector& grid) { cerr << "[L " << line << "]: "; cerr << expr << ":\n"; for(const auto& row : grid) { dbg_write(cerr, row); cerr << "\n"; } cerr << "\n"; } #ifdef PROCON_LOCAL #define DBG(args...) DBG_IMPL(__LINE__, CPP_STR_I(args), args) #define DBG_DP(args...) DBG_DP_IMPL(__LINE__, CPP_STR_I(args), args) #define DBG_GRID(args...) DBG_GRID_IMPL(__LINE__, CPP_STR_I(args), args) #else #define DBG(args...) #define DBG_DP(args...) #define DBG_GRID(args...) #endif // }}} // modint {{{ template struct ModIntT { static_assert(M >= 2, ""); i64 v_; // [0,M) ModIntT() : v_(0) {} ModIntT(i64 v) { i64 r = v % M; v_ = r >= 0 ? r : r+M; } ModIntT operator-() const { return ModIntT(-v_); } ModIntT& operator+=(ModIntT rhs) { v_ += rhs.v_; v_ %= M; return *this; } ModIntT& operator-=(ModIntT rhs) { v_ += M; v_ -= rhs.v_; v_ %= M; return *this; } ModIntT& operator*=(ModIntT rhs) { v_ *= rhs.v_; v_ %= M; return *this; } ModIntT& operator++() { return *this += 1; } ModIntT& operator--() { return *this -= 1; } ModIntT operator++(int) { return exchange(*this, *this+1); } ModIntT operator--(int) { return exchange(*this, *this-1); } explicit operator i64() const { return v_; } ModIntT inv() const { i64 g,x; tie(g,x,ignore) = EXTGCD(v_, M); ASSERT(g == 1); return ModIntT(x); } }; template ModIntT operator+(ModIntT lhs, ModIntT rhs) { return ModIntT(lhs) += rhs; } template ModIntT operator+(ModIntT lhs, i64 rhs) { return ModIntT(lhs) += rhs; } template ModIntT operator+(i64 lhs, ModIntT rhs) { return ModIntT(rhs) += lhs; } template ModIntT operator-(ModIntT lhs, ModIntT rhs) { return ModIntT(lhs) -= rhs; } template ModIntT operator-(ModIntT lhs, i64 rhs) { return ModIntT(lhs) -= rhs; } template ModIntT operator-(i64 lhs, ModIntT rhs) { return ModIntT(rhs) -= lhs; } template ModIntT operator*(ModIntT lhs, ModIntT rhs) { return ModIntT(lhs) *= rhs; } template ModIntT operator*(ModIntT lhs, i64 rhs) { return ModIntT(lhs) *= rhs; } template ModIntT operator*(i64 lhs, ModIntT rhs) { return ModIntT(rhs) *= lhs; } template bool operator==(ModIntT lhs, ModIntT rhs) { return lhs.v_ == rhs.v_; } template bool operator==(ModIntT lhs, i64 rhs) { return lhs == ModIntT(rhs); } template bool operator==(i64 lhs, ModIntT rhs) { return ModIntT(lhs) == rhs; } template bool operator!=(ModIntT lhs, ModIntT rhs) { return !(lhs == rhs); } template bool operator!=(ModIntT lhs, i64 rhs) { return !(lhs == rhs); } template bool operator!=(i64 lhs, ModIntT rhs) { return !(lhs == rhs); } template struct Scan> { static ModIntT scan(istream& in) { return Scan::scan(in); } }; template struct Fmt> { static void fmt(ostream& out, ModIntT x) { fmt_write(out, x.v_); } }; template struct Dbg> { static void dbg(ostream& out, ModIntT x) { dbg_write(out, x.v_); } }; using ModInt = ModIntT; // }}} // }}} // init {{{ struct ProconInit { static constexpr int IOS_PREC = 15; static constexpr bool AUTOFLUSH = false; ProconInit() { cin.tie(nullptr); ios::sync_with_stdio(false); cin.exceptions(ios::failbit | ios::badbit); cout << fixed << setprecision(IOS_PREC); #ifdef PROCON_LOCAL cerr << fixed << setprecision(2); #endif if(AUTOFLUSH) cout << unitbuf; } } PROCON_INIT; // }}} //-------------------------------------------------------------------- void solve() { i64 N = RD(); vector X(N); REP(i, N) { REP(j, N) { i64 x = RD(); if(x) X[i] |= 1LL< bool { REP(_, N) { REP(i, N) { if((X[i] & mask) == X[i]) mask |= 1LL<