QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#103131#5066. String-dle Countlonytree#AC ✓400ms46564kbC++143.9kb2023-05-04 15:59:562023-05-04 15:59:59

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-04 15:59:59]
  • 评测
  • 测评结果:AC
  • 用时:400ms
  • 内存:46564kb
  • [2023-05-04 15:59:56]
  • 提交

answer


#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std; const int maxn = 1e4 + 5, maxk = 19, mod = 1e9 + 7; typedef long long ll;

int n, k;

char s[maxk + 1], t[maxk + 1];

int mst[26], atl[26], eql[26], fbd[26];

int num[26];

int F[1 << maxk], G[maxk + 1][1 << maxk];

inline void get(int &x, int y) { if ((x += y) >= mod) x -= mod; }

int main()
{
    scanf("%d%d", &n, &k);
    for (int c = 0; c < 26; c++) eql[c] = -1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%s%s", s, t);
        memset(num, 0, sizeof num);
        for (int j = 0; j < k; j++)
        {
            int c = s[j] - 'A';
            if (t[j] == 'O') num[c]++, mst[c] |= 1 << j;
        }
        for (int j = 0; j < k; j++)
        {
            int c = s[j] - 'A';
            if (t[j] == '-')
            {
                if (num[c] == -1) return 0 * puts("0");
                num[c]++;
                fbd[c] |= 1 << j;
            }
            else if (t[j] == 'x')
            {
                if (num[c] != -1)
                {
                    if (eql[c] != -1 && eql[c] != num[c]) return 0 * puts("0");
                    eql[c] = num[c];
                    num[c] = -1;
                }
                fbd[c] |= 1 << j;
            }
        }
        for (int j = 0; j < 26; j++) atl[j] = max(atl[j], num[j]);
    }
    F[0] = 1;
    for (int c = 0; c < 26; c++)
    {
        int r;
        if (eql[c] != -1)
        {
            if (atl[c] > eql[c]) return 0 * puts("0");
            r = eql[c];
            for (int i = 1; i <= r; i++) memset(G[i], 0, sizeof G[i]);
            memcpy(G[0], F, sizeof F);
            for (int j = 0; j < k; j++)
            {
                if (fbd[c] >> j & 1)
                {
                    if (mst[c] >> j & 1) return 0 * puts("0");
                    else continue;
                }
                else if (mst[c] >> j & 1)
                {
                    memset(G[r], 0, sizeof G[r]);
                    for (int i = r - 1; i >= 0; i--)
                    {
                        for (int S = 0; S < 1 << k; S++) if (!(S >> j & 1)) G[i + 1][S | (1 << j)] = G[i][S];
                        memset(G[i], 0, sizeof G[i]);
                    }
                }
                else
                {
                    for (int i = 0; i < r; i++) for (int S = 0; S < 1 << k; S++) if (!(S >> j & 1))  get(G[i + 1][S | (1 << j)], G[i][S]);
                }
            }
        }
        else
        {
            r = atl[c];
            for (int i = 1; i <= r; i++) memset(G[i], 0, sizeof G[i]);
            memcpy(G[0], F, sizeof F);
            for (int j = 0; j < k; j++)
            {
                if (fbd[c] >> j & 1)
                {
                    if (mst[c] >> j & 1) return 0 * puts("0");
                    else continue;
                }
                else if (mst[c] >> j & 1)
                {
                    for (int S = 0; S < 1 << k; S++) if (!(S >> j & 1)) G[r][S | (1 << j)] = G[r][S], G[r][S] = 0;
                    for (int i = r - 1; i >= 0; i--)
                    {
                        for (int S = 0; S < 1 << k; S++) if (!(S >> j & 1)) get(G[i + 1][S | (1 << j)], G[i][S]);
                        memset(G[i], 0, sizeof G[i]);
                    }
                }
                else
                {
                    for (int i = 0, ti; ti = min(i + 1, r), i <= r; i++) for (int S = 0; S < 1 << k; S++) if (!(S >> j & 1)) get(G[ti][S | (1 << j)], G[i][S]);
                }
            }
        }
        memcpy(F, G[r], sizeof F);
        bool fl = 0;
        for (int S = 0; S < 1 << k; S++) if (F[S]) { fl = 1; break; }
        if (!fl) break;
    }
    return 0 * printf("%d\n", F[(1 << k) - 1]);
}

詳細信息

Test #1:

score: 100
Accepted
time: 7ms
memory: 13752kb

input:

2 5
CRANE
xx--x
NASAL
OOxOO

output:

21

result:

ok 1 number(s): "21"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3476kb

input:

1 5
BBBAA
xxxx-

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

2 5
ABCDE
-xxxx
ABCDE
xxxxx

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

1 3
ABC
---

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 22ms
memory: 11800kb

input:

1 15
AAAAAAAAAAAAAAB
-xxxxxxxxxxxxxx

output:

918547951

result:

ok 1 number(s): "918547951"

Test #6:

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

input:

1 15
AAAAAAAAAAAAAAA
-xxxxxxxxxxxxxx

output:

0

result:

ok 1 number(s): "0"

Test #7:

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

input:

1 1
K
x

output:

25

result:

ok 1 number(s): "25"

Test #8:

score: 0
Accepted
time: 159ms
memory: 11968kb

input:

19 19
ZAZZZAZZZZZZZZZZAAZ
x-xxxxxxxxxxxxxxxxx
ZBZBZZBZZZZBZZZZBZZ
x-xxxxxxxxxxxxxxxxx
CZZCZZCZCZZCZZZCZZZ
-xxxxxxxxxxxxxxxxxx
ZDZZDZDZZZZZZZZZZZZ
x-xxxxxxxxxxxxxxxxx
ZZZZEEZEZZEEZZZZZZZ
xxxx-xxxxxxxxxxxxxx
ZZZZZFZZZZZZZZZZZZF
xxxxx-xxxxxxxxxxxxx
ZZGGZZZZZZZZGGGZZGZ
xx-xxxxxxxxxxxxxxxx
HHHHZHZZZZHHZZ...

output:

182644947

result:

ok 1 number(s): "182644947"

Test #9:

score: 0
Accepted
time: 167ms
memory: 11888kb

input:

19 19
AZZZZZAZZZZZZAZZZZZ
-xxxxxxxxxxxxxxxxxx
ZZZBZZBBZZBBZZBZBZB
xxx-xxxxxxxxxxxxxxx
ZZZZZCCZZZZZZZZZZZZ
xxxxx-xxxxxxxxxxxxx
ZZZDZDZZZZZZDZZZZDZ
xxx-xxxxxxxxxxxxxxx
EZZZZZZZEZZZZZZZZZZ
-xxxxxxxxxxxxxxxxxx
ZZZZZZZZFFZZZZZZZZZ
xxxxxxxx-xxxxxxxxxx
ZZZZZZZZZZZZZGZZZZG
xxxxxxxxxxxxx-xxxxx
ZZHHZZHZZZHZZH...

output:

791604390

result:

ok 1 number(s): "791604390"

Test #10:

score: 0
Accepted
time: 175ms
memory: 11748kb

input:

19 19
ZAZAZZZZAZZZZZZAZZZ
x-xxxxxxxxxxxxxxxxx
ZBZZZBZZBZZZZZZZBZZ
x-xxxxxxxxxxxxxxxxx
ZZZZZZZCZCZZZZZZZZZ
xxxxxxx-xxxxxxxxxxx
ZDDDZZZDZZZZZZZZZZZ
x-xxxxxxxxxxxxxxxxx
ZEZZEEZZZZZEZZEZZZE
x-xxxxxxxxxxxxxxxxx
ZZZFZZZZFZZZZZFZFFZ
xxx-xxxxxxxxxxxxxxx
ZZZGGZZZZZZZZZZZZZG
xxx-xxxxxxxxxxxxxxx
ZHHZZZZZZZZZHZ...

output:

721023482

result:

ok 1 number(s): "721023482"

Test #11:

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

input:

19 19
ZZZAZZZAZZZAZZAAZZA
xxx-xxxxxxxxxxxxxxx
BBZZBZZBZZZBBBZZBZB
-xxxxxxxxxxxxxxxxxx
ZZCZCCZCCCZCCZCCZZC
xx-xxxxxxxxxxxxxxxx
ZDZZDZDDZDZZZDZDDZZ
x-xxxxxxxxxxxxxxxxx
EEZEZEZEZZZZEZEEEZE
-xxxxxxxxxxxxxxxxxx
ZZZFZFFFZFFFFZFFFFZ
xxx-xxxxxxxxxxxxxxx
ZGZGGZGZGZGGGZZGGGZ
x-xxxxxxxxxxxxxxxxx
ZHZZZHZHHZZHZZ...

output:

432987142

result:

ok 1 number(s): "432987142"

Test #12:

score: 0
Accepted
time: 131ms
memory: 11768kb

input:

19 19
ZAAZAZZAAZAZZZZZZAA
x-xxxxxxxxxxxxxxxxx
ZBZBBBZZBZZBZBBBZZB
x-xxxxxxxxxxxxxxxxx
CZCCCZZCCCZZZCCZZCC
-xxxxxxxxxxxxxxxxxx
DZDZDDDDZDDZZZZZZDD
-xxxxxxxxxxxxxxxxxx
ZEEEEEZZEEZEZZZZEZE
x-xxxxxxxxxxxxxxxxx
ZZFFZZZFZFFFZZFFZFF
xx-xxxxxxxxxxxxxxxx
ZZGZZZGZGZZGZZZGZGG
xx-xxxxxxxxxxxxxxxx
HZZZHZHZZZZZHZ...

output:

562846236

result:

ok 1 number(s): "562846236"

Test #13:

score: 0
Accepted
time: 137ms
memory: 11964kb

input:

19 19
AZZZZAZAZZZAZAZZAZZ
-xxxxxxxxxxxxxxxxxx
BZBBZBZZZBBZBZBBZBZ
-xxxxxxxxxxxxxxxxxx
ZCCCCCZCCZCCZZCZZCC
x-xxxxxxxxxxxxxxxxx
DDDDZDDZDZDZDDDZZDZ
-xxxxxxxxxxxxxxxxxx
EZZEZZEZZEEZEEZZEEZ
-xxxxxxxxxxxxxxxxxx
ZZZZFZZFZZZFZZZZFZZ
xxxx-xxxxxxxxxxxxxx
GGZGZGGZGGZGGZZZGGG
-xxxxxxxxxxxxxxxxxx
ZHZZHHHHHZZHHH...

output:

241578701

result:

ok 1 number(s): "241578701"

Test #14:

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

input:

26 19
AAAAAAAAAAAAAAAAAAA
-------------------
BBBBBBBBBBBBBBBBBBB
-------------------
CCCCCCCCCCCCCCCCCCC
-------------------
DDDDDDDDDDDDDDDDDDD
-------------------
EEEEEEEEEEEEEEEEEEE
-------------------
FFFFFFFFFFFFFFFFFFF
-------------------
GGGGGGGGGGGGGGGGGGG
-------------------
HHHHHHHHHHHHHH...

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 325ms
memory: 11728kb

input:

19 19
ZAZZZZZZZZZZZZZZZZZ
x-xxxxxxxxxxxxxxxxx
ZZZZZZZZBZZZZZZZZZZ
xxxxxxxx-xxxxxxxxxx
ZZZZZZZZZZZZZZCZZZZ
xxxxxxxxxxxxxx-xxxx
ZZDZZZZZZZZZZZZZZZZ
xx-xxxxxxxxxxxxxxxx
ZZZZZZZZZZZZZEZZZZZ
xxxxxxxxxxxxx-xxxxx
ZZZZZZZZZZZZZZZFZZZ
xxxxxxxxxxxxxxx-xxx
ZZZZZZZZZZZGZZZZZZZ
xxxxxxxxxxx-xxxxxxx
ZZZZZZZZZZZZZZ...

output:

143269517

result:

ok 1 number(s): "143269517"

Test #16:

score: 0
Accepted
time: 13ms
memory: 9736kb

input:

1 3
PYP
xxx

output:

13824

result:

ok 1 number(s): "13824"

Test #17:

score: 0
Accepted
time: 13ms
memory: 9724kb

input:

3 3
ENP
xxx
PJK
xxx
BZL
xxx

output:

5832

result:

ok 1 number(s): "5832"

Test #18:

score: 0
Accepted
time: 13ms
memory: 9712kb

input:

5 3
LLK
xxx
WUQ
xxx
RDR
xxx
EUZ
xxx
FBU
xxx

output:

3375

result:

ok 1 number(s): "3375"

Test #19:

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

input:

10 3
PKX
xxx
FBB
xxx
JSZ
xxx
RGB
xxx
BOS
x-x
OPG
Oxx
SHW
xxx
RDM
xxx
LHO
xx-
NBP
xxx

output:

81

result:

ok 1 number(s): "81"

Test #20:

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

input:

15 3
DCJ
xxx
NCW
xxx
WDE
xxx
MAO
xOO
JXC
xxx
OBO
xxO
ALB
-xx
JWZ
xxx
QXK
xxx
FZW
xxx
VAJ
xOx
VHL
xxx
AZG
-x-
BWQ
xxx
GWB
Oxx

output:

1

result:

ok 1 number(s): "1"

Test #21:

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

input:

20 3
FPR
xxx
FHF
xxx
WBH
xxx
XGA
xx-
QAC
x-x
JYS
xxx
ARR
Oxx
AAF
Oxx
LDY
xxx
ESD
xxx
QMB
xxx
EMS
xxx
UFT
xx-
JCK
xxO
YBH
xxx
KEN
-xx
FVL
xxx
PJP
xxx
DRB
xxx
UDL
xxx

output:

1

result:

ok 1 number(s): "1"

Test #22:

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

input:

10000 3
XIX
xxx
RRY
xxx
RJB
xxx
XUT
x-x
BQB
xxx
RDP
xxx
EEX
xxx
DYJ
xxx
NHI
-xx
VMD
xxx
IVU
xxO
VBR
xxx
CJE
Oxx
BCF
x-x
WSS
xxx
ARP
xxx
HYR
xxx
YTO
xxx
NLJ
-xx
NMU
-xO
GUY
x-x
KAC
xx-
UYQ
-xx
OBU
xxO
ANA
xOx
HCK
x-x
GOX
xxx
ZNU
xOO
LSH
xxx
COM
Oxx
OAM
xxx
HNF
xOx
VOX
xxx
CZM
Oxx
KXM
xxx
MAN
xx-
RUG
...

output:

1

result:

ok 1 number(s): "1"

Test #23:

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

input:

1 5
VYQWB
x-xxx

output:

835275

result:

ok 1 number(s): "835275"

Test #24:

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

input:

3 5
UFJVJ
xxxxx
XAHKG
x-Oxx
ITJDN
--xxx

output:

150

result:

ok 1 number(s): "150"

Test #25:

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

input:

5 5
QJUFA
-xOxx
BDVNF
xxxxx
TABZV
xxxxx
KSFCQ
xxxx-
PFZOQ
xxxx-

output:

2783

result:

ok 1 number(s): "2783"

Test #26:

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

input:

10 5
DOBUN
xxxxx
POMVH
xxOxx
PNCJB
xxxxx
GCWID
xxx-x
XPPHR
xxxxx
ZMXCW
xOxxx
CBSKY
xxxxO
GTHGA
xxxx-
IIHSL
Oxxxx
TBRSZ
xxxxx

output:

1

result:

ok 1 number(s): "1"

Test #27:

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

input:

15 5
GZULJ
xxx-x
AXDPU
xxx-x
BWJIU
xxxxx
NKIND
xxxxx
YXMQF
xxxxx
RGAUS
xxxxx
VXZEJ
xxx-x
ITBNY
x-xxx
HJXRL
xxxx-
IHDML
xxxx-
GHHPP
xxxxO
PFZNR
-xxxx
MOMTI
x-x-x
UNJHO
xxxx-
EPIPE
O-xxx

output:

1

result:

ok 1 number(s): "1"

Test #28:

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

input:

20 5
WSHYB
-xx-x
CAVYO
Oxx-x
ADNZR
xxxxx
DRNVU
xxxx-
YEHWB
-xx-x
MVHPW
xxxx-
NJALD
xxx-x
SGNTS
xxxxx
DKHHP
xxxxx
GYDKZ
x-xxx
KSRVD
xxxxx
DYGKH
x-xxx
DNSME
xxxxx
DDUUJ
xxxOx
EPQGV
xxxxx
TFXTG
xxxxx
SGXNC
xxxx-
JOVUX
xxxOx
EHBYU
xxx--
LCZYD
--x-x

output:

3

result:

ok 1 number(s): "3"

Test #29:

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

input:

10000 5
UERNA
xxxx-
KIWJZ
xxxxx
LPMLP
xxxxx
WVPCT
x-xx-
SLFMH
xxxxx
HTZGM
xOxxx
GFTSP
xx-xx
PRBTN
xxx-x
XCOWY
xxxxx
EAHPE
x-xxx
XWFLX
xxxxx
ZHSVX
xxx-x
YQHKK
x-xxx
QWKNH
-xxxx
LBKBU
xxxxx
TCMXG
-xxxx
PQUMQ
x-xxx
JFWSJ
xxxxx
JSQFA
xx-x-
OXKVR
xxx-x
OWMXL
xxxxx
WJETS
xxx-x
BPNFO
xxxxx
BFLCW
xxxxx
EWAQ...

output:

1

result:

ok 1 number(s): "1"

Test #30:

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

input:

1 10
UZWZMLRBON
-xxxx-x--x

output:

108066093

result:

ok 1 number(s): "108066093"

Test #31:

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

input:

3 10
CYGFEKBVZY
xxx-xxxxxx
KNRFGBVTVK
x-x-xxx-xx
RRSEPXGYLJ
xxxx--xxxx

output:

322428370

result:

ok 1 number(s): "322428370"

Test #32:

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

input:

5 10
VSVMKIMLTX
OxxxOxxx-x
QKDDMDRUCB
x-xxxx-xxx
UNQAFDUZQX
xxxxxxx-xx
VUUSNBQTFE
Oxxxxxx-x-
NKAXCIVSFD
x-xxxx-xxx

output:

7078784

result:

ok 1 number(s): "7078784"

Test #33:

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

input:

10 10
ZNASODMTHF
xxxx-xxO-x
AGKLZJSLIC
xx-xxxxx-x
WJVQUIBCPS
-xx-x--xxx
KHVLHJGWLM
-xxxOxx-xx
UOJUVRJXKT
xOxxxxx---
GXTGEQBJPZ
x--xx--xxx
YQZQWBCTYH
x-xx-OxOx-
FCPCTHSSUK
xxxx--xxx-
WUQKPNYQWL
xx--xxxxOx
JREXWEWTJA
xxxO-xxOxx

output:

15

result:

ok 1 number(s): "15"

Test #34:

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

input:

15 10
BSRHUHFKDB
xx---xxxxx
IYWQJKDFBK
xxxx-xxxxx
EEDAEFQMMQ
xxx-xxx-xx
OQBUXEEWXL
xxx--xxxxx
BHPKFDWCPR
x--xxxx-x-
WRWYCQTWDF
x-xx-xxxxx
FBOTDYYMGO
xxxxxxx--x
SGLWOYFWZY
x-xxxxxxxx
BKXJGXUTDI
xxxO-O-xxx
WKFDXQRCEZ
xxxx-x--xx
WZQYEIXVGV
xxxxxx-x-x
VYFIAADRIB
xxxx-xx-xx
CLZGWKNRIH
-xx-xxx-x-
HGRDECGM...

output:

833

result:

ok 1 number(s): "833"

Test #35:

score: 0
Accepted
time: 13ms
memory: 13940kb

input:

20 10
FCCKSZOJLC
xxx---xx-x
GGEDVVPNOV
xxOxxxxxxx
SGGDAIAHIP
-xxx-xxxxx
GGVAULXPGP
xxx--Oxxxx
DLLQSWLEVI
x-x--xO-xx
DUWRFTNQQA
x-xxxxx-x-
MHTFMAYJDN
xxxxx-xxxx
FUYVYGXIUL
x-xxxxxx--
NJSBZWRJKT
xx-x-xxxOx
DMSYQXGEXZ
xx-xOxx-xO
OEUFRLYPSE
x--xxOxx-x
BFNSAKQXSL
xxx----xx-
XWKTQTTAVG
xx-xOxxOxx
TUQXRAMR...

output:

1

result:

ok 1 number(s): "1"

Test #36:

score: 0
Accepted
time: 12ms
memory: 13984kb

input:

10000 10
BGRKIVRKRM
x-xx-xxxxx
AXLWMNNVMG
x-xxxxxxx-
SGMZGJEHXG
--xxxxxx-x
LBBGPZSSMA
xxx-xx-xxx
JLJIMZDICO
xxx-xxxx--
CMHSOVCTHE
-xxO-xx-xx
HGIOECKNRW
x---xOxxxx
XYLTHEQOYJ
-Ox-xxxO-x
XDJTYRPWUU
-xx-Oxxxxx
AEZWRFDCVC
xxxxxxx-xx
SVPTXBOTUL
-xx--x-xxx
RBSTIWRDIM
xx---xxxxx
ILHDJAVREH
-xxxxxxxxx
EZNBI...

output:

1

result:

ok 1 number(s): "1"

Test #37:

score: 0
Accepted
time: 15ms
memory: 11704kb

input:

1 15
QVUWVUTBXUITDRS
-x--xx--xxxx-xx

output:

577051591

result:

ok 1 number(s): "577051591"

Test #38:

score: 0
Accepted
time: 13ms
memory: 13780kb

input:

3 15
PGKQCHEFVTGTEPE
xx-Ox--xx-x-xxx
ZRNMLMDFULGZUMO
x-x-xxxx-xxxxxx
HZVTASECXFSDFSH
-xx--x-xxxxxxxx

output:

250741371

result:

ok 1 number(s): "250741371"

Test #39:

score: 0
Accepted
time: 17ms
memory: 13796kb

input:

5 15
KQBFFVASLNITBAQ
xx--x--x-xxxx-x
CVMHXVRGIYTZDUT
O-xxxx-xxxx---x
MZVFQMRTLGAVJKM
x---xx-x-x-xxxx
FFTQJAPDYAJYFBF
-xxxx-x-x-xxx-x
CBWRGNWIGOHKBPB
O-x-xxxxx-xxxxx

output:

297257451

result:

ok 1 number(s): "297257451"

Test #40:

score: 0
Accepted
time: 17ms
memory: 13852kb

input:

10 15
JZNPISWDTIWUNNR
---xxxxx-xxxxxx
NNRYEPCJZLIIERN
-xxx-x---Oxxxxx
ZXULUHHYMEJJGHC
--x-xxxxx--x-x-
VJNBWOGXJJEYKJZ
x---x-OOxx-x-x-
JYXVOMPPBNHJAYI
-x-x-xxx--xx-xx
KDSITFHFUSDZXGQ
-xxxOxxxxxx----
SIXKCUYHBSITUYC
xx---xxx-xxOxxx
PSTIIRYIMCYOHSB
xx-xxxxxx-x-xx-
JDXKVANYLRBMAHU
-x--x--x-x-xxxx
YOPTVR...

output:

7938

result:

ok 1 number(s): "7938"

Test #41:

score: 0
Accepted
time: 16ms
memory: 13824kb

input:

15 15
VSVTJJPPGOYELZA
-xx--xxx---x--x
JAZIWUIBWRMUSWZ
-x----x-xxxxxxx
QRUBSAWHQSNALQI
xx--xx-xxxxx-x-
UCQXYHYOTPPJDHG
-xx--xO--xx-xx-
FVUZVRTKVFMWEED
---Oxx-xxxx-xxx
WBVIGOVHXTPTGMZ
------xx--xxxx-
ZDXFUOHLXIYNTRJ
-x----x-x--x-xO
GXCRJBOHDTPGREI
--xx-O-xx-xxxx-
ZDRUNDNIDWKXSDA
-xx-xxx-x-x-xxx
LXZYXU...

output:

3560

result:

ok 1 number(s): "3560"

Test #42:

score: 0
Accepted
time: 17ms
memory: 13780kb

input:

20 15
FAUPGDEXPEAJGUT
-O-xx--xx--xxx-
XGCLSBXVAMAPIGA
xxx-xxxx-x-xxxx
BKRGJCWZAIGMJAR
x-xxxx-x-xxxx-x
FGQUTOGJGOWPAXP
-xx--xxxxx-x-xx
HUGXVIDUQTYHVQR
--xxxx-xx--xxxx
ARMAVNBXQSFULHS
Oxx-x-xxxx----x
ZOLGUOYLIRFOOYW
xx-x-x-xxx-xx--
MMSBNDXGWYORCRO
xxxx--xx-Oxxxxx
FMZOULBTOJMZTMN
-xxx--x-xxxxxx-
NPEKXE...

output:

4

result:

ok 1 number(s): "4"

Test #43:

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

input:

10000 15
ADZIQJSZEVTTOKW
xxxxxx-x--xx-xx
BKIHMBBOHHJBKMZ
-xxx-xx-xxxxxxx
TCMMTZSPARRDNZF
xx-xxx-xxxxx-xx
NXBRJXDQYSJOIHH
-x-xxxxxxOx-xxx
JGOKDILOAYDHBQP
xO-xxx-xxxxx-xx
LUDWCEYLABQNEBY
--xxx-xxx-x--xx
KPBWFKHBWXRISXA
xx-xxxxxxxxxOxx
CWXCNPCMMPVKVFZ
xxxx-xx-xx-xxxx
MHNURAZEPAXGUIJ
-x--xxx-xxx-xxx
QUQ...

output:

1

result:

ok 1 number(s): "1"

Test #44:

score: 0
Accepted
time: 165ms
memory: 13748kb

input:

1 19
IEIMSENQDSTNAPVSNAN
x-xx-x-xxxx-xOxxxxx

output:

337065816

result:

ok 1 number(s): "337065816"

Test #45:

score: 0
Accepted
time: 201ms
memory: 11764kb

input:

3 19
HRXRMZDQERFUBORITOO
-x-xxx---O---xx--xx
PZZRQQGGARUXFOTYABP
xxxxOxxx-O-O-x--x-x
DIGUVSFNJVSLCTXIDCB
--xOx--x-xx-x--xxx-

output:

417344546

result:

ok 1 number(s): "417344546"

Test #46:

score: 0
Accepted
time: 182ms
memory: 13752kb

input:

5 19
KFXDGBBMEXVXJIBGYGM
-OxOxxOxxx-xx-xx-xx
CNMRHGAXWNFNRARAEFD
x-xx-x-x-x-xxxxxx--
HOLWTUDCHGSXCAPMMMX
-xx----xxx-xx--xxxx
HMRTNFVGNLBHJEGEPOC
-xx-x--xOx-xxxxx-xx
LVJQXEYHFDBRKMVKHNY
x-xxxx-----x-x-xx-x

output:

121474019

result:

ok 1 number(s): "121474019"

Test #47:

score: 0
Accepted
time: 131ms
memory: 13856kb

input:

10 19
SCTWOSTURDAMARVNENO
x-x-xxx-O-xxx--x-xx
TMBEMRYFMULRYJOFCAY
xxx-x--xx---x-xx-xx
MLBWXOPOETUFLDTNPCA
x-x--x-x-x-xxOxxx-x
XVWYJGVAZHSOHLAXFUW
-----xxxxxxxx-xxx-O
PCAQXZKNYVVZJYTYWGU
--xx-x-x--xx-xxxOx-
TWZGXNVEGFLQQWBLXJI
x-xx-x--xx-xx-xxx--
BKWYQSWEGXGOIDKUNXJ
x---xx--x-xx-Ox-xx-
KNQVTEZOJSYMXW...

output:

404122654

result:

ok 1 number(s): "404122654"

Test #48:

score: 0
Accepted
time: 107ms
memory: 15804kb

input:

15 19
OTMWXBRFLAFQOVFCXXY
x--Oxxxxx-x-x-x-xxx
QGFMSWKLJUXLFXYRIWD
Oxx----x--xxxxxxxxO
JGZMRJHRAUHTRHAFSNW
-xx-xO-x--x-xxxx-x-
UOVFVYYRQYFOMGMVMYN
-x-xxxxx-xxx-x-xOxx
DUCXYILKABZYKTLKMFY
---xxxxO-xxxx-xxOxx
OUUJPCQJPKIXUWTCOBS
x-x-----x-xxx--xxx-
QVPYBYSHXSXSVFYVKHX
O--xxx--xxxxxxxx-xx
MTAUHSPTUQYVHX...

output:

51

result:

ok 1 number(s): "51"

Test #49:

score: 0
Accepted
time: 75ms
memory: 15880kb

input:

20 19
XNTIKSCKCNYDTCFXDMX
--xxx-xxxx-xxx--xxx
YBXHLGTAGNGBHGYXQUF
---O-xxxx-xx-x---x-
PIQTQJHTZFCCQNYDETY
-x-xxx-x--xxx--xxx-
XITBMLDXWYUBHMQHHQY
-xx-x-x---xx-x--xx-
YASMJTIYZTGJXUPKZBE
-x-xxxx--xxx-x-xx-x
POQEXPWYFUPHEUHLRQH
---x-x---xx-xx--xxx
WXRZOLRPHNRFXIDZXNT
--xx--x---xO-xxOxxx
DFVETBZWUJSMLX...

output:

40644

result:

ok 1 number(s): "40644"

Test #50:

score: 0
Accepted
time: 35ms
memory: 17844kb

input:

10000 19
ZTLLZAQQFLFITIAWEMY
-x---x-x-xxxxxxxx--
BWKXGMFNCMMQMBOPLTK
-x-xx----xx-x-xx-xO
PLWAMBWCNCFCUIFKSKA
x-xx--x--x-xxxx-x-x
FEKJAUYVKDNDKSAOUEE
-x-xxx-x-x-x-xxxxxx
XPYSGAXIPVSKNOSKJWX
xx-xxxxxxxx--xx-xxx
VNPIVLMLCVYSJAXRUFA
x-xxx----x-xxxxxx-x
JEYYBUSAFHSXDSVVUMY
xx-x-xxx--xxxxxxx-x
DQWXXZYVLGU...

output:

1

result:

ok 1 number(s): "1"

Test #51:

score: 0
Accepted
time: 400ms
memory: 46564kb

input:

2 19
ZZZZZZZZZZZZZZZZZZA
OOOOOOOOOOOOOOOOOOx
YAAAAAAAAAAAAAAAAAA
-xxxxxxxxxxxxxxxxxx

output:

1

result:

ok 1 number(s): "1"

Test #52:

score: 0
Accepted
time: 166ms
memory: 13816kb

input:

1 19
QZAMSYSPMFXBGNAVJGW
x--xxOxxxxxxx--xxx-

output:

7597869

result:

ok 1 number(s): "7597869"

Test #53:

score: 0
Accepted
time: 168ms
memory: 11952kb

input:

1 19
KQQPBXAMBCMPBEKIOAF
x-xxx--xxxxxxxx-xx-

output:

961982430

result:

ok 1 number(s): "961982430"

Test #54:

score: 0
Accepted
time: 192ms
memory: 14004kb

input:

1 19
JLFJWSINIGWRRRZJWMK
-x--xxx-xxOOxx-xxx-

output:

16277388

result:

ok 1 number(s): "16277388"

Test #55:

score: 0
Accepted
time: 184ms
memory: 13816kb

input:

1 19
ABDQNNUOBCKXZARWEGT
-xx-xxxxxxOOx-x-xx-

output:

381502553

result:

ok 1 number(s): "381502553"

Test #56:

score: 0
Accepted
time: 200ms
memory: 11788kb

input:

1 19
VKTXJIPMMHYHUVFJMVC
---xx--xxx-xxx-xxxx

output:

845767424

result:

ok 1 number(s): "845767424"

Test #57:

score: 0
Accepted
time: 142ms
memory: 14012kb

input:

19 19
AZZZZZAZZZZZZAZZZZZ
-xxxxxxxxxxxxxxxxxx
ZZZBZZBBZZBBZZBZBZB
xxx-xxxxxxxxxxxxxxx
ZZZZZCCZZZZZZZZZZZZ
xxxxx-xxxxxxxxxxxxx
ZZZDZDZZZZZZDZZZZDZ
xxx-xxxxxxxxxxxxxxx
EZZZZZZZEZZZZZZZZZZ
-xxxxxxxxxxxxxxxxxx
ZZZZZZZZFFZZZZZZZZZ
xxxxxxxx-xxxxxxxxxx
ZZZZZZZZZZZZZGZZZZG
xxxxxxxxxxxxx-xxxxx
ZZHHZZHZZZHZZH...

output:

0

result:

ok 1 number(s): "0"

Test #58:

score: 0
Accepted
time: 191ms
memory: 13752kb

input:

18 19
AZZZZZAZZZZZZAZZZZZ
-xxxxxxxxxxxxxxxxxx
ZZZBZZBBZZBBZZBZBZB
xxx-xxxxxxxxxxxxxxx
ZZZZZCCZZZZZZZZZZZZ
xxxxx-xxxxxxxxxxxxx
ZZZDZDZZZZZZDZZZZDZ
xxx-xxxxxxxxxxxxxxx
EZZZZZZZEZZZZZZZZZZ
-xxxxxxxxxxxxxxxxxx
ZZZZZZZZFFZZZZZZZZZ
xxxxxxxx-xxxxxxxxxx
ZZZZZZZZZZZZZGZZZZG
xxxxxxxxxxxxx-xxxxx
ZZHHZZHZZZHZZH...

output:

802932781

result:

ok 1 number(s): "802932781"

Test #59:

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

input:

2 2
AA
Ox
BB
Ox

output:

0

result:

ok 1 number(s): "0"

Test #60:

score: 0
Accepted
time: 2ms
memory: 11704kb

input:

3 2
AA
-x
BB
-x
CC
-x

output:

0

result:

ok 1 number(s): "0"

Test #61:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #62:

score: 0
Accepted
time: 2ms
memory: 5476kb

input:

2 1
A
O
A
x

output:

0

result:

ok 1 number(s): "0"

Test #63:

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

input:

2 1
A
O
A
-

output:

0

result:

ok 1 number(s): "0"

Test #64:

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

input:

2 1
A
x
A
-

output:

0

result:

ok 1 number(s): "0"

Test #65:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #66:

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

input:

1 1
A
-

output:

0

result:

ok 1 number(s): "0"

Test #67:

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

input:

1 3
AAA
-xO

output:

0

result:

ok 1 number(s): "0"

Test #68:

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

input:

1 3
AAA
-Ox

output:

0

result:

ok 1 number(s): "0"

Test #69:

score: 0
Accepted
time: 2ms
memory: 14016kb

input:

1 3
AAA
O-x

output:

0

result:

ok 1 number(s): "0"

Test #70:

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

input:

1 3
AAA
Ox-

output:

0

result:

ok 1 number(s): "0"

Test #71:

score: 0
Accepted
time: 2ms
memory: 3624kb

input:

1 3
AAA
x-O

output:

0

result:

ok 1 number(s): "0"

Test #72:

score: 0
Accepted
time: 2ms
memory: 3324kb

input:

1 3
AAA
xO-

output:

0

result:

ok 1 number(s): "0"

Test #73:

score: 0
Accepted
time: 2ms
memory: 3480kb

input:

2 9
AAAZZZZZZ
-xxxxxxxx
AAAZZZZZZ
--xxxxxxx

output:

0

result:

ok 1 number(s): "0"

Test #74:

score: 0
Accepted
time: 2ms
memory: 3328kb

input:

2 9
AAAAAAZZZ
-xxxxxxxx
AAAAAAZZZ
xxxxOOxxx

output:

0

result:

ok 1 number(s): "0"