// https://yukicoder.me/problems/no/1421 #define STATIC_MOD 1e9 + 7 #ifdef BTK /**/ # include "Template.hpp" /**/ #else /**/ /* #region auto includes */ /* #region stl */ /**/ # include # include # include using namespace std; /**/ /* #endregion */ /* #region template/Grid.hpp*/ /** * @brief グリッドをラップするための関数 * @tparam T std::string や std;:vector を想定 * @tparam U 周りに配置する要素の型 * @param grid 入力、R > 0 でないとバグる * @param material 周りに配置する要素 * @return std::vector material で 周りを埋めた grid */ template inline std::vector wrapGrid(std::vector grid, U material) { std::vector wrappedGrid(grid.size() + 2, T(grid[0].size() + 2, material)); for (std::size_t i = 0; i < grid.size(); i++) { for (std::size_t j = 0; j < grid[i].size(); j++) { wrappedGrid[i + 1][j + 1] = grid[i][j]; } } return wrappedGrid; } /** * @brief * */ constexpr int dr4[] = {0, 1, 0, -1}; constexpr int dc4[] = {-1, 0, 1, 0}; /* #endregion */ /* #region template/IO.hpp*/ /** * @file IO.hpp * @author btk * @brief cin高速化とか,出力の小数桁固定とか * @version 0.2 * @date 2021-03-01 * * @copyright Copyright (c) 2021 */ /** * @brief 入出力の設定を行うための構造体 */ namespace io { inline void enableFastIO() { std::ios::sync_with_stdio(false); std::cin.tie(0); } inline void setDigits(int digits) { std::cout << std::fixed; std::cout << std::setprecision(digits); } } // namespace io /** * @brief * vectorに直接cin流すためのやつ * @tparam T * @param is * @param v * @return istream& */ template std::istream& operator>>(std::istream& is, std::vector& v) { for (auto& it : v) is >> it; return is; } /* #endregion */ /* #region template/IncludeSTL.hpp*/ /** * @file IncludeSTL.hpp * @author btk * @brief 標準ライブラリをincludeするだけ * @version 0.1 * @date 2019-07-21 * @todo 何故か2回includeされる(展開scriptに * @copyright Copyright (c) 2019 * */ /* #endregion */ /* #region template/Loop.hpp*/ /** * @file Loop.hpp * @author btk * @brief rangeとかループ系のクラス * @version 0.1 * @date 2019-07-13 * * @copyright Copyright (c) 2019 * */ /** * @brief * rangeを逆向きに操作したいとき用 * @details * ループの範囲は[bg,ed)なので注意 * @see range */ class reverse_range { private: struct I { int x; int operator*() { return x - 1; } bool operator!=(I& lhs) { return x > lhs.x; } void operator++() { --x; } }; I i, n; public: /** * @brief Construct a new reverse range object * * @param n */ reverse_range(int n) : i({0}), n({n}) {} /** * @brief Construct a new reverse range object * * @param i * @param n */ reverse_range(int i, int n) : i({i}), n({n}) {} /** * @brief * begin iterator * @return I& */ I& begin() { return n; } /** * @brief * end iterator * @return I& */ I& end() { return i; } }; /** * @brief * python みたいな range-based for を実現 * @details * ループの範囲は[bg,ed)なので注意 * !つけると逆向きにループが回る (reverse_range) * 空間計算量はO(1) * 使わない変数ができて警告が出がちなので,unused_varとかを使って警告消しするとよい */ class range { private: struct I { int x; int operator*() { return x; } bool operator!=(I& lhs) { return x < lhs.x; } void operator++() { ++x; } }; I i, n; public: /** * @brief Construct a new range object * * @param n */ range(int n) : i({0}), n({n}) {} /** * @brief Construct a new range object * * @param i * @param n */ range(int i, int n) : i({i}), n({n}) {} /** * @brief * begin iterator * @return I& */ I& begin() { return i; } /** * @brief * end iterator * @return I& */ I& end() { return n; } /** * @brief * 逆向きに参照するrange(reverse_rangeを取得できるs) * @return reverse_range */ reverse_range operator!() { return reverse_range(*i, *n); } }; /* #endregion */ /* #region template/Macro.hpp*/ /** * @file Macro.hpp * @author btk * @brief マクロとか,LLとか * @version 0.1 * @date 2019-07-13 * * @copyright Copyright (c) 2019 * */ /** * @def DEBUG * @brief デバッグ用のif文 提出時はif(0)で実行されない */ /**/ # ifdef BTK # define DEBUG if (1) # else # define DEBUG if (0) # endif /** * @def ALL(v) * @brief * ALLマクロ */ # define ALL(v) (v).begin(), (v).end() /** * @def REC(ret, ...) * @brief * 再帰ラムダをするためのマクロ */ # define REC(ret, ...) std::function /** * @def VAR_NAME(var) * @brief 変数名を取得する */ # define VAR_NAME(var) # var /** * @brief * rangeで生まれる使わない変数を消す用(警告消し) */ template inline T& unused_var(T& v) { return v; } template std::vector nestingVector(std::size_t size) { return std::vector(size); } template inline auto nestingVector(std::size_t size, Ts... ts) { return std::vector(ts...))>( size, nestingVector(ts...)); } /* #endregion */ /* #region template/ChainOperation.hpp*/ /** * @file ChainOperation.hpp * @author btk * @brief パラメータパックを利用した演算子結合を実現 */ /** * @brief テンプレート再帰の末尾 * @tparam F 二項演算 * @tparam T * @param v * @return T */ template inline T chain(T&& v) { return v; } /** * @brief 複数項における演算の結果を返す * @tparam F * @tparam T * @tparam Ts * @param head * @param tail * @return T */ template inline auto chain(const T head, Ts&&... tail) { return F::exec(head, chain(tail...)); } /** * @brief * 先頭の値をFで参照する関数に基づいて変更できたらする * @tparam F * @tparam T * @tparam Ts * @param target * @param candidates * @return true * @return false */ template inline bool changeTarget(T& target, Ts&&... candidates) { const T old = target; target = chain(target, candidates...); return old != target; } /* #endregion */ /* #region template/Math.hpp*/ /** * @file Math.hpp * @author btk * @brief 最大値とか最小値を求める */ /** * @brief gcd, ceil等自作算数用関数を集める。stdと被るので名前空間を区切る */ namespace math { /** * @brief 拡張ユークリッド互除法 * @details ax + by = gとなるx,yを求める * @param a 入力 * @param b 入力 * @param x 値引き継ぎ用の変数 * @param y 値引き継ぎ用の変数 * @return int64_t g:aとbの最大公約数 */ int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y) { int64_t g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; } /** * @brief 一次不定方程式の解 * @details 値の説明は betouzEquation 関数を参照のこと */ struct BetouzSolution { int64_t x, y, dx, dy; }; /** * @brief 一次不定方程式 * @details a(x + k*dx) + b(y -k*dy) = cとなる x, y, dx, dy を求める。 * @param a 入力 * @param b 入力 * @param c 入力 * @return int64_t 解がないときは nullopt が返る */ std::optional betouzEquation(int64_t a, int64_t b, int64_t c) { BetouzSolution sol; const int64_t g = extgcd(a, b, sol.x, sol.y); if (c % g == 0) { return std::nullopt; } sol.dx = b / g; sol.dy = a / g; sol.x *= c / g; sol.y *= c / g; return sol; } namespace inner { /** * @brief 2項のgcdを求める * @tparam T */ template struct GCDFunc { /** * @brief 本体 * @param l * @param r * @return T */ static inline T exec(T l, T r) { while (r != 0) { T u = l % r; l = r; r = u; } return l; } }; /** * @brief 2項のgcdを求める * @tparam T */ template struct LCMFunc { /** * @brief 本体 * @param l * @param r * @return T */ static inline T exec(T l, T r) { return (l / GCDFunc::exec(l, r)) * r; } }; } // namespace inner /** * @brief valuesの最大公約数 * @tparam Ts パラメータパック * @param values gcdを求めたい値の集合(2個以上) * @return int64 最大公約数 */ template inline int64_t gcd(Ts&&... values) { return chain>(values...); } /** * @brief valuesの最小公倍数 * @tparam Ts パラメータパック * @param values lcmを求めたい値の集合(2個以上) * @return int64 最小公倍数 */ template inline int64_t lcm(Ts&&... values) { return chain>(values...); } /** * @brief iterator で指定された集合のlcmを求める * @tparam ITR iterator * @param l 開始位置 * @param r 終了位置 * @return int64_t lcm */ template inline int64_t lcmAll(ITR l, ITR r) { int64_t ret = 1; for (auto it = l; it != r; ++it) { ret = lcm(ret, *it); } return ret; } /** * @brief container (配列など) で指定された要素のlcmを求める * @tparam Container vectorやlist * @param container コンテナ * @return int64_t lcm */ template inline int64_t lcmAll(Container container) { int64_t ret = 1; for (auto e : container) { ret = lcm(ret, e); } return ret; } /** * @brief iterator で指定された集合のgcdを求める * @tparam ITR iterator * @param l 開始位置 * @param r 終了位置 * @return int64_t lcm */ template inline int64_t gcdAll(ITR l, ITR r) { int64_t ret = 0; for (auto it = l; it != r; ++it) { ret = gcd(ret, *it); } return ret; } /** * @brief container (配列など) で指定された要素のgcdを求める * @tparam Container vectorやlist * @param container コンテナ * @return int64_t gcd */ template inline int64_t gcdAll(Container container) { int64_t ret = 0; for (auto e : container) { ret = gcd(ret, e); } return ret; } /** * @brief u/dを切り上げした整数を求める * @todo 負の数への対応 * @tparam T 整数型 * @param u 入力 * @param d 入力 * @return T 切り上げ後の値 */ template inline T ceil(T u, T d) { return (u + d - (T)1) / d; } } // namespace math /** * @brief 2項の最小値求める * @tparam T */ template struct minFunc { /** * @brief 本体 * @param l * @param r * @return T */ static T exec(const T l, const T r) { return l < r ? l : r; } }; /** * @brief 2項の最大値求める * * @tparam T */ template struct maxFunc { /** * @brief 本体 * * @param l * @param r * @return T */ static T exec(const T l, const T r) { return l > r ? l : r; } }; /** * @brief 複数項の最小値 * @see chain * @tparam T * @tparam Ts * @param head * @param tail * @return T */ template inline T minOf(T head, Ts... tail) { return chain>(head, tail...); } /** * @brief 複数項の最大値 * @see chain * @tparam T * @tparam Ts * @param head * @param tail * @return T */ template inline T maxOf(T head, Ts... tail) { return chain>(head, tail...); } /** * @brief change min * @tparam T 型 * @param target 変更する値 * @param candidates * @return 更新があればtrue */ template inline bool chmin(T& target, Ts&&... candidates) { return changeTarget>(target, candidates...); } /** * @brief chminのmax版 * @see chmin * @tparam T 型 * @param target 変更する値 * @param candidates * @return 更新があればtrue */ template inline bool chmax(T& target, Ts&&... candidates) { return changeTarget>(target, candidates...); } /* #endregion */ /* #region template/Random.hpp*/ /** * @file Random.hpp * @author btk * @brief 乱数生成系 * @version 0.1 * @date 2019-07-13 * @copyright Copyright (c) 2019 */ //! 乱数のシード値をプロセスIDとして取得 const pid_t pid = getpid(); /** * @brief XorShift32の実装 */ class XorShift32 { private: //! XorShiftの現在の値 unsigned value; /** * @brief XorShift32のアルゴリズムに基づいて value を更新 */ inline void update() { value = value ^ (value << 13); value = value ^ (value >> 17); value = value ^ (value << 5); } /** * @brief 値を更新し,更新前の値を返却 * @return unsigned 呼び出し時の value を用いる */ inline unsigned get() { unsigned v = value; update(); return v; } public: /** * @brief [0, 2^bit) の範囲の乱数値を取り出す * @tparam デフォルトは31 * @return int */ template inline int next_int() { return (int)(get() >> (32 - bit)); } /** * @brief [-2^bit,2^bit)の範囲の乱数値を取り出す * @tparam デフォルトは31 * @return int */ template inline int next_signed() { unsigned v = get(); return (int)((v >> (31 - bit)) - (1 << (bit))); } /** * @brief next_int呼び出し時の最大値を取得 * @tparam 31 * @return int */ template inline int range_max() { return (int)((1u << bit) - 1); }; /** * @brief Construct a new XorShift32 object * @param seed * @details 初期シードをvalueとするXorShift32のインスタンスを生成 */ XorShift32(const unsigned seed) { value = seed; update(); } /** * @brief Construct a new XorShift 32 object * @details 初期シードをプロセスIDとするXorShift32のインスタンスを生成 */ XorShift32() : XorShift32(pid) {} }; /* #endregion */ /* #region template/STLExtension.hpp*/ /** * @file STLExtension.hpp * @brief STL独自拡張 */ namespace ext { /** * @brief std::sortのWrapper関数 * @tparam Container std::vectorやstd::listを想定 * @param container ソートしたいコンテナオブジェクト * @return Container& * ソート後のコンテナオブジェクト==引数に渡したオブジェクト */ template inline Container& sort(Container& container) { sort(std::begin(container), std::end(container)); return container; } /** * @brief std::sortのWrapper関数 * @tparam Container std::vectorやstd::listを想定 * @tparam Comparator 比較関数の型 * @param container ソートしたいコンテナオブジェクト * @param comparator 比較関数 * @return Container& * ソート後のコンテナオブジェクト==引数に渡したオブジェクト */ template inline Container& sort(Container& container, Comparator comparator) { sort(std::begin(container), std::end(container), comparator); return container; } /** * @brief std::reverseのWrapper関数 * @tparam Container std::vectorやstd::listを想定 * @param container 反転したいコンテナオブジェクト * @return Container& * 反転後のコンテナオブジェクト==引数に渡したオブジェクト */ template inline Container& reverse(Container& container) { reverse(std::begin(container), std::end(container)); return container; } /** * @brief std::accumulateのvector限定Wrapper関数 * @tparam T 配列の要素の型 * @tparam U 戻り値の型 * @param container 配列 * @param zero 初期値 * @return U 総和 */ template inline U accumulate(const std::vector& container, U zero) { return std::accumulate(std::begin(container), std::end(container), zero); } /** * @brief std::accumulateのvector限定Wrapper関数の、引数省略版 * @tparam T 配列の要素の型 && 戻り値の型 * @param container 配列 * @return T 総和 overflowに注意 */ template inline T accumulate(const std::vector& container) { return accumulate(container, T(0)); } /** * @brief std::countのWrapper関数 * @tparam Container std::vectorやstd::listを想定 * @tparam T 数える値の型 * @param container コンテナオブジェクト * @param value 数える値 * @return int */ template inline int count(Container& container, T value) { return std::count(std::begin(container), std::end(container), value); } /** * @brief 等差数列のvectorを作る関数 * @param n 要素数 * @param startFrom 初項 * @param step 公差 * @return std::vector 等差数列 */ inline std::vector iota(int n, int startFrom = 0, int step = 1) { std::vector container(n); int v = startFrom; for (int i = 0; i < n; i++, v += step) { container[i] = v; } return container; } /** * @brief * (*max_element) のwrapper、位置は返さない * @tparam ITR iterator * @param l iteratorの最初 * @param r iteratorの終了位置 * @param defaultValue 要素がないときのデフォルト値 * @return auto 最大値、型はコンテナ内の型 */ template inline auto maxIn(ITR l, ITR r, std::remove_reference_t defaultValue = 0) { if (r == l) { return defaultValue; } return *std::max_element(l, r); } /** * @brief maxIn の vector 限定版 * @tparam T 戻り値の型 * @param containter 最大値求める対象のコンテナ * @param defaultValue コンテナの要素がない場合の初期値 * @return T 最大値、コンテナ似要素がない場合はdefaultValue */ template inline T maxIn(std::vector container, T defaultValue = 0) { return maxIn(container.begin(), container.end(), defaultValue); } /** * @brief * (*min_element) のwrapper、位置は返さない * @tparam ITR iterator * @param l iteratorの最初 * @param r iteratorの終了位置 * @param defaultValue 要素がないときのデフォルト値 * @return auto 最小値、型はコンテナ内の型 */ template inline auto minIn(ITR l, ITR r, std::remove_reference_t defaultValue = 0) { if (r == l) { return defaultValue; } return *std::min_element(l, r); } /** * @brief minIn の vector 限定版 * @tparam T 戻り値の型 * @param containter 最大値求める対象のコンテナ * @param defaultValue コンテナの要素がない場合の初期値 * @return T 最小値、コンテナ似要素がない場合はdefaultValue */ template inline T minIn(std::vector container, T defaultValue = 0) { return minIn(container.begin(), container.end(), defaultValue); } } // namespace ext /* #endregion */ /* #region template/Strings.hpp*/ /** * @file Strings.hpp * @author btk * @brief 文字列を扱いやすくするライブラリ */ /** * @brief コレクションを文字列に変換する関数 * @tparam T コレクションの型、range-based for に対応している必要あり * @tparam DelimiterType 区切り文字の型 * @param v コレクション * @param delimiter 区切り文字 * @return std::string delimiterで結合された文字列 */ template std::string join(const T& v, const DelimiterType& delimiter) { std::stringstream ss; bool isFirst = true; for (auto& it : v) { if (!isFirst) { ss << delimiter; } isFirst = false; ss << it; } return ss.str(); } /** * @brief コレクションを文字列に変換する関数(イテレータ版) * @tparam ITR イテレータ型 * @tparam DelimiterType 区切り文字の型 * @param bg 開始 * @param ed 終了 * @param delimiter 区切り文字 * @return std::string delimiterで結合された文字列 */ template std::string join(const ITR bg, const ITR ed, const DelimiterType& delimiter) { std::stringstream ss; bool isFirst = true; for (auto it = bg; it != ed; ++it) { if (!isFirst) { ss << delimiter; } isFirst = false; ss << *it; } return ss.str(); } /** * @brief Strings.hppの内部関数 */ namespace strings { /** * @brief std::size_tをWrapする構造体 * @tparam i 本体 */ template struct IndexWrapper {}; /** * @brief tuple用のjoin関数の内部で使われるテンプレート構造体(関数) * @tparam CurrentIndex 現在のindex * @tparam LastIndex 最後のindex * @tparam DelimiterType 区切り文字 * @tparam Ts tupleに使用するパラメータパック */ template struct JoinFunc; /** * @brief tuple用join関数の再帰末尾用構造体 .joinが本体 * @tparam i 現在のid = tupleの最後の要素のid * @tparam DelimiterType 区切り文字 * @tparam Ts tupleに使用するパラメータパック */ template struct JoinFunc, IndexWrapper, DelimiterType, Ts...> { /** * @brief tuple用join関数の末尾再帰 * @param ss stringstream * @param values 文字列化したいtuple * @param delimiter 区切り文字 * @return std::stringstream& 引数で渡したもの */ static std::stringstream& join(std::stringstream& ss, const std::tuple& values, const DelimiterType& delimiter) { unused_var(delimiter); ss << std::get(values); return ss; } }; /** * @brief tuple用join関数の内部構造体 * @tparam i 現在のid * @tparam j tupleの最後の要素のid * @tparam DelimiterType 区切り文字 * @tparam Ts パラメータパック */ template struct JoinFunc, IndexWrapper, DelimiterType, Ts...> { /** * @brief tuple用join関数の本体 * @param ss stringstream * @param values 文字列化したいtuple * @param delimiter 区切り文字 * @return std::stringstream& 引数で渡したもの */ static std::stringstream& join(std::stringstream& ss, const std::tuple& values, const DelimiterType& delimiter) { ss << std::get(values); ss << delimiter; return JoinFunc, IndexWrapper, DelimiterType, Ts...>::join(ss, values, delimiter); } }; } // namespace strings /** * @brief 複数の値をjoinする関数 * @tparam DelimiterType 区切り文字の型 * @tparam Ts パラメータパック * @param values 文字列として結合したいタプル * @param delimiter 区切り文字 * @return std::string 結合後の文字列 */ template std::string join(const std::tuple& values, const DelimiterType& delimiter) { std::stringstream ss; constexpr std::size_t lastIndex = std::tuple_size>::value - 1u; return strings::JoinFunc, strings::IndexWrapper, DelimiterType, Ts...>::join(ss, values, delimiter) .str(); } /* #endregion */ /* #region Template.hpp*/ /** * @file Template.hpp * @brief 競技プログラミング用テンプレート * @author btk15049 * @date 2019/05/02 */ /* #endregion */ /* #endregion */ /**/ #endif struct cww { cww() { io::enableFastIO(); io::setDigits(10); } } star; struct expr { using LeftHandSide = bitset<64>; LeftHandSide lhs; int rhs; expr() {} expr(LeftHandSide lhs, int rhs) : lhs(lhs), rhs(rhs) {} bool isLhs0() { return lhs.none(); } bool isInvalid() { return isLhs0() && rhs == 0; } }; expr operator^(expr l, expr r) { return expr(l.lhs ^ r.lhs, l.rhs ^ r.rhs); } // Ax = y を解く // 解なしのときはfalseが返る bool gaussJordan(vector& exprList) { constexpr size_t termSize = expr::LeftHandSide().size(); vector> es(termSize); for (auto e : exprList) { if (e.isInvalid()) { return false; } if (e.isLhs0()) { continue; } es[e.lhs._Find_first()].push_back(e); } for (int i : range(termSize)) { if (es[i].empty()) { continue; } auto& f = es[i].front(); while (es[i].size() > 1u) { auto newExpr = f ^ es[i].back(); es[i].pop_back(); if (newExpr.isInvalid()) { return false; } if (newExpr.isLhs0()) { continue; } es[newExpr.lhs._Find_first()].push_back(newExpr); } for (int j : range(i)) { for (auto& e : es[j]) { e = e ^ f; } } } exprList.clear(); for (int i : range(termSize)) { if (es[i].empty()) { continue; } exprList.push_back(es[i].front()); } return true; } vector getOneX(vector& exprList) { constexpr size_t termSize = expr::LeftHandSide().size(); vector x(termSize); for (auto& it : exprList) { x[it.lhs._Find_first()] = it.rhs; } return x; } int main() { /* write here */ int N, M; cin >> N >> M; vector> A(M); vector> Y(M); for (int i : range(M)) { int num; cin >> num; for (int j : range(num)) { int b; cin >> b; A[i][b - 1] = true; } unsigned y; cin >> y; Y[i] = bitset<64>(y); } vector> ret(N); for (int bi : range(30)) { vector es(M); for (int i : range(M)) { es[i] = expr(A[i], Y[i][bi] ? 1 : 0); } if (gaussJordan(es) == false) { cout << -1 << endl; return 0; } auto X = getOneX(es); for (int i : range(N)) { ret[i][bi] = (X[i] == 1); } } for (int i : range(N)) { cout << ret[i].to_ullong() << endl; } return 0; }