QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73720#3528. Cockroach RacingsinbadAC ✓245ms18924kbC++7.9kb2023-01-27 19:09:122023-01-27 19:09:13

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-27 19:09:13]
  • 评测
  • 测评结果:AC
  • 用时:245ms
  • 内存:18924kb
  • [2023-01-27 19:09:12]
  • 提交

answer

// #define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
  return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}

using int64 = long long;
using int128 = __int128_t;
using ii = pair<int, int>;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
mt19937_64 mrand(random_device{}());
int64 rnd(int64 x) { return mrand() % x; }
constexpr inline int lg2(int64 x) { return x == 0 ? -1 : sizeof(int64) * 8 - 1 - __builtin_clzll(x); }
constexpr inline int p2ceil(int64 x) { return 1 << (lg2(x - 1) + 1); }
template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
inline void add_mod(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
inline void sub_mod(int& x, int y) { x += MOD - y; if (x >= MOD) x -= MOD; }
inline int mod(int x) { return x >= MOD ? x - MOD : x; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

template <int MOD_> struct modnum {
  static constexpr int MOD = MOD_;
  static_assert(MOD_ > 0, "MOD must be positive");

 private:
  int v;
  static int minv(int a, int m) {
    a %= m; assert(a);
    return a == 1 ? 1 : int(m - int64(minv(m, a)) * int64(m) / a);
  }

 public:
  modnum() : v(0) {}
  modnum(int64 v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  explicit operator int() const { return v; }
  friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  friend std::istream& operator >> (std::istream& in, modnum& n) { int64 v_; in >> v_; n = modnum(v_); return in; }
  friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

  modnum inv() const { modnum res; res.v = minv(v, MOD); return res; }
  friend modnum inv(const modnum& m) { return m.inv(); }
  modnum neg() const { modnum res; res.v = v ? MOD-v : 0; return res; }
  friend modnum neg(const modnum& m) { return m.neg(); }

  modnum operator- () const { return neg(); }
  modnum operator+ () const { return modnum(*this); }

  modnum& operator ++ () { ++v; if (v == MOD) v = 0; return *this; }
  modnum& operator -- () { if (v == 0) v = MOD; --v; return *this; }
  modnum& operator += (const modnum& o) { v += o.v; if (v >= MOD) v -= MOD; return *this; }
  modnum& operator -= (const modnum& o) { v -= o.v; if (v < 0) v += MOD; return *this; }
  modnum& operator *= (const modnum& o) { v = int(int64(v) * int64(o.v) % MOD); return *this; }
  modnum& operator /= (const modnum& o) { return *this *= o.inv(); }

  friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
  friend modnum power(modnum a, int64 n) {
    modnum ret = 1;
    for (; n; n >>= 1) {
      if (n & 1) ret *= a;
      a *= a;
    }
    return ret;
  }
};

using mint = modnum<MOD>;

int main() {
  int n, m;
  cin >> n >> m;
  vector<string> s(n);
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
    reverse(s[i].begin(), s[i].end());
  }
  trace(s);
  auto col = vect<int>(0, m, n + 1, 10);
  for (int pos = 0; pos < m; ++pos) {
    for (int i = 0; i < n; ++i) {
      col[pos][i + 1] = col[pos][i];
      if (s[i][pos] == '?') {
        for (int k = 0; k < 10; ++k) col[pos][i + 1][k]++;
      } else {
        int x = s[i][pos] - '0';
        col[pos][i + 1][x]++;
      }
    }
  }

  vector<mint> p10(m + 1);
  for (int i = 0; i <= m; ++i) p10[i] = i == 0 ? 1 : p10[i - 1] * 10;

  auto dp = vect<array<mint, 2>>({0, 0}, n + 1, n, m, 11); // [sum, cnt]
  for (int i = n - 1; i >= 0; --i) {
    for (int j = i; j < n; ++j) {
      for (int pos = 0; pos < m; ++pos) {
        for (int x = 9; x >= 0; --x) {
          for (int len = 0; len <= j - i + 1; ++len) {
            if (col[pos][i + len][x] - col[pos][i][x] != len) continue;
            trace("!!!!", i, j, pos, x, len);
            auto t1 = len == 0
              ? array<mint, 2>{0, 1}
              : (pos > 0 ? dp[i][i + len - 1][pos - 1][0]
                 : (len > 1 ? array<mint, 2>{0, 0} : array<mint, 2>{0, 1}));
            auto t2 = len == j - i + 1
              ? array<mint, 2>{0, 1}
              : (i + len < n ? dp[i + len][j][pos][x + 1] : array<mint, 2>{0, 1});
            trace(i, j, pos, x, len, t1, t2);
            mint sum = (x * p10[pos] * len * t1[1] + t1[0]) * t2[1] + t2[0] * t1[1];
            mint cnt = t2[1] * t1[1];
            trace(sum, cnt);
            dp[i][j][pos][x][0] += sum;
            dp[i][j][pos][x][1] += cnt;
            trace(i, j, pos, x, len, "done", dp[i][j][pos][x]);
          }
        }
      }
    }
  }
  cout << dp[0][n - 1][m - 1][0][0] << '\n';

  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3388kb

input:

2 2
??
??

output:

490050

result:

ok 1 number(s): "490050"

Test #2:

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

input:

2 3
4??
??2

output:

6403775

result:

ok 1 number(s): "6403775"

Test #3:

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

input:

4 1
0
?
4
8

output:

42

result:

ok 1 number(s): "42"

Test #4:

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

input:

9 9
??08???90
??767??7?
?7????297
6?7?06257
?002?3???
8?4250???
9????0270
933??10??
977?4747?

output:

780526017

result:

ok 1 number(s): "780526017"

Test #5:

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

input:

19 19
??3?7??007?845??2??
0?7?4?8143?20?2??5?
??7???1??30???53?2?
?????9?2616629????6
1????33?641????????
??6605?16????492?42
307??0?7343?836??2?
?41169?140???05??3?
3??94????0?33??769?
?9219??5??3??9?18?0
5??82010??48?9??02?
6?087?05???07?0?722
?0?34?86?29?96?4?9?
6???22?2????1??20?5
67??2?9?8?????...

output:

658914611

result:

ok 1 number(s): "658914611"

Test #6:

score: 0
Accepted
time: 46ms
memory: 17964kb

input:

49 49
0?5?3?6?5????1??7?9???9??1???7883808?5?8??5???63?
?49????4?50??844?30?4??5???04?08???2?03?1?2??????
?????42??0?444?01???2?41?5?2???161528?36??85?????
?7?7?????65??????5?9?2??8??6????4?81441?0??555?0?
?25?16?????2???70?259???5????3?5?1219???09?953??4
125?53880???6893??97705996??20????08?????3??...

output:

794517533

result:

ok 1 number(s): "794517533"

Test #7:

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

input:

10 10
0?????????
??????????
??????2??5
??????????
3????5?4??
??6???????
????2?????
???62?????
??6??????1
???????9??

output:

373003917

result:

ok 1 number(s): "373003917"

Test #8:

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

input:

10 10
???????720
??3??2????
??05????66
?6????????
49????????
6?0?4?9???
??8???87??
???2??????
77????????
?????6????

output:

295277581

result:

ok 1 number(s): "295277581"

Test #9:

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

input:

10 10
???32??11?
????2??8??
12??7???8?
2???0??7??
?????0??8?
3??0?0?65?
???6?4?866
5605??3?81
6?6?35????
??2?????1?

output:

771798451

result:

ok 1 number(s): "771798451"

Test #10:

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

input:

10 10
0?6143?68?
2404??6847
36?792108?
4??02??708
411842??8?
?6?5062064
54613?7?96
752585840?
7693?6??89
??0982??83

output:

894510331

result:

ok 1 number(s): "894510331"

Test #11:

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

input:

10 10
035411442?
?41?317918
2528?53977
393?321??1
456515667?
515?229158
?6?7637035
59??270?57
794??36593
9?85474573

output:

438146771

result:

ok 1 number(s): "438146771"

Test #12:

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

input:

10 20
1????03?????????????
?0???2?????2????????
???49??????4????????
???6???????2??8?6???
5??????????????????8
??????3????2????????
???????????????7????
??????5??9??????????
??1???????????1?3??4
??????3??????3?677??

output:

84063386

result:

ok 1 number(s): "84063386"

Test #13:

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

input:

10 20
0??????5???70???2??6
0????9??6???????????
?0???9?4???8???1?15?
38???9?????9??2?8???
????81??0?9?1??1????
?????9??????????0???
?????1??982??32????4
7???3?4??????8????3?
?7??0?????????9?????
??9????9?7?9????????

output:

560480313

result:

ok 1 number(s): "560480313"

Test #14:

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

input:

10 20
11??476366?5?????038
1???0?9???1?1?4??7??
?98??3?5?4?295571???
3?155?8?????163?2???
??9484???97?254???6?
?462?5???481??0???31
4??11?0?2???6???9???
52?3???198???????2??
?5?5??928?????3??2??
?4?2??1364????81800?

output:

677516333

result:

ok 1 number(s): "677516333"

Test #15:

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

input:

10 20
108???8594118?88??72
1?4??0?49919?4??8553
?37626306?4??05?5?73
6840383??502?5?63??7
?957911?911699?1?858
?990016971165787?582
721202756140622?49?0
80?0??48????2?501451
9683105?22?615479?0?
96?62099900?3??76300

output:

748614195

result:

ok 1 number(s): "748614195"

Test #16:

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

input:

10 20
0153571811059179671?
108455749027?3920418
?1?43032879107395723
34650?889837215122?4
43?6587865?8?1063850
8117?154031662462430
8418294265?25??33102
898756?4670623028928
905599266?16?0855?31
?66832962163?503242?

output:

943616887

result:

ok 1 number(s): "943616887"

Test #17:

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

input:

10 50
??????5?6??40??????????????9????2?????????????????
??????0???????7????8??????????????7??????2??????3?
????6????0???????????????????????3????????????????
????2????5?????1??5?????????4?05?????????5?9??????
??????9?????5?????????????????????9????????1?3????
??????????????????????8????????????????...

output:

302976629

result:

ok 1 number(s): "302976629"

Test #18:

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

input:

10 50
?4??0???????9?2?2???????0???3??????7?4??2??75???4?
???????7?6???8?4????7????0???????8?9?86?????1??8?2
?????0?69??3?90?597???1?12???6?62?8??????????27???
????????3???????380?9??????3?????8??7?????0????71?
?5??7?3??3??????????9?3??????00?3?9???4??????8??69
???1?2??????91???4???8???5????4???4??9?...

output:

301976692

result:

ok 1 number(s): "301976692"

Test #19:

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

input:

10 50
0??????2??2???51??6?12484801??6??7????????1944???4
?38?5?5?6??????71832???1?????40??7??9???5?7?82??81
1??4?05?0?8?174??76??5?956?135???40?4?428?1?2??23?
4??4??774?83?7?255??4??88?09766603??38?6??739?6015
630?7??4?0????32?5??0????778?3???????????0???6379?
739709617?999?773?3418301?79?76?587?309...

output:

509626305

result:

ok 1 number(s): "509626305"

Test #20:

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

input:

10 50
0487??10817??1?16?71?54184557?9876900672102?895??3
4?81?3?028?98?42?26206?754?617?59?657???7212769891
5927?48????40404887634???6?51?47460?5?2???835?3?47
6?38894316?6738?644??21????966259183263?309?76?47?
64?52113283940?7?58064?6313573013?7?6151?9592???27
8349444???6759347?7523?6?8???5777?6391?...

output:

827241925

result:

ok 1 number(s): "827241925"

Test #21:

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

input:

10 50
?4?79633?643976?63250753375396461365544512?78?35?4
14??221689365403375417594?231044?762893??3?267?979
?51?491386057?509?906?1?28428275985810035?14?19845
2?040?163678410917662928842186149125811??218971906
355353125?6209649??6796449?2878?266152774911284760
3714438373?718562?4510708?9168593444832...

output:

664103560

result:

ok 1 number(s): "664103560"

Test #22:

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

input:

20 10
??????????
????????57
?????4??6?
??2??8??8?
??????????
????6?????
???8??????
??????????
4????7??9?
???1???1??
4?????????
??????????
??????????
?3????????
??1??????3
??????6?2?
??????????
??????????
?5????????
??????5??4

output:

384126155

result:

ok 1 number(s): "384126155"

Test #23:

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

input:

20 10
??????2???
??1????2??
?1??2?0???
??????????
????????8?
?98092??2?
??453?????
????????0?
3????649??
?9?2?15?5?
4??1?????2
?3???35??7
??????????
?????22?1?
???3?7??2?
??????4??6
?????5???1
7???????3?
??3?9??8??
8??1????8?

output:

97199393

result:

ok 1 number(s): "97199393"

Test #24:

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

input:

20 10
002?3??012
?1460?424?
???7??48?4
?4?3521?97
??650611?3
?3??1?9???
?????6??80
16?0?0?5??
17????????
?8?9?79???
3??4??53??
?8?265?6?5
5022812?34
?5?6??????
?7?335?1??
59?8?87?5?
6??4?0?4?8
78????16??
???63????9
??28?01895

output:

970610157

result:

ok 1 number(s): "970610157"

Test #25:

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

input:

20 10
??6427?355
0?4736502?
139022861?
??44605?51
2321570082
2501432??8
29202789?1
311???420?
3247?8042?
?881??98?6
4274?962??
44116?159?
4?637804?2
???4451761
?68?484277
6356514??6
6554356736
817?511935
??48725824
9967?2?757

output:

777766220

result:

ok 1 number(s): "777766220"

Test #26:

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

input:

20 10
?5?0443?45
2552451909
3?95468846
358?4230?6
37?4?2?106
38?5278788
41742?4379
45?6?80664
4?6?21?316
520358?02?
?742675127
58?45365?3
65?9934??7
6798553448
77?89?7969
7884864904
8188?6??75
87?2456758
8840?40183
9245265930

output:

848368858

result:

ok 1 number(s): "848368858"

Test #27:

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

input:

20 20
????????????????1???
??????????????????96
??????6?????8???????
2?????????????????7?
?????3???????1??????
??6??7????????????2?
??????5???4????????0
?????9??????????????
?????????????6??????
???????????????6????
???????7?3??????3???
????????6????????4??
5???2??9???1?8???0??
???2?????2??8???????
...

output:

67854164

result:

ok 1 number(s): "67854164"

Test #28:

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

input:

20 20
???????????????8?5??
???????6?6?0?0???72?
????????????2??2??2?
?????4?0????????????
??1????3??4????64???
3?0??5?5?7?????307??
?????????1???83???69
???????29?9???8?????
?1????0??6?35?3?7???
????0???????????????
?????0?????783?????6
?0?18?17???????5????
??????5??????4??7???
????0??????767???5??
...

output:

956277142

result:

ok 1 number(s): "956277142"

Test #29:

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

input:

20 20
09?1?0???154???58?8?
??5?7599?87?22??8956
?95?7???7?188?903???
2?0????99588??346116
347?7???????142???65
????6??9?4?941?33???
3???89?94?6?1??88??8
??3?76???9??5?6??5?4
46??32???8??97?1???5
???801?28????9?96???
???8?870??4?970?54??
5?6??????0???222779?
?7?021?8?4????2????7
6???69????027388?3?3
...

output:

976947581

result:

ok 1 number(s): "976947581"

Test #30:

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

input:

20 20
083095228?5?2644?168
10392020300554638700
30??386?6717?881758?
3239??882040095554?0
38?40?5219?053884469
394?5?0075?02?41?6??
???1742?64?41102???4
5008?728?5?6??53?311
53436403?0?33?198645
54717324?98921941?59
??3?360?12?285?7?8??
?39828?6?6?5?9210??4
6?350?5?1?5322049?27
?58739015?476376162?
...

output:

51567474

result:

ok 1 number(s): "51567474"

Test #31:

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

input:

20 20
0?23153440476153105?
09061873814519257143
?202?799560072466388
1218?651?5?204452589
207?1937293118?02140
?32?1987721668387?3?
2432922?6761?9?04138
2579?12??6?29???1?91
28?75812799484303849
43593?79148?31?903?5
46224442256853014570
52061320?93414541493
5304238?085837549931
67776952060?1?1?8?87
...

output:

225558553

result:

ok 1 number(s): "225558553"

Test #32:

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

input:

20 50
?2??????6????????????????????????????????0??0?????
??????????????????????2??????7???????????7????????
2????????0?????????????3??5????????????????????3??
????????5???30????????????3???4??????47???????8???
??3???1?????????????????????????2??5????????4????8
??????????1?25??????????????9????7?????...

output:

678184250

result:

ok 1 number(s): "678184250"

Test #33:

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

input:

20 50
???1???????0???17??????6?????2??8?4?48?2??????????
?8??5??9?1??6????44????1??1?7?????????9?1??????23?
20????842???79?????6???80????02???0?39????????9???
2?4??6???????6?????????535???????2??02?7????9??50?
??????????61?????7?????????0??7?????0???3?1?8??2??
3413???????3?9??????????????????28??725...

output:

57297550

result:

ok 1 number(s): "57297550"

Test #34:

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

input:

20 50
03??8338?45?677??5??1???68?4??49?9?0?15?07?0?9?873
?6?7????????83?4????????91?895??79?9????1?7??7?5?1
1?357??659??5??5?6???84???8??68??1160?????21?8??47
?27?45???????41?54?572?4??1??8?9?0?3??61??5?5886??
2???7?1????2???4????9??2?849277??7?934?29992180???
??68911???76?935?566?59???5??0??914??25...

output:

584219333

result:

ok 1 number(s): "584219333"

Test #35:

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

input:

20 50
1?525?6?497823?475?69?6492?157?4609889?980?5162?94
1728547?16279?3?0834209927?548?24686?4?88?753?2?84
281?6?92?9337975?10900??1691?920?757969?914?1?6095
30?84794??115?22908?22??7?41??3?79728?85?0122?8636
364280154?15??343542??9711??1?915?55354?570897?201
4078036??8?5?7593749?77?84?905?72??880?...

output:

121549800

result:

ok 1 number(s): "121549800"

Test #36:

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

input:

20 50
00?18359996770??863998??7056819?0223598059918?0853
02146371385183?368?4040?9167??123?86707770?1?676?7
03373293725341?9940886?7599?2030?614234022805602??
056374196442793542?34?6143737952171?819990?159633?
12363981023395399915345863799?0599?085136168?08?63
125709533724163350923408644?10?07446?3?...

output:

754423372

result:

ok 1 number(s): "754423372"

Test #37:

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

input:

50 10
??????0???
?????????2
???0??????
??????????
?????????8
???2??????
??????????
?????????3
???1?2????
????4????8
???4????6?
?3???????8
??????????
????94???5
???3??????
?7??????8?
??????????
?????5????
???????3??
???2??6???
?4??8??8??
??????????
??????3???
????1?????
??????????
?8????????
????????...

output:

720198811

result:

ok 1 number(s): "720198811"

Test #38:

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

input:

50 10
0?320?????
?71??151??
???0????2?
?2??9?????
??????0???
?6????????
2??5956??1
?8?56???7?
??4?0?4?7?
?9??29????
??8??6????
?1????0???
??296?387?
??561?30??
??????0???
3????98??3
??????81??
??????????
?69???85??
????77??5?
???68?????
?2???9????
?4??44????
?5??2?????
?????9???2
???????4?7
5???????...

output:

880397834

result:

ok 1 number(s): "880397834"

Test #39:

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

input:

50 10
??3996????
????2?1?9?
042??851?0
??58?688?2
04???215?5
?7?20879?5
16?33??438
2?0??6????
?11578?755
??59?77?44
24??663??2
2?71???5??
2?8??1??7?
29??767??3
?19???????
?19?9?8???
3?682?395?
3?4??592?3
37????9???
????14?88?
?6?1??03??
????978???
??9?4?????
53??4??289
??1?96?4??
5???42??9?
6008?177...

output:

436473853

result:

ok 1 number(s): "436473853"

Test #40:

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

input:

50 10
0238?52?43
0277?63089
0?9381?311
?4?899??0?
063725413?
???904?6??
08?60?9?20
0882?11?7?
09?1?03401
?97?787?29
099?989?0?
10930402?8
11705?6?1?
?4?80?05?1
164?73?586
1???926?46
17?2724258
?596?993?2
?6921?8328
329?609?43
3666?1756?
373?3?676?
3?7886???1
?173?8275?
??080?6?81
49768?44??
53?25?56...

output:

486819799

result:

ok 1 number(s): "486819799"

Test #41:

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

input:

50 10
0436184989
04??41890?
05465614?8
072?3?13??
?779743961
11641609?8
1?43353075
1260855865
1589?42??7
230887?68?
311234?81?
3?52655974
33?7235667
3435350313
3515413172
?559?96?11
3766489294
4?82991774
44313332?6
?62?353230
4646431908
48?15214?4
49834?0572
5066990844
5287357?57
??81350?96
60679816...

output:

277980085

result:

ok 1 number(s): "277980085"

Test #42:

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

input:

50 20
?18??7????????????06
???0?????????9??????
??????4??0??????????
?????????9?38???????
??????4?????????9???
??668???????7??0?6??
??????2???0?????????
????????????????????
??????62?1??????????
???????93??7????????
3??????8???????0????
3??????????????9????
???3??????4??8??????
?????68????4?7??????
...

output:

502169464

result:

ok 1 number(s): "502169464"

Test #43:

score: 0
Accepted
time: 27ms
memory: 9640kb

input:

50 20
???8?4?2???4????98??
0??4?6??7??3?2??5???
0???72?33?3???8????8
0?4?8?????4?1???05??
????7??8?0??5???????
?826??????8?9?????0?
?05?3?011?1????1????
?8????43?????3????7?
1?309?????4?????47?1
??6????5?3?????94?3?
2??????????38??64?2?
?????????79?????????
?7?04????6?1???0????
?????????????82???8?
...

output:

583076940

result:

ok 1 number(s): "583076940"

Test #44:

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

input:

50 20
?0903?579993????3655
?30?41???4?????7?5?4
?3?10838????1???071?
?????046?007??085012
06?09?7???9684?8545?
??4?30341892?03?38??
?79???81???9?2?5?496
?94?0?31????????4?2?
?407????06483??09???
???19??7?4?2??7?4?9?
???????81????99?9?02
19???05??31??46?424?
??94??9??647????09??
2?????7?6?1??2?6???0
...

output:

280419440

result:

ok 1 number(s): "280419440"

Test #45:

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

input:

50 20
00914????414???2?7?7
082?62719?3679??6617
0?4?2?7371?7868?8184
?135018?0?5????25?1?
1435146?214??1?81?2?
?524?03?031?307??657
?613?54?47??81?49338
19?1529614?98?070?7?
??084?424872?15047?9
235?616813?44?360382
246645143013697?1??5
2??2???32834789456?6
2639034390234???32?1
2780372859?358?42?03
...

output:

813127409

result:

ok 1 number(s): "813127409"

Test #46:

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

input:

50 20
000502?94?4449??9994
0?3797520?15?593?793
02265363070904148599
?3982451?84158192624
0922?01594870?0?4?34
?949735434811923303?
0?90?419323550558?79
??2?10?942176222006?
1?23252543?190089770
17812403623?93515579
?87136951201?5278034
206?2357?60779829997
23108903723692?6462?
24?49387096110?360?1
...

output:

702382634

result:

ok 1 number(s): "702382634"

Test #47:

score: 0
Accepted
time: 99ms
memory: 18924kb

input:

50 50
?????????????????????67?3???1????????????????2??3?
?64?????4???????????????86??8?????1???????????????
0???????????????8??????1???1?3???????1????0???????
?97?22??????????????????????????6??9??????30?2????
?????????????807??????6??????1?3??????????????????
???7???????????02??????4??????9??1?????...

output:

34908478

result:

ok 1 number(s): "34908478"

Test #48:

score: 0
Accepted
time: 74ms
memory: 18884kb

input:

50 50
??2????0??????1???????????6??4?432??2??9??????????
?4??2?????04???4????2?7???????????2?18????7?????0?
?4?7?0?58??64???????7???62???8????2???9?????????1?
?5???9????7???????????????????????3?21????????????
???7????????1?73???????????3??????0???32?????782??
??1???01????05?38????6?9????54?????????...

output:

400228884

result:

ok 1 number(s): "400228884"

Test #49:

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

input:

50 50
0???97964?5?8??943???7?7??81?8???27?14?9?5?69?????
04???6?5?66306??31??????248??801?5???31?33?9??4?0?
??77?99???1??88?7557?1?4?8?28?81???6777??92??9??1?
?7??39???5?????181411044???7?23366?6?4?0??99?9????
0?7??86198???55??7?17?96????????960??4596????31??8
1??928317????00?55?1?091?6?03?5??????1?...

output:

46072945

result:

ok 1 number(s): "46072945"

Test #50:

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

input:

50 50
0712930?998?62?141?7??5944722063?0?1????03401?2709
?9?874217604698?9?5477?081?79132?61?0200196?014600
1145926388498?1793?837047202?042??62??0604901?5??8
???548?742149?6???810?60?63?4?48?35??5032?1?63?330
?2626175??010811510??5?570?4???4719??78226?5438809
1332040189157?46388??1961?176?77?11?8?0...

output:

913581097

result:

ok 1 number(s): "913581097"

Test #51:

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

input:

50 50
02?0??67306??228833?10425685289996?38131??06111150
???5338459437770?1160454385626349?088???2709904811
?358309?43067857774996427155144?5402716613?7101?08
1066067?5172?7?1?1941098?458?22?7525768224?52???53
1359935009425163480954?6760??4495809902510?40?963?
?378672?696925?0?70?5?925352263684?2688...

output:

454658329

result:

ok 1 number(s): "454658329"

Test #52:

score: 0
Accepted
time: 245ms
memory: 18876kb

input:

50 50
????????????????????????????????4?????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
???????????????????????????????????????...

output:

136998761

result:

ok 1 number(s): "136998761"

Test #53:

score: 0
Accepted
time: 240ms
memory: 18900kb

input:

50 50
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
???????????????????????????????????????...

output:

564071240

result:

ok 1 number(s): "564071240"

Test #54:

score: 0
Accepted
time: 34ms
memory: 18880kb

input:

50 50
03887126663007067971362875340843831423377201714531
05941508836659209975229528627364167944196991552144
13379796300726573301501397816844474131798821542728
18610331756265877746645641719453123282222850374392
21651242668814092190894932647801215330392024380650
216989323857609919665101768593491326566...

output:

748137777

result:

ok 1 number(s): "748137777"

Test #55:

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

input:

1 1
?

output:

45

result:

ok 1 number(s): "45"

Test #56:

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

input:

1 1
1

output:

1

result:

ok 1 number(s): "1"

Test #57:

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

input:

1 1
0

output:

0

result:

ok 1 number(s): "0"

Test #58:

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

input:

1 1
5

output:

5

result:

ok 1 number(s): "5"

Test #59:

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

input:

10 1
9
8
7
6
5
4
3
2
1
0

output:

0

result:

ok 1 number(s): "0"

Test #60:

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

input:

5 3
999
???
???
???
???

output:

0

result:

ok 1 number(s): "0"

Test #61:

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

input:

3 3
3?8
?1?
4??

output:

11528550

result:

ok 1 number(s): "11528550"

Test #62:

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

input:

3 3
998
9??
999

output:

0

result:

ok 1 number(s): "0"

Test #63:

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

input:

3 3
997
???
999

output:

2994

result:

ok 1 number(s): "2994"