QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213215#6555. Sets May Be Gooducup-team087#AC ✓42ms4320kbC++145.6kb2023-10-14 13:06:022023-10-14 13:06:02

Judging History

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

  • [2023-10-14 13:06:02]
  • 评测
  • 测评结果:AC
  • 用时:42ms
  • 内存:4320kb
  • [2023-10-14 13:06:02]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;


// \sum[x \in (Z/2Z)^n] (-1)^(\sum[u<=v] adj[u][v] x[u] x[v])
namespace solver {
constexpr int MAX_N = 2010;
int n;
bitset<MAX_N> adj[MAX_N];
void init(int n_) {
  assert(n_ >= 0);
  n = n_;
  for (int u = 0; u < n; ++u) adj[u].reset();
}
void ae(int u, int v) {
  assert(0 <= u); assert(u < n);
  assert(0 <= v); assert(v < n);
  adj[u].flip(v);
  if (u != v) adj[v].flip(u);
}
Mint run() {
  vector<int> del(n, 0);
  Mint ans = 1;
  for (int u = 0; u < n; ++u) if (!del[u]) {
    del[u] = 1;
    bool isol = true;
    for (int v = u + 1; v < n; ++v) if (!del[v] && adj[u][v]) {
      // \sum[x[u],x[v]] (-1)^(x[u][v] + adj[u][u] x[u] + adj[v][v] x[v] + x[u] \sum[u-w] x[w] + x[v] \sum[u-w] x[w])
      // = 2 (-1)^((adj[u][u] + \sum[u-w] x[w]) (adj[v][v] + \sum[v-w] x[w]))
      del[v] = 1;
      ans *= 2;
      if (adj[u][u] && adj[v][v]) ans = -ans;
      if (adj[u][u]) for (int w = u + 1; w < n; ++w) if (!del[w] && adj[v][w]) adj[w].flip(w);
      if (adj[v][v]) for (int w = u + 1; w < n; ++w) if (!del[w] && adj[u][w]) adj[w].flip(w);
      for (int w = u + 1; w < n; ++w) if (!del[w]) {
        if (adj[u][w] && adj[v][w]) adj[w].flip(w);
        if (adj[u][w]) adj[w] ^= adj[v];
        if (adj[v][w]) adj[w] ^= adj[u];
      }
      isol = false;
      break;
    }
    if (isol) {
      // \sum[x[u]] (-1)^(adj[u][u] x[u])
      if (adj[u][u]) {
        ans = 0;
        break;
      } else {
        ans *= 2;
      }
    }
  }
  return ans;
}
}  // solver


int main() {
  int N, M;
  for (; ~scanf("%d%d", &N, &M); ) {
    solver::init(N);
    for (int i = 0; i < M; ++i) {
      int u, v;
      scanf("%d%d", &u, &v);
      --u;
      --v;
      solver::ae(u, v);
    }
    Mint ans = solver::run();
    ans = (Mint(2).pow(N) + ans) / 2;
    printf("%u\n", ans.x);
  }
  return 0;
}

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

詳細信息

Test #1:

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

input:

5 5
1 2
2 3
3 4
4 5
1 5

output:

16

result:

ok 1 number(s): "16"

Test #2:

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

input:

3 0

output:

8

result:

ok 1 number(s): "8"

Test #3:

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

input:

2 1
1 2

output:

3

result:

ok 1 number(s): "3"

Test #4:

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

input:

4 6
1 2
1 3
1 4
2 3
2 4
3 4

output:

6

result:

ok 1 number(s): "6"

Test #5:

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

input:

1 0

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

4 5
1 2
1 3
1 4
2 3
3 4

output:

8

result:

ok 1 number(s): "8"

Test #7:

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

input:

5 3
1 3
1 4
1 5

output:

24

result:

ok 1 number(s): "24"

Test #8:

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

input:

5 0

output:

32

result:

ok 1 number(s): "32"

Test #9:

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

input:

6 3
1 2
3 4
3 6

output:

40

result:

ok 1 number(s): "40"

Test #10:

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

input:

6 0

output:

64

result:

ok 1 number(s): "64"

Test #11:

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

input:

7 3
2 3
3 6
6 7

output:

80

result:

ok 1 number(s): "80"

Test #12:

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

input:

7 0

output:

128

result:

ok 1 number(s): "128"

Test #13:

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

input:

20 30
1 7
1 9
1 12
1 13
2 6
2 17
3 13
4 12
4 15
4 17
6 10
6 17
7 8
7 18
8 14
9 13
10 16
10 17
12 14
13 15
13 16
13 20
14 16
14 18
14 20
15 17
15 18
15 19
15 20
16 17

output:

524288

result:

ok 1 number(s): "524288"

Test #14:

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

input:

20 73
1 4
1 9
1 13
2 6
2 7
2 12
2 14
2 18
2 19
3 6
3 10
3 12
3 14
3 16
3 17
3 18
4 6
4 7
4 11
4 14
4 15
4 18
4 19
5 6
5 7
5 9
5 10
5 12
5 14
5 15
5 17
5 18
5 19
5 20
6 12
6 13
6 15
6 16
6 17
7 9
7 16
7 19
8 11
8 15
8 16
8 20
9 10
9 12
9 17
9 20
10 11
10 12
10 14
10 16
10 17
10 18
11 12
11 20
12 13
1...

output:

524288

result:

ok 1 number(s): "524288"

Test #15:

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

input:

1000 499500
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1...

output:

818794637

result:

ok 1 number(s): "818794637"

Test #16:

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

input:

1000 10000
1 14
1 53
1 132
1 139
1 174
1 237
1 246
1 278
1 302
1 349
1 353
1 396
1 465
1 652
1 698
1 706
1 753
1 845
1 848
1 862
1 884
1 911
1 1000
2 31
2 57
2 80
2 118
2 182
2 195
2 198
2 344
2 347
2 585
2 591
2 597
2 611
2 623
2 642
2 672
2 694
2 704
2 731
2 770
2 852
2 923
2 974
3 8
3 12
3 59
3 8...

output:

128609606

result:

ok 1 number(s): "128609606"

Test #17:

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

input:

1000 1000
1 179
1 188
1 421
3 14
3 676
4 386
4 740
4 797
6 164
6 374
7 161
8 34
8 359
8 402
9 188
9 452
9 708
10 278
10 425
10 758
11 242
12 338
12 402
12 875
13 22
13 313
13 340
13 711
14 624
14 729
14 857
15 493
15 611
16 540
17 628
17 745
18 598
18 844
19 453
20 147
20 527
21 62
21 313
22 560
22 ...

output:

890151081

result:

ok 1 number(s): "890151081"

Test #18:

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

input:

1000 100
7 816
19 226
20 568
24 530
26 137
33 640
61 149
67 521
77 701
79 976
80 313
84 958
84 991
85 555
95 428
107 181
108 800
110 898
120 481
136 737
147 275
148 970
153 919
163 326
177 842
178 257
189 808
195 1000
200 580
204 509
207 746
211 419
216 387
219 534
225 796
232 633
238 769
248 997
25...

output:

57698280

result:

ok 1 number(s): "57698280"

Test #19:

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

input:

1000 100000
1 2
1 27
1 34
1 41
1 53
1 60
1 66
1 81
1 82
1 84
1 88
1 93
1 97
1 100
1 101
1 107
1 111
1 112
1 119
1 126
1 127
1 128
1 132
1 133
1 134
1 139
1 153
1 155
1 177
1 182
1 185
1 187
1 192
1 197
1 214
1 215
1 217
1 221
1 227
1 230
1 231
1 232
1 235
1 240
1 243
1 246
1 247
1 248
1 254
1 258
1 ...

output:

818794637

result:

ok 1 number(s): "818794637"

Test #20:

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

input:

1000 200000
1 3
1 4
1 7
1 11
1 14
1 15
1 18
1 21
1 23
1 25
1 26
1 27
1 28
1 29
1 32
1 33
1 38
1 40
1 41
1 43
1 44
1 46
1 48
1 49
1 50
1 51
1 52
1 53
1 56
1 57
1 60
1 61
1 62
1 65
1 69
1 72
1 74
1 77
1 83
1 86
1 87
1 89
1 96
1 97
1 100
1 103
1 104
1 105
1 106
1 108
1 111
1 113
1 115
1 119
1 122
1 125...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #21:

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

input:

1000 100002
1 2
1 6
1 10
1 12
1 14
1 29
1 31
1 39
1 49
1 50
1 51
1 52
1 56
1 60
1 67
1 71
1 73
1 74
1 75
1 83
1 84
1 86
1 87
1 88
1 91
1 96
1 97
1 100
1 108
1 111
1 123
1 125
1 127
1 132
1 136
1 140
1 142
1 149
1 157
1 158
1 159
1 176
1 179
1 181
1 182
1 184
1 188
1 189
1 191
1 198
1 206
1 207
1 209...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #22:

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

input:

1000 200022
1 2
1 4
1 11
1 12
1 15
1 16
1 18
1 24
1 27
1 29
1 34
1 35
1 37
1 38
1 40
1 41
1 42
1 43
1 45
1 46
1 48
1 49
1 51
1 59
1 61
1 66
1 69
1 71
1 73
1 75
1 78
1 80
1 81
1 88
1 89
1 93
1 95
1 102
1 104
1 107
1 108
1 111
1 112
1 115
1 119
1 120
1 122
1 124
1 128
1 130
1 131
1 141
1 150
1 151
1 1...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #23:

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

input:

1000 50000
1 5
1 37
1 81
1 91
1 101
1 125
1 126
1 139
1 140
1 155
1 163
1 168
1 170
1 187
1 205
1 219
1 226
1 230
1 232
1 242
1 247
1 256
1 264
1 271
1 284
1 298
1 312
1 323
1 337
1 365
1 372
1 375
1 378
1 384
1 391
1 396
1 399
1 402
1 413
1 437
1 446
1 451
1 463
1 482
1 496
1 499
1 515
1 534
1 541
...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #24:

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

input:

1000 88888
1 7
1 12
1 18
1 19
1 26
1 32
1 41
1 42
1 44
1 54
1 55
1 59
1 60
1 65
1 74
1 77
1 82
1 90
1 95
1 100
1 103
1 107
1 112
1 114
1 115
1 117
1 128
1 130
1 136
1 137
1 141
1 142
1 143
1 145
1 148
1 155
1 158
1 164
1 172
1 182
1 186
1 188
1 208
1 210
1 211
1 212
1 217
1 221
1 223
1 231
1 236
1 2...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #25:

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

input:

1000 100010
1 4
1 9
1 21
1 25
1 29
1 34
1 43
1 57
1 60
1 63
1 71
1 72
1 73
1 76
1 92
1 94
1 95
1 105
1 107
1 117
1 123
1 127
1 137
1 138
1 142
1 148
1 151
1 156
1 158
1 161
1 163
1 173
1 175
1 176
1 178
1 182
1 184
1 186
1 187
1 194
1 210
1 214
1 216
1 220
1 222
1 224
1 225
1 227
1 229
1 230
1 231
1...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #26:

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

input:

1000 99111
1 4
1 13
1 14
1 24
1 25
1 32
1 35
1 36
1 39
1 64
1 65
1 68
1 71
1 74
1 76
1 83
1 87
1 104
1 112
1 115
1 118
1 119
1 121
1 136
1 138
1 142
1 148
1 151
1 153
1 159
1 162
1 165
1 171
1 188
1 200
1 202
1 206
1 207
1 219
1 234
1 237
1 238
1 239
1 243
1 244
1 254
1 267
1 269
1 271
1 274
1 275
1...

output:

202675993

result:

ok 1 number(s): "202675993"

Test #27:

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

input:

1000 90000
1 2
1 18
1 26
1 43
1 44
1 46
1 47
1 51
1 53
1 55
1 73
1 76
1 78
1 92
1 114
1 120
1 145
1 148
1 156
1 165
1 173
1 174
1 186
1 192
1 194
1 206
1 213
1 214
1 225
1 239
1 240
1 247
1 254
1 273
1 278
1 286
1 290
1 292
1 297
1 298
1 301
1 308
1 323
1 325
1 330
1 342
1 353
1 356
1 363
1 366
1 38...

output:

818794637

result:

ok 1 number(s): "818794637"

Test #28:

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

input:

1000 71111
1 2
1 3
1 7
1 14
1 17
1 34
1 36
1 44
1 51
1 68
1 77
1 88
1 108
1 122
1 127
1 130
1 147
1 149
1 155
1 156
1 160
1 176
1 179
1 193
1 216
1 227
1 232
1 237
1 246
1 259
1 261
1 264
1 288
1 295
1 299
1 304
1 307
1 320
1 321
1 328
1 330
1 350
1 362
1 367
1 379
1 388
1 397
1 400
1 403
1 404
1 41...

output:

892861024

result:

ok 1 number(s): "892861024"

Test #29:

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

input:

1000 55555
1 2
1 3
1 4
1 14
1 29
1 30
1 34
1 43
1 56
1 64
1 71
1 88
1 93
1 112
1 114
1 130
1 140
1 141
1 148
1 158
1 182
1 183
1 187
1 193
1 194
1 195
1 206
1 214
1 215
1 219
1 232
1 241
1 251
1 252
1 259
1 269
1 289
1 319
1 323
1 339
1 341
1 345
1 349
1 357
1 377
1 378
1 381
1 394
1 443
1 446
1 453...

output:

202675993

result:

ok 1 number(s): "202675993"

Test #30:

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

input:

1000 20000
1 40
1 108
1 143
1 160
1 179
1 181
1 246
1 266
1 279
1 299
1 309
1 323
1 348
1 357
1 363
1 370
1 387
1 417
1 452
1 465
1 475
1 480
1 486
1 495
1 496
1 500
1 501
1 545
1 548
1 560
1 600
1 622
1 676
1 688
1 710
1 720
1 749
1 775
1 785
1 795
1 815
1 840
1 845
1 865
1 880
1 890
1 900
1 918
1 ...

output:

818794637

result:

ok 1 number(s): "818794637"

Test #31:

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

input:

1000 22222
1 30
1 35
1 38
1 39
1 42
1 46
1 95
1 96
1 134
1 145
1 160
1 194
1 204
1 239
1 244
1 248
1 250
1 255
1 282
1 284
1 289
1 308
1 311
1 314
1 321
1 339
1 352
1 355
1 379
1 385
1 402
1 433
1 437
1 443
1 461
1 493
1 509
1 517
1 555
1 569
1 576
1 607
1 608
1 611
1 673
1 681
1 728
1 820
1 821
1 8...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #32:

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

input:

1000 33442
1 13
1 80
1 110
1 112
1 115
1 131
1 141
1 156
1 158
1 162
1 167
1 178
1 193
1 198
1 224
1 229
1 243
1 251
1 281
1 283
1 291
1 296
1 325
1 349
1 353
1 354
1 400
1 415
1 417
1 420
1 450
1 497
1 520
1 525
1 530
1 539
1 587
1 594
1 600
1 612
1 624
1 638
1 639
1 657
1 658
1 667
1 674
1 676
1 6...

output:

202675993

result:

ok 1 number(s): "202675993"

Test #33:

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

input:

1000 15000
1 8
1 18
1 96
1 112
1 125
1 128
1 130
1 137
1 165
1 174
1 191
1 192
1 205
1 300
1 443
1 446
1 449
1 464
1 476
1 497
1 546
1 557
1 562
1 567
1 619
1 624
1 634
1 649
1 650
1 699
1 713
1 725
1 746
1 774
1 777
1 814
1 856
1 924
1 992
2 45
2 102
2 129
2 140
2 167
2 176
2 202
2 346
2 358
2 377
...

output:

892861024

result:

ok 1 number(s): "892861024"

Test #34:

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

input:

1000 13000
1 161
1 262
1 330
1 356
1 358
1 412
1 497
1 552
1 555
1 563
1 621
1 624
1 626
1 868
1 907
1 947
1 978
2 96
2 122
2 226
2 258
2 273
2 290
2 302
2 344
2 358
2 474
2 504
2 505
2 528
2 531
2 550
2 566
2 654
2 727
2 832
2 858
2 902
3 25
3 32
3 84
3 101
3 160
3 165
3 171
3 172
3 194
3 295
3 352...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #35:

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

input:

1000 14000
1 78
1 155
1 158
1 212
1 223
1 248
1 255
1 309
1 321
1 351
1 402
1 403
1 460
1 505
1 508
1 515
1 533
1 575
1 603
1 610
1 669
1 677
1 712
1 773
1 805
1 865
1 892
1 928
2 20
2 27
2 40
2 44
2 84
2 132
2 183
2 250
2 270
2 302
2 312
2 322
2 335
2 352
2 354
2 377
2 532
2 542
2 608
2 621
2 638
2...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #36:

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

input:

1000 14132
1 14
1 22
1 46
1 84
1 91
1 134
1 249
1 251
1 301
1 316
1 321
1 330
1 399
1 402
1 433
1 451
1 455
1 482
1 504
1 518
1 541
1 552
1 594
1 596
1 600
1 602
1 633
1 651
1 667
1 711
1 748
1 776
1 793
1 913
1 978
1 979
2 28
2 100
2 179
2 181
2 223
2 290
2 312
2 344
2 406
2 456
2 461
2 594
2 611
2...

output:

818794637

result:

ok 1 number(s): "818794637"

Test #37:

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

input:

1000 300000
1 2
1 3
1 4
1 5
1 7
1 11
1 13
1 15
1 17
1 18
1 19
1 20
1 21
1 24
1 25
1 27
1 29
1 31
1 32
1 34
1 39
1 40
1 45
1 46
1 48
1 49
1 52
1 55
1 61
1 62
1 66
1 67
1 69
1 71
1 73
1 77
1 78
1 81
1 82
1 84
1 85
1 87
1 88
1 89
1 90
1 92
1 95
1 96
1 98
1 100
1 104
1 108
1 110
1 111
1 112
1 113
1 114
...

output:

202675993

result:

ok 1 number(s): "202675993"

Test #38:

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

input:

1000 300011
1 2
1 3
1 5
1 6
1 7
1 8
1 9
1 11
1 13
1 14
1 15
1 16
1 17
1 19
1 20
1 21
1 22
1 23
1 24
1 26
1 27
1 28
1 30
1 31
1 32
1 36
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 49
1 50
1 51
1 52
1 53
1 54
1 58
1 60
1 62
1 66
1 73
1 77
1 80
1 81
1 83
1 84
1 85
1 86
1 88
1 90
1 92
1 93
1 95
1 97
...

output:

818794637

result:

ok 1 number(s): "818794637"

Test #39:

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

input:

1000 252525
1 7
1 12
1 15
1 16
1 17
1 18
1 20
1 21
1 25
1 26
1 28
1 33
1 34
1 35
1 36
1 37
1 38
1 42
1 43
1 48
1 49
1 51
1 52
1 53
1 54
1 55
1 60
1 64
1 65
1 68
1 69
1 71
1 76
1 80
1 83
1 84
1 87
1 88
1 90
1 91
1 93
1 95
1 97
1 98
1 99
1 100
1 104
1 106
1 112
1 119
1 121
1 122
1 125
1 126
1 127
1 12...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #40:

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

input:

1000 5111
1 145
1 173
1 227
1 274
1 392
1 516
1 518
1 637
1 786
1 884
1 892
1 961
2 44
2 93
2 107
2 163
2 179
2 194
2 313
2 444
2 487
2 495
2 622
2 735
2 747
2 779
2 837
2 841
2 864
2 900
2 957
2 971
3 224
3 261
3 458
3 499
3 555
3 754
3 840
3 891
4 65
4 124
4 221
4 261
4 373
4 486
4 541
4 554
4 930...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #41:

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

input:

1000 3333
1 154
1 206
1 498
1 527
1 537
1 573
1 695
1 778
1 781
1 991
2 94
2 256
2 416
2 580
2 747
2 848
2 983
3 7
3 127
3 276
3 317
3 449
3 451
3 521
3 686
3 738
4 10
4 223
4 235
4 814
4 883
5 18
5 456
5 632
5 656
5 771
5 912
6 164
7 175
7 312
7 330
7 446
8 66
8 89
8 315
8 335
8 413
8 480
8 600
8 8...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #42:

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

input:

1000 5700
1 182
1 258
1 299
1 365
1 481
1 484
1 612
1 730
1 877
1 946
2 32
2 37
2 104
2 276
2 301
2 351
2 843
2 905
2 907
2 943
2 992
2 996
3 272
3 340
3 367
3 402
3 478
3 530
3 585
3 676
3 767
4 33
4 181
4 267
4 337
4 345
4 422
4 431
4 450
4 516
4 759
4 893
5 230
5 276
5 385
5 397
5 444
5 478
5 641...

output:

892861024

result:

ok 1 number(s): "892861024"

Test #43:

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

input:

1000 6319
1 106
1 143
1 312
1 420
1 472
1 589
1 610
1 757
1 788
1 879
1 890
2 26
2 114
2 163
2 182
2 213
2 287
2 295
2 306
2 325
2 336
2 339
2 340
2 364
2 403
2 432
2 436
2 521
2 739
2 754
2 779
2 780
2 807
2 989
3 32
3 47
3 107
3 141
3 169
3 265
3 280
3 322
3 340
3 711
3 739
3 778
3 902
4 214
4 237...

output:

892861024

result:

ok 1 number(s): "892861024"

Test #44:

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

input:

1000 2889
1 136
1 236
1 519
1 653
1 846
1 852
2 141
2 168
2 258
2 591
2 681
2 794
2 805
3 105
3 503
3 627
3 635
3 795
3 807
4 223
4 493
4 844
4 951
4 975
5 194
5 215
5 398
5 450
5 523
5 720
5 832
5 969
5 976
6 151
6 279
6 686
6 803
6 849
7 277
8 76
8 334
8 344
8 649
9 55
9 658
9 784
9 801
9 802
10 6...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #45:

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

input:

1000 1337
1 128
1 516
1 666
1 980
2 223
2 365
2 714
3 184
4 450
4 511
4 859
5 133
5 208
5 435
6 38
6 118
6 139
6 296
6 550
7 284
7 659
8 144
9 138
9 197
9 258
9 841
10 350
10 789
11 43
11 451
11 523
11 551
12 195
12 283
12 819
13 242
13 705
13 901
15 53
15 88
15 248
16 331
16 916
17 487
17 703
17 91...

output:

223599922

result:

ok 1 number(s): "223599922"

Test #46:

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

input:

1000 999
1 682
1 812
2 705
3 201
4 709
4 732
6 443
6 627
7 258
7 440
7 634
8 739
8 875
9 707
10 98
10 372
11 265
11 397
11 737
12 177
13 79
13 559
13 786
14 75
14 364
14 551
15 61
15 177
15 233
15 438
16 161
16 229
17 228
18 59
18 136
18 167
18 303
18 515
18 966
19 742
20 800
22 359
23 55
23 421
23 ...

output:

551328384

result:

ok 1 number(s): "551328384"

Test #47:

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

input:

1000 700
1 294
1 409
1 423
1 682
1 895
2 852
4 657
4 679
4 858
5 30
5 993
7 766
9 621
9 751
10 157
10 951
11 305
13 325
13 483
14 42
14 142
14 685
15 604
16 576
16 750
17 443
18 303
18 697
18 779
19 58
19 568
21 112
21 186
22 867
23 285
23 437
24 470
24 782
26 38
26 781
27 355
28 87
29 280
29 784
30...

output:

418946261

result:

ok 1 number(s): "418946261"

Test #48:

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

input:

1000 401
1 752
4 866
6 385
8 61
8 727
9 549
10 646
11 168
13 265
15 589
16 963
21 640
24 221
24 685
26 310
26 990
27 596
27 924
28 667
29 285
29 341
30 200
30 353
31 785
33 49
33 904
34 683
34 882
37 621
38 252
38 406
40 47
40 221
42 140
43 701
48 408
48 991
49 305
49 397
50 378
52 811
53 107
54 95
...

output:

828365840

result:

ok 1 number(s): "828365840"

Test #49:

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

input:

1000 0

output:

23226277

result:

ok 1 number(s): "23226277"

Test #50:

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

input:

1000 20
7 787
19 823
20 40
50 252
134 890
170 290
198 437
204 335
275 723
309 354
329 751
331 683
368 665
372 829
472 661
490 916
574 984
585 982
705 767
714 914

output:

435715346

result:

ok 1 number(s): "435715346"

Test #51:

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

input:

1000 97778
1 2
1 8
1 12
1 16
1 22
1 31
1 36
1 37
1 42
1 46
1 50
1 56
1 62
1 66
1 67
1 79
1 90
1 98
1 100
1 114
1 118
1 129
1 132
1 134
1 139
1 144
1 148
1 151
1 160
1 165
1 173
1 177
1 179
1 184
1 189
1 194
1 196
1 197
1 200
1 204
1 206
1 208
1 214
1 225
1 233
1 236
1 240
1 251
1 266
1 280
1 282
1 2...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #52:

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

input:

1000 120000
1 4
1 5
1 19
1 22
1 24
1 27
1 35
1 43
1 52
1 57
1 62
1 66
1 69
1 82
1 88
1 89
1 102
1 105
1 108
1 114
1 116
1 117
1 125
1 129
1 130
1 145
1 146
1 156
1 157
1 162
1 164
1 169
1 170
1 171
1 175
1 179
1 182
1 183
1 184
1 186
1 195
1 197
1 204
1 207
1 209
1 215
1 219
1 221
1 222
1 223
1 225
...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #53:

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

input:

1000 133311
1 2
1 6
1 7
1 11
1 13
1 14
1 24
1 26
1 30
1 32
1 42
1 45
1 47
1 56
1 59
1 62
1 64
1 66
1 71
1 74
1 75
1 77
1 83
1 84
1 87
1 95
1 97
1 103
1 107
1 112
1 114
1 115
1 117
1 119
1 121
1 122
1 124
1 130
1 131
1 133
1 134
1 139
1 148
1 149
1 151
1 152
1 153
1 159
1 162
1 166
1 179
1 183
1 184
...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #54:

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

input:

1000 122200
1 2
1 8
1 20
1 27
1 35
1 40
1 48
1 62
1 64
1 66
1 69
1 70
1 71
1 73
1 75
1 76
1 79
1 82
1 83
1 85
1 90
1 92
1 99
1 108
1 111
1 114
1 116
1 119
1 125
1 129
1 130
1 135
1 136
1 144
1 148
1 151
1 152
1 154
1 155
1 161
1 166
1 172
1 173
1 186
1 188
1 191
1 194
1 200
1 204
1 207
1 214
1 215
1...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #55:

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

input:

1000 97772
1 11
1 23
1 31
1 32
1 41
1 44
1 50
1 60
1 63
1 65
1 70
1 73
1 77
1 78
1 83
1 84
1 88
1 96
1 97
1 99
1 103
1 104
1 108
1 111
1 115
1 118
1 127
1 132
1 136
1 138
1 148
1 150
1 155
1 156
1 169
1 170
1 172
1 175
1 179
1 190
1 193
1 196
1 197
1 200
1 203
1 205
1 206
1 208
1 210
1 211
1 212
1 2...

output:

128609606

result:

ok 1 number(s): "128609606"

Test #56:

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

input:

1000 96666
1 2
1 7
1 18
1 21
1 23
1 25
1 37
1 43
1 48
1 52
1 55
1 61
1 76
1 77
1 80
1 83
1 90
1 113
1 117
1 120
1 123
1 136
1 139
1 140
1 143
1 144
1 149
1 151
1 155
1 164
1 171
1 173
1 174
1 177
1 179
1 193
1 197
1 205
1 208
1 210
1 212
1 215
1 218
1 220
1 225
1 233
1 236
1 245
1 248
1 249
1 250
1 ...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #57:

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

input:

1000 94444
1 2
1 3
1 11
1 17
1 27
1 32
1 34
1 40
1 41
1 49
1 52
1 58
1 60
1 61
1 64
1 69
1 77
1 84
1 87
1 92
1 93
1 100
1 101
1 107
1 109
1 117
1 119
1 122
1 123
1 124
1 130
1 150
1 160
1 166
1 168
1 174
1 197
1 199
1 200
1 208
1 211
1 212
1 225
1 232
1 238
1 239
1 245
1 257
1 259
1 261
1 262
1 268
...

output:

202675993

result:

ok 1 number(s): "202675993"

Test #58:

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

input:

1000 93933
1 15
1 18
1 22
1 23
1 26
1 27
1 39
1 46
1 47
1 61
1 62
1 67
1 68
1 72
1 75
1 79
1 85
1 94
1 98
1 101
1 103
1 114
1 120
1 128
1 132
1 140
1 143
1 144
1 145
1 146
1 151
1 154
1 163
1 169
1 172
1 175
1 179
1 189
1 215
1 217
1 219
1 223
1 224
1 237
1 238
1 242
1 251
1 258
1 275
1 276
1 279
1 ...

output:

892861024

result:

ok 1 number(s): "892861024"

Test #59:

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

input:

1000 87659
1 15
1 20
1 25
1 41
1 46
1 47
1 49
1 52
1 56
1 59
1 79
1 92
1 109
1 110
1 111
1 115
1 116
1 117
1 137
1 151
1 154
1 155
1 161
1 164
1 167
1 183
1 184
1 189
1 206
1 214
1 216
1 221
1 223
1 225
1 227
1 239
1 240
1 244
1 251
1 253
1 255
1 262
1 265
1 266
1 267
1 279
1 284
1 287
1 309
1 319
1...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #60:

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

input:

1000 150005
1 11
1 12
1 16
1 17
1 18
1 19
1 28
1 32
1 33
1 36
1 38
1 39
1 43
1 45
1 46
1 50
1 53
1 55
1 56
1 63
1 64
1 65
1 66
1 72
1 86
1 90
1 92
1 93
1 103
1 115
1 117
1 123
1 125
1 126
1 134
1 135
1 138
1 142
1 143
1 149
1 152
1 156
1 166
1 168
1 171
1 172
1 174
1 182
1 183
1 184
1 187
1 188
1 19...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #61:

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

input:

1000 140001
1 4
1 5
1 6
1 10
1 11
1 32
1 34
1 44
1 45
1 50
1 51
1 61
1 62
1 63
1 65
1 66
1 68
1 69
1 76
1 79
1 82
1 83
1 88
1 90
1 99
1 101
1 110
1 112
1 116
1 123
1 129
1 141
1 145
1 156
1 158
1 160
1 163
1 164
1 167
1 171
1 176
1 181
1 182
1 185
1 189
1 191
1 198
1 204
1 205
1 209
1 211
1 217
1 22...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #62:

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

input:

1000 160001
1 2
1 3
1 6
1 14
1 15
1 16
1 21
1 26
1 27
1 31
1 36
1 37
1 38
1 41
1 42
1 44
1 46
1 47
1 48
1 51
1 52
1 58
1 70
1 71
1 73
1 77
1 79
1 80
1 97
1 101
1 102
1 104
1 108
1 110
1 113
1 115
1 116
1 117
1 118
1 120
1 123
1 124
1 132
1 138
1 142
1 149
1 152
1 153
1 156
1 166
1 169
1 170
1 173
1 ...

output:

892861024

result:

ok 1 number(s): "892861024"

Test #63:

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

input:

1000 118118
1 2
1 11
1 17
1 22
1 27
1 29
1 40
1 48
1 49
1 61
1 66
1 69
1 71
1 73
1 76
1 77
1 82
1 94
1 96
1 99
1 102
1 113
1 115
1 117
1 121
1 124
1 125
1 131
1 135
1 146
1 148
1 151
1 161
1 163
1 167
1 176
1 185
1 186
1 188
1 196
1 201
1 204
1 211
1 218
1 228
1 231
1 237
1 241
1 248
1 249
1 250
1 2...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #64:

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

input:

1000 100100
1 3
1 5
1 6
1 15
1 17
1 19
1 20
1 22
1 23
1 32
1 36
1 41
1 49
1 58
1 61
1 63
1 66
1 67
1 70
1 72
1 77
1 80
1 82
1 88
1 93
1 97
1 103
1 106
1 109
1 110
1 114
1 116
1 122
1 130
1 134
1 135
1 136
1 142
1 147
1 157
1 159
1 164
1 168
1 172
1 173
1 178
1 182
1 185
1 187
1 189
1 190
1 195
1 198...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #65:

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

input:

1000 100134
1 2
1 3
1 7
1 14
1 24
1 36
1 50
1 65
1 74
1 75
1 97
1 103
1 107
1 111
1 112
1 119
1 126
1 131
1 136
1 138
1 141
1 152
1 158
1 160
1 163
1 164
1 165
1 180
1 181
1 183
1 192
1 194
1 197
1 204
1 211
1 213
1 223
1 224
1 232
1 244
1 248
1 251
1 252
1 255
1 257
1 269
1 275
1 276
1 279
1 281
1 ...

output:

202675993

result:

ok 1 number(s): "202675993"

Test #66:

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

input:

1000 56222
1 2
1 3
1 5
1 7
1 11
1 13
1 22
1 25
1 28
1 37
1 81
1 98
1 100
1 111
1 115
1 116
1 131
1 138
1 143
1 145
1 148
1 160
1 165
1 184
1 192
1 194
1 201
1 204
1 220
1 232
1 236
1 237
1 243
1 244
1 267
1 268
1 281
1 306
1 333
1 343
1 360
1 365
1 384
1 390
1 420
1 427
1 434
1 453
1 459
1 463
1 470...

output:

202675993

result:

ok 1 number(s): "202675993"

Test #67:

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

input:

1000 13331
1 57
1 101
1 153
1 228
1 265
1 323
1 324
1 336
1 371
1 382
1 420
1 428
1 430
1 474
1 495
1 507
1 567
1 702
1 715
1 721
1 722
1 735
1 739
1 749
1 773
1 825
1 831
1 894
1 923
1 972
2 32
2 41
2 99
2 113
2 139
2 154
2 190
2 200
2 227
2 234
2 237
2 254
2 274
2 308
2 333
2 335
2 352
2 432
2 446...

output:

510735315

result:

ok 1 number(s): "510735315"

Test #68:

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

input:

1000 13324
1 62
1 71
1 79
1 104
1 145
1 224
1 324
1 345
1 393
1 405
1 415
1 451
1 512
1 589
1 640
1 661
1 760
1 786
1 788
1 828
1 860
1 889
1 971
2 17
2 40
2 52
2 56
2 99
2 115
2 125
2 182
2 284
2 300
2 312
2 326
2 394
2 466
2 467
2 505
2 626
2 657
2 676
2 685
2 687
2 688
2 691
2 711
2 717
2 752
2 7...

output:

128609606

result:

ok 1 number(s): "128609606"

Test #69:

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

input:

1000 77777
1 2
1 5
1 8
1 17
1 19
1 22
1 28
1 29
1 34
1 48
1 55
1 58
1 76
1 100
1 109
1 110
1 121
1 122
1 123
1 130
1 131
1 132
1 133
1 137
1 143
1 149
1 150
1 153
1 164
1 176
1 177
1 190
1 192
1 195
1 196
1 206
1 208
1 223
1 225
1 229
1 237
1 240
1 250
1 253
1 255
1 259
1 264
1 279
1 287
1 291
1 294...

output:

202675993

result:

ok 1 number(s): "202675993"