QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#539484#8935. Puzzle: Easy as Scrabbleucup-team087#AC ✓38ms30524kbC++2018.2kb2024-08-31 14:57:192024-08-31 14:57:19

Judging History

你现在查看的是最新测评结果

  • [2024-08-31 14:57:19]
  • 评测
  • 测评结果:AC
  • 用时:38ms
  • 内存:30524kb
  • [2024-08-31 14:57:19]
  • 提交

answer

#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

bool dbg=false;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;
using vvi=vc<vc<int>>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

ll rand_int(ll l, ll r) { //[l, r]
	//#ifdef LOCAL
	static mt19937_64 gen;
	/*#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif*/
	return uniform_int_distribution<ll>(l, r)(gen);
}

ll rand_int(ll k){ //[0,k)
	return rand_int(0,k-1);
}
string rand_string(int n,char lw,char up){
	string s(n,'?');
	rep(i,n)s[i]=rand_int(lw,up);
	return s;
}

int current_run_id,run_batch_size=1000;
int calc_random_limit(){
	return current_run_id/run_batch_size+1;
}
template<class t>
void generate_single(t&a){
	a=rand_int(1,calc_random_limit());
}
void generate_single(string&a){
	int n;generate_single(n);
	a=rand_string(n,'a','b');
}
template<class t,class u>
void generate_single(pair<t,u>&a){
	generate_single(a.a);
	generate_single(a.b);
}
//https://trap.jp/post/1224/
template<class... Args>
void input(Args&... a){
	if(dbg){
		(generate_single(a),...);
	}else{
		(cin >> ... >> a);
	}
}
#define INT(...) int __VA_ARGS__;input(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;input(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;input(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;input(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;input(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;input(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;input(__VA_ARGS__)
#define overload3(a,b,c,d,...) d
#define VI2(name,size) vi name(size);rep(i_##name,size)input(name[i_##name]);
#define VI3(name,size,offset) vi name(size);rep(i_##name,size)input(name[i_##name]),name[i_##name]+=offset;
#define VI(...) overload3(__VA_ARGS__,VI3,VI2)(__VA_ARGS__)
#define VPI(name,size) vc<pi> name(size);rep(i_##name,size)input(name[i_##name]);
#define VVI(name,sizeN,sizeM) vvi name(sizeN,vi(sizeM));\
rep(i_##name,sizeN)rep(j_##name,sizeM)input(name[i_##name][j_##name]);
#define VS(name,size) vc<string> name(size);rep(i_##name,size)input(name[i_##name]);

#define overload5(a,b,c,d,e,f,...) f
#define VVC4(type,name,sizeN,sizeM) vvc<type> name(sizeN,vc<type>(sizeM));
#define VVC5(type,name,sizeN,sizeM,ini) vvc<type> name(sizeN,vc<type>(sizeM,ini));
#define VVC(...) overload5(__VA_ARGS__,VVC5,VVC4)(__VA_ARGS__)

template<class T>
T vvvc(T v){
	return v;
}

template<class T,class...Args>
auto vvvc(int n,T v,Args...args){
	return vector(n,vvvc(v,args...));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

void printsuc(int suc){
	if(suc==1){
		if(dbg)cout<<endl;
		else{
			#ifdef LOCAL
			cout<<endl;
			#else
			cout<<"\n";
			#endif
		}
	}
	if(suc==2)
		cout<<" ";
}

template<class t>
void print_single(t x,int suc=1){
	cout<<x;
	printsuc(suc);
}

template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
	print_single(p.a,2);
	print_single(p.b,suc);
}

template<class T>
void print_single(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print_single(v[i],i==int(v.size())-1?3:2);
	printsuc(suc);
}

template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
	rep(i,N)
		print_single(v[i],i==int(N)-1?3:2);
	printsuc(suc);
}

template<class T>
void print(const T&t){
	print_single(t);
}

template<class T,class ...Args>
void print(const T&t,const Args&...args){
	print_single(t,2);
	print(args...);
}

template<class T>
void printvv(const vvc<T>&vs){
	for(const auto&row:vs)print(row);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

void YES(bool ex=true){
	cout<<"YES\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void NO(bool ex=true){
	cout<<"NO\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void Yes(bool ex=true){
	cout<<"Yes\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void No(bool ex=true){
	cout<<"No\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}*/
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
int popcount(ull t){
	return __builtin_popcountll(t);
}
int bitparity(ll t){
	return __builtin_parityll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}
ull umask(int i){
	return (ull(1)<<i)-1;
}
ll minp2(ll n){
	if(n<=1)return 1;
	else return ll(1)<<(topbit(n-1)+1);
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class S> void mkuni(S&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

template<class t> bool isuni(vc<t> v){
	int s=si(v);
	mkuni(v);
	return si(v)==s;
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class S,class u>
int lwb(const S&v,const u&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t,class u>
bool bis(const vc<t>&v,const u&a){
	return binary_search(all(v),a);
}

//VERIFY: yosupo
//KUPC2017J
//AOJDSL1A
//without rank
struct unionfind{
	vi p,s;
	int c;
	unionfind(int n):p(n,-1),s(n,1),c(n){}
	void clear(){
		fill(all(p),-1);
		fill(all(s),1);
		c=si(p);
	}
	int find(int a){
		return p[a]==-1?a:(p[a]=find(p[a]));
	}
	//set b to a child of a
	bool unite(int a,int b){
		a=find(a);
		b=find(b);
		if(a==b)return false;
		p[b]=a;
		s[a]+=s[b];
		c--;
		return true;
	}
	bool same(int a,int b){
		return find(a)==find(b);
	}
	int sz(int a){
		return s[find(a)];
	}
};

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> rand_tree(int n){
	vvc<int> t(n);
	unionfind uf(n);
	while(uf.c>1){
		int a=rand_int(n);
		int b=rand_int(n);
		if(uf.unite(a,b)){
			t[a].pb(b);
			t[b].pb(a);
		}
	}
	return t;
}

vvc<int> readTree(int n){
	if(dbg){
		return rand_tree(n);
	}else{
		return readGraph(n,n-1);
	}
}

void printTree(const vvc<int> t){
	int n=si(t);
	int degsum=0;
	rep(i,n)degsum+=si(t[i]);
	if(degsum==n-1){
		//directed
		rep(i,si(t))for(auto j:t[i]){
			print(i+1,j+1);
		}
	}else if(degsum==2*(n-1)){
		//undirected
		rep(i,si(t))for(auto j:t[i])if(i<j){
			print(i+1,j+1);
		}
	}else{
		assert(false);
	}
}

template<class t>
vc<t> presum(const vc<t>&a){
	vc<t> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
vc<ll> presum(const vi&a){
	vc<ll> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
	gnr(i,1,si(a))a[i]-=a[i-1];
	return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
	int n=si(a),m=si(a[0]);
	vvc<ll> b(n+1,vc<ll>(m+1));
	rep(i,n)rep(j,m)
		b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
	return b;
}

//verify してないや
void transvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[j][i]=a[i][j];
	}
	a.swap(b);
	transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[m-1-j][i]=a[i][j];
	}
	a.swap(b);
	rotvvc(n,m,args...);
}

//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
	int n=si(a);
	vi idx(n);iota(all(idx),0);
	sort(all(idx),[&](int i,int j){return a[i]<a[j];});
	return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
	int n=si(a);
	assert(si(idx)==n);
	vc<t> vs(n);
	rep(i,n)vs[i]=a[idx[i]];
	return vs;
}
//CF850C
vi invperm(const vi&p){
	int n=si(p);
	vi q(n);
	rep(i,n)q[p[i]]=i;
	return q;
}

template<class t,class s=t>
s SUM(const vc<t>&a){
	return accumulate(all(a),s(0));
}
template<class t,size_t K,class s=t>
s SUM(const array<t,K>&a){
	return accumulate(all(a),s(0));
}

template<class t>
t MAX(const vc<t>&a){
	return *max_element(all(a));
}

template<class t>
pair<t,int> MAXi(const vc<t>&a){
	auto itr=max_element(all(a));
	return mp(*itr,itr-a.bg);
}

template<class A>
auto MIN(const A&a){
	return *min_element(all(a));
}

template<class t>
pair<t,int> MINi(const vc<t>&a){
	auto itr=min_element(all(a));
	return mp(*itr,itr-a.bg);
}

vi vid(int n){
	vi res(n);iota(all(res),0);
	return res;
}

template<class S>
void soin(S&s){
	sort(all(s));
}

template<class S,class F>
void soin(S&s,F&&f){
	sort(all(s),forward<F>(f));
}

template<class S>
S soout(S s){
	soin(s);
	return s;
}

template<class S>
void rein(S&s){
	reverse(all(s));
}

template<class S>
S reout(S s){
	rein(s);
	return s;
}

template<class t,class u>
pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){
	a.a+=b.a;a.b+=b.b;return a;}
template<class t,class u>
pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){
	a.a-=b.a;a.b-=b.b;return a;}
template<class t,class u>
pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(a.a-b.a,a.b-b.b);}
template<class t,class u,class v>
pair<t,u>&operator*=(pair<t,u>&a,v b){
	a.a*=b;a.b*=b;return a;}
template<class t,class u,class v>
pair<t,u> operator*(pair<t,u> a,v b){return a*=b;}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a){return mp(-a.a,-a.b);}
namespace std{
template<class t,class u>
istream&operator>>(istream&is,pair<t,u>&a){
	return is>>a.a>>a.b;
}
}

template<class t>
t gpp(vc<t>&vs){
	assert(si(vs));
	t res=move(vs.back());
	vs.pop_back();
	return res;
}

template<class t,class u>
void pb(vc<t>&a,const vc<u>&b){
	a.insert(a.ed,all(b));
}

template<class t,class...Args>
vc<t> cat(vc<t> a,Args&&...b){
	(pb(a,forward<Args>(b)),...);
	return a;
}

template<class t,class u>
vc<t>& operator+=(vc<t>&a,u x){
	for(auto&v:a)v+=x;
	return a;
}

template<class t,class u>
vc<t> operator+(vc<t> a,u x){
	return a+=x;
}

template<class t>
vc<t>& operator+=(vc<t>&a,const vc<t>&b){
	a.resize(max(si(a),si(b)));
	rep(i,si(b))a[i]+=b[i];
	return a;
}

template<class t>
vc<t> operator+(const vc<t>&a,const vc<t>&b){
	vc<t> c(max(si(a),si(b)));
	rep(i,si(a))c[i]+=a[i];
	rep(i,si(b))c[i]+=b[i];
	return c;
}

template<class t,class u>
vc<t>& operator-=(vc<t>&a,u x){
	for(auto&v:a)v-=x;
	return a;
}
template<class t,class u>
vc<t> operator-(vc<t> a,u x){
	return a-=x;
}

template<class t,class u>
vc<t>& operator*=(vc<t>&a,u x){
	for(auto&v:a)v*=x;
	return a;
}
template<class t,class u>
vc<t> operator*(vc<t> a,u x){
	return a*=x;
}

template<class t,class u>
vc<t>& operator/=(vc<t>&a,u x){
	for(auto&v:a)v/=x;
	return a;
}
template<class t,class u>
vc<t> operator/(vc<t> a,u x){
	return a/=x;
}

template<class t>
vc<t>& operator<<=(vc<t>&a,int k){
	assert(k>=0);
	a.insert(a.bg,k,t(0));
	return a;
}
template<class t>
vc<t> operator<<(vc<t> a,int k){
	return a<<=k;
}

template<class t>
vc<t>& operator>>=(vc<t>&a,int k){
	if(si(a)<=k)a.clear();
	else a.erase(a.bg,a.bg+k);
	return a;
}
template<class t>
vc<t> operator>>(vc<t> a,int k){
	return a>>=k;
}

template<class t,class u>
void remval(vc<t>&a,const u&v){
	a.erase(remove(all(a),v),a.ed);
}
//消した要素の個数を返してくれる
//UCUP 2-8-F
template<class t,class F>
int remif(vc<t>&a,F f){
	auto itr=remove_if(all(a),f);
	int res=a.ed-itr;
	a.erase(itr,a.ed);
	return res;
}

template<class VS,class u>
void fila(VS&vs,const u&a){
	fill(all(vs),a);
}

template<class t,class u>
int findid(const vc<t>&vs,const u&a){
	auto itr=find(all(vs),a);
	if(itr==vs.ed)return -1;
	else return itr-vs.bg;
}

template<class t>
void rtt(vc<t>&vs,int i){
	rotate(vs.bg,vs.bg+i,vs.ed);
}

//Multiuni2023-8 C
//f(lw)=false,...,f(n-1)=false,f(n)=true,...,f(up)=true,
//のときに n を返す
template<class F>
int find_min_true(int lw,int up,F f){
	while(up-lw>1){
		const int mid=(lw+up)/2;
		if(f(mid))up=mid;
		else lw=mid;
	}
	return up;
}
//f(lw)=true,f(up)=false
template<class F>
int find_max_true(int lw,int up,F f){
	while(up-lw>1){
		const int mid=(lw+up)/2;
		if(f(mid))lw=mid;
		else up=mid;
	}
	return lw;
}

template<class t> using pqmin=priority_queue<t,vc<t>,greater<t>>;
template<class t> using pqmax=priority_queue<t>;
using T=tuple<int,int,int>;

void slv(){
	INT(n,m);
	VS(ss,n+2);
	vi lc(n),rc(n,m),uc(m),dc(m,n);
	
	auto genmask=[&](char c)->int{
		if(c=='.')return mask(26);
		else return 1<<(c-'A');
	};
	auto L=[&](int i){
		assert(inc(0,i,n-1));
		return genmask(ss[1+i].front());
	};
	auto R=[&](int i){
		assert(inc(0,i,n-1));
		return genmask(ss[1+i].back());
	};
	auto U=[&](int i){
		assert(inc(0,i,m-1));
		return genmask(ss.front()[1+i]);
	};
	auto D=[&](int i){
		assert(inc(0,i,m-1));
		return genmask(ss.back()[1+i]);
	};
	VVC(int,cur,n,m,mask(26));
	bool globalbad=false;
	VVC(bool,banned,n,m);
	vc<pi> banq;
	auto chmask=[&](int i,int j,int v){
		if(cur[i][j]){
			cur[i][j]&=v;
			if(cur[i][j]==0){
				banq.eb(i,j);
			}
		}
	};
	auto ban=[&](int i,int j){
		if(banned[i][j])return;
		//assert(!banned[i][j]);
		banned[i][j]=true;
		while(lc[i]<m&&banned[i][lc[i]])lc[i]++;
		if(L(i)!=mask(26)){
			if(lc[i]==m){
				globalbad=true;
				return;
			}
			chmask(i,lc[i],L(i));
		}
		while(rc[i]>0&&banned[i][rc[i]-1])rc[i]--;
		if(R(i)!=mask(26)){
			if(rc[i]==0){
				globalbad=true;
				return;
			}
			chmask(i,rc[i]-1,R(i));
		}
		while(uc[j]<n&&banned[uc[j]][j])uc[j]++;
		if(U(j)!=mask(26)){
			if(uc[j]==n){
				globalbad=true;
				return;
			}
			chmask(uc[j],j,U(j));
		}
		while(dc[j]>0&&banned[dc[j]-1][j])dc[j]--;
		if(D(j)!=mask(26)){
			if(dc[j]==0){
				globalbad=true;
				return;
			}
			chmask(dc[j]-1,j,D(j));
		}
	};
	
	rep(i,n){
		chmask(i,lc[i],L(i));
		chmask(i,rc[i]-1,R(i));
	}
	rep(j,m){
		chmask(uc[j],j,U(j));
		chmask(dc[j]-1,j,D(j));
	}
	rep(i,n)rep(j,m)if(ss[1+i][1+j]=='x')banq.eb(i,j);
	
	while(!globalbad&&si(banq)){
		dmp(banq);
		auto [i,j]=gpp(banq);
		ban(i,j);
	}
	if(globalbad)return NO(0);
	YES(0);
	vc<string> ans(n,string(m,'.'));
	rep(i,n)rep(j,m)if(!banned[i][j]&&cur[i][j]){
		ans[i][j]='A'+botbit(cur[i][j]);
	}
	rep(i,n)print(ans[i]);
}

signed main(signed argc,char*argv[]){
	if(argc>1&&strcmp(argv[1],"D")==0)dbg=true;
	
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	if(dbg){
		while(1){
			if(current_run_id%run_batch_size==0){
				cerr<<"Current Run "<<current_run_id<<endl;
			}
			slv();
			current_run_id++;
		}
	}else{
		//int t;cin>>t;rep(_,t)
		slv();
	}
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3868kb

input:

5 5
.CBA...
....x..
..x...C
A.....B
B..x..A
C......
.......

output:

YES
CBA.A
A.AAC
AAAAB
BA.AA
CAAAA

result:

ok Correct.

Test #2:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

1 2
....
Nx..
..O.

output:

NO

result:

ok Correct.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

5 5
.U.N.X.
U....xX
Ox....X
M...xxN
Vx....S
Ix.x..X
..IBHX.

output:

YES
UANX.
.OAAX
MAN..
.VBAS
.I.HX

result:

ok Correct.

Test #4:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

10 10
.BAZEMIEKUJ.
A..........K
B..x.x.x..x.
K.........xT
A.x..x.....J
Hx....x....B
Q..x....x.xW
S...x......W
S...x.xxx..Z
...x......xZ
I..x..x.x.xR
.QKO.ID..RW.

output:

YES
.AZEMIEK..
BA.A.A.AU.
KAAAAAAAT.
A.AA.AAAAJ
.HAAA.AAAB
QA.AAAA.W.
SAA.AAAAAW
SAO.A...Z.
QK.AADAAZ.
...II.A.R.

result:

ok Correct.

Test #5:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

5 10
.PTWIVVISPY.
T...x.x....Y
Xx.x.xx..x.K
P.x.xx.....K
S..........A
E.........xS
.SPEASDCYSA.

output:

YES
.TW.V.ISPY
.X.I..AA.K
P.A..VAAAK
SPAAAAAAAA
..EASDCYS.

result:

ok Correct.

Test #6:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

10 5
.HVYN..
Y.x...C
V..x..B
H...x.Z
....xxN
....x.P
B.x...G
Fx.x..D
Txx..xK
E..x.xR
Sx....B
.EPSBD.

output:

YES
..YNC
.V.AB
HAA.Z
AAN..
AAA.P
B.AAG
.F.AD
..TK.
EP.R.
..SB.

result:

ok Correct.

Test #7:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

50 50
.YDOGQIDENEUMONVSGZNMNHLEZCXIRMK.OOCKJOKXXZDUFEMPXS.
Y.x...x.x.x..x..........x.......x......x.....x....xX
N.........x.....x.....x....x.x.xxxxx.x...x.........E
U.....x.....x....x......x.....x........x..........xS
...x......x........x..x.....x.x.x........x.x.x.....S
Q.....x.x..x..........x....x....

output:

YES
Y.OGQ.D.N.UM.NVSGZNMNHL.ZCXIRMK.OOCKJO.XXZDU.EMPX.
NDAAAIAEA.AAOAA.AAAAA.AEAA.A.A.....A.AKA.AAAFAAAE.
UAAAA.AAAEA.AAAA.AAAAAA.AAAAA.AAAAAAAA.AAAAAAAAAS.
AA.AAAAAA.AAAAAAAA.AA.AAAAA.A.A.AAAAAAAA.A.A.AAAAS
QAAAA.A.AA.AAAAAAAAAA.AAAA.AAA.AA.AAA..AAA.AAA.AAL
FAAAA.A.AA.AA.AAAA.AAA..AA..AAAAA.AAAAAAA...

result:

ok Correct.

Test #8:

score: 0
Accepted
time: 1ms
memory: 3960kb

input:

100 100
.NUXAMX.LNWZKRRKZIRNZVDJF.XRB.VEFQXHTGLGIKZYSRPPF.YGVTOSQCADEG.KYKH.NWWO.XDXJW.G.RBHABFLWHFVUNOLBHMKN.
U..x...x...x....xx........x.....x.....xxx..x..........x..x...x..xx..x..x..x............x.....x.....x.N
C...x.......x.............x....x.x.x..x........x..x.xx..x..xx.................x..........

output:

YES
.U.AMX.LNW.KRRK..RNZVDJFA.RBAVE.QXHTG...KZ.SRPPFAYGVT.SQ.ADE.AK..HA.WW.AX.XJWAGARBHABF.WHFVU.OLBHM.N
.CX.AAAAAAZ.AAAZIAAAAAAAA.AAAA.F.A.AA.GIAAYAAA.AA.A..OA.CA..GAAYKAANAAOAADAAA.AAAAAAAA.AA...NAAA..KO
.OAAAAAAAAAAAAAA.AAAAA..A..AA.A..A.AAL....AAAAAAA.AA..AA.AA.AAAAAAAAA.AAAAA.AAAAAAA.AA.AAAA.AA...

result:

ok Correct.

Test #9:

score: 0
Accepted
time: 5ms
memory: 6876kb

input:

500 500
..FHFDLGFGHREQBGILNRAGJ.ERZSAFGLQ.ESEBI.ELKM.RENLNFQSPT.TXUEIKHHOQWABSELMOPGTFGTXGYMTSU.N.O.AX.OGNSWTFSLUIMTUX.RUCECKZCXOJNPTFVAJUJTF.LHXURYIQIJCVWDBVZ.ZXFRAT.XIPXTDCSLHJHSZCW.RMNUGPIHYUQYUYAY.NHCBU.JPMLG.DDXAJWKNZJVKNAWAJZAHW.FCBEVATZ.YZ.HQ..QPLFARSHNP..EDPIKLYLF.FIFXEXR.XSUORAP.CZPMJXPUS.W...

output:

YES
A..FDL...HREQ..ILNRA..AERZSA.GL.A.SE.IA.LK.A.ENLNFQS.TATX.E.K.HOQWA.SE.M.PGTFG.XGY..SUA..OAAX.OGNS.TFSLUIM.UXA..CEC..CXOJNPT.VA..JTFALHXURYIQI.CVWDB.ZA.XFR.T..IPXTD..LHJHSZCW.RMNUGPIHYUQY.YA.AN.CB.AJPM.GADD.AJW.NZJ...AWAJZAHWAFCB...T.AYZ.HQAAQ.LFA.S.NPAAEDPI.LYLFA.IFXEX...SUO.APACZP.JXPUSAW.D.WU...

result:

ok Correct.

Test #10:

score: 0
Accepted
time: 8ms
memory: 17176kb

input:

1000 1000
.SKFDQ.AV.GPTHMF.PL.YOQRQOXDOF.XVZ.H.MYOJIYT.QZNJQI.ZZMAJ.OAWBJBRXFW.CLEPPKGGAWGTVBKOBL.GPCO.ML.DBL.A.RJ..GF.EHK.CDXLLTCBCL.CGYJBMUSPIN.QELGYW.JE..CFVQF.LVYLFHYJ.MY.FZ.RU.ODLAYTWIZQOQZXBW.BVD.RFPLHLEHAU.G.PLFWFUKA.RSG..AVU.SA.PWRGJYO.OXD..S.Z.LIIADT.YXH..NHWXY.R.YFLS.URIJGPPURZPPVHJFLMKTDT...

output:

YES
S.FDQAAVAGPTHMFAP.AYOQRQOXD.FAXV.A.A.YO.IYTAQZ.JQIAZZMAJAOAWBJBRX..AC.EPP.GGAWGT.B..BLAGPCOAMLAD.LAAAR.A.GFAE.K.CDXLLT.BCLACGYJB.USPIN..EL..WAJ.A.CFVQ.ALV.LFHYJAMY.FZAR.AODLAYTWIZQO.ZX.WA..DAR..LHLE.A.AG.PLFWFUKAAR.GAAA..ASAA.WRGJ..AOXDAA.AZ.L.I.DTAY.HAAN.WXY.RAY.LSA.RI.G.PU.ZP.V..FLMKT.TWI.ZKHZ...

result:

ok Correct.

Test #11:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

1 1000
.K.CCS...LC.....Y..J...E.W.B..Q..KQ...Q...L..U.XSWX..NB..K.OLF...Y.A....HG....RRQO..Y...J.LOS...IN..C......H......X.....B.B.PQRT....VB.........P...E....MF.E...RH.XADCQN.D.KT.W..XNI..PH.Q.L.H..G...ZJR.V.I.......O......J.X..N..QS......UN....HLS..Z..N....X.YH.W..E.Z..JHSAV......YXT.P..TX.WT.SHE....

output:

YES
KACCSAA.LCAY.WAY.AJ.AAE.W.BAAQ..KQ.AEQD..LTAUAXSWXA.NB..K.OLF..AYAAAAA.HG.BH.RRQO.AY..PJ.LOSU.AINA.C..A.AAH.AAA.AX.AAAABABAPQRT...QVBA..VAAK..P...EA.A.MF.E..ARHAXADCQN.D.KTAW.AXNI.APHAQAL.H..G..ZZJR.V.IA.AAA.AOAAAAADJAX.ANCAQS..A..AUN..A.HLS.TZ..NA.AAXAYHAW..EBZZAJHSAV..AAA.YXTAPAATXAWT.SHEAA.YG...

result:

ok Correct.

Test #12:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

2 1000
.D..JPYBD.H..F.I.NTFC.VJKS..Q.PBW..XLW.ZS..ATCTMPPKRK.V.NN.MPE.SPN.QODI.H...OR.V..INXOZMGF.KIS.GANJ.WV.YLALHHXO..M.TMTJ..XYP.N.BUENZCUA.I.XJO.Q.NVG.B.TXNI.TVLY.N.CWE.ZEO.ANYRZ.W.PQI.LORBYIYJIK.JZ.PENB.HPJPTIIGVOMF.RPZ..WFM.IS..H..U.ZEX.DXZU.YHM.UOMPOHV.HW..SZ.RHWXW.SZH.....R.X.R.L.JRYLL.CE.IE...

output:

YES
..JJPYBD.H..FAI.N.FCAVJKSAAQAPBW.AXLWAZSAAATCTMPPKRK.VANNAMP.ASPN..ODIAHA.A.R.VAAINXOZMGFAKISAGANJAWVAYLALHHXOAA.A.MTJ.A.Y.ANABUENZCUA.IAXJOAQAN.G.BA...IATVLYAN.CWE.ZEOAANYRZ.WBPQI.LORBYIY..KAJZAPENB.HPJPTI.GVOMFARPZ..W.M.ISAA..QUAZ.X.D.ZU.Y.MAUO.POHV.HW..SZ..HWXWASZ.A.A.AR..ARAL.J.YLLACEAIEZDX....

result:

ok Correct.

Test #13:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

1000 1
.N.
N.N
G.G
...
...
.x.
U.U
...
.x.
P.P
K.K
..O
.x.
.x.
Y.Y
...
.x.
..D
.x.
...
J.J
Q.Q
E.E
.x.
A..
W..
.x.
H.H
D.D
...
...
E.E
..H
..A
.x.
...
C.C
..E
O.O
...
..Z
J.J
...
..Y
P.P
W.W
X.X
G.G
...
...
...
...
L.L
F.F
B.B
.x.
K.K
R.R
U.U
F.F
.x.
...
...
...
B.B
...
L.L
.x.
E.E
N.N
Z.Z
...
Z.Z
W...

output:

YES
N
G
A
A
.
U
A
.
P
K
O
.
.
Y
A
.
D
.
A
J
Q
E
.
A
W
.
H
D
A
A
E
H
A
.
A
C
E
O
A
Z
J
A
Y
P
W
X
G
A
A
A
A
L
F
B
.
K
R
U
F
.
A
A
A
B
A
L
.
E
N
Z
A
Z
W
A
A
A
I
V
P
A
A
J
K
D
X
Y
A
.
.
S
A
X
A
.
J
F
O
S
N
.
D
.
A
E
U
A
A
T
C
D
M
A
A
A
T
A
.
A
A
.
F
A
.
Y
E
K
.
.
A
.
T
A
A
.
A
G
T
A
A
A
H
R
X
A
.
.
A
U
...

result:

ok Correct.

Test #14:

score: 0
Accepted
time: 1ms
memory: 4092kb

input:

1000 2
.HE.
.xx.
....
H..E
..x.
Z..N
U.xU
..x.
Rx.R
A..A
D..L
J..T
..x.
A.xA
Ax.A
...V
.x..
F..F
.x..
U..Q
Bx.B
F..X
E..E
...G
B..V
..x.
.x..
..x.
E.xE
...I
..x.
...W
Tx.T
.x..
Tx.T
H..H
K..K
M..I
..xK
V..I
.x.Y
...V
....
A..M
B.xB
Hx.H
A.xA
...K
...X
O...
J..X
S..U
X..M
F.xF
..x.
M..I
D.xD
Y.xY
Hx....

output:

YES
..
HE
HE
A.
ZN
U.
A.
.R
AA
DL
JT
A.
A.
.A
AV
.A
FF
.A
UQ
.B
FX
EE
AG
BV
A.
.A
A.
E.
AI
A.
AW
.T
.A
.T
HH
KK
MI
K.
VI
.Y
AV
AA
AM
B.
.H
A.
AK
AX
OA
JX
SU
XM
F.
A.
MI
D.
Y.
.H
XF
SX
AK
.R
B.
AA
A.
KE
NN
ZA
..
BI
PV
ZD
AD
.G
.A
RR
V.
.O
EE
.A
CA
AJ
SP
.A
GG
JI
A.
.P
DH
AA
QQ
.A
V.
ZL
W.
QC
P.
KK
AO...

result:

ok Correct.

Test #15:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

1 1
.M.
M.M
.M.

output:

YES
M

result:

ok Correct.

Test #16:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

2 2
.FG.
F..G
D..D
.DG.

output:

YES
FG
D.

result:

ok Correct.

Test #17:

score: 0
Accepted
time: 10ms
memory: 18512kb

input:

1000 1000
.SALZWWWEFVNIEX.ZDPPWJHROFIITXR.CSOKTMFFUGSA.UW.X.QYXWNAC.YCVHOGAHGZQAJWINRU.Z..CCFQKASZXMPWSQGILOT.N.PKGZ.JWPZ.ALPWSOFCMWABPW.ZAFSQQUASJHPIAMITPJEAJLKMGVGDOHFFNYKKXFHUIPFYDPQ.RWKD.PWLTQPZGPMYPQHOAGOHIDQMFGJU.MLXPCUK.ES.KZHPRLBGCTGYHPVYMX.DFAZODQ.QXANEJTISMUGV.LIGKZDSNOC.NDWM.N.JYHJIWCBQ.L...

output:

YES
..LZW..EFV.IEX.ZDPPW.HROF.ITXR..SOKT.FFU.S.AUW.XAQY.WNACAYCVHOGAHGZQ.JW.NRU.ZA..CF..A..XMPW.Q...OTANAPKGZA.WPZAALP.SOFCMWABPWAZAFSQQ.ASJHPI.M.TPJ.A.LKMGVG.OHFFNYK.XFHU.PF.DPQ...KDA.WLT.PZGP...Q.OA.O.ID.MFGJUA.LX...K.ESAKZHPR..GCTGYHPV..XA.FA.O.QAQXANE...S.UG.A..GKZDS..C.NDW..NA.YHJIW.B.ALIU.N.NI...

result:

ok Correct.

Test #18:

score: 0
Accepted
time: 19ms
memory: 22128kb

input:

1000 1000
..EYLAGAENPDPZMGY.K.MSRTZBHDENS..YJRW.IWCLBIQQICT.ODBUMXFPO.UDPELUBMQSLZ.EHIVABC.ME.NQQI..QEHTIIFGJQWZSLDNDKGWA.UGMR.CJ.RPAQYJUAIIFQAMRAWECAAFHV.GUGIXROGEYDUX.FUUP.JKSYZITIHMSCKEQQKU.SFAXDPIPSHHYGGYLLEHUHZYRKYBKNAAOAWZHPRKHIQRZJXO.LMJUHDR.AWTBOEEJIHRH.XBUDQHGHKSL.SKW.SZZNIZAF..PK.NVOIMECDI...

output:

YES
.......................ZB.DE.S..Y.RWAIW.L.IQ..CT.O.BUMX...AUD.ELUB.QSL..E..VABC.MEAN..I.A.EHT..F...W.S.D..KGW..UG.R.C.A.PAQYJUAIIFQA.R....AAFHVAGUG..ROG..DUX...U..J.S....IHMSCKE...U...AXDP...HH.G..L.E.UHZY.KY.K.AAOA..HPR.HI.RZJ..ALMJUH..A.WT..E.JI.RH..BU..HGHK.L.S...SZZ.I..FAA......IME..IKXFG.JA...

result:

ok Correct.

Test #19:

score: 0
Accepted
time: 20ms
memory: 22752kb

input:

1000 1000
.YOTYESJGMDJYFO.GICQVC.PBBNUUXFEIX.OJ.DBWOESWK.TEI.DITEQKIKC.QOTZBX..UB..SW.ODDBU.ZDILJKQYEM.CXOWRNAX.RYRPM.VMVYI.PBYXXUDDAFQUMAI..UFRHYOQA.PUWEP.AHEMMHMRCEZRFJQRWKLVXA.HXPHIMHV.SEHGFEJB.WRT.EYCWPI.CTERLDCPFUXKOWGIVNJKKOPUZRZI..NCHBODRTVKZRNHGTOQTYAKSEBA.TEX..EFIVBSBFOAJ.M.PXGTMHN.PRAPFIDD...

output:

YES
..............X.IC......BN......XA.J...W.ESWKA......TEQ.I..AQOT..XA.UB.AS.A.D..UA.D.L..QYEM..XOWRNA.ARY..MAV..Y..P...X......U.A..AUFRH...AAPU.E.AAHE.M....EZR.J.RWK.VX..HX.H.M....E.GF.JBA.RT.E.C.PIAC.E.L.CP..X..W.I.N..KO..ZRZI..N....DR.V.Z.N.GTOQ.Y..SE.AAT.X.AE..VB.BFO.J.M.PX..MH..PRAPF..DH.O.G.T...

result:

ok Correct.

Test #20:

score: 0
Accepted
time: 37ms
memory: 30188kb

input:

1000 1000
.HXXXGGPVDEYBGKDYLMRYKPIY.B..BQBPSH.DHV.RNWZKUYVSVELVLW.IAZZSBAGJSPHY..LFURSTQY.BTDPZ.GQCCNHBHJNUBDRQRGESN.TIGYPZVZ..MAWLKSUBOR.OJ.FEYPDJBAI.WV.EYBPRKNB.V.NY.QESGNGLNTUF.EY.EOIUPSETRWU.AWLP.DCBRZ.IDJIZW.UEJYDHPYOJPH.QJJAR.EOYFQKOSXUK.LNXOHJNINT.NVJFEGZOMSJQT.XHISZWU.Z.GYGELPGGDVTFAGA.TSYDN...

output:

YES
.....................P....A.BQ..S.A........KUY......L.A.....B..............T......P.....C..B.J...........A............WL..........F.......I........R.NB.........G.G........A....P.........L..D......DJ.Z........P...P..Q......O.........A.........T.........M....AX......AZA..G.L.GGD....G..........M......

result:

ok Correct.

Test #21:

score: 0
Accepted
time: 37ms
memory: 28908kb

input:

1000 1000
.CCFMBZB.AUU.H.ZXYVAIMTA.D.JJIPERQWJVCTTAKSARUVYRPOPQMNFTNMPUBAZLCD.NXITOLEGFETDCOOBBGTL.U.IDCGBOOWFZ.VAWT.BXDK.YXRPTAVKNVAEMTDFY.UEUJCXSVZTYVJIN.ZOXGSTHSGUJWPTSLSUKFZDICKCPNTF.TTVUZUWAWFIPJ.HSXCJWRLDXZPXSHYLE..VZDEXCIGCFVBJBRNLAZDYXYGBDSRJUKRLVGREJGHMBFFK.SQSFXVDXBOULXPVHXPXKDZADDQA.JJCLE...

output:

YES
.................................................................................................W.........................................Y.................................................A........D.............................................................X......................................

result:

ok Correct.

Test #22:

score: 0
Accepted
time: 38ms
memory: 30476kb

input:

1000 1000
.YYJG..U..V.ZKZL.MR.Y.BFP.RK.Y...Y.P...LZ.HB.FECA.O...DDWYTFMKZZ.RZ..AJD....ND.P.B...MPYOAU.DYJX..Y.UEUN..IVDN.C..WXXF...FRP...A..NP.B.O.Z.D..LFC.F..TR.G..M..ULQ..VPC..X.DHPY..UGO.F.P.BM.R..HXJ..STSJMS.Q.AZMF.EF..OXMSV.BAG..ADIR.FD.QDJN.DM...NKI...IYMNE.CP...J...G.KSX..B.J.HLYJC.PMBBJG.F.....

output:

YES
...........................................................................................................................................................................................................................................................................................................

result:

ok Correct.

Test #23:

score: 0
Accepted
time: 24ms
memory: 30428kb

input:

1000 1000
...H......V...............A......Y.....L...W........E....O....I.................................................M.........DM...................W........D...................F...............................F...........................Q.L............Q..............D..U...........................

output:

YES
...........................................................................................................................................................................................................................................................................................................

result:

ok Correct.

Test #24:

score: 0
Accepted
time: 24ms
memory: 29500kb

input:

1000 1000
...............................................P................................................................................................L.......................................................................F....................................T.......................................

output:

YES
...........................................................................................................................................................................................................................................................................................................

result:

ok Correct.

Test #25:

score: 0
Accepted
time: 23ms
memory: 29916kb

input:

1000 1000
.....................................................................................................................................................................................................................................................................................................

output:

YES
...........................................................................................................................................................................................................................................................................................................

result:

ok Correct.

Test #26:

score: 0
Accepted
time: 3ms
memory: 14152kb

input:

1000 1000
.LSJXLZZD.YK.B.STLUYFB.O.MZDTXTLLSRCHKNQVK.LPMVY.KV.BFQGD.NAYTTLK..EAP.XGSIYRXDMVNGNPGL.DNGDONQCYC.EQUJOAEYUTVNWRJFT.PU.QBTJMBEM.AA.RKJRIQJOK.TRGYTNXZXBKCCECOBFJXPRVQHASGE.FBTEDJH.QNNLCUAQRKZISWRCJIRHHCUAORAOKKSWLSHYSHDTB.APURKPFQWWVEQVSJ.LRILACYRW.XPPAAFLL.GTUWWTCMAIAWRDAAUB.VIPK.KMOKEOLR...

output:

YES
LSJXLZZDAYKABASTLUYF.AOAMZDTXTLLSRCHK.QVKALPMVYAKVABFQGDANAYTTLK.AEAPAXGS.YRXDMVNGNP.LADNGDONQ.YCAEQUJOAEYUTVNWRJFTA.U.QBTJMBEMAAAARKJRIQJOKATRGYTNXZXBKCCECO.FJXPRVQHA.GEAFBTEDJHAQNNLCUA.RKZISWRCJIRHHCUAORAOKKSWLSHYSHDTBAAPURKPFQWWVEQ.SJALRILACYRWAXPPA.FLLAGTUWWTCMAI.WRDA.UBAVIPKA..OKEOLRNLAJCUA...

result:

ok Correct.

Test #27:

score: 0
Accepted
time: 0ms
memory: 13564kb

input:

1000 1000
.DP.QPM.HQWBGIPFTNLVIWMOIVHQNBUCWBOAJSDZCB.RAXNSVHCQESPHTPCBYD..OWFUSZLXAOY.SL.XUVPDQFOV.QUD.RIWPEEFRTGXAXX.CE.FYTRYUGTLLYFRBRJ.G.KCZAWVQHEW.MR.HBVAD.IXHDT..L.ZFKI.CBZXXBVWOXXAFG.UQZJACGQSWTXXQHGDUUYBAVYJBLA.QBACTMZQQVARPNNBNPH..KDUT.HHRUNOMQAWQQXNFR.CWHYRSWLI.IRNNNY.YCKFZXIMTSJX.GZSKZNKNS...

output:

YES
DPAQPMAHQWBGIPFTNLVIWMOIVHQNBUCWBOAJSDZCBARAXNSVHCQESPHTPCBYDAAOWFUSZLXAOYASLAXUVPDQFOVAQUDARIWPEEFRTGXAXXACEAFYTRYUGTLLYFRBRJAGAKCZAWVQHEWAMRAHBVADAIXH.TAALAZFKIACBZXXBVWOXXAFGAUQZJACGQSWTXXQHGDUUYBAVYJBLAAQBACTMZQQVARPNNBNPHAAKDUTAHHRUNOMQAWQQXNFRACWHYRSWLIAIRNNNYAYCKFZXIMTSJXAGZSKZNKNSZFAYMAS...

result:

ok Correct.

Test #28:

score: 0
Accepted
time: 8ms
memory: 13420kb

input:

1000 1000
.QACXHKHSI.T..MNSDIFWXJC..MMWQ.FEHIDIB.WPW.JBWAOVY.EHYJNMCLINCOTHRZCJNCVHSTKAFKYCTILGKRGY.NM.Y.H.J.KFZ.CW.WSYOYLFRLZENLVKN.SZNJFGFVDWCW.AE..FQJJNLXY.UOSAAIWYHM.YWZQS.XPB.YTTAU.YN.HWTQH.YBYDGSDCGKDUGRJDEZWVGTOWKVKXDPPONDGEQ.IZOI.UCF.M.USZYUQZAAOQC.TG.UETLCUYKWKZAFYYWDDCU.OQ.WCZQSXOESQDDHWJF...

output:

YES
QACXHKHSIATAAMNSDIFWXJCAAMMWQAFEHIDIBAWPWAJBWAOVYAEHYJNMCLINCOTHRZCJNCVHSTKAFKYCTILGKRGYANMAYAHAJAKFZACWAWSYOYLFRLZENLVKNASZNJFGFVDWCWAAEAAFQJJNLXYAUOSAAIWYHMAYWZQSAXPBAYTTAUAYNAHWTQHAYBYDGSDCGKDUGRJDEZWVGTOWKVKXDPPONDGEQAIZOIAUCFAMAUSZYUQZAAOQCATGAUETLCUYKWKZAFYYWDDCUAOQAWCZQSXOESQDDHWJFMOTOQJZ...

result:

ok Correct.

Test #29:

score: 0
Accepted
time: 8ms
memory: 13504kb

input:

1000 1000
.JX.NOOUEQW.OZCKCF.VT.IDFDPWZXXBXQWMIVNT.ZM.YJPAACHOEEFDBGZXLLCGKEPKW.BDMEIDRFC.EPJRENUNKJDMTVR.HRMMSPS.ZEQBXAGRIGAEABSDTQVEJUWWIVF.IMGCRNLOAOBMCVYOGEWRAYOJTRUMU.NSZW.B.EUZKBIZ.YMHFOOCGX.DHSZJXMBDMYDDJXXSHVTOU.EJ.XKPZQJACHZE.BHRHEQYIBNVDYBUBMNVKMSYXZXEFIV.OPL.BFWMJYRE.VV.SV.X.H..EZGHAWZHOA...

output:

YES
JXANOOUEQWAOZCKCFAVTAIDFDPWZXXBXQWMIVNTAZMAYJPAACHOEEFDBGZXLLCGKEPKWABDMEIDRFCAEPJRENUNKJDMTVRAHRMMSPSAZEQBXAGRIGAEABSDTQVEJUWWIVFAIMGCRNLOAOBMCVYOGEWRAYOJTRUMUANSZWABAEUZKBIZAYMHFOOCGXADHSZJXMBDMYDDJXXSHVTOUAEJAXKPZQJACHZEABHRHEQYIBNVDYBUBMNVKMSYXZXEFIVAOPLABFWMJYREAVVASVAXAHAAEZGHAWZHOATDUMZDA...

result:

ok Correct.

Test #30:

score: 0
Accepted
time: 8ms
memory: 14864kb

input:

1000 1000
.DZIRSLTJU.UBNKSQOQVBCO.LHXP.KQDKAIWOJMNI.KQBHNSJ.HCWUMEX.LJLWEA.SYZFBQUCCQTXL.IGNQXHMHAM.KBIUTYZB.DQCRUU.WLPBDWDEDV.JWOAAMYEA..LVHWWSQXOPMZRDSL.TGJD.XMPNO.RTHCKJFIRCKDBMT.UKXNDIR.PDZOSFRVUBZBUJVTNKHUUGEHLSKDWKO.CQKIFNL.ZIQDTKKSAXMKJBPGMNVLNIMFPR.YOVHMNZAFROGZYPKSBTRDGLICIK.MUQGP..QSUOPJAZ...

output:

YES
DZIRSLTJUAUBNKSQOQV.COALHXPAKQDKAIWOJMNIAKQBH.SJAHCWUMEXALJLWEAASYZFBQU.CQTXLAIGNQXHMHAMAKBI.TYZBADQCRUUAWLPBDWDEDVAJWOAAMYEAAALVHWWSQXOPM.RDSLATGJDAXMPN.AR.HCKJFIRC.DBMTAUKX.DIRAPDZOSF..UBZBUJVTNKHUUGE.LSKDWKOACQK.FNLAZIQDTKKSAXMKJBPGMNVLNIMFPR.YOVHMNZAFROGZYPK.BTRD...CIKAMUQG.AAQSUOPJAZLZO.UPC...

result:

ok Correct.

Test #31:

score: 0
Accepted
time: 33ms
memory: 29812kb

input:

1000 1000
.MYLDYUACWALSDVAKZ.IKAHZYFABRPMLLULC.GSVPUSYNNEGAOAIGOATRIUUFEZOCJQDYHFMCYJUDYE.UCQCUUCZK.MFVXRCQUZQZI.O.WPHOCVKVAMPXK.NURJ.B.BTUBNWG.ZRPXJALNMIVCBTITZ.BCNSYJH.SGSO.XXIOQEYFXHZHWQV.TIYSPF.XBFAZMHTDCEBEGLJNJU.WXAKKJ.ONGZJ.HERVPG.QI.JHLGYZAFOFSFX.IWFPQBEW.XPUL.NNAXIGWKK..VATW.TVHXBGPBLBDGIB....

output:

YES
........W....................M......G.....Y..E...............Z....D.......U...................C...............KV...........B.B......A..P.J..N.........A.....................X............F.............E......A..AK.................I.......A...........Q........A................T............B.....O.....

result:

ok Correct.

Test #32:

score: 0
Accepted
time: 36ms
memory: 30316kb

input:

1000 1000
.LYXHPBWMFMTKVIQXQRMUIZ.HW..IEYGSAP.BXGZJXSIOVE.DQHJOFDOLARYPEOLAIFL.YUIFKWAYBDAYDLYOPKNEIA.VGZFMXNASKXPEOFRPVVKKRCQLCRCEMXRVD.ACTHSAZYDB.SC.SLTBJWCGNPCX.SZFT.HHMSTEWXWOEITHWKIIXWO.HFQHXSX.GA.L.MXYQRFTQTER.IVZZV..Q.NRBCF.PNMJEXT.SDISTHXWN.TAHJJB.XEZQOWVRMO.MH.JULNAYILOQLSE.JGCB.GCBE.LTMGUM...

output:

YES
L...P....M..V...Q.M..ZA.W..............J.S.....D.HJ...O....P.....FL......W.YB...D............ZFMX.ASK..E......K.R...C..E...V..A.......D.A....LTBJ...N..X....TA....T.....E......I.W..H.Q.............Q.......A..Z....Q..R.......J..T.S.....X.....H.....E..O.V........U.....L......J.C.....EA.T..UM....Y.....

result:

ok Correct.

Test #33:

score: 0
Accepted
time: 20ms
memory: 21644kb

input:

1000 1000
.XYEMFHIER.CZ.LNREYNVNIF.CUNLURC...HSHZ.J.OLEFFS.ZSVWGNGN.YGPOMDIFCTMRA.JRLMTCS..AWYBBJKHOYHINDIRRWS.OMOQ.ZHEWDSBHNKGD.ZAUSEHMELEMWRLC.LIPNSNJOB.XNMT.ETIQFVCPYMITVHY.X.SNDCAEFE.FFK.CE.GKNRJHIY.WAXYCQIVNLEQYYSABBWOJ.CTT.F.NVYYCNFRQRFYBEBS.WGVWFSOLYEKWTRDKGLBLLQKSURZ.QWNR.APGQQRUIMKRL..YXIOJ...

output:

YES
X..M....R.CZ..NR.Y..N..ACU.LUR..AAHSHZA.AO.....A...W.N.NAYGPOM.I.CTMR.A.R...CS.A.WYBBJK..YHIND.R.WSA.MO.AZ.E...B.NK..AZ....H.E.EMW.LC.LI......B...M.......V...MITVHYAX.SND........KA.E.GKNRJHI........IVNL.Q.Y.....O.A.TT..A.V.YCN.RQRFY.E.S..GVW..OLYEK..RD.G...LQKS.RZ.Q.NRAA.G.QR.IM.R.AA..I.J....MU....

result:

ok Correct.

Test #34:

score: 0
Accepted
time: 19ms
memory: 22472kb

input:

1000 1000
.UXMHORG.PYDICJWAKCP.OTSOWYKDMSUHPQJOXYUTSV.MGSRR.GRCVZYDYVPTIZOUYYBSELDTXKEPTLYBNRH.IRFTZ.NTMQB.UZGI.IF...GDVSSMRSPOVSJJFXVBXA.YYTY.NR.DURKGBXUOEZU.BQCNGG..OZDNEKFMHJH.UOSRLSPXGUX.AMRIL.LFR.QUGU.VLTOYILWAENLHDSZWK.DVOZX.FDQFS.EXZS.HFKJ.QRLVSGDWDZMZKE.BPFPPIPURDPRYHMGJAJASAJDZP..CSP.Y.CZCC...

output:

YES
.XM.O.G.PYDI..WAKCPAO.SO..KDM.UH.Q.OXYUTSVAMG.RR.GRCV.YDY..TI.OUYYBSE.DTXK.P..YBNRHAIR..Z..T...AUZGIAIFA..GDVS.MR.P.VSJJFX.BXAAYYTYANRA.URKG..UOEZ..BQCNGGA.OZDNE.FMHJHA.OS.L..XGU.AAM.ILALF.AQUGUA.L.OY.L.....HD.ZWKAD.O..AF.QF..E.ZSAH.KJAQ....GDWDZMZKEA.PFP.IPURDPRYHMGJ.JA..JDZP.AC.P.Y..Z.CAXV.O.R...

result:

ok Correct.

Test #35:

score: 0
Accepted
time: 8ms
memory: 15080kb

input:

1000 1000
.QNBDJYHFQVESJURS.YEWMCEZFLRKSZTAWCYOVTSQOZQIWUVRROZAWYYJUJBUB.SLNZIZGXXPQFDHPD.KJTIDKNMDQEYTPVUSBOMJ.ESCQ.SCGJWYLRE.R.OVFVIN..W.SMQHQOMXGEFP.OYVTCIIDKPCJNRJYMCWOWSWENITNRZNDH.DU.S.JMTOVIJFJ..OBUJ.NMIXFPMPHUYOXDLRDTOZFRT.LKLPFC.OBXZLKERXNSVHLZQD.HTDWBVOMERMJUUKAYOXRXWCPPOQ.WXSJIYK.YC.MDUFB...

output:

YES
QNBDJYHFQVESJ.RSAYEWMCEZFLRKSZ.AWCYOVTSQO.QIWUVRROZAWYY.UJBUBASLNZIZG.XPQF..PDAKJTIDKNMDQEYTPV.S.OM.A.SCQASCGJ.YLREARAOVF.INAA..SMQHQOMXGE.PAOYVTCIIDKPCJNRJYMC.OW.WENIT.RZ.D.ADUASAJMTOVIJFJA.OBUJANMIXF..PHUYOXDLRDTOZFRTALKLPFCAOBXZLKERX.SVH.ZQDAHTDWBVOMERMJUUKAYOXR.WCPPOQAW.SJIYKAY.AMDUF.NSYNXXA...

result:

ok Correct.

Test #36:

score: 0
Accepted
time: 4ms
memory: 13560kb

input:

1000 1000
.KWOUVJPAYKRTHLIOBSGJBIVNOHFPHZXGEKC.MMM.AHC.QIFGFDWDQAGFR.IVJGTBLMBRIZXVY.TE..TFXZBXPRD.XBHKSLNYFOS.BWCRGHXEVJQE.CHVIYUSXWPWWLSXYYSWFRGTNHAISCNTHKSNBXWJ.SEE.LJXWY.BIDCTJOPDDE.MVBYHWPL.ANVUWDK.DJOVJRG.GTGTJJ.VHDRDLQ.SL.EX.RCMBAQSEBRWLCY.HDFT.IRVIOKIENARHVWJCPAECFEVSMVZPZJZSG..VB.EQFVWA.OJG...

output:

YES
KWOUVJPAYKRTHLIOBSGJBIVNOHFPHZXGEKCAMMMAAHCAQIFGFDWDQAGFRAIVJGTBLM.RIZXVYATEAATFXZBXPRDAXBHKSLNYFOSABWCRGHXEVJQ.ACHVIYUSXWPWWLSXYYSWFRGTNHAISCNTHKSNBXWJASEEALJXWYABIDCTJOPDDEAMVBYHWPLAANVUWDKADJOVJRGAGTGTJJAVHDRDLQASLAEXARCMBAQSEBRWLCYAHDFTAIRVIOKIENARHVWJCPAECFEVSMVZP.JZSGAAVBAEQFVWAAOJGWYAPBVR...

result:

ok Correct.

Test #37:

score: 0
Accepted
time: 4ms
memory: 13508kb

input:

1000 1000
.EFA.YUPBMIUK.CSBRM.XZM.XBX.HHDKKBL.ST.XATVYDVCDBFPFJPU.DRV..WK.TYM.IRI.BVERBB.ALYMJNBXDSTTUJYN.LYIAQTFOMKLEIXHPZGS.BFRAVJXGGBEU.AUQRDSRCOJZYLOJLWASW.I.AVSNDP.LUUIYAKB..DIDNLXBHOSDSUUYQUTYKADLX.HQHZAGOFWGNN.ZBVBL.RTSZNGDUEPWHO.AZS.SBAVXEZTODPCMDA.EMGVHWTP..XQCLGGBTIHQ.LFPZQFW.LEMBX.U.HZL.H...

output:

YES
EFAAYUPBMIUKACSBRMAXZMAXBXAHHDKKBLASTAXATVYDVCDBFPFJPUADRVAAWKATYMAIRIABVERBBAALYMJNBXDSTTUJYNALYIAQTFOMKLEIXHPZGSABFRAVJXGGBEUAAUQRDSRCOJZYLOJLWASWAIAAVSNDPALUUIYAKBAADIDNLXBHOSDSUUYQUTYKADLXAHQHZAGOFWGNNAZBVBLARTSZNGDUEPWHOAAZSASBAVXEZTODPCMDAAEMGVHWTPAAXQCLGGBTIHQALFPZQFWALEMBXAUAHZLAHGQLAAAG...

result:

ok Correct.

Test #38:

score: 0
Accepted
time: 11ms
memory: 17652kb

input:

1000 1000
.DEABUNIECDFTUYSXMIRUXYFCUZSTHBLSF.X.ENER.ICAXCG.ZVHTEMJULIQMMGCODDAWNCT..RGX.MZMZEELLDRZNE.HMKXUK.L.EAYFMDXSETLOIPSN.PMFITTGPGVQT.ZN..WEQ.QCTJBYCXMWZHONLWPWPAZBJ.LBHGQQ.DYXZLSXGW.R.YTRIWM.LMS.DP.SCEGDSEEUCXRVP.JGFLFYXEDXNXNVQKKDGGOBCIH.TIMSDLVKUMSIH.YGGIOGYVFEEAFKIFXG..R.QUFRNMPNWQBOGSQAH...

output:

YES
D.A.UNIE.DFTUYSXMI.UXY.C..STH.LS..XA.N.RAICA.CG.ZVHTEMJU.IQMMGCODDA.N..AARGXAM..ZEELLDRZNE.H.KXU.ALAEAYF.DXSETLOIP.N.PM.IT.GPG.QTAZNAA..Q.Q.TJBYCX.WZ.O.LWPWPAZBJ.LBHG..AD.XZL.XG..RAYTRIWMALMSADPAS.E.DSEEUCXRVP.JGFL.YXE.XNX.V.KK.GGO.CIHATIMSD.VK..SIHAYGGIOGY...EAF..F.GA..A.U..NM.NWQ.O.SQAH.O.HZBZ...

result:

ok Correct.

Test #39:

score: 0
Accepted
time: 26ms
memory: 21708kb

input:

1000 1000
.TVYCUGGIMJMYOKVYZG.UPGOKUCMEHFBZLTVVHQWJDGCFBEZDPBTVSNVID.UXLFWOTWX..CIUYWUICWP.EQNRE..SXNUEJ.KGQKR.EURQP.NVCFUDVPBNRPFA.APB.EOOSSY..EVP.BFBTKUQOTHHNQCSI.L.ECGGDBCLSERQKHPWYJFXOLK.NTNY.XCPPGHFXVJE.UGZ..EBPXJKJ.MBRBAYFECGIFBF.KG.JZAT.YA..QAMNMDHCEOVWZVHXTDVXUJGC.YMWWUX..OOR.QAVKCGLUFIDEONU...

output:

YES
T.Y.UGG.MJ..O.VY.GA.PGOK.C.EH..ZLTV.HQ..DG....ZDPB...N.ID.UX..W.T...ACIUY.U..W.AEQNRE...X.UEJAK.QKR.....P...C...V.B.R.F.A..BAE...SYAAE..A....KUQOT..NQ.S..L.EC.G.BC..ERQ..PWYJFXOL.AN.NY.X.PP..FX.J..UGZA..BPX.KJA..RBAYF.CG.F...KGAJZ.TAYA...AMN.DH.EOV.Z..XT.VXU....Y.....A..O.AQA..CGLUFIDEONUAP.WO.T...

result:

ok Correct.

Test #40:

score: 0
Accepted
time: 28ms
memory: 22120kb

input:

1000 1000
.UVJ.HHDYINQXSFEEZFLY.QDEOVACYPM.PMKWBBWTOMUBBACYKDNBYCAMUAPWDXFYZWVAMLLJ.AFDRCQAV.LPRBCHV.BUVVJXXYHRFUM..WQBPLQF.DLRUYAIKY.DPGLWKJAZRDIILTDLAD.IJM.SO.OIFVLVFCUHCT.LAXAGHDHVVKAQGYTUERMWBFRPQRPBDLLTOGKA.E.BWUQNENXPVFWWTVYVK.JL.WWXICG.OYMSOHRRZZJ..CEAOVHEQIS.LMBJNXURGLQJBIPPEBKY.O.TRXUYJH......

output:

YES
...............E..LYAQ.E.VA..PMA.M.WBBWTO...B.CYK.N..CAMUA...X...WVAML...A.DR......PR..HVA.U..J...HRFUM...QB..Q.AD.RU....YA.P...KJ.ZR.IIL.DLADAIJ.A...O.FVL.F.UH...LAXA.HD...K.QG.TUE...B.RP...BDLLT.G.A.EA.W..NEN..VF....Y.K...A.....G.OY....R.Z.JA.CEA....Q..ALM..N.URGLQJ.IP..B..AOA.RXUY.....U.S.LOH...

result:

ok Correct.

Test #41:

score: 0
Accepted
time: 32ms
memory: 30380kb

input:

1000 1000
.PDEBKFYBQ.NC.LRSEECWOELCLU.BWAHI.XV.TJZQBMQQI.TFFLLFKVAFVMG.AX.ESOPFPY.YCQTVPPSVLFH.CCHQBIOIFBOWNIEKGCQDPKVI..VQJX.BZVIRCNMRXUVBYCWDMWQDLVC.HFFSRACRDMVKWQVDITTNWBGNNQMXWL.OQOZVRTBHYJVDRCFOLBWHUEPYBMXQYPHUEUZYLANFNXGSEUSF.IQDXZB.D.TPYMMIUXDRK.MHYRUDUWMPKE.XPPTGIITGWTKIORNCJHA.B.KDLWSEL.RUN...

output:

YES
...B......NC..R.E........U.B..H.............IA.F.....V...........O............S.L.........O...OW..........V.............C....UV.Y.....QD..C..FF...C..........T...B...QMX...O..........VDR..OL..H...Y..XQ.............XG....F..Q...BAD.......UX....................T.........O.....A.......S......V..BZ.....

result:

ok Correct.

Test #42:

score: 0
Accepted
time: 36ms
memory: 28972kb

input:

1000 1000
.PPG.NQPNBYORDXVDN.KWLWJPW.HDX.WCNRWZSWLPUOOGAKKTXAYE.KZV.DD.Q..WHSRLIQZPMMQKTJLZWE.IF.SUVMAIVSEL...BXAAWAURQMZBQ.LSUCGPNMFXZMFX.DYMUKPHA.HMJUKMPDWSVPGQR.JSZIJKCTVVHETWCQG.OTOQFQGLI.S.QUHWTCXHUTYBWRS.JYHCK.CLDIMF.A.Z.GU.INRFVKU.VVUJAHWIVBTF.FSNDOPCFLXXT.LJCWDPUVGGZAOTXSAQLBXBWMJOBRTWCM.POY...

output:

YES
..........................................................................................................................................................................X...........................................................................................G.........................Y..........

result:

ok Correct.

Test #43:

score: 0
Accepted
time: 36ms
memory: 29928kb

input:

1000 1000
.HBE...ZCY.TXH..AYMVG..GZFO..M.YAOZIZKS.ILML.J..BWCIWWYL......OM....NZ.N.....UH.HD.VHCRDI..WEP..AUUPDZP.QHM.ZMUT..CK.E.P.W.J..F.AIY...FPFVSHCI.H.N..K.....C.WI...ODR.XOZ..I.ZT.RO..MEC..RV.X.IY..S.QL.YXM.FSM.YQP.IC.K.C.GCL.Y.F.FI.CFGKS.MX..JV....CU.M..K..NY.FH.KY.GRY.V.BX...I.HAE..EKWL..AP.O...

output:

YES
...........................................................................................................................................................................................................................................................................................................

result:

ok Correct.

Test #44:

score: 0
Accepted
time: 24ms
memory: 30496kb

input:

1000 1000
....................................T...I...L.....W.......................X..CE.........U.............E......................F.K.......D...XR...Q.....D.....C................M..........................................................................................................N............

output:

YES
...........................................................................................................................................................................................................................................................................................................

result:

ok Correct.

Test #45:

score: 0
Accepted
time: 18ms
memory: 28800kb

input:

1000 1000
...............................................................................M.............O......................................................................................................................................OS...............................................................

output:

NO

result:

ok Correct.

Test #46:

score: 0
Accepted
time: 14ms
memory: 30488kb

input:

1000 1000
.....................................................................................................................................................................................................................................................................................................

output:

NO

result:

ok Correct.

Test #47:

score: 0
Accepted
time: 5ms
memory: 14148kb

input:

1000 1000
.VKCQQI.KRWGIWNWR.IEQSJIQMHXHQIEQSOL.PGPAIRULWBFCZXBQ.DAYYTRCZPZKFZVGRHLVJSDTLYJPTNRWAFJDBUJQ.CJRURR.CICDNZFSB.PIBBUOWEZBREBKPKQRBDTPOOZTDAWKHHDLZNDLENILCHFKVBNKNUCDRPMZXBWY.FBQXQUHAOUWL.NOAV.WNCN.SXECYMLAUPTXESE.SRMIAYKC.BR.NRSW.OMCPWL.PZDYLJDQIG.MUZFV.KQTUEUN.GOGYCGFGMZJBXWPINNKP.GCEJTWL...

output:

YES
VKCQQIAKRWGIWNWRAI.QSJIQMHXHQIEQSOLAP.PAIRULWBFCZXBQADAYYTRCZPZKFZVGRHLVJSDTLYJPTNRWAFJDBUJQACJR.RRACICDNZFSBAPIBBUOWEZBREBKPKQRBDTPOOZTDAW.HHDLZNDLENILC.FKVBNKN.C.RPMZXBWYAFBQ.QUHAOUWLANOAVAWNCNA.XECYMLAUPTXESEAS.MIAYK.ABRANRS.AOMCPWLAPZDYLJDQIGAMUZFVAKQT.EUNAGOGYCGFGMZJBXWPINNKPAGCEJTWLAZFEZTG...

result:

ok Correct.

Test #48:

score: 0
Accepted
time: 3ms
memory: 13424kb

input:

1000 1000
..HBOGEV.WGWNL.XDANPUKVBERPKGQJNTWDRY.SHV.LMAHPWO.EZLSYUHHMTRITSSLTOYCAPTEZO.EHDO.CPJFIAXS.FXZZZJYHSWBF.DGYATXIYPYNSATZJWOH.OJKUAGRWWEWH.YDE.QFWPVT..SEHIZQER.L.ZVGGHDHJEQWK.LWGSQCNL.T.ATZFSVGXMUJZOBNZWQIUNOWOOREOLFXSKCNNKCLZQPXAV.DFSKNWG.XLXT.DWJ.VZGTAK.CASZBJUZTMICFUIM.ATKLHMKWYVVFUYLW.RM...

output:

YES
RHBOGEVAWGWNLAXDANPU.VBERPKGQJNTWDRYASHVALMAHPWOAEZLSYUHHMTRITSSLTOYCAPTEZOAEHDOACPJFIAXSAFXZZZJYHSWBFADGYATXIYPYNSATZJWOHAOJKUAGRWWEWHAYDE.QFWPVTAASEHIZQERALAZV.GHDHJEQWKALWGSQCNLATAATZFSVGXMUJZOBNZWQIUNOWOOREOLFXSKCNNKCLZQP.AVADFSKNWGAXLXTADWJAVZGTAKACASZBJUZTMICFUIMAATKLHMKWYVVFUYLWA.MIVBAALN...

result:

ok Correct.

Test #49:

score: 0
Accepted
time: 4ms
memory: 13460kb

input:

1000 1000
.ERZINQ.NXXFQANJCQINMCSPUQYBKF.QFYN.TPRUQDGEB.GNOMYVWU..MYNWJHG.ZCVK.DVO.NQ.LCJMSQDPNGMOGFGSX.KGTCN.PDA.ZFBDPZFEEJHBKASYZDJ.UBKJW.BETKIMP.WRLBXD.FYOJAGYONFOKO..AQLXWWBPMFZZFOHHLUOVVY.PDLULHAXD.XND.JBHY..DLJTAU.REQEQRICRP.BHD.KLYEXJFPZEH.AJMHDTOIQKTZ.Y.PWG.LNLKAQPXTUFNDAGFGMYWSAXZOBCORPUJUR...

output:

YES
ERZINQANXXFQANJCQINMCSPUQYBKFAQFYNATPRUQDGEBAGNOMYVWUAAMYNWJHGAZCVKADVOANQALCJMSQDPNGMOGFGSXAKGTCNAPDAAZFBDPZFEEJHBKASYZDJAUBKJWABETKIMPAWRLBXDAFYOJAGYONFOKOAAAQLXWWBPMFZZFOHHLUOVVYAPDLULHAXDAXNDAJBHYAADLJTAUAREQEQRICRPABHDAKLYEXJFPZEHAAJMHDTOIQKTZAYAPWGALNLKAQPXTUFNDAGFGMYWSAXZOBCORPUJURAEMIEAU...

result:

ok Correct.

Test #50:

score: 0
Accepted
time: 4ms
memory: 13404kb

input:

1000 1000
.THOCTULZ..WAT.G.SNOIDVQWZB.NQIMZPBVX.ISIXGQQXVVBYJXXIWXOYFSIQ.QDKDEYBINJZ.B..BDYQEEXFSWR.ROG.EXWKHICUNSYNVNOPOOALSGY.YFFDTWTN.WYVIRBQLKCAC.GE.YGOZDPKSF.LLNFY.JVLD.ELOJIPIKETZRQFIZIBPLAF.QMIEAXZ.VHYJB.SHGB.THGSJDSUIRKN.FGZAZWXOVVRYFTNW.SZQNILLVQILCQSBUT.AASSWVY.KLISXFPUMFFZSOAVDHHWMN..IL.Q...

output:

YES
THOCTULZAAWATAGASNOIDVQWZBANQIMZPBVXAISIXGQQXVVBYJXXIWXOYFSIQAQDKDEYBINJZABAABDYQEEXFSWRAROGAEXWKHICUNSYNVNOPOOALSGYAYFFDTWTNAWYVIRBQLKCACAGEAYGOZDPKSFALLNFYAJVLDAELOJIPIKETZRQFIZIBPLAFAQMIEAXZAVHYJBASHGBATHGSJDSUIRKNAFGZAZWXOVVRYFTNWASZQNILLVQILCQSBUTAAASSWVYAKLISXFPUMFFZSOAVDHHWMNAAILAQOXIGJKA...

result:

ok Correct.

Test #51:

score: 0
Accepted
time: 4ms
memory: 14680kb

input:

1000 1000
.NNGL.U.FBTKNXHXAFTLMLFIHLFIXDBLHZNN.WLHNUELBRDSCJFLLCDZTJZ..CDGECUPH.F.MWBYWRTAWTLBWIB.QF.HVTFTYQOVVGMSXXBTNHHXUZATHBHNHV.UYTSSCVOFPOCRZCD.OCU.MQAEILPSYWLED.URMHMSXSLGI.RJKROYQLAAOIBGYVVXVD.T.WG.ZSVIPPNQB.FSQAG.UMHYNKLUCSOFBK.WOSMVUQZRBPO.VLJZHBV.AMLCFKXZAR.P.YJOAMGIW..YYKBHNZ.TDGWCME.JA....

output:

YES
NNGLAUA.BTK.XHXAF.LMLFIHLFIXDB.HZNNAWLHNUELBRDSCJFLLCDZTJZAACDGECUPHAFAMW.YWRTAWTLBWIBAQFAHVTFT.Q.VVGM.XXB.NHHXU.ATHBHNHVAU.TSSCVOFPOC.ZCDA.CUAMQAE.LPSYW.ED.URM.MS.SLGIARJK.O.QLAAOIB.YVVXVDAT.WGAZSV.PPNQBAFSQAGAUMHYNKL..SOFBKAWOSMVUQZRBPOAVLJ.HBVAA.LCFKX.ARA.AY.OAMGIWAAYYKBHNZATDGWCMEAJAAGPYCHSA...

result:

ok Correct.

Test #52:

score: 0
Accepted
time: 31ms
memory: 30524kb

input:

1000 1000
.KEMKWAYMRCRUOH.WYNPC.JCFSPZNM.EVMVLCFIEN.JQZFDAQETQQPSLFMFPOL.VLVFAW.Z.NNWOBPVFLLWVGPCWJQWCUSIHSOE.WX.YYYJNO.O.IQVMFVG.BZACL..JNVZQ.L.USHAOXBALQFWXB.DRLYRVKBF.ASFRLFFYMQGJZVMZSIVQFJKSJCFKB.FWZFK.RUBLZHEQ.BZKUXETRULWAPQGNDWMLY.WYRAYD.A.DT.FNWPKBEMXFOYMQRW.N.GUPR.PZ.MOCLXEYOLVMTSSUBILSLVAHD...

output:

YES
...K................A.C..P.N...........N.........T...........A.........N.W.B.......................W........................A..........S.A...............R.......F.............................Z..A....Z.E.............A........Y............AF....B................R.P.......E........U...S........X......

result:

ok Correct.

Test #53:

score: 0
Accepted
time: 30ms
memory: 29428kb

input:

1000 1000
.DVWLYCUZIHRAJFJOZH.DJEIA.RFZBMMADGYCIZ.OHFVJEKNK.HH.QHB.QHKLDDJSU.UEVGQMLAN.BYUSLKGXZOITKNTYSEQ.KZWG.WSGVVWHO.YRUMYAFQAAWZCQOGFD.JIABJP.USF.N.LNPDCJCGCV.WU.AACMBPHJUEIWUV.ZCXYALY.KUJMSIK.O.ZYMTJIXYX..W.RQZYVPBO.O.LBJJ.EEZPHQ.WSBFMTXCMLGKKZR.EU.Z.ODZ.FREWDGSWS.LIIEOLV.TIVRJIK.FOECGA.QSATAK...

output:

YES
..W.Y..ZI.R....OZHAD.E.A........D.YC....HF...K.......HB.......JS.A....QM.....Y...KG...I..NT.......WG......W..........QA.W....G.......J......N..NP.....C........M..H.U.I.U.A....AL..K..M.I..O..Y..J.............P...............Q....FMTXC..G.K.RA.UA.....A.R.....W..L...O.......J..A...C........K...Y.Y....

result:

ok Correct.

Test #54:

score: 0
Accepted
time: 24ms
memory: 22120kb

input:

1000 1000
.HZMFAX.HJPEHCAKYURF.RDHMXPVBNAQOOJB.MVLPXIYBQ..AASHLENXIHETILINR.QMLT.WFLKCAM.PJEFGPMES.GEHCVBWKUW.EFRCS.PQTVRYS.KM.MLYCFVDQMTNONDDTCG.TZAGGJUVABEH.IZSDNXWHAVFRRLFHMX.HUNK.CVHSZ.SUDGU.BSWGJTSFCJXCOMJQEHRAKCNWUNWRGFGQPNRPOWTBCPHYP..GAUUUMAYXNNXZAULDZHLRD.QDHCUAARNAQWOOTNUJKELLBCCPOP.HCODMH...

output:

YES
HZMF..AH.P..CAK....A.D.M..V.N.QO.J.AMVLP.IY.QA...S.....I.ET.LIN.AQ.LT...LK.AM..JEF.....AG...V...UWA....SA.Q..R.SAKMAMLY...D...N.NDD..GATZ..GJUV....AIZSDN.W..VF.R.FHMX.H.N.A....ZA.UDGU.BSWGJ..FCJ.C.MJQE...K...UNW.G.G.PNR....BCPH.P.AGA.U.MAY.N.......Z.LRDA..H...AR..QW..TN....LL..CPOPAH.O..HY..A......

result:

ok Correct.

Test #55:

score: 0
Accepted
time: 19ms
memory: 20852kb

input:

1000 1000
.S.FIYMOI..MQ.ZFWBHJU.SMJHI.RX.NIFHMCQUOMDMJEPHYVGDWV.OLRUREYURSAEM.VZ.VQSKUKOAEACMMEKELRBTGKS.JHLLPLXKPV.YSUBHYMLVOBICCCWRKLG.XOYBZENXMFHIOTYSGTIAVUGI.QT.URRZEOTKPCFNCBWGGFZIVOPMRVHOGOQ.YJTJITXBHXOILT.QQRQZ.BLTLG.YRIHTVNUALIIMPQISNLBUEHVQTVUS.EESTTHITUAKKD.FRGYZRXAWLE.TXW.MFADPBXFZ.QTEXYM...

output:

YES
SAF.YMOI.AMQAZ..BHJUA.MJHIARXANIF.M..UOMDMJEP.Y...WVAOLR...Y....EM.VZ.V.SKU.OAEA.MM..ELRBTGKSA...LP.XKPVAYSUB.Y....BIC.CWRK..A.O..ZEN.M.HIOTYSGT.AVUGI..TAU.R.EOTKP.FN.B..GFZ..O..R..O.O..YJ.JI.X.HXOILT.Q.RQZABLTLG.YRIHTVNUALIIM.QISN.BU.HVQTVU.A..ST.HIT.AK..AFR.YZR.AWL.....AM.ADPBX.ZAQTE.Y.DROO.XA...

result:

ok Correct.

Test #56:

score: 0
Accepted
time: 4ms
memory: 14980kb

input:

1000 1000
.RBRW.HL.XFRZEMOUWLXIUPYV.TGOHSBBVV.VAPNRVP.AXAULVMQPJLSHQLKZHRYZXNCBB.DMLCJZHCYEOTOWGIVKW.EYP.YJUS.CHG.GZSLTQMY.AKFRPUMKVJAFHEDJTTR.UWYMSV.CVUKVZWCOEGVPDKP..YVLGIG..WPEDTSIAWQUWTZJOOXPGBOAHNY.O.FPXPOKAQBGOMNINHXSERYKYILLABGTBMSYKBHPZOUI.GOPJPYROTX.PEPCXMB.MSNNRHN.GKNLZ.JOIGMMXJWKN.JAYMZ.L...

output:

YES
.BRWAHLAXFRZEMOUWLXIUPYVATGOHSBBVVAVAPNRVPAAXAUL.M.P.LSHQLKZHRYZXN.BB.DMLCJZHCYEOT.WGIVKWAEY.AY.USACHGAGZSLTQMYAAKFR.UMKVJAFHEDJTTRAUWYM.V.CVUKVZW.OEGVPDK.AAYVL.I.AAWPEDTSIAWQUWTZJOOXP.BO.HNYAOAFP..OKAQBGOMNINHXSERYKYILLA.GTBMSYKBH.ZOUI.GOPJ.YROTX.PEPCXMBAMSN.RHNAGK.LZAJ.I.MMXJWKN.JAYMZALAAVPLEQ...

result:

ok Correct.

Test #57:

score: 0
Accepted
time: 4ms
memory: 13424kb

input:

1000 1000
.UVE.BWTHRULI.MEQKFS.F.Q.KPRPSKJDDDLK.MKPDTLQZO.ZCBXWR.BBNOROKYL.ZIUTDGPKSN.LCGZWKUFMPM.XZLNXAY.S.N.Y.VMQPQRGCRNZUYJBSIWZG.ENONWOGABTB.VE.Y.NVI.TADDXYP.L.PF.GXGCQCIYGLKEGP..RVZZYWQYBQPSMCADMW.OUNKTQJPLYDRG..I.PHL.LNPDSJRE..XLBG.GYBCVAMNEIRCBGXYJBDSUB.QESZ.RNFTFGPHUPSAEVTE.BIRXJSUEFTY.LBTQS...

output:

YES
UVEABWTHRULIAMEQKFSAFAQAKPRPSKJDDDLKAMKPDTLQZOAZCBXWRABBNOROKYLAZIUTDGPKSNALCGZWKUFMPMAXZLNXAYASANAYAVMQPQRGCRNZUYJBSIWZGAENONWOGABTBAVEAYANVIATADDXYPALAPFAGXGCQCIYGLKEGPAARVZZYWQYBQPSMCADMWAOUNKTQJPLYDRGAAIAPHLALNPDSJREAAXLBGAGYBCVAMNEIRCBGXYJBDSUBAQESZARNFTFGPHUPSAEVTEABIRXJSUEFTYALBTQSJOWJOQM...

result:

ok Correct.

Test #58:

score: 0
Accepted
time: 0ms
memory: 13432kb

input:

1000 1000
.STXDDI..TODOZDSZE.O.E.YLBJOVWOZMF.ZZGNVBEIHVFIGY.NXZPHQY.FWBCCCU.IALMPSUMAOHTJOBILOFC..DVMWWGZWJ.PGAXACPPPQDIOEQZP.HLBYDZACYQFCDX.DKHAZ.X.DDORVTPQQ.DAAOPOO.XCQOGIJJEK.UAFVDVKTURBOR.SGS.ILPQEHUGSMFG..JOFQLYWPVLYXONQUGCPYCTR.PKDZINZAIPFNSFELLS.URLAMGZ.XJ.TPVEFUJTPBWXJATRWKLYERIVJKBUGFETILUF...

output:

YES
STXDDIAATODOZDSZEAOAEAYLBJOVWOZMFAZZGNVBEIHVFIGYANXZPHQYAFWBCCCUAIALMPSUMAOHTJOBILOFCAADVMWWGZWJAPGAXACPPPQDIOEQZPAHLBYDZACYQFCDXADKHAZAXADDORVTPQQADAAOPOOAXCQOGIJJEKAUAFVDVKTURBORASGSAILPQEHUGSMFGAAJOFQLYWPVLYXONQUGCPYCTRAPKDZINZAIPFNSFELLSAURLAMGZAXJATPVEFUJTPBWXJATRWKLYERIVJKBUGFETILUFBKIAULU...

result:

ok Correct.

Test #59:

score: 0
Accepted
time: 4ms
memory: 14680kb

input:

1000 1000
..I........................Z.......C......F.....B..........SW.....R.D.Z..S.LX...TR.....S.B.....B...I..P.R......S...T.BL.M......Z.U......R...............HB.G....K...........D.W....T...S......U..MIG.........UY.....D........M..........X.XK...........V......WT......H...................S..B.......

output:

YES
OI..AA.AAAA.AA.AAAAAAAAAAAZAAAAAAACAAAAAAFA..AABAAAAA.AAA.SWAAAAARADAZ.ASALXAAATRAAA.ASABAA.AABA.AIAAPARAAAAAASAAATABLAMAAAAAAZA..AAAAARAAAAA.AAAAAAAAAHBAGAAA.KAAAAAAAAAAAD.WAAAATAAASAAA.AAUAAMIGAAAAAAAAAUYAAAAADA.AAAAAAMAAAAA.AAAAXA.KAAA.A.A.AAA.AAAAAAWTAAAAAAHAA..AAAAAAAAAAAAAAASAABA.AAVAAAAA....

result:

ok Correct.

Test #60:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

10 10
.GKUDKGMANA.
A..........H
N..........N
Q..........B
J..........V
Y..........P
O..........U
D..........T
X..........P
D..........E
U..........R
.NYOASKFGBM.

output:

NO

result:

ok Correct.

Test #61:

score: 0
Accepted
time: 1ms
memory: 4000kb

input:

100 100
.RRLADAYHEBSINAJACSHZANHTEJTYUOJFDGIAYODQDELQNYUDFSKZBGWJJTISIDZADCRPVJEYQIITKMPNDGIQYZDXWWMQETIPFBZO.
S....................................................................................................O
E........................................................................................

output:

YES
..........SINAJACSHZANHTEJTYUOJFDGIAYODQDELQNYUDFSKZBGWJJTISIDZADCRPVJEYQIITKMPNDGIQYZDXWWMQETIPFBZO
........EBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAW
..LADAYHAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

result:

ok Correct.

Test #62:

score: 0
Accepted
time: 4ms
memory: 13440kb

input:

1000 1000
.JAKFUFMSHIGMDNRMFGIOEQPSTWONZYFQVGFGMRMNNDDXPGARMHIBPXXESWLTWSIEQULLIXQRBHSJLSHZLJRNNBUEAESLQKNSZYHAEOANLMGYOHXOIOBQQECHNXSINXZCIQTHRFGPPRASDVWKGOGDCTBPHUHDUCYQOEMUCSKEXMSEUCJTXXRCUIJZKVPETRNOOAHANWWAPACUYNODHPMQKYWVUHMVHGWIAHSIEXUICRQDWKSUFWMZZLECVXMISJIKBSSWXUMOZHVXOKRYZYZZDMVIRNHGWYXYF...

output:

YES
................................VGFGMRMNNDDXPGARMHIBPXXESWLTWSIEQULLIXQRBHSJLSHZLJRNNBUEAESLQKNSZYHAEOANLMGYOHXOIOBQQECHNXSINXZCIQTHRFGPPRASDVWKGOGDCTBPHUHDUCYQOEMUCSKEXMSEUCJTXXRCUIJZKVPETRNOOAHANWWAPACUYNODHPMQKYWVUHMVHGWIAHSIEXUICRQDWKSUFWMZZLECVXMISJIKBSSWXUMOZHVXOKRYZYZZDMVIRNHGWYXYFJSBAJSR...

result:

ok Correct.

Test #63:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

10 10
.VBYCDNLKSW.
R..........U
S..........P
G..........M
K......x...Y
P.x....x...P
V..........A
R..........E
O..........V
R..........U
K..........Q
.XYOOIHYQZX.

output:

NO

result:

ok Correct.

Test #64:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

100 100
.BHMXXBSMUHVYTUTYDHQQYTVVMPXVCYWAIRJGBZBRJXMJAFBQBYYFCMYEIRAIDCELHMYCBONBFTIYVOBFIWLSXJRWKCJQRPSCFDNT.
C.....................................................................x.x.x..........................P
F.......x................x...............................................................

output:

NO

result:

ok Correct.

Test #65:

score: 0
Accepted
time: 9ms
memory: 13684kb

input:

1000 1000
.UIGXNGKSRDNDTUAEHIRNXLHRLSYYZMIATKNZXOPWKWNMKAPWJCGZVKJGMKVMRYVNOQGISKECIYCTYEIBUSWJLQEPIQCPXDJYPQZMGETFODCIFKLDHCHJRTZIVQFWNJUSNHSXNLXOATNASASFSHHDOHGUBCYDEAQYJLDVJEWTKOPDXAZTSXACZKUTOGOLPPXYNLXAMHURAITERGIMPDUTOXSHQCIYEWPMMZDCMXSJWLXHQQNQHBFSXEUGBAOBQEQIEIBJBZSDCPWBYXUFYGKDCKDLMSLUORYRO...

output:

YES
.........DNDTUAEHIRNXLHRLSYYZMIATKNZXO.WKWNMKAPWJCGZVK.GM.VMRYVNOQGISKE.IYCTYEIBUSWJLQEPIQCPXDJ.PQZMGETFODCIFKLDHCHJRTZIVQFWN.USNHSXNLXOATNASASFSHHDOHGUBCYDEAQYJLDVJEWT.OPDXAZTSXACZKUTOGOLPPXYNLXAMHURAITERGIMPDUTOXSHQCIYEWPMMZ.CMXSJWLXHQQNQHBFSXEUGBAOBQEQIEIBJBZSDCPWBYXUFYGK.CKDLMSLUORYROXCNDPPJ...

result:

ok Correct.

Test #66:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

10 10
.UTSAZHTXYX.
L.........xX
C......x...I
T......x...W
E..........Y
M.x........T
S..x..xx...H
H.....x....S
U......x...J
U..........B
A...x..x...C
.OHMGKKTKQH.

output:

NO

result:

ok Correct.

Test #67:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

100 100
.JAFDLLBUUSDKENTKACNZBYKAYOXBHHKRQEPYWPNKYNKNZTKJEMOUFFEKSLCCQAVMCDRCJZQGITTGNKADWZTJAVNUCEEUVDKRDXQB.
A.........................x...................................x......................x.....x....x....R
K...........x...........................................x...x.x..........................

output:

NO

result:

ok Correct.

Test #68:

score: 0
Accepted
time: 5ms
memory: 14564kb

input:

1000 1000
.NULNZJLOQREAOHHZRSBEMIOAYQYPGEJVXWIOCNCFXXHIYOXXJKNYZPCTLSDMXLAJVURIIYKXOHFRIYYEIQUXGCANJFFGDGCPJQOXHSIXDMJYURIOTHZYUUKNZJAVQIGPFNENLBEFLTVNMRSXWDWDSEGVVAVUIICAFNCKLATYOUCZYYYFWFSMWKIKOKYJHCTXQFAIPPVHQRBMTIBGRTJNTSSAZZCVHMRKNJXRGTGKRWKDAMXITEPONEAXWRVASSXXAMANWYAASZTQXEFHAUKJHPGLIUBPOJXIR...

output:

YES
..........................................................................................................................................................................................................BMTIBGRTJNTS.AZZCVHMRKNJXRGTGKRWKDAMXITEPON..XWRVASSXXAMANWYAASZTQXEFHAUKJH.GLIU.POJXIRKVGXO.U...

result:

ok Correct.

Test #69:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

10 10
.XIIYSTPPDQ.
J..........L
H..x.......Q
K..........T
R.....x....C
Bx.........G
T.x........A
C..x.......H
A.x...x....T
P.......x..L
U.....xx...R
.BTHGJRRIEM.

output:

NO

result:

ok Correct.

Test #70:

score: 0
Accepted
time: 1ms
memory: 3820kb

input:

100 100
.WCHFDUVNQZXTXCLWYSNAMVUBFQXPIJYHUVUQKFZURHQDYDWCCAFFEDNJZGAAEIMAUUCYZFLMWFNHXKZTOHXEAHCDUCZQGJCBOHXN.
Yx.xxx.x.x.x.xx..x..x.x..xx..xxxx.x..x.xxx..x.xx.xxxxxxxx..x..x..xxxx........x...xxxx..xx.xxxxxx.x..xY
M.............x.............xx............x.xx...........x.....x.........................

output:

NO

result:

ok Correct.

Test #71:

score: 0
Accepted
time: 6ms
memory: 15240kb

input:

1000 1000
.YYQPCIJLWNSKJEJHGBDWKBONGSKGORSBWFMZGIUGNBBQQKJZGOIBVLRKOAMMMVFGZJFECUVWDYDUVAGEXXRGFKBQSQITXJQBDMLMIKWMLWNJFLYMAISFAWZJUUOPLCPYOHQHKUWOLTVRTIVLZGMCWTVKHQDMRMSZXUEJIPTRWNDRZTXBDZCXBXSJWWLZDTPZSULUACNKGWNVEPYVBGOKXAATPWSSKZAXSTWKALPLHEIYOHQNFDHBCMGSQEUKIKXBVUHBOBLPBVZNAHPMCDKXQYSIFEVLVAEDJ...

output:

YES
....................................................VLRKOAMMM.FGZJ.ECU.WDYDUVAGEX.RGFKBQ.QITXJQBDMLMIK.MLWNJFL.M.ISFAWZ.UUOPLCPYOH..KUWOLT.RT..LZGMCWT..HQDMRM.ZXUEJ.PTRWNDRZTXBDZCXBXSJWWLZDTPZ.ULUACNKGWNVEPY.BGOKXAATPWS.KZAX..WKALPLH.IYOHQNFDHBCMGSQEUKIKXB.UHBOBL.BVZNA.PMCDKXQYSIFE.L..EDJBLDOJQF...

result:

ok Correct.

Test #72:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

10 10
.EACBPCUCNR.
D..........S
I...xx.....J
U..........V
E.....x.x..C
M..........O
R....x....xI
A.x........V
G.x........H
K..........V
C..x..x....L
.HGFJIYQZSZ.

output:

NO

result:

ok Correct.

Test #73:

score: 0
Accepted
time: 1ms
memory: 4040kb

input:

100 100
.JAJHQEAHMORBUNSADNSXTEJGNXBWFSMMGROIGWLNLYNMCUXZFGRDHSPLKIPVJBHGTZWCEIOSCNGLCGZNCKCDDXYAMDVRKCXYYCXV.
Wx...............xx.x....x.xx...xx....xxx..x........................x.....x.....x............x.......N
R........x.............x....x.....x....x......................x....x.....................

output:

NO

result:

ok Correct.

Test #74:

score: 0
Accepted
time: 7ms
memory: 18296kb

input:

1000 1000
.BHUNFMSMVENVZNPGULRKVZVELQNXNJTIAKLSLZPXABRTIDVWCOPHAIOXNJUMTINGHMPAOJKESKKSEYRHYDDUJSYTUBMCDPJSJLSTBBLJAJYVPWNFLFKXZYJKPGCNLSBUSOCBEJDXSWEAJDMGGGBCAYZKSCADVQMYUXDUCQLRAXMEWVSEPLQIYXOWEJVPRKTKZNXKGWFBWERACNJLCWPECUAMFPEHNUCNBCUHQZZIFPVUXDWTVGYKOTPVLWXUZZAYIZGPJFTEWEOBZGRSFNBGZEHJCCTGVWHTE...

output:

YES
.......................................................................................TUB.CDPJSJLSTBB.JAJYVPWNFLFKXZYJKPGCNLS.U.OCBEJDXSWEAJDMGGGBCAYZKSCADVQMYUXDUCQLRAXMEWVSEPLQIY.OWEJVPRK.KZNXKG.FBWERACNJLCWPECUA..PE.NU.N.C..QZZ.FPVUXDWTVGYKOTPVLWXUZZAYIZGPJF.EWEOBZGRSFNBGZE.JCC...W..EOJEJUBI...

result:

ok Correct.

Test #75:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

10 10
.HTADQAQMWO.
B..........Z
S..........U
Z..........B
Ux.........C
F...x.x....X
K.x......x.B
R.........xO
M..x....x..V
N....x....xG
T.x......x.W
.UKMFGFPLKN.

output:

NO

result:

ok Correct.

Test #76:

score: 0
Accepted
time: 0ms
memory: 4040kb

input:

100 100
.WGLRIGBLIUDGFHSQADPGWNQUUWBCPCAHGIUAUEYYESTQXEOOEUMSOMYNYCNPXJCHGPPUQPRXJNSTYGYHUKCYYFMJMXUVOQLNBIWI.
Qxxxxxxxxxx.xxx.xxx.xx.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xxxxxxxx.xxxxxxx.xxxxxxxxxxxxxxxxxxxxQ
Wx...........x.x...x.x..x.xx.x............xx...........x.x..x.....xx..x....x.............

output:

NO

result:

ok Correct.

Test #77:

score: 0
Accepted
time: 10ms
memory: 17776kb

input:

1000 1000
.NLZDUTQNBAWRYWRCMQXBUSCMTSVODXKKDWPZLPCFRFLFEZCGHSOKAFDOTVUQVNWHOTDWZFVZZTNRAADZNGBDAERKDYHPFOXEHLPEGHACTOCGWQZRAGDICHYHTNUHOMNZOQOVYZRSESIFRULCKNMKWNSZASXQETYEQECTZJHWHHVWXQRMWTIWAYUZIJMOMCKNCOIONIXWIJZINTFTIJLGGGEFNMZBIHPAUMWFKVNJIOMMHCHDDBEOITVQFNAEXNZVAHFUEIESQWMYUJBUHABQIJTGQMMFDSDKA...

output:

NO

result:

ok Correct.

Test #78:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

10 10
.KIATNNBQHI.
L...x......E
A..x.......H
Y......x...B
I.x....xx.xB
S......x.x.Z
J..........U
J........x.H
G...x......L
H......x.x.S
L...x......Z
.CXPLXPSIZR.

output:

NO

result:

ok Correct.

Test #79:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

100 100
.VUHOPFRWLYETEXERXRDCIVXPOJATRTEKQANWDHLBJHLICCFGCINTOGRTTFKJAIXRIJWRFQFGQCDMVOFMFMFROXUQFQYMRXUELVNL.
H..x............x..x............x.x...x...x.....x..x.......x..........x...........x......xx.......x..K
Q.......x.x.....x.......x.....x..x..............................x.x...x..x.x.............

output:

NO

result:

ok Correct.

Test #80:

score: 0
Accepted
time: 9ms
memory: 17504kb

input:

1000 1000
.VJZQSRRPMHKGNFWBCDXHIVWFLVOGNQMPUQXKGDFICDCGVSZLTUROODTOGKXIFZQCCYRTAVSONKGYXCNGWHWCUEUPOWFJFTARPLMHMFODRKKMIHHAJISAQGHUSWPVHPYETJHTDDBUDGWMIGDPIHRKNGCOAKDCTXZGKMYPCJXNLUTGNVMXXKSNTYNYRRKQQYNEISUYJKOZGLSCXBMUWTBLWVQMPOQVVDJGPFMIJNIGTRLIYISRVMPBMDJLINDNKOBTZTKIFQFKKOKKYIQIYOETBUGYFTFIJIEMM...

output:

NO

result:

ok Correct.

Test #81:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

10 10
.NAQRRDBDNF.
F.........xH
Nxx......x.A
L...x.x.x..D
V......xx..B
D.....x....I
C.x........J
E....xx....W
I..........Z
G..x.......C
B......x..xS
.TJGLWWRVRS.

output:

NO

result:

ok Correct.

Test #82:

score: 0
Accepted
time: 1ms
memory: 3732kb

input:

100 100
.PRJMCTWZORMJPQWDUMIELEICWQEHACOAUNKOVTBUCYJVBUKZFWMEVVXVEHDHNYSFDWHVRBEMFKXRISECTPNQJNJRXOYMZMPSVQNT.
F.......x........x..x.....x.....................xx..............xx.......x...................x.x.....Z
Sx....x..........x.......x...x........x....................x...x..............x..x.......

output:

NO

result:

ok Correct.

Test #83:

score: 0
Accepted
time: 7ms
memory: 18248kb

input:

1000 1000
.CREOVUSQSUBZHGCAMEHDHOEKYXWYDEVOBZAVCCAVPDWBJGLQQGURPAIXJWGJHIDUOFFPMOHFQTRBLWZGLFULTNRNPLJTLWTINHFTFPDVZPOBTAEYMJKHOIRZSISGGNKJTPSNXLHLKJAZCBYHLGGKJLRPMIHQTFLEYOXAEUXOXIGBOYLXFACCYYBPNZBPEQQHPLOCIAGQWQELHDJOYFYEBDUFBLCPYTPXUOGCZJWDRCXHHDKAEHZOCKOOCECYAGETYBJABTQZAGIVBLARAYEDKZSZUZZAQAHHI...

output:

NO

result:

ok Correct.

Test #84:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

10 10
.UTCQOMFRSG.
D.x.x.x....W
P.......x..L
Ux.........A
I..x.......X
Sx.......x.U
W.x..x.....V
C..x......xK
O....x.x.x.F
E..........N
S........x.E
.ZWIDVDMLFK.

output:

NO

result:

ok Correct.

Test #85:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

100 100
.CLKWQRYTKUGOIJWPVYEBSBTZDWMKXMUJGEMKRKJFRSPHADSSDYUTYPCBSFBBSSJGUFAREHPVHWQVWOEWDPNLRVFXXPPIYSDDUSUY.
Zx...x.x...x......x.....x..x...x..x..........x....x....x.........................x.........x........xC
J.............x...x............xx......x...x.x.........x.......x...x..........x..........

output:

NO

result:

ok Correct.

Test #86:

score: 0
Accepted
time: 7ms
memory: 17192kb

input:

1000 1000
.NZFEZUYNRISOCPIEAOOISHLWCREPCVAUFDECHSNVFHMJCDXSQOTTPBFSIFSJOWDVZQULKUWVFBLEYGHJDQNZKRWQYRMGFDIVHGQAGHROSZZNZLQRBODARKGAJTGAJHXFXREDREAYOJJEGSXCPGVSNERMUUIHYNBHVVVDFRLLXSHTLSOFRIUQVDPNRDLFAHIKRIRPXMGHMUEUKJUEEWZGFTGYNESQTGRRRYIZTXFELFODRZVGUKQXSKUFWWFIRVEQMFASWWUKVUJSWOKTDPNJPIDWZXSZQSKXD...

output:

NO

result:

ok Correct.

Test #87:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10 10
.AAHAPMZFHH.
K..........Y
F......xx..Z
F.......x..Y
Y......x...Z
E..........X
Yxx.x......A
Y....x.....G
I.....x....W
S.......x..C
E..........U
.OTBPGWPSOV.

output:

NO

result:

ok Correct.

Test #88:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

100 100
.VLZZHFSYLELLKWHKTYGPRPVLXKTOVUSYLOTLHFHDOGWCHSKICKQJNYXRFFBLGLJFEKYIOPWSFDNKNVEIMIQWKOMYYBEQDWZNELWB.
Gx.......x.x..x....x...........x..........x.......x......xx..x....................x.x...x............A
Rx.....x.xx....xx.x.xx..................................x........x.............x..x......

output:

NO

result:

ok Correct.

Test #89:

score: 0
Accepted
time: 6ms
memory: 18224kb

input:

1000 1000
.XWGCCNEHTKSGEGYLDZPMUSEXZISJXQITQKYNZTBXHQPBCNTCOJLOEIHBRREEZBILHQWBRPUGZPBEKVCAIVBOSJUMXAOAPJHJYLKQHRYOTFSQGDOXXMBAABFUFDOVINZTXRTFTVSHGOEYLNGJFBAISGBMARUCGRKLBGBSSVEEZCJWIOUXOQAUQOIUOXWBREHTLMFAARFBINPIZFOJBGYPPDCPPPUNJKQFRQHDDVOJOZSODGIMSUGOYPFUNBKCTZKRDAILLJZUUXMPZSJSYQHJTUFLFDCEJWBRF...

output:

NO

result:

ok Correct.

Test #90:

score: 0
Accepted
time: 5ms
memory: 12728kb

input:

1000 1000
.AACADBEBCBCBDACDEDCBCCAEECCAAECCDBECCBBBECCDEEDCACBBAEAADDCEACCABCCECCAAECBCBCDCDDCAABBDADCCDCBBBDBEAAABDEEAEBCDBDDEAEACBDCADEADDCDECDABCBBEEEEEDECEBBADEBDBDDDAAEBEBCCCBACEDABBEAABEBCCAADCCECBAEBADDDCBBCBDDEAECBDBAEAABCADCAADDAAEEBAEABEADBADCACCCADCAEDEDACBADAEDEBABEEBBECCCECEDCBACDEBAACE...

output:

NO

result:

ok Correct.

Test #91:

score: 0
Accepted
time: 0ms
memory: 12668kb

input:

1000 1000
.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

NO

result:

ok Correct.

Test #92:

score: 0
Accepted
time: 3ms
memory: 14172kb

input:

1000 1000
.CSUBCKBTFPZSKIIWUOHEGDHVTJNTLVDPVAJBLBUSOISEXNRUPHCWJCGJQSTUPIPZKMVHHREJWJCRHBNBEPYXVSVBTJPDLBVNLIGJGJFLNETPIAMVRCIBBZCTMQDFNUBBHUKIMVJRXULOKEUSNUYGXTVAVISTQICLQNMVTUKLIDWYNDWGDLFWHSYWLUFVHYIJYCYYRHKYYHSTTLQDHNYHTNXCHIQAYQQROFXNEEZELTDMHAFPOSZSQEMUNRNFDWYPSCPYSQREDNIFRKFSGIRFREIZLCCKKSZNN...

output:

YES
....................GDHVTJNTLVDPVAJBLBUSOISEXN.UPHCWJCGJQSTUPIPZ.MVHHREJWJCRHBNBEPYXVSVBTJP.LBVNLI.J.JFLNETPIAMVRCIBBZCTMQDFNUBBHUKIMVJRXULOKEUSNUY.XTVAVISTQICLQNMVTUKLIDWYNDWGDLFWHSYWLUFVHYIJYCYYRHKYYHSTTLQDHNYHTNXC.IQAYQQROFXNEEZELTDM.AFPOSZSQEMUNRNFDWYPSCPYSQREDN.FR.FSGIRFREIZLCC.KSZNNLSQMUKO...

result:

ok Correct.

Extra Test:

score: 0
Extra Test Passed