QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#564873#8679. Tilting TilesRngBasedAC ✓195ms32908kbC++178.0kb2024-09-15 16:22:102024-09-15 16:22:10

Judging History

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

  • [2024-09-15 16:22:10]
  • 评测
  • 测评结果:AC
  • 用时:195ms
  • 内存:32908kb
  • [2024-09-15 16:22:10]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second 
#define all(x) x.begin(), x.end()
using namespace std;

const int C = 500 * 500;
int n, m, arr[505][505], p[505 * 505], vis[505 * 505], notp[C + 5];
pii pos[505 * 505];
char s[505][505], f[505][505], tmp[505][505];
vector<int> prime;

void moveL()
{
    for (int i = 0; i < n; i++){
        vector<int> have;
        for (int j = 0; j < m; j++)
            if (arr[i][j] != 0)
                have.emplace_back(arr[i][j]);
        for (int j = 0; j < m; j++){
            if (have.size() > j)
                arr[i][j] = have[j];
            else arr[i][j] = 0;
        }
    }
}

void moveR(){
    for (int i = 0; i < n; i++){
        vector<int> have;
        for (int j = 0; j < m; j++)
            if (arr[i][j] != 0)
                have.emplace_back(arr[i][j]);
        for (int j = m - 1; j >= 0; j--){
            if (!have.empty())
                arr[i][j] = have.back(), have.pop_back();
            else arr[i][j] = 0;
        }
    }
}

void moveU(){
    for (int j = 0; j < m; j++){
        vector<int> have;
        for (int i = 0; i < n; i++)
            if (arr[i][j] != 0)
                have.emplace_back(arr[i][j]);
        for (int i = 0; i < n; i++){
            if (have.size() > i)
                arr[i][j] = have[i];
            else arr[i][j] = 0;
        }
    }
}

void moveD()
{
    for (int j = 0; j < m; j++){
        vector<int> have;
        for (int i = 0; i < n; i++)
            if (arr[i][j] != 0)
                have.emplace_back(arr[i][j]);
        for (int i = n - 1; i >= 0; i--){
            if (!have.empty())
                arr[i][j] = have.back(), have.pop_back();
            else arr[i][j] = 0;
        }
    }
}

void execute(char c)
{
    if (c == 'U')
        moveU();
    else if (c == 'D')
        moveD();
    else if (c == 'L')
        moveL();
    else if (c == 'R')
        moveR();
}

char inv(char c)
{
    if (c == 'U') return 'D';
    else if (c == 'D') return 'U';
    else if (c == 'L') return 'R';
    else if (c == 'R') return 'L';
    assert(0);
}

void print()
{
    // for (int i = 0; i < n; i++)
    //     for (int j = 0; j < m; j++)
    //         cerr << arr[i][j] << " \n"[j == m - 1];
    // cerr << '\n';
}

void dfs(int u, string &buf, char ext[505][505], bool reset)
{
    vis[u] = 1;
    buf.push_back(ext[pos[u].F][pos[u].S]);
    if (!vis[p[u]])
        dfs(p[u], buf, ext, reset);
    if (reset)
        vis[u] = 0;
}

vector<int> KMP(string s, string t)
{
    t = " "s + t;
    vector<int> f(t.size(), 0);
    f[0] = -1;
    for (int i = 1, j = -1; i < (int)t.size(); i++)
    {
        while (j >= 0 && t[j + 1] != t[i])
            j = f[j];
        f[i] = ++j;
    }
    vector<int> match;
    for (int i = 0, j = 0; i < s.size(); i++)
    {
        while (j >= 0 && t[j + 1] != s[i])
            j = f[j];
        if (++j + 1 == t.size()) match.emplace_back(i), j = f[j];
    }
    return match;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    for (int i = 2; i <= n * m; i++)
        if (!notp[i])
        {
            prime.emplace_back(i);
            for (int j = i * 2; j <= n * m; j += i)
                notp[j] = 1;
        }

    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++)
        {    
            cin >> s[i][j];
            if (s[i][j] == '.') s[i][j] = 0;
        }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {    
            cin >> f[i][j];
            if (f[i][j] == '.') f[i][j] = 0;
        }
    
    auto check = [&]()
    {
        bool flag = true;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (f[i][j] != arr[i][j])
                    flag = false;
        return flag;
    };
    auto copy = [&]()
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                arr[i][j] = s[i][j];
    };

    if ((copy(), check()) || (copy(), moveD(), check()) || (copy(), moveU(), check()) || (copy(), moveL(), check()) || (copy(), moveR(), check()))
    {
        cout << "yes\n";
        return 0;
    }
    
    for (auto a1 : "UDLR"s)
        for (auto a2 : "UDLR"s)
        {    
            if ("LR"s.find(a1) != string::npos && "LR"s.find(a2) != string::npos)
                continue;
            if ("UD"s.find(a1) != string::npos && "UD"s.find(a2) != string::npos)
                continue;

            auto check_prefix = [&](string ops)
            {
                // cerr << "check " << ops << '\n';
                copy();
                for (auto op : ops)
                    execute(op);
                int k = 0;
                bool bad = 0;
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < m; j++)
                    {    
                        tmp[i][j] = arr[i][j];
                        if (arr[i][j])
                            arr[i][j] = ++k, vis[k] = 0;
                        if ((arr[i][j] > 0) != (f[i][j] > 0))
                            bad = 1;
                    }
                if (bad)
                    return;
                print();
                execute(inv(ops.end()[-2]));
                execute(inv(ops.end()[-1]));
                execute(ops.end()[-2]);
                execute(ops.end()[-1]);
                print();

                for (int i = 0, t = 0; i < n; i++)
                    for (int j = 0; j < m; j++)
                        if (arr[i][j])
                            p[++t] = arr[i][j], pos[t] = pii(i, j);
                map<int, int> cond;

                auto add_cond = [&](int pkmod, int rem)
                {
                    if (cond.find(pkmod) != cond.end() && cond[pkmod] != rem)
                        bad = true;
                    cond[pkmod] = rem;
                };

                for (int i = 1; i <= k; i++)
                    if (!vis[i])
                    {
                        string orig, after;
                        dfs(i, orig, tmp, true);
                        dfs(i, after, f, false);
                        auto v = KMP(orig + orig, after);
                        if (v.size() == 0)
                        {
                            bad = true;
                            break;
                        }
                        int offset = v[0], mod;
                        if (v.size() >= 2)
                            mod = v[1] - v[0];
                        else 
                            mod = orig.size();

                        for (int j = 2; j <= mod; j++)
                            if (mod % j == 0)
                            {
                                int mul = 1;
                                while (mod % j == 0)
                                    mul *= j, mod /= j;
                                add_cond(mul, offset % mul);
                            }
                    }
                
                for (auto pr : prime)
                {
                    ll i = 1, last = -1, r = -1;
                    while (i <= n * m)
                    {
                        if (cond.find(i) != cond.end())
                        {
                            if (r != -1 && cond[i] % last != r)
                                bad = true;
                            r = cond[i], last = i;
                        }
                        i *= pr;
                    }
                }
                if (!bad)
                {
                    cout << "yes\n";
                    exit(0);
                }
            };

            string ops = ""s + a1 + a2;
            
            for (int _ = 0; _ < 4; _++)
                check_prefix(ops), ops += inv(ops.end()[-2]);
        }
    cout << "no\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 7676kb

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: 0ms
memory: 3644kb

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: 0ms
memory: 7752kb

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: 1ms
memory: 7916kb

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: 1ms
memory: 7684kb

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: 1ms
memory: 5740kb

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: 1ms
memory: 5944kb

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: 1ms
memory: 5728kb

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: 0ms
memory: 7748kb

input:

3 3
...
.a.
...

...
.a.
...

output:

yes

result:

ok single line: 'yes'

Test #11:

score: 0
Accepted
time: 92ms
memory: 9164kb

input:

500 500
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...

output:

no

result:

ok single line: 'no'

Test #12:

score: 0
Accepted
time: 145ms
memory: 14256kb

input:

500 500
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...

output:

no

result:

ok single line: 'no'

Test #13:

score: 0
Accepted
time: 80ms
memory: 10860kb

input:

496 495
oanhdonngaokopboqljdalgpfdeqfelhjchogdmrcaqb.ooogggggicgenlbipaprnfbcrapabfjaemrhdelojgbldirmidgihpjfobgopinddhhmacjcqljgajndcgemiepgipqmdgcqndqadkialgjddpkdfhamldedgrejbbgirpmbeqjc.mbipndabllbjbgrlbrhrcaiphrpogicjdcqeqdhdldpefdekqqihifhagjokepbbceqprongafeqmhbripqceodmfaecpgnaenfjjrjbbabaec...

output:

yes

result:

ok single line: 'yes'

Test #14:

score: 0
Accepted
time: 48ms
memory: 9620kb

input:

367 490
ababbaabbbabbabaabbabbbabababbbabaabbbabbababbabbaaaabbbbaaabbbbababaaaaabbaabaabbbabbbbbababaaabbabaabbaabaabbbabbbbabbbabbabbabbabbbababbabbaaabaabaababaaababaabaabbbbbaaaaabbaaaaabbababaababbaabaabaaaababbbbbaabaaababbabbbbaabaabbabbabbbbaaabbaaababbbaaabbbaaabbbbaabbaaabbbabaaaaaaaaaabaa...

output:

yes

result:

ok single line: 'yes'

Test #15:

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

input:

500 500
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

yes

result:

ok single line: 'yes'

Test #16:

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

input:

500 500
tztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztztz...

output:

yes

result:

ok single line: 'yes'

Test #17:

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

input:

2 4
.xxx
..xx

xx..
xx..

output:

no

result:

ok single line: 'no'

Test #18:

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

input:

5 8
........
........
.aaaaa..
........
........

........
........
........
........
..aaaaaa

output:

no

result:

ok single line: 'no'

Test #19:

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

input:

5 8
........
........
.aaaaaa.
........
........

........
........
........
........
...aaaaa

output:

no

result:

ok single line: 'no'

Test #20:

score: 0
Accepted
time: 153ms
memory: 10300kb

input:

500 500
fwizgbybbgxihqejzkgyvdcrgzkfhfktchdilsfgigilfktykliwrykymilrmjjmrlimykyrwilkytkflihifguljdhctkjhgkzfrcdvyfkzfexhxifbbybgziwg...........................................................................................................................................................................

output:

no

result:

ok single line: 'no'

Test #21:

score: 0
Accepted
time: 149ms
memory: 9976kb

input:

500 500
hkmkgolmmlokbyyeohmmvmkhbpgmmkypmbmkmhcqvcbkkkbkbbkkwkkobrrdjkjgelllvclldgcvlddxclxvhvwlglkxsxklglwvhvxlcxddlvcgdllcvlllocaxaarrbokkwkkbbkbkkkbdvzkkmkmbmpykgmgpbhkmvgghoeyybkolgglomkmkh..............................................................................................................

output:

no

result:

ok single line: 'no'

Test #22:

score: 0
Accepted
time: 195ms
memory: 10492kb

input:

500 500
xueftjjjxjyzctkjocmokbkomcojktczyjxjjjtfeuxexumbooocaoljckojectkrketulbzlejoxoloxojelzblutekrktcejokcjloacooobmuxexueftjjjxjyzctkjocmokbkomcojktczyjxjjjtfeuxexumbooocaoljckojectkrketulbzlejhxoloxojelzblutekrktcejokcjloacooobmuxexueftjjjxjyzctkjocmokbkomcojktczyjxjjjtfeuxexumbooocaoljckojectk...

output:

no

result:

ok single line: 'no'

Test #23:

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

input:

1 6
..h...

h.....

output:

yes

result:

ok single line: 'yes'

Test #24:

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

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: 1ms
memory: 5668kb

input:

4 2
.e
..
..
..

..
..
..
e.

output:

yes

result:

ok single line: 'yes'

Test #26:

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

input:

9 10
..........
......f...
..........
..........
....k.uo.k
..........
..........
......k...
..........

......kfok
.........u
.........k
..........
..........
..........
..........
..........
..........

output:

yes

result:

ok single line: 'yes'

Test #27:

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

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: 22ms
memory: 6732kb

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: 0ms
memory: 5684kb

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: 53ms
memory: 8772kb

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: 17ms
memory: 7408kb

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: 2ms
memory: 6464kb

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: 33ms
memory: 8164kb

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: 73ms
memory: 10600kb

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: 107ms
memory: 11580kb

input:

500 500
djebdknlnkkkkkdbnmdhjimlkgkmdahblbch.hnlddcehclbekbafhkfahagmhiieah.kkknklcaielnfnendejgaffiekjkkkidmicnkmdgaikmjcgehebhigcjhbmijndemeljdkechaebdnlkmikkkckdgnhaadmnhmjhkfbjdcdkgkkkkiflndcchhgfkcfelnnmdhhgieachdhfghihieikfchenmiemejbkkkikfddi.dnadmfdegklkbghikfkkkmhdmkgnmiifjkbanhkfhdhcabfdn....

output:

yes

result:

ok single line: 'yes'

Test #36:

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

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: 47ms
memory: 9328kb

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: 1ms
memory: 5636kb

input:

10 1
c
.
.
.
.
.
l
.
c
b

c
l
b
c
.
.
.
.
.
.

output:

no

result:

ok single line: 'no'

Test #39:

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

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: 5660kb

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: 1ms
memory: 3680kb

input:

10 4
....
....
..wn
....
....
....
....
....
....
....

....
....
....
....
....
....
....
....
....
..wn

output:

yes

result:

ok single line: 'yes'

Test #42:

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

input:

3 5
m....
h.k..
g....

...mg
....h
....k

output:

no

result:

ok single line: 'no'

Test #43:

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

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: 65ms
memory: 9632kb

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: 4ms
memory: 5800kb

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: 11ms
memory: 7592kb

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: 3556kb

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: 90ms
memory: 8332kb

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: 26ms
memory: 9452kb

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: 129ms
memory: 10868kb

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: 118ms
memory: 10424kb

input:

500 500
iah.fbgnlhahdbobnbojkgggafbfnianbnalnlmjbaafjgkmml.hangakeamfgjjhacancngnnnceolibdekjfgaljalhba.ncclbn.jhmohcnmleda.moimmkajenjcjkgmkalnaocafmnehaaaccmlaoggdldbkibomhkbf.gmnabdoahlamnfhfdngiofdnbhcdmbhfgbkiblhammhcngjenlolcchaaclmnjanbahbjkhmaheoolednbogcjmhajmljclfihhakbg.dfcobnagnlldbajkoa...

output:

no

result:

ok single line: 'no'

Test #52:

score: 0
Accepted
time: 125ms
memory: 10340kb

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