QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#420849 | #8679. Tilting Tiles | bulijiojiodibuliduo# | AC ✓ | 152ms | 22516kb | C++17 | 7.6kb | 2024-05-24 23:21:33 | 2024-05-24 23:21:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=550;
int n,m,go[N*N];
char bs[N*N],s[N][N],t[N][N];
bool vis[N*N];
array<int,2> pos[N*N];
typedef pair<int,int> hashv;
const ll mod1=1000000007;
const ll mod2=1000000009;
hashv operator + (hashv a,hashv b) {
int c1=a.fi+b.fi,c2=a.se+b.se;
if (c1>=mod1) c1-=mod1;
if (c2>=mod2) c2-=mod2;
return mp(c1,c2);
}
hashv operator - (hashv a,hashv b) {
int c1=a.fi-b.fi,c2=a.se-b.se;
if (c1<0) c1+=mod1;
if (c2<0) c2+=mod2;
return mp(c1,c2);
}
hashv operator * (hashv a,hashv b) {
return mp(1ll*a.fi*b.fi%mod1,1ll*a.se*b.se%mod2);
}
hashv pw[N*N],base;
typedef pair<ll,ll> PLL;
namespace Factor {
const int N=1010000;
ll C,fac[10010],n,mut,a[1001000];
int T,cnt,i,l,prime[N],p[N],psize,_cnt;
ll _e[100],_pr[100];
vector<ll> d;
inline ll mul(ll a,ll b,ll p) {
if (p<=1000000000) return a*b%p;
else if (p<=1000000000000ll) return (((a*(b>>20)%p)<<20)+(a*(b&((1<<20)-1))))%p;
else {
ll d=(ll)floor(a*(long double)b/p+0.5);
ll ret=(a*b-d*p)%p;
if (ret<0) ret+=p;
return ret;
}
}
void prime_table(){
int i,j,tot,t1;
for (i=1;i<=psize;i++) p[i]=i;
for (i=2,tot=0;i<=psize;i++){
if (p[i]==i) prime[++tot]=i;
for (j=1;j<=tot && (t1=prime[j]*i)<=psize;j++){
p[t1]=prime[j];
if (i%prime[j]==0) break;
}
}
}
void init(int ps) {
psize=ps;
prime_table();
}
ll powl(ll a,ll n,ll p) {
ll ans=1;
for (;n;n>>=1) {
if (n&1) ans=mul(ans,a,p);
a=mul(a,a,p);
}
return ans;
}
bool witness(ll a,ll n) {
int t=0;
ll u=n-1;
for (;~u&1;u>>=1) t++;
ll x=powl(a,u,n),_x=0;
for (;t;t--) {
_x=mul(x,x,n);
if (_x==1 && x!=1 && x!=n-1) return 1;
x=_x;
}
return _x!=1;
}
bool miller(ll n) {
if (n<2) return 0;
if (n<=psize) return p[n]==n;
if (~n&1) return 0;
for (int j=0;j<=7;j++) if (witness(rand()%(n-1)+1,n)) return 0;
return 1;
}
ll gcd(ll a,ll b) {
ll ret=1;
while (a!=0) {
if ((~a&1) && (~b&1)) ret<<=1,a>>=1,b>>=1;
else if (~a&1) a>>=1; else if (~b&1) b>>=1;
else {
if (a<b) swap(a,b);
a-=b;
}
}
return ret*b;
}
ll rho(ll n) {
for (;;) {
ll X=rand()%n,Y,Z,T=1,*lY=a,*lX=lY;
int tmp=20;
C=rand()%10+3;
X=mul(X,X,n)+C;*(lY++)=X;lX++;
Y=mul(X,X,n)+C;*(lY++)=Y;
for(;X!=Y;) {
ll t=X-Y+n;
Z=mul(T,t,n);
if(Z==0) return gcd(T,n);
tmp--;
if (tmp==0) {
tmp=20;
Z=gcd(Z,n);
if (Z!=1 && Z!=n) return Z;
}
T=Z;
Y=*(lY++)=mul(Y,Y,n)+C;
Y=*(lY++)=mul(Y,Y,n)+C;
X=*(lX++);
}
}
}
void _factor(ll n) {
for (int i=0;i<cnt;i++) {
if (n%fac[i]==0) n/=fac[i],fac[cnt++]=fac[i];}
if (n<=psize) {
for (;n!=1;n/=p[n]) fac[cnt++]=p[n];
return;
}
if (miller(n)) fac[cnt++]=n;
else {
ll x=rho(n);
_factor(x);_factor(n/x);
}
}
void dfs(ll x,int dep) {
if (dep==_cnt) d.pb(x);
else {
dfs(x,dep+1);
for (int i=1;i<=_e[dep];i++) dfs(x*=_pr[dep],dep+1);
}
}
void norm() {
sort(fac,fac+cnt);
_cnt=0;
rep(i,0,cnt) if (i==0||fac[i]!=fac[i-1]) _pr[_cnt]=fac[i],_e[_cnt++]=1;
else _e[_cnt-1]++;
}
vector<ll> getd() {
d.clear();
dfs(1,0);
return d;
}
vector<ll> factor(ll n) {
cnt=0;
_factor(n);
norm();
return getd();
}
vector<PLL> factorG(ll n) {
cnt=0;
_factor(n);
norm();
vector<PLL> d;
rep(i,0,_cnt) d.pb(mp(_pr[i],_e[i]));
return d;
}
bool is_primitive(ll a,ll p) {
assert(miller(p));
vector<PLL> D=factorG(p-1);
a%=p;
if (a<0) a+=p;
if (a==0) return 0;
rep(i,0,SZ(D)) if (powl(a,(p-1)/D[i].fi,p)==1) return 0;
return 1;
}
}
bool check() {
bool vs=1;
rep(i,0,n) rep(j,0,m) if (s[i][j]!=t[i][j]) vs=0;
if (vs) return 1;
bs[0]='.';
int tot=0;
vector<VI> lab(n,VI(m,0));
rep(i,0,n) rep(j,0,m) if (s[i][j]!='.') {
bs[++tot]=s[i][j];
lab[i][j]=tot;
} else {
lab[i][j]=0;
}
auto mov=[&](const vector<VI> &lab,char u) {
rep(i,0,n) rep(j,0,m) if (lab[i][j]>0) pos[lab[i][j]]={i,j};
if (u=='L'||u=='R') {
rep(i,0,n) {
VI vr;
rep(j,0,m) if (lab[i][j]!=0) vr.pb(lab[i][j]);
if (u=='L') {
rep(j,0,SZ(vr)) pos[vr[j]][1]=j;
} else {
rep(j,0,SZ(vr)) pos[vr[j]][1]=m-SZ(vr)+j;
}
}
} else {
rep(j,0,m) {
VI vc;
rep(i,0,n) if (lab[i][j]>0) vc.pb(lab[i][j]);
if (u=='U') {
rep(i,0,SZ(vc)) pos[vc[i]][0]=i;
} else {
rep(i,0,SZ(vc)) pos[vc[i]][0]=n-SZ(vc)+i;
}
}
}
vector<VI> nlab(n,VI(m,0));
rep(i,1,tot+1) nlab[pos[i][0]][pos[i][1]]=i;
return nlab;
};
auto checksm=[&](const vector<VI> &lab) {
rep(i,0,n) rep(j,0,m) {
if (bs[lab[i][j]]!=t[i][j]) return false;
}
return true;
};
auto checksp=[&](const vector<VI> &lab) {
rep(i,0,n) rep(j,0,m) {
if ((lab[i][j]==0)!=(t[i][j]=='.')) return false;
}
return true;
};
auto checkcyc=[&](const vector<VI> &alab,const vector<VI> &blab) {
rep(i,0,n) rep(j,0,m) {
assert((alab[i][j]==0)==(blab[i][j]==0));
go[alab[i][j]]=blab[i][j];
pos[alab[i][j]]={i,j};
}
rep(i,1,tot+1) vis[i]=0;
map<int,vector<PII>> cs;
rep(i,1,tot+1) if (!vis[i]) {
VI cyc;
int u=i;
while (!vis[u]) {
cyc.pb(u); vis[u]=1; u=go[u];
}
int l=SZ(cyc);
string tt;
for (auto x:cyc) tt.pb(bs[x]);
hashv ht(0,0);
for (auto x:cyc) {
ht=ht*base+mp(t[pos[x][0]][pos[x][1]],t[pos[x][0]][pos[x][1]]);
}
hashv hh(0,0);
rep(i,0,l) hh=hh*base+mp(tt[i],tt[i]);
hashv ho=hh;
int bs=-1,cc=l;
rep(i,0,l) {
if (hh==ht) bs=i;
hashv c=mp(tt[i],tt[i]);
hh=hh*base+c-c*pw[l];
if (hh==ho) { cc=i+1; break; }
}
if (bs==-1) return false;
auto o=Factor::factorG(cc);
for (auto [p,e]:o) {
int pc=1;
rep(j,0,e) pc=pc*p;
cs[p].pb(mp(pc,bs%pc));
}
}
for (auto [p,d]:cs) {
sort(all(d));
int r=d.back().se;
for (auto [pc,pr]:d) if (r%pc!=pr) return false;
}
return true;
};
auto debug=[&](const vector<VI> &lab) {
rep(i,0,n) {
rep(j,0,m) putchar(bs[lab[i][j]]);
puts("");
}
//puts("-----");
};
auto gao=[&](string op) {
auto nlab=mov(lab,op[0]);
if (checksm(nlab)) return true;
//cout<<op<<"\n";
//debug(nlab);
nlab=mov(nlab,op[1]);
rep(j,0,4) {
auto clab=nlab;
if (checksp(clab)) {
//puts("!!!");
rep(k,0,4) clab=mov(clab,op[(j+2+k)%4]);
if (checkcyc(nlab,clab)) return true;
}
nlab=mov(nlab,op[(j+2)%4]);
}
return false;
};
if (gao("ULDR")) return 1;
if (gao("URDL")) return 1;
if (gao("DLUR")) return 1;
if (gao("DRUL")) return 1;
if (gao("LURD")) return 1;
if (gao("LDRU")) return 1;
if (gao("RULD")) return 1;
if (gao("RDLU")) return 1;
return 0;
}
int main() {
Factor::init(250000);
scanf("%d%d",&n,&m);
rep(i,0,n) scanf("%s",s[i]);
rep(i,0,n) scanf("%s",t[i]);
base=mp(13331,23333);
pw[0]=mp(1,1);
rep(i,0,n*m) pw[i+1]=pw[i]*base;
if (check()) puts("yes"); else puts("no");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 14916kb
input:
5 7 ..g.... ....... h.i.j.k abcde.f ..lmn.o hbgdj.k a.ime.f ..c.n.o ..l.... .......
output:
yes
result:
ok single line: 'yes'
Test #2:
score: 0
Accepted
time: 2ms
memory: 14000kb
input:
5 7 ..g.... ....... h.i.j.k abcde.f ..lmn.o g...... ....... hijk... abcdef. lmno...
output:
yes
result:
ok single line: 'yes'
Test #3:
score: 0
Accepted
time: 2ms
memory: 14432kb
input:
5 7 ..g.... ....... h.i.j.k abcde.f ..lmn.o ....... ..g.... ..i.j.k h.cde.f ablmn.o
output:
yes
result:
ok single line: 'yes'
Test #4:
score: 0
Accepted
time: 2ms
memory: 14412kb
input:
5 7 ..g.... ....... h.i.j.k abcde.f ..lmn.o ......g ....... ...hijk .abcdef ...lmno
output:
yes
result:
ok single line: 'yes'
Test #5:
score: 0
Accepted
time: 2ms
memory: 14676kb
input:
5 7 ..g.... ....... h.i.j.k abcde.f ..lmn.o ......g ....... ...hijk .abcdfe ...lmno
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 0ms
memory: 14900kb
input:
8 10 axudxmgb.. rpyvs..... fozux..... xnve...... hx........ t......... c......... .......... cxvgxpea.. toyur..... dnzvx..... xmuh...... fx........ s......... b......... ..........
output:
yes
result:
ok single line: 'yes'
Test #7:
score: 0
Accepted
time: 2ms
memory: 13160kb
input:
9 7 kbi...b ....mm. .c.fc.. ...j.k. ..f..j. m....f. .igl.fl .g...a. ...f... k.j.... am.l... .....ib ..i.m.. ..gg.c. .....ff .mf.... jf..f.k cl..b..
output:
no
result:
ok single line: 'no'
Test #8:
score: 0
Accepted
time: 3ms
memory: 16612kb
input:
5 6 iyazl. bzxf.. yzxe.. czdzzy j..yk. jyfziy azxez. yzxdl. bzcz.. ky....
output:
yes
result:
ok single line: 'yes'
Test #9:
score: 0
Accepted
time: 3ms
memory: 16888kb
input:
5 6 iyazly bzxfz. yzxek. czdz.. jy.... kyfzjy azxez. yzxdi. bzcz.. ly....
output:
no
result:
ok single line: 'no'
Test #10:
score: 0
Accepted
time: 2ms
memory: 12844kb
input:
3 3 ... .a. ... ... .a. ...
output:
yes
result:
ok single line: 'yes'
Test #11:
score: 0
Accepted
time: 51ms
memory: 16748kb
input:
500 500 abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
no
result:
ok single line: 'no'
Test #12:
score: 0
Accepted
time: 105ms
memory: 19616kb
input:
500 500 abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
no
result:
ok single line: 'no'
Test #13:
score: 0
Accepted
time: 56ms
memory: 21232kb
input:
496 495 oanhdonngaokopboqljdalgpfdeqfelhjchogdmrcaqb.ooogggggicgenlbipaprnfbcrapabfjaemrhdelojgbldirmidgihpjfobgopinddhhmacjcqljgajndcgemiepgipqmdgcqndqadkialgjddpkdfhamldedgrejbbgirpmbeqjc.mbipndabllbjbgrlbrhrcaiphrpogicjdcqeqdhdldpefdekqqihifhagjokepbbceqprongafeqmhbripqceodmfaecpgnaenfjjrjbbabaec...
output:
yes
result:
ok single line: 'yes'
Test #14:
score: 0
Accepted
time: 36ms
memory: 19916kb
input:
367 490 ababbaabbbabbabaabbabbbabababbbabaabbbabbababbabbaaaabbbbaaabbbbababaaaaabbaabaabbbabbbbbababaaabbabaabbaabaabbbabbbbabbbabbabbabbabbbababbabbaaabaabaababaaababaabaabbbbbaaaaabbaaaaabbababaababbaabaabaaaababbbbbaabaaababbabbbbaabaabbabbabbbbaaabbaaababbbaaabbbaaabbbbaabbaaabbbabaaaaaaaaaabaa...
output:
yes
result:
ok single line: 'yes'
Test #15:
score: 0
Accepted
time: 19ms
memory: 21588kb
input:
500 500 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
yes
result:
ok single line: 'yes'
Test #16:
score: 0
Accepted
time: 16ms
memory: 22516kb
input:
500 500 tztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztz...
output:
yes
result:
ok single line: 'yes'
Test #17:
score: 0
Accepted
time: 3ms
memory: 14640kb
input:
2 4 .xxx ..xx xx.. xx..
output:
no
result:
ok single line: 'no'
Test #18:
score: 0
Accepted
time: 0ms
memory: 13152kb
input:
5 8 ........ ........ .aaaaa.. ........ ........ ........ ........ ........ ........ ..aaaaaa
output:
no
result:
ok single line: 'no'
Test #19:
score: 0
Accepted
time: 0ms
memory: 14396kb
input:
5 8 ........ ........ .aaaaaa. ........ ........ ........ ........ ........ ........ ...aaaaa
output:
no
result:
ok single line: 'no'
Test #20:
score: 0
Accepted
time: 121ms
memory: 20836kb
input:
500 500 fwizgbybbgxihqejzkgyvdcrgzkfhfktchdilsfgigilfktykliwrykymilrmjjmrlimykyrwilkytkflihifguljdhctkjhgkzfrcdvyfkzfexhxifbbybgziwg...........................................................................................................................................................................
output:
no
result:
ok single line: 'no'
Test #21:
score: 0
Accepted
time: 107ms
memory: 21240kb
input:
500 500 hkmkgolmmlokbyyeohmmvmkhbpgmmkypmbmkmhcqvcbkkkbkbbkkwkkobrrdjkjgelllvclldgcvlddxclxvhvwlglkxsxklglwvhvxlcxddlvcgdllcvlllocaxaarrbokkwkkbbkbkkkbdvzkkmkmbmpykgmgpbhkmvgghoeyybkolgglomkmkh..............................................................................................................
output:
no
result:
ok single line: 'no'
Test #22:
score: 0
Accepted
time: 152ms
memory: 21840kb
input:
500 500 xueftjjjxjyzctkjocmokbkomcojktczyjxjjjtfeuxexumbooocaoljckojectkrketulbzlejoxoloxojelzblutekrktcejokcjloacooobmuxexueftjjjxjyzctkjocmokbkomcojktczyjxjjjtfeuxexumbooocaoljckojectkrketulbzlejhxoloxojelzblutekrktcejokcjloacooobmuxexueftjjjxjyzctkjocmokbkomcojktczyjxjjjtfeuxexumbooocaoljckojectk...
output:
no
result:
ok single line: 'no'
Test #23:
score: 0
Accepted
time: 3ms
memory: 16480kb
input:
1 6 ..h... h.....
output:
yes
result:
ok single line: 'yes'
Test #24:
score: 0
Accepted
time: 4ms
memory: 18388kb
input:
5 7 ...sr.k .pits.t ..gss.m q.hubko ..xi.bb .....sk ...okbi ...mssu ..trsgx qptihbb
output:
yes
result:
ok single line: 'yes'
Test #25:
score: 0
Accepted
time: 0ms
memory: 14904kb
input:
4 2 .e .. .. .. .. .. .. e.
output:
yes
result:
ok single line: 'yes'
Test #26:
score: 0
Accepted
time: 3ms
memory: 16624kb
input:
9 10 .......... ......f... .......... .......... ....k.uo.k .......... .......... ......k... .......... ......kfok .........u .........k .......... .......... .......... .......... .......... ..........
output:
yes
result:
ok single line: 'yes'
Test #27:
score: 0
Accepted
time: 3ms
memory: 14976kb
input:
5 10 .n.n.icfbl .c.hb..kkj .l.dd...cg .b.bh..bge lh.j..ikpb cifl...... nikkb..... bdhbcg.... nhdbkgj... lcbljhpeb.
output:
yes
result:
ok single line: 'yes'
Test #28:
score: 0
Accepted
time: 11ms
memory: 17912kb
input:
186 354 b....c....b..c....c....a...cb.a..aaa.....aac......c......aa..a....b....aaa.ca..c.a...bb..c..bcbb.bccaaa.a.a..c......cc.a..aa.abab.b.ba....c.c.bba.ba.c....cc..aa....ab..abb..c.a.b.c......b.b.a...cc.cb..c..b.....ac.c..a.cb.c.bbb......b..b.a...caab....a.aaccabba..a...aac..ccbab..a....b....a.a.....
output:
yes
result:
ok single line: 'yes'
Test #29:
score: 0
Accepted
time: 3ms
memory: 14924kb
input:
10 49 .kfmb.inlmmeeqj.mmgldemgoiklmm..gbgmm.lflmfpillmm dmmaj.okllj.bhojoj.dklpkbohjoenqjjlkp.ohqjodaecdq .oekcjhoalrhkpk.fdhlmbjrjoired.ocbrdo.qrmjlkobk.m .mdbjol.l.m.rcn.jq.aqi..lqckgm..h.qemcipfdhkodc.i .rlokjoei.m.bbpnoj.lik.akfjroek.i.iff.qbrndojaa.. cmafo.o.dhe.dkn..k.kfomkajoag.aaehh.m.eigdok...
output:
yes
result:
ok single line: 'yes'
Test #30:
score: 0
Accepted
time: 35ms
memory: 16940kb
input:
493 266 ....gg..d..e.ff..f..bhaa.d.....c...gidee...e.i...e....dch.....a.g.ebb..cce.fe.cbhi.f.....i..c.c..d.........b...c........e..bd..fidd..ic..g.e.a.icacb..bd.id.c.fi..cdhfd..i..a...gde...gg...agd..cbi..c.g...c.g..i..b.dh..d...id..c.i.....bh.id.fbaa..fc.f....a.h...ediaggf c...hcaaba...iggcgf.i.fea...
output:
yes
result:
ok single line: 'yes'
Test #31:
score: 0
Accepted
time: 15ms
memory: 18308kb
input:
255 381 ub........d..p...............l..kk..s..nd.....i.vx.lu..tx..y.n.m.....f..b.q.yc..t...f.....throlw.o.n..g.dn....rby.y......y.a.i..n...e.if......m.f..eg.i.q.....na.....nq..aaw.r..bfi..a.sb.c...bon.o..t....ab.up....e.rw.o.mt.....i...hs..lkj.iewb...oqn.f..u.b..q..i..q..rp....c..b.ptq..l...ks.q......
output:
yes
result:
ok single line: 'yes'
Test #32:
score: 0
Accepted
time: 0ms
memory: 17160kb
input:
183 61 ...abaa.bbcbcbcacbacaacccbbbaaaaababcbbcbcbac.cbabaabbbc.bbca .....abcbab....ccc...bbacc.cccc.c..ac...aba.aab......ab...cc. ......c...b.........c..b..b.......b........a........b........ ...abc..ca.bb..bca.b.cb...cc.a.bcbacba..c.b.c.b...c..c..b..a. ................................................
output:
yes
result:
ok single line: 'yes'
Test #33:
score: 0
Accepted
time: 28ms
memory: 21776kb
input:
500 500 j...p....hk....wiwo..k...b..p...n...y...g.............og..h..q.h..l.....p....f.....y..rji.....j...r.a....t.d.......mwvv..j...lxn.....b...mc.....l..x.r.f..d.......n...v..bnv...f.f..d..v.....j.....f.......w........qrce....k.w..t.k.........v...ke.hg...w....t..j..p.....x......wk.dw..qgnyr.v..na....
output:
yes
result:
ok single line: 'yes'
Test #34:
score: 0
Accepted
time: 50ms
memory: 20656kb
input:
500 500 .ec...a...fbb.aa....de.....e.......bd..bdeeeff.a.b...........c....e.ca.dbe..eedaa..d.cddc..c..ccbdc.aee...c.fce.d...e..fddfb......b..ea..fa......a..cead.e.f.d....bc......ea...a.f..a....a.....efc.d.cfe.baf.e.e.c..d..a....c..ec..d....ebc.ec.......ddbc...ebb.ff..dead.b.ac..fe..ce.e......a.a.e.e...
output:
yes
result:
ok single line: 'yes'
Test #35:
score: 0
Accepted
time: 78ms
memory: 19160kb
input:
500 500 djebdknlnkkkkkdbnmdhjimlkgkmdahblbch.hnlddcehclbekbafhkfahagmhiieah.kkknklcaielnfnendejgaffiekjkkkidmicnkmdgaikmjcgehebhigcjhbmijndemeljdkechaebdnlkmikkkckdgnhaadmnhmjhkfbjdcdkgkkkkiflndcchhgfkcfelnnmdhhgieachdhfghihieikfchenmiemejbkkkikfddi.dnadmfdegklkbghikfkkkmhdmkgnmiifjkbanhkfhdhcabfdn....
output:
yes
result:
ok single line: 'yes'
Test #36:
score: 0
Accepted
time: 19ms
memory: 20728kb
input:
500 500 l.hd........d.....lva..s....i...r...r....j...b...sth.frs.ik....t............p.k.qq..m.......b.....m.gvi...f.t..qf.....t..dt.p.b.......eg.u...q.v.........s.h...ip.kc..i.h..d...v.m.b....hb.ld.r.m..hlhu...u...e....l.i...k.m.cdu.......vj..e...l....m...m.n..........a..tc.....ai..a....o.....om..p....
output:
yes
result:
ok single line: 'yes'
Test #37:
score: 0
Accepted
time: 38ms
memory: 20428kb
input:
500 500 igb..hi.fc..ede..d..ehacfaia.f.g.hb.ad.......h.hichfd...ae.agi.gegi.a...ddhfbdi.hh.b.ib...g.biifh..a.d.hhab.a..acec.gh..a.hfdc.bch.i..daia.dcda.bieachifd.bbahbd..c..hbbcd.aeiie.cb.dfha.h.haggcbfaiba.hda.dfhigce.e.ehg.ce.fh..bcbee.hhdg.gciff.egee...a.ghd..d.gbcbiaiga...i.ehb.dd.ahiedef.ddggi....
output:
yes
result:
ok single line: 'yes'
Test #38:
score: 0
Accepted
time: 3ms
memory: 16532kb
input:
10 1 c . . . . . l . c b c l b c . . . . . .
output:
no
result:
ok single line: 'no'
Test #39:
score: 0
Accepted
time: 3ms
memory: 16432kb
input:
9 4 k... ..n. hhbh .fdd fda. ..ok .lef ..k. eobm khan kfoh fdef elkh obd. b... d... m... ....
output:
yes
result:
ok single line: 'yes'
Test #40:
score: 0
Accepted
time: 0ms
memory: 14932kb
input:
7 7 ...c..c c...c.. d...b.. ....c.a ....... b.cbcb. ....... .cbdccc ...bcbc .....ba ......c ....... ....... .......
output:
yes
result:
ok single line: 'yes'
Test #41:
score: 0
Accepted
time: 3ms
memory: 15928kb
input:
10 4 .... .... ..wn .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ..wn
output:
yes
result:
ok single line: 'yes'
Test #42:
score: 0
Accepted
time: 3ms
memory: 16236kb
input:
3 5 m.... h.k.. g.... ...mg ....h ....k
output:
no
result:
ok single line: 'no'
Test #43:
score: 0
Accepted
time: 5ms
memory: 15688kb
input:
238 218 ....v.w.mk.dkwi....qz...fyae...xjz..bdk..uuetxo......q.j...d.hta..mu.ha....cqlg.cbou..l..gc..w.fryubayqj.sf......av.r..z..fvt..i...uf.g...........m...mn.w.mj.x......q...q.xgxbnq.fqjoo......qxvc.qnr...f..cbb.....n.....y ....e...i..x.e..................b....tk..w.......w.......c.i.w..w..k........
output:
yes
result:
ok single line: 'yes'
Test #44:
score: 0
Accepted
time: 48ms
memory: 20228kb
input:
487 438 ..dc.f.dhcaefc.ag.d.cjc..e.je.hfib.ib.j.e.dccjacd.jh.ccc..hhc.g...h.cicccg.i.gccac.haec..h..ab.c.fheij.c.jc.bdh.c.gcg.c.j.g.f.j.h.d...ba.aifbd.gc.chgbed..gjif.de.ec.g.jjeeccacif..c.jgjc.cec.ff.jc.eg.ddeghecj.dfc..ff.gghch..j..hbi.dahagbb.ggd.f...jibe.g.fcg.ejcjeeecj..ghajgi..e.dcb.ciid.efdb....
output:
yes
result:
ok single line: 'yes'
Test #45:
score: 0
Accepted
time: 0ms
memory: 15080kb
input:
15 461 b.dbc.gec..eg.....dde.d...cg.c....fab....aae....f.a..be.c...fg.e.......bed.a.a..g...fa......c....b....g....d...dc.b......b..c..fb..cf...a.....dac.g....f...ec.db.bfdgcg...c.d......d.......ec...b....g..a......gd.ggc..d.g...f.bb.f.c..f....gb......f..a.dc...d...dfefc....a.g.e..a.d..d.e.b...g..ea....
output:
yes
result:
ok single line: 'yes'
Test #46:
score: 0
Accepted
time: 6ms
memory: 15292kb
input:
428 49 ndj...mh..g.m.i.b..kb.j..nei...lgffe..c.hej.n...i genbamkh...l..lfff.h.kca.gc.mdh.ih...ica.ldnhhhik .............................h.......h........... a.cibcnhf.ibilebh.fhbfd.hl.n.fbd.b....ke.fa..e.kf ................................................. ...............e..fm.h.....d..hb.hh...h.......
output:
yes
result:
ok single line: 'yes'
Test #47:
score: 0
Accepted
time: 0ms
memory: 14948kb
input:
1 420 ..d.c.cbb..d.abdda...c...bbc.db.d...d.b.b.a..bc.cd.abcccc.cb.a.ac.dd..d...c.caa..cbdd.cdb.a.bda.b.a..cbb...ab.b.b.c.bac.aaab..aa.dbb..ada..aaabab.d..baccbccdbbd.......a...c.bdcc..ddd.badd.cc..badbc.adbb....b.dd...bcb...bdb.d..aa.acab.ad.a..aa.ac.a.adbdbca.d.c..bcd.bdddcbc.cc.daac.cc.c.b..dcacc...
output:
yes
result:
ok single line: 'yes'
Test #48:
score: 0
Accepted
time: 57ms
memory: 20840kb
input:
500 500 ...........a..........m...................b..............cg.....j................c................km.....k.............a.g...............................o.g....e.i.........h.....................n.............b....e..d....................l......................i...l.................f.....b..m...
output:
yes
result:
ok single line: 'yes'
Test #49:
score: 0
Accepted
time: 23ms
memory: 22100kb
input:
500 500 b.d.....d.ad.a.ccd...dc...d..bc...............ac........a....................b..............b.......d..c....ac......................d....d............b................c.....a.....a...d..b......................a.......d.b...b........a.......c.......a.....b.d................b..dd........d........
output:
yes
result:
ok single line: 'yes'
Test #50:
score: 0
Accepted
time: 91ms
memory: 19476kb
input:
500 500 ef..hfkbbfgg.ggfaj.i.l.f.fiigbgakld...bjjfladbg.ijkc..g.fkjjcebllbgd.hddh.abglbc.clilagc.cefifhij..gj.cfh.jka.gcf.e.dllkef.ggkffh.lkdgaji.fg.c.hga..ceajbjkkjejfhgcjiaf.dgfbihe.bkd.jeaec.gae.elbjh..b.fk.ileihddef.lgcbl.egfka.afhlgkfbkccklid.fh..igf..jckdca.jafeebhe.cfdgflfai.effi..cffbbd.j.gc...
output:
no
result:
ok single line: 'no'
Test #51:
score: 0
Accepted
time: 88ms
memory: 20724kb
input:
500 500 iah.fbgnlhahdbobnbojkgggafbfnianbnalnlmjbaafjgkmml.hangakeamfgjjhacancngnnnceolibdekjfgaljalhba.ncclbn.jhmohcnmleda.moimmkajenjcjkgmkalnaocafmnehaaaccmlaoggdldbkibomhkbf.gmnabdoahlamnfhfdngiofdnbhcdmbhfgbkiblhammhcngjenlolcchaaclmnjanbahbjkhmaheoolednbogcjmhajmljclfihhakbg.dfcobnagnlldbajkoa...
output:
no
result:
ok single line: 'no'
Test #52:
score: 0
Accepted
time: 97ms
memory: 20788kb
input:
500 500 clkabhi.kkecebhfeicieiggchhjcjdabekabkjihcgfckkdbkgj.jiifblalbjkcfgkfchkakjfgiclkjfbfbbcddcfgg.hjhiiiagabaiklaeaglaiafjeagceeebbahfabhiefbhfcfilgajhabkke.gcigebffaddfejadkfeibejcgeadlbjlikd.ebhjaaeeeafgkailljggbhekfbieiefikkbej.kfkbggdjgfibbafkfcbbj.adcgfckkiidhhgeaj.kkagbeebiklei.ebbhk.ekfk...
output:
no
result:
ok single line: 'no'
Extra Test:
score: 0
Extra Test Passed