#include typedef uint64_t u64; typedef int64_t i64; using namespace std; void solve(); int main(){ cout<>T; } for(int i=0;i void turtle_in(T& n){ cin>>n; } template void turtle_in(pair& p){ turtle_in(p.first); turtle_in(p.second); } template void turtle_in(vector& v){ for(auto& u:v){ turtle_in(u); } } template void turtle_out(T& n){ cout< void turtle_out(pair& p){ cout<<"{"; turtle_out(p.first); cout<<", "; turtle_out(p.second); cout<<"}"; } template void turtle_out(vector& v){ for(int i=0;i void turtle_out(vector>& v){ for(int i=0;i void scan(T& n,Args&... args){ turtle_in(n); scan(args...); } void print(){} template void print(T n,Args... args){ turtle_out(n); print(args...); } template void println(T n){ turtle_out(n); cout< void println(T n,Args... args){ turtle_out(n); cout<<" "; println(args...); } template struct modint{ u64 val; modint(i64 val_=0):val((val_%i64(mod)+i64(mod))%i64(mod)){} modint operator-(){ return modint(mod-val); } modint operator+(modint rhs){ return modint(*this)+=rhs; } modint operator-(modint rhs){ return modint(*this)-=rhs; } modint operator*(modint rhs){ return modint(*this)*=rhs; } modint operator/(modint rhs){ return modint(*this)/=rhs; } modint &operator+=(modint rhs){ val+=rhs.val; val-=((val>=mod)?mod:0); return (*this); } modint &operator-=(modint rhs){ val+=((val>=1; } return (*this)*=now; } bool operator==(modint rhs){ return val==rhs.val; } bool operator!=(modint rhs){ return val!=rhs.val; } friend std::ostream &operator<<(std::ostream& os,modint x){ return os<<(x.val); } friend std::istream &operator>>(std::istream& is,modint& x){ u64 t; is>>t,x=t; return is; } }; template T power(T a,U n){ T res=1; while(n>0){ if(n%2==1){ res*=a; } a*=a; n/=2; } return res; } template struct genrand{ uniform_int_distribution gen; mt19937 engine; genrand(T a,T b):gen(a,b){ random_device seed_gen; engine.seed(seed_gen()); } T operator()(){ return gen(engine); } }; template struct comb{ vector dat,idat; comb(int mx=3000000):dat(mx+1,1),idat(mx+1,1){ for(int i=1;i<=mx;++i){ dat[i]=dat[i-1]*i; } idat[mx]/=dat[mx]; for(int i=mx;i>0;--i){ idat[i-1]=idat[i]*i; } } T operator()(int n,int k){ if(n<0||k<0||n struct NTT{ typedef modint mint; mint g=getg_(); vector rev; mint getg_(){ for(mint i=2;;i+=1){ if(power_(i,(mod-1)>>1)!=1){ return i; } } } mint power_(mint a,u64 n){ mint res=1; while(n){ res*=((n&1)?a:1); a*=a; n>>=1; } return res; } void dft(vector& f){ int siz=f.size(); for(int i=0;i operator()(vector a,vector b){ int cnt=0,siz=1,mxsiz=a.size()+b.size()-1; while(siz>1]>>1)+(1< struct Poly{ typedef modint mint; NTT ntt; vector val; Poly():val({0}){} Poly(mint t):val({t}){} Poly(int siz):val(max(1,siz)){} Poly(initializer_list> init):val(init){} Poly(vector init):val(init){} mint &operator[](int i){ return val[i]; } int size(){ return val.size(); } void resize(int siz){ val.resize(siz); } Poly operator+(Poly rhs){ return Poly(*this)+=rhs; } Poly operator-(Poly rhs){ return Poly(*this)-=rhs; } Poly operator*(Poly rhs){ return Poly(*this)*=rhs; } Poly operator/(Poly rhs){ return Poly(*this)/=rhs; } Poly operator%(Poly rhs){ return Poly(*this)%=rhs; } Poly operator-(){ for(mint& v:val){ v=mint(0)-v; } return (*this); } Poly operator+=(Poly rhs){ resize(max(this->size(),rhs.size())); for(int i=0;isize(),rhs.size())); for(int i=0;i0;--i){ if(val[i]==0){ val.pop_back(); } else{ return; } } } vector multieval(vector> a){ int siz=1; while(siz> t(siz*2-1,{1}); for(int i=0;i=0;--i){ t[i]=t[2*i+1]*t[2*i+2]; } vector> g(siz*2-1); g[0]=(*this)%t[0]; for(int i=1;i> res(a.size()); for(int i=0;i> a){ int siz=1; while(siz> res(siz*2-1,{1}); for(int i=0;i=0;--i){ res[i]=res[2*i+1]*res[2*i+2]; } (*this)=res[0]; } void lagrange_interpolation(vector x,vector y){ int N=x.size(); vector> h(N); for(int i=0;i g; g.product(h); Poly g_=g; g_.diffrent(); vector t=g_.multieval(x); for(int i=0;i> den(2*N-1),num(2*N-1,{1}); for(int i=0;i=0;--i){ den[i]=den[2*i+1]*den[2*i+2]; num[i]=num[2*i+1]*den[2*i+2]+num[2*i+2]*den[2*i+1]; } (*this)=num[0]; } }; void solve(){ int H,W; scan(H,W); vector S(H); scan(S); set> all; for(int i=0;i> st=all; vector> tmp; while(st.size()){ auto p=(*st.begin()); st.erase(st.begin()); tmp.emplace_back(); tmp.back().emplace_back(0); for(int t=-50;t<=50;++t){ if(st.count({p.first+I*t,p.second+J*t})){ st.erase({p.first+I*t,p.second+J*t}); tmp.back().emplace_back(t); } } } bool f=1; for(auto v:tmp){ while(2<=v.size()){ int n=v.size(); if(v[n-2]+1==v[n-1]){ v.resize(n-2); } else{ break; } } if(v.size()!=0){ f=0; } } if(f){ println("YES"); return; } } } println("NO"); }