#include using namespace std; typedef long long ll; /* 実行時modint: template struct Fp{}; int main(){ static int mod;cin >> mod; using mint = Fp; } */ template struct Fp{ long long x; constexpr Fp(const long long _x=0)noexcept:x((_x%mod+mod)%mod){} constexpr Fp operator-()const noexcept{ return x ? mod-x:0; } friend constexpr Fp& operator+=(Fp &l,const Fp r)noexcept{ l.x+=r.x; if(l.x>=mod)l.x-=mod; return l; } friend constexpr Fp& operator-=(Fp &l,const Fp r)noexcept{ l.x-=r.x; if(l.x<0)l.x+=mod; return l; } //modが十分小さい場合 friend constexpr Fp& operator*=(Fp &l,const Fp r)noexcept{ l.x=l.x*r.x %mod; return l; } //modが巨大な場合 /* friend constexpr Fp prod(Fp l,long long r)noexcept{ if(r==0)return 0; Fp res=prod(l+=l,r>>1); if(r&1)res+=l; return res; } friend constexpr Fp& operator*=(Fp &l,const Fp r)noexcept{ return l=prod(l,r.x); } */ friend constexpr Fp& operator/=(Fp &l,const Fp r)noexcept{ long long a=r.x,b=mod,u=1,v=0; while(b){ ll t=a/b; a-=t*b;swap(a,b); u-=t*v;swap(u,v); } l.x=l.x*u%mod; if(l.x<0)l.x+=mod; return l; } friend constexpr Fp operator+(Fp l,const Fp r){ return l+=r; } friend constexpr Fp operator-(Fp l,const Fp r){ return l-=r; } friend constexpr Fp operator*(Fp l,const Fp r){ return l*=r; } friend constexpr Fp operator/(Fp l,const Fp r){ return l/=r; } #ifdef LOGX friend constexpr bool operator==(const Fp l,const Fp r){ return l.x==r.x; } friend constexpr bool operator!=(const Fp l,const Fp r){ return l.x!=r.x; } #endif friend constexpr ostream& operator<<(ostream &os,const Fp &r)noexcept{ return os << r.x; } friend constexpr istream& operator>>(istream &is,Fp &r)noexcept{ ll t=0;is >> t; r.x=(Fp(t)).x; return is; } }; template struct Matrix{ vector> v; Matrix(const int n,const int m,T x=0):v(n,vector(m,x)){} size_t size()const{return v.size();} inline vector& operator[](const int i){return v[i];} }; template int modp_Gauss_Jordan(Matrix> &a,bool is_ex=false){ int m=a.size(),n=a[0].size(); int rank=0; for(int col=0;col now=1/a[rank][col]; for(int col2=col;col2=colでよい. for(int row=0;row fac=a[row][col]; for(int col2=col;col2 int modp_linear_equation(Matrix>A,vector b,vector &res){ int m=A.size(),n=A[0].size(); Matrix> M(m,n+1); for(int i=0;i val[MAX_ROW]; bitMatrix(int m=1,int n=1):h(m),w(n){} inline bitset& operator[](const int i){return val[i];} }; int bit_Gauss_Jordan(bitMatrix &a,bool is_ex=false){ int rank=0; for(int col=0;col b,vector &res){ int m=A.h; int n=A.w; bitMatrix M(m,n+1); for(int i=0;i>; int main(){ int N,M;cin >> N >> M; bitMatrix B(M,N); vector Y(M); for(int i=0;i> A; for(int j=0;j> b; B[i][b-1]=1; } cin >> Y[i]; } bool ok=true; vector ans(N); vector res; vector b(M); for(int i=0;i<30;i++){ for(int j=0;j>i)&1); int rank=bit_linear_equation(B,b,res); if(rank==-1){ ok=false; break; } for(int j=0;j