QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200873#6673. Be Careful 2yllcmWA 8934ms959064kbC++146.7kb2023-10-04 21:51:512023-10-04 21:51:52

Judging History

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

  • [2023-10-04 21:51:52]
  • 评测
  • 测评结果:WA
  • 用时:8934ms
  • 内存:959064kb
  • [2023-10-04 21:51:51]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define mp make_pair
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 5e3 + 10;
const int P = 998244353;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int n, m, k;
int tot1, tot2;
int ls1[N], ls2[N];
pii a[N];
void disc() {
  for(int i = 1; i <= k; i++)ls1[++tot1] = a[i].FR;
  for(int i = 1; i <= k; i++)ls2[++tot2] = a[i].SE;
  sort(ls1 + 1, ls1 + 1 + tot1);
  tot1 = unique(ls1 + 1, ls1 + 1 + tot1) - (ls1 + 1);
  sort(ls2 + 1, ls2 + 1 + tot2);
  tot2 = unique(ls2 + 1, ls2 + 1 + tot2) - (ls2 + 1);
  for(int i = 1; i <= k; i++) {
    a[i].FR = lower_bound(ls1 + 1, ls1 + 1 + tot1, a[i].FR) - ls1;
    a[i].SE = lower_bound(ls2 + 1, ls2 + 1 + tot2, a[i].SE) - ls2;
  }
  return ;
}
vector<int> A[N];
struct UFS {
  int L[N], R[N];
  void init() {
    for(int i = 1; i <= tot2 + 1; i++)L[i] = R[i] = i;
    return ;
  }
  int ql(int x) {return L[x] == x ? x : L[x] = ql(L[x]);}
  int qr(int x) {return R[x] == x ? x : R[x] = qr(R[x]);}
  void del(int x) {L[x] = x - 1; R[x] = x + 1;}
}ufs;
int sum1[N][N], sum2[N][N], vis[N][N];
int calc2(int l, int r) {
  int i6 = 166374059, res = 0;
  auto _calc = [&](int r) {
    int v1 = 1ll * r * (r + 1) % P, v2 = (2ll * r + 1) % P;
    return 1ll * v1 * v2 % P * i6 % P;
  };
  add(res, _calc(r)); sub(res, _calc(l - 1));
  return res;
}
int calc3(int l, int r) {
  int i2 = 499122177, res = 0;
  auto _calc = [&](int r) {
    int v = 1ll * r * (r + 1) % P * i2 % P;
    return 1ll * v * v % P;
  };
  add(res, _calc(r)); sub(res, _calc(l - 1));
  return res;
}
int calc4(int l, int r) {
  int i30 = 432572553, res = 0;
  auto _calc = [&](int r) {
    int v1 = 1ll * r * (r + 1) % P;
    int v2 = (2ll * r + 1) % P;
    int v3 = (3ll * r % P * r % P + 3ll * r - 1) % P;
    return 1ll * v1 * v2 % P * v3 % P * i30 % P;
  };
  add(res, _calc(r)); sub(res, _calc(l - 1));
  return res;
}
int Calc(int tv1, int td1, int tv2, int td2, int l, int r) {
  int res = 0;
  add(res, 1ll * tv1 * tv2 % P * calc2(l, r) % P);
  add(res, 1ll * (1ll * tv1 * td2 % P + 1ll * tv2 * td1 % P) % P * calc3(l, r) % P);
  add(res, 1ll * td1 * td2 % P * calc4(l, r) % P);
  return res;
}
int calc_coef(int x, int y, int z, int w) {
  int coef = 0;
  if(x == y && z == w)coef = P - 1;
  else if(x == y)coef = (sum1[x][w - 1] - sum1[x][z] ? 0 : 1);
  else if(z == w)coef = (sum2[y - 1][z] - sum2[x][z] ? 0 : 1);
  else {
    vector<pii> p;
    if(vis[x][z])p.pb(mp(0, 0));
    if(vis[x][w])p.pb(mp(0, 2));
    if(vis[y][z])p.pb(mp(2, 0));
    if(vis[y][w])p.pb(mp(2, 2));
    if(sum1[x][w - 1] - sum1[x][z])p.pb(mp(0, 1));
    if(sum1[y][w - 1] - sum1[y][z])p.pb(mp(2, 1));
    if(sum2[y - 1][z] - sum2[x][z])p.pb(mp(1, 0));
    if(sum2[y - 1][w] - sum2[x][w])p.pb(mp(1, 2));
    int f[3][3][3][3] = {0};
    for(auto t : p) {
      int u = t.FR, v = t.SE;
      // printf("%d %d\n", u, v);
      for(int i = 0; i < 3; i++) {
        for(int j = 2; j >= i; j--) {
          for(int k = 0; k < 3; k++) {
            for(int l = 2; l >= k; l--) {
              // printf("qwq:%d\n", f[i][j][k][l]);
              int ni = min(i, u), nj = max(j, u);
              int nk = min(k, v), nl = max(l, v);
              sub(f[ni][nj][nk][nl], f[i][j][k][l]);
            }
          }
        }
      }
      sub(f[u][u][v][v], 1);
    }
    coef = f[0][2][0][2];
  }
  return coef;
}
int calc(int x, int y, int z, int w) {
  int coef = calc_coef(x, y, z, w), res = 0;
  x = ls1[x]; y = ls1[y]; z = ls2[z]; w = ls2[w];
  int st = max(y - x + 2, w - z + 2);
  vector<int> p = {st, y + 1, n - x + 1, w + 1, m - z + 1, min(n, m) + 1};
  sort(p.begin(), p.end());
  p.erase(unique(p.begin(), p.end()), p.end());
  // printf("st:%d\n", st);
  for(int i = 0; i < p.size(); i++) {
    if(p[i] < st)continue;
    if(p[i] > min(n, m))continue;
    int tv1 = 1, td1 = 0, tv2 = 1, td2 = 0;
    int l = p[i], r = p[i + 1] - 1;
    if(l > r)continue;
    (x - 1 < n - p[i] ? add(tv1, x - 1) : (add(tv1, n), sub(td1, 1)));
    (y - p[i] + 1 > 0 ? (sub(tv1, y + 1), add(td1, 1)) : void());
    (z - 1 < m - p[i] ? add(tv2, z - 1) : (add(tv2, m), sub(td2, 1)));
    (w - p[i] + 1 > 0 ? (sub(tv2, w + 1), add(td2, 1)) : void());
    add(res, Calc(tv1, td1, tv2, td2, l, r));
    // printf("range:%d %d %d\n", l, r, Calc(tv1, td1, tv2, td2, 5, 5));
  }
  // printf("calc:%d %d %d %d %d %d\n", x, y, z, w, coef, res);
  return 1ll * res * coef % P;
}
int main() {
  n = read(); m = read(); k = read();
  for(int i = 1; i <= k; i++)a[i].FR = read(), a[i].SE = read();
  disc();
  for(int i = 1; i <= k; i++) {
    vis[a[i].FR][a[i].SE] = 1;
    sum1[a[i].FR][a[i].SE] = 1;
    sum2[a[i].FR][a[i].SE] = 1;
  }
  for(int i = 1; i <= tot1; i++) {
    for(int j = 1; j <= tot2; j++) {
      sum1[i][j] += sum1[i][j - 1];
      sum2[i][j] += sum2[i - 1][j];
    }
  }
  int ans = Calc(n + 1, P - 1, m + 1, P - 1, 1, min(n, m));
  // printf("ans:%d\n", ans);
  sort(a + 1, a + 1 + k);
  set<array<int, 4> > rec;
  for(int i = 1; i <= k; i++)rec.insert({a[i].FR, a[i].FR, a[i].SE, a[i].SE});
  // for(int i = 1; i <= k; i++)add(ans, calc(a[i].FR, a[i].FR, a[i].SE, a[i].SE));
  for(int i = 1; i <= k; i++) {
    ufs.init();
    vector<int> cnt(tot2 + 1);
    for(int j = i + 1; j <= k; j++)cnt[a[j].SE]++;
    for(int j = 1; j <= tot2; j++)if(!cnt[j])ufs.del(j);
    for(int t = k; t > i; t--) {
      if(!(--cnt[a[t].SE]))ufs.del(a[t].SE);
      if(ufs.ql(a[t].SE - 1) > a[i].SE)continue;
      if(ufs.ql(a[i].SE - 1) > a[t].SE)continue;
      int nl = min(a[i].SE, a[t].SE), nr = max(a[i].SE, a[t].SE);
      int tl = ufs.ql(nl), tr = ufs.qr(nr);
      // printf("id:%d %d %d %d\n", i, t, tl, tr);
      rec.insert({a[i].FR, a[t].FR, nl, nr});
      if(tl)rec.insert({a[i].FR, a[t].FR, tl, nr});
      if(tr <= tot2)rec.insert({a[i].FR, a[t].FR, nl, tr});
      if(tl && tr <= tot2)rec.insert({a[i].FR, a[t].FR, tl, tr});
      // add(ans, calc(a[i].FR, a[t].FR, nl, nr));
      // if(tl)add(ans, calc(a[i].FR, a[t].FR, tl, nr));
      // if(tr <= tot2)add(ans, calc(a[i].FR, a[t].FR, nl, tr));
      // if(tl && tr <= tot2)add(ans, calc(a[i].FR, a[t].FR, tl, tr));
    }
  }
  for(auto t : rec)add(ans, calc(t[0], t[1], t[2], t[3]));
  printf("%d\n", ans);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10160kb

input:

3 3 1
2 2

output:

21

result:

ok 1 number(s): "21"

Test #2:

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

input:

5 5 2
2 1
2 4

output:

126

result:

ok 1 number(s): "126"

Test #3:

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

input:

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

output:

161

result:

ok 1 number(s): "161"

Test #4:

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

input:

15 38 6
12 6
7 15
2 18
3 19
4 2
14 29

output:

80066

result:

ok 1 number(s): "80066"

Test #5:

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

input:

5145 5419 9
547 285
294 284
375 385
217 857
348 925
14 274
3104 853
184 953
794 603

output:

334363567

result:

ok 1 number(s): "334363567"

Test #6:

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

input:

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

output:

25

result:

ok 1 number(s): "25"

Test #7:

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

input:

9145 9419 12
123 456
223 456
547 285
294 284
375 385
217 857
348 925
14 274
1104 853
184 953
794 603
2234 5678

output:

921360185

result:

ok 1 number(s): "921360185"

Test #8:

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

input:

6 8 4
2 3
3 3
4 2
1 1

output:

444

result:

ok 1 number(s): "444"

Test #9:

score: 0
Accepted
time: 2207ms
memory: 351880kb

input:

1000000000 1000000000 5000
1657 1
1644 1
1000000 116362
1186 1
2392 1
1560 1
995 1
2340 1
1916 1
2143 1
1762 1
1000000 116109
1651 1
1000000 116059
2289 1
1000000 115730
1000000 115896
1000000 116499
1608 1
342 1
1000000 116949
1965 1
1000000 114571
1000000 116602
2171 1
1000000 114848
1000000 11627...

output:

80025633

result:

ok 1 number(s): "80025633"

Test #10:

score: 0
Accepted
time: 2340ms
memory: 351896kb

input:

1000000000 1000000000 5000
1 2581
1 2273
115983 1000000
116105 1000000
114552 1000000
1 1955
1 2254
116061 1000000
116182 1000000
115783 1000000
114564 1000000
116614 1000000
116229 1000000
116087 1000000
114956 1000000
1 2453
114766 1000000
115750 1000000
115448 1000000
1 1748
116665 1000000
1 2237...

output:

80025633

result:

ok 1 number(s): "80025633"

Test #11:

score: 0
Accepted
time: 3184ms
memory: 281060kb

input:

1000000000 1000000000 5000
824 1
811 1
2300000 114696
353 1
1559 1
727 1
162 1
1507 1
1083 1
1310 1
929 1
1000000 116109
818 1
1000000 116059
1456 1
1000000 115730
1000000 115896
2300000 114833
775 1
2300000 115576
2300000 115283
1132 1
1000000 114571
2300000 114936
1338 1
1000000 114848
2300000 114...

output:

537083161

result:

ok 1 number(s): "537083161"

Test #12:

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

input:

1000000000 1000000000 5000
1 1748
1 1440
115983 1000000
116105 1000000
114552 1000000
1 1122
1 1421
116061 1000000
114516 2300000
115783 1000000
114564 1000000
114948 2300000
114563 2300000
116087 1000000
114956 1000000
1 1620
114766 1000000
115750 1000000
115448 1000000
1 915
114999 2300000
1 1404
...

output:

537083161

result:

ok 1 number(s): "537083161"

Test #13:

score: 0
Accepted
time: 5235ms
memory: 204124kb

input:

1000000000 1000000000 5000
2300000 115622
1000000 116216
1000000 116852
2300000 115827
2300000 116715
1000000 116212
2300000 116390
2300000 114646
1000000 114857
2300000 116404
1000000 116398
1000000 115409
2300000 115721
1000000 116136
2300000 114925
2300000 114869
2300000 116176
1000000 115774
100...

output:

129612365

result:

ok 1 number(s): "129612365"

Test #14:

score: 0
Accepted
time: 8934ms
memory: 740056kb

input:

1000000000 1000000000 5000
116495 1000000
116269 1000000
115204 2300000
115724 1000000
116508 1000000
115095 2300000
116712 1000000
114789 2300000
115009 2300000
114795 1000000
115093 2300000
115612 1000000
116183 2300000
116140 2300000
116148 2300000
115608 2300000
115111 1000000
115058 1000000
115...

output:

129612365

result:

ok 1 number(s): "129612365"

Test #15:

score: 0
Accepted
time: 569ms
memory: 47196kb

input:

999999992 999999990 5000
1035170 5702575
3959104 3959104
3887901 7432303
11377527 9794948
6282049 47695
11781994 2037659
11292228 47695
6787467 878630
10441683 5492431
1240650 1129736
5631557 11377527
4863442 5631557
6662382 4863442
8837935 7070049
8837935 10441683
4878561 5702575
5610718 2664505
58...

output:

892807048

result:

ok 1 number(s): "892807048"

Test #16:

score: 0
Accepted
time: 6506ms
memory: 959064kb

input:

999999948 999999898 5000
6033860 10854965
57219333 28077882
18498300 33290576
34559919 16960059
40765867 73389700
9985342 17984966
54717579 26853732
13059544 23513592
56562634 27758141
19776481 35613289
6632028 11929378
14942564 7329745
7337824 13208993
33584464 60460021
13330979 6539654
32561958 58...

output:

461431823

result:

ok 1 number(s): "461431823"

Test #17:

score: 0
Accepted
time: 6601ms
memory: 958960kb

input:

999999524 999999758 5000
28630401 15905366
49821653 27672863
52823763 29343863
14406464 29362320
3914600 2178863
15379626 31340404
2382937 4856861
26445243 14692595
15255307 8475517
23233725 12911959
8922530 4954657
80413834 44658470
59845170 33233185
38234833 21236207
48814787 27111180
7919671 4397...

output:

811760775

result:

ok 1 number(s): "811760775"

Test #18:

score: 0
Accepted
time: 7004ms
memory: 605004kb

input:

999999991 999999996 5000
191981012 91509738
114514 75994027
113271868 114514
191981012 74412508
73311176 114514
55237456 114514
157017806 114514
114514 38589289
114514 48208495
50968309 114514
151891598 191981012
34509833 191981012
112566922 191981012
54162112 191981012
99866720 114514
191981012 404...

output:

477858401

result:

ok 1 number(s): "477858401"

Test #19:

score: 0
Accepted
time: 7099ms
memory: 606272kb

input:

999999997 999999992 5000
157493349 191981012
191981012 739725
191981012 103830381
191981012 56086190
163612413 114514
191981012 56630806
191981012 56513816
170698088 114514
97262819 114514
130313445 191981012
114514 113985965
114514 112636345
114514 76391763
114514 36458624
114514 35952358
114514 33...

output:

109114433

result:

ok 1 number(s): "109114433"

Test #20:

score: 0
Accepted
time: 6888ms
memory: 584784kb

input:

999999999 999999992 5000
114514 21049898
101232053 191981012
114514 14704290
114514 85418326
191981012 17641251
90959749 191981012
114514 48586425
114514 85286676
114514 85318864
180324603 191981012
73453197 114514
191981012 96571986
191981012 42295145
114514 113760745
166197584 191981012
129916604 ...

output:

239360106

result:

ok 1 number(s): "239360106"

Test #21:

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

input:

100 100 40
13 77
15 17
74 83
25 51
49 65
60 19
83 86
71 87
47 2
7 31
34 65
84 32
58 69
89 92
67 61
49 79
92 74
76 87
96 37
45 21
56 84
53 72
16 30
59 41
55 9
31 72
86 53
95 53
80 87
51 99
55 83
13 93
3 90
61 83
65 27
66 57
52 34
3 46
6 30
92 80

output:

12252760

result:

ok 1 number(s): "12252760"

Test #22:

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

input:

100 100 100
91 50
58 1
93 95
58 77
32 60
36 77
18 3
67 33
25 6
23 77
69 2
24 77
96 17
50 99
81 22
22 46
88 54
50 18
74 40
4 38
77 3
2 7
98 37
14 98
68 33
13 23
17 51
40 63
43 58
27 76
77 19
48 73
14 92
27 72
63 33
33 54
98 96
47 2
49 37
36 85
5 43
23 69
5 19
78 98
99 91
48 12
26 51
11 90
93 31
27 26...

output:

4466541

result:

ok 1 number(s): "4466541"

Test #23:

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

input:

100 100 500
87 54
94 64
78 54
80 11
74 87
84 2
72 96
8 8
19 29
3 78
62 38
28 44
60 14
56 81
91 57
64 33
75 35
98 8
26 65
87 81
94 63
86 96
1 4
74 69
90 71
96 33
13 97
97 68
52 61
50 84
27 20
22 31
7 36
15 18
17 41
49 64
13 63
18 5
57 62
38 66
54 65
35 5
62 29
2 30
21 30
83 44
40 22
29 11
83 11
30 69...

output:

550657

result:

ok 1 number(s): "550657"

Test #24:

score: 0
Accepted
time: 58ms
memory: 18136kb

input:

100 100 1500
74 35
31 76
66 71
12 96
74 92
68 67
3 4
86 29
60 40
24 12
50 11
19 20
51 95
3 14
85 64
22 60
79 18
28 48
60 70
20 88
37 23
8 75
92 46
91 13
39 18
91 88
77 47
16 96
34 58
18 44
39 70
33 21
99 99
56 27
70 32
71 32
73 98
33 51
10 35
41 29
5 70
24 44
84 51
53 71
78 33
14 55
7 25
71 1
85 24
...

output:

142410

result:

ok 1 number(s): "142410"

Test #25:

score: 0
Accepted
time: 188ms
memory: 26660kb

input:

100 100 3000
18 46
35 86
98 87
79 87
56 43
87 40
7 74
41 65
81 42
58 82
20 94
85 97
94 68
64 27
67 19
71 58
51 85
19 55
29 17
27 52
54 24
35 22
85 61
88 83
94 59
62 3
32 97
36 29
57 99
79 62
42 23
39 12
61 44
67 21
72 17
52 66
99 40
36 25
80 51
68 3
15 15
59 20
35 75
16 5
86 93
83 6
41 33
99 2
31 98...

output:

63891

result:

ok 1 number(s): "63891"

Test #26:

score: 0
Accepted
time: 488ms
memory: 44688kb

input:

100 100 4999
90 57
24 41
25 59
46 59
16 49
17 15
88 89
56 25
18 8
74 30
68 34
75 37
58 74
72 19
40 23
54 81
3 95
9 75
85 57
8 40
45 30
96 13
63 63
27 51
40 26
56 9
39 12
7 63
66 17
11 37
44 26
79 99
65 34
49 77
70 46
38 48
31 69
44 19
82 80
2 84
30 68
6 94
85 65
97 56
19 34
14 21
26 80
29 58
34 20
5...

output:

34812

result:

ok 1 number(s): "34812"

Test #27:

score: 0
Accepted
time: 491ms
memory: 43076kb

input:

100 100 5000
4 96
13 14
29 98
17 27
5 49
98 22
15 87
23 15
17 67
97 30
49 6
45 98
70 70
90 2
98 5
65 17
63 43
41 26
76 82
30 48
52 4
26 53
73 67
71 92
59 36
33 46
15 14
98 27
55 69
98 52
50 17
69 25
82 95
49 28
87 10
98 36
8 82
16 97
32 18
10 30
47 33
30 88
33 93
92 85
9 3
31 89
27 20
38 76
88 64
58...

output:

34455

result:

ok 1 number(s): "34455"

Test #28:

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

input:

100 2000 40
82 172
10 1709
49 504
80 1874
54 1543
65 1552
68 1116
89 501
62 1279
36 1385
36 1027
78 1662
58 1031
17 545
68 875
93 1837
56 1758
27 1845
46 1007
57 721
35 1153
77 76
18 889
68 27
49 863
15 885
72 264
88 1747
28 1808
26 1265
94 1838
21 1947
71 1220
51 709
80 491
34 1121
29 1878
57 638
4...

output:

476630897

result:

ok 1 number(s): "476630897"

Test #29:

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

input:

100 2000 100
64 1327
7 1857
34 130
52 998
50 122
98 1720
90 15
37 305
66 1956
97 1335
5 1223
98 717
94 182
18 931
58 159
92 1212
47 815
23 59
87 1735
76 133
98 1397
45 17
87 1529
16 1071
87 1722
56 645
17 408
34 1599
96 1684
16 843
35 1245
62 1630
38 539
4 598
92 849
92 1424
68 892
5 1304
66 103
94 ...

output:

874863095

result:

ok 1 number(s): "874863095"

Test #30:

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

input:

100 2000 500
60 1213
50 1837
19 1974
70 1136
92 1979
54 1180
49 211
76 1898
56 536
85 1091
6 118
3 254
66 393
28 1889
72 72
27 1122
35 112
75 616
44 1378
60 69
28 806
37 929
94 735
76 1146
5 707
40 1638
8 1900
90 760
18 135
43 1519
85 775
28 579
36 935
4 1458
46 1499
8 1613
82 540
75 1700
74 210
96 ...

output:

545166322

result:

ok 1 number(s): "545166322"

Test #31:

score: 0
Accepted
time: 39ms
memory: 17528kb

input:

100 2000 1500
49 1888
86 1376
46 856
79 17
45 697
92 1752
52 1378
63 1442
7 882
71 1370
96 702
52 497
93 897
74 249
63 1655
80 90
46 1904
27 371
15 1265
92 214
89 1812
87 719
45 823
15 1708
3 827
99 850
63 1180
6 401
87 124
77 32
2 377
85 627
40 169
14 281
14 1101
12 314
14 447
19 1781
51 626
90 745...

output:

148961647

result:

ok 1 number(s): "148961647"

Test #32:

score: 0
Accepted
time: 138ms
memory: 22472kb

input:

100 2000 3000
93 1277
2 1750
66 1555
38 1627
23 1251
4 332
68 266
18 1078
24 1386
6 1444
70 673
28 806
28 629
31 456
42 1407
26 545
22 1643
27 409
79 1991
95 394
94 1614
15 680
26 399
20 86
66 94
75 306
18 345
30 836
46 1023
11 1655
26 513
77 1336
72 588
86 505
38 274
98 96
34 691
84 627
2 1788
53 1...

output:

56815774

result:

ok 1 number(s): "56815774"

Test #33:

score: 0
Accepted
time: 309ms
memory: 31448kb

input:

100 2000 4999
69 141
90 319
92 570
13 503
74 817
41 1656
33 1735
29 1366
52 419
26 1608
15 417
17 1193
91 1056
31 1797
18 544
5 1792
81 1881
12 255
24 1177
75 1534
96 277
84 1562
8 1665
49 91
13 120
72 953
29 539
96 1831
51 1903
50 1843
27 1337
22 1178
73 307
59 1951
28 1431
79 911
66 1530
89 969
5 ...

output:

29031348

result:

ok 1 number(s): "29031348"

Test #34:

score: 0
Accepted
time: 306ms
memory: 30960kb

input:

100 2000 5000
78 1655
79 1968
97 1538
75 1328
75 780
24 1025
64 1775
99 1319
59 877
49 705
95 597
83 921
9 523
49 367
76 553
28 1623
30 1616
52 145
23 296
98 662
5 249
6 1095
18 982
2 793
31 1941
49 1670
9 1596
88 467
40 1178
34 220
34 318
15 1014
98 130
64 465
56 1356
40 257
46 108
60 1406
54 373
9...

output:

28106075

result:

ok 1 number(s): "28106075"

Test #35:

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

input:

100 1000000000 40
91 906492795
44 220406215
46 697653054
57 115159754
41 410299001
2 856461372
11 829769415
19 154206891
87 111013909
2 558231357
53 227124152
8 25775632
77 819248359
66 956427714
23 438568455
40 885638653
93 953383697
97 674250396
91 168010516
71 425324837
84 679265396
92 438925795
...

output:

308636238

result:

ok 1 number(s): "308636238"

Test #36:

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

input:

100 1000000000 100
13 107090664
57 269885036
71 253364299
23 124674877
34 158640158
34 212481096
97 96462559
5 905248661
7 721358783
36 406914955
93 304044767
10 758826649
86 870834795
22 78209124
95 821043354
15 747758089
79 209048751
10 92632533
40 167864124
54 140677453
8 260747605
32 673110337
3...

output:

15721069

result:

ok 1 number(s): "15721069"

Test #37:

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

input:

100 1000000000 500
9 884176880
92 685216500
60 349365908
33 909262376
80 346546370
90 933603462
52 93869530
44 694779448
96 634413542
16 534218862
98 895186467
18 257872364
50 304205239
24 979628465
10 212894893
61 705524564
66 695239491
58 881000335
1 718387750
29 744828497
37 746039846
17 96409865...

output:

732332250

result:

ok 1 number(s): "732332250"

Test #38:

score: 0
Accepted
time: 43ms
memory: 18068kb

input:

100 1000000000 1500
3 874996650
86 465478752
71 678518381
8 721100871
65 36660500
46 628307861
25 249070752
48 926487045
51 101624043
78 8109175
75 39868981
67 361110166
44 222180507
91 738700669
37 490125317
94 462382018
80 201684972
10 80444765
15 309604275
37 731634425
5 810314270
24 229206345
47...

output:

753671314

result:

ok 1 number(s): "753671314"

Test #39:

score: 0
Accepted
time: 140ms
memory: 22308kb

input:

100 1000000000 3000
46 315468771
89 795555094
87 273919299
75 763599031
39 557565439
69 561796240
29 858884876
98 867636821
76 947865397
13 149920455
45 960937190
30 581327774
82 994611919
48 695928933
27 814619938
41 453055204
57 78794097
97 664376126
79 381113636
39 183850392
13 863767314
52 77581...

output:

165068431

result:

ok 1 number(s): "165068431"

Test #40:

score: 0
Accepted
time: 355ms
memory: 31100kb

input:

100 1000000000 4999
23 981436455
78 697469606
14 778058249
45 580983878
98 690859674
94 768219874
7 799618639
14 218210131
9 313076636
33 658739035
97 571652795
20 699689049
43 479246235
49 563485912
99 130776916
32 135723448
17 658033163
90 77170696
28 663286691
28 383151393
4 26990484
21 856223099...

output:

162258766

result:

ok 1 number(s): "162258766"

Test #41:

score: 0
Accepted
time: 365ms
memory: 32012kb

input:

100 1000000000 5000
28 127064660
67 990623740
19 94387764
21 184315217
94 518385844
85 794171229
37 583105000
84 199077103
4 549302796
56 626057952
70 523247708
86 920946496
59 996375805
66 707676893
58 418428414
39 518883170
65 402514408
23 581452060
23 804453957
39 532845441
24 729930201
46 445780...

output:

493451776

result:

ok 1 number(s): "493451776"

Test #42:

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

input:

1000 100 40
815 84
52 18
361 39
621 81
492 73
694 1
88 43
393 97
369 21
758 85
905 68
461 73
392 45
866 32
26 96
816 17
858 49
828 10
976 41
169 91
327 82
669 20
796 50
559 24
314 82
547 14
473 74
715 77
235 76
896 15
548 34
451 80
387 97
223 49
713 17
828 57
758 70
103 64
687 39
560 85

output:

258922145

result:

ok 1 number(s): "258922145"

Test #43:

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

input:

1000 100 100
490 7
149 93
485 65
309 82
31 86
267 56
687 1
711 65
877 66
417 19
871 45
652 43
430 42
777 45
486 45
764 99
690 73
446 68
850 41
470 62
805 93
510 89
32 97
482 84
300 38
60 74
861 8
828 32
790 24
913 38
847 81
229 19
393 39
492 55
379 58
503 57
398 1
700 27
916 21
888 72
28 25
382 3
26...

output:

887311204

result:

ok 1 number(s): "887311204"

Test #44:

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

input:

1000 100 500
834 15
787 54
830 24
187 21
541 10
188 68
772 94
979 37
177 85
369 20
99 85
552 14
115 40
234 22
814 81
72 95
921 53
804 50
74 66
675 5
69 54
279 80
444 68
420 47
885 84
414 72
983 45
628 41
938 28
810 46
630 81
549 75
102 82
412 4
234 66
672 70
394 76
784 21
421 50
943 57
994 35
601 33...

output:

127131287

result:

ok 1 number(s): "127131287"

Test #45:

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

input:

1000 100 1500
603 80
292 38
376 94
475 36
688 75
225 80
775 94
369 70
191 9
73 82
242 78
707 8
914 67
600 54
651 80
482 12
616 95
320 62
775 40
75 63
141 93
33 14
943 88
432 88
136 8
766 13
638 19
840 4
644 22
169 65
919 74
836 19
295 75
247 72
627 25
213 17
840 38
144 99
584 43
618 8
557 4
129 50
8...

output:

27193936

result:

ok 1 number(s): "27193936"

Test #46:

score: 0
Accepted
time: 162ms
memory: 78896kb

input:

1000 100 3000
350 91
134 52
423 12
820 31
185 26
915 54
985 53
509 98
49 22
566 53
522 70
588 85
547 48
372 62
795 47
753 2
467 63
964 66
149 94
415 26
709 90
581 51
614 11
35 63
423 57
705 27
279 69
319 36
576 13
962 76
728 53
854 73
282 98
541 89
858 15
376 55
972 62
435 26
405 43
82 74
98 89
453 ...

output:

11057434

result:

ok 1 number(s): "11057434"

Test #47:

score: 0
Accepted
time: 381ms
memory: 98224kb

input:

1000 100 4999
641 94
258 7
643 83
270 3
811 31
813 24
707 76
570 61
239 80
817 96
917 17
785 24
875 50
120 51
8 46
930 33
464 73
748 82
377 28
162 14
861 84
358 46
20 10
299 22
159 20
298 41
758 83
124 67
388 21
422 56
593 60
831 61
421 88
181 54
664 40
42 30
419 83
200 21
759 67
737 57
698 39
305 7...

output:

5859428

result:

ok 1 number(s): "5859428"

Test #48:

score: 0
Accepted
time: 379ms
memory: 96104kb

input:

1000 100 5000
106 35
76 76
8 23
308 70
88 32
265 32
463 67
567 43
156 32
52 2
584 81
833 90
689 42
192 30
237 25
184 68
497 21
999 33
850 49
189 18
660 66
478 83
273 18
496 72
466 38
316 66
549 89
354 26
894 77
765 70
581 47
937 85
767 50
424 96
319 8
399 26
493 92
222 99
655 14
933 94
806 15
284 68...

output:

5722436

result:

ok 1 number(s): "5722436"

Test #49:

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

input:

1000 2000 40
64 701
722 362
64 1299
754 1805
380 616
566 1903
781 1619
903 1871
230 977
497 922
209 637
656 261
576 894
222 733
900 104
277 1872
523 1756
297 132
250 538
523 689
650 749
567 648
114 1231
311 1835
205 1980
18 371
919 665
920 274
46 908
40 1034
409 1476
319 1301
44 168
444 990
445 986
...

output:

142200714

result:

ok 1 number(s): "142200714"

Test #50:

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

input:

1000 2000 100
684 1360
268 1574
85 1382
690 114
705 863
453 1825
15 201
919 559
579 944
970 1464
111 419
169 560
898 1549
453 1278
732 302
50 735
216 1223
617 1523
635 250
139 153
253 299
887 102
556 1217
765 301
772 70
533 806
961 1556
723 1040
800 1576
93 1307
342 1975
507 1802
783 864
225 1421
87...

output:

173515609

result:

ok 1 number(s): "173515609"

Test #51:

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

input:

1000 2000 500
108 1246
470 217
947 37
568 252
216 722
374 768
537 398
626 153
236 1522
405 411
855 1168
506 243
226 1614
347 91
418 70
793 938
446 666
538 227
858 1229
826 606
953 1561
701 497
968 277
703 1039
358 1200
405 1799
3 1195
86 571
431 1362
427 1837
481 1505
186 89
492 1260
144 428
22 1896...

output:

554189117

result:

ok 1 number(s): "554189117"

Test #52:

score: 0
Accepted
time: 56ms
memory: 56936kb

input:

1000 2000 1500
410 1420
794 1051
182 1573
884 1027
170 1309
828 1237
310 1854
239 389
499 1053
817 1610
981 803
391 750
415 63
33 560
348 1588
350 1615
235 45
762 1535
419 174
732 1593
488 1128
781 162
816 38
171 1544
813 250
16 1039
910 1947
955 350
512 1439
314 1188
810 877
838 95
90 549
932 1594
...

output:

238838802

result:

ok 1 number(s): "238838802"

Test #53:

score: 0
Accepted
time: 147ms
memory: 71704kb

input:

1000 2000 3000
594 810
636 1425
310 936
25 1300
104 381
955 334
3 80
941 25
715 748
748 1539
342 257
273 1059
565 1794
242 104
492 822
826 1552
86 1930
888 92
792 900
509 1481
57 1594
250 1976
50 1614
649 1921
664 34
874 494
631 1113
791 785
801 1821
108 148
699 1013
294 141
951 821
788 1964
648 671...

output:

654807693

result:

ok 1 number(s): "654807693"

Test #54:

score: 0
Accepted
time: 328ms
memory: 78016kb

input:

1000 2000 4999
805 1010
323 1847
13 1950
37 1366
731 1283
417 1658
804 213
877 312
468 443
642 1848
737 664
470 1445
377 367
553 1962
703 1958
440 654
163 168
315 1419
21 1939
336 915
646 256
544 713
892 735
913 1409
961 1542
467 1805
31 1306
596 1263
738 1073
210 336
485 1691
271 500
92 687
865 126...

output:

793206926

result:

ok 1 number(s): "793206926"

Test #55:

score: 0
Accepted
time: 321ms
memory: 83796kb

input:

1000 2000 5000
832 1187
140 308
813 919
75 856
7 56
305 218
997 1588
438 411
822 239
314 946
966 35
80 1174
628 1834
62 532
933 1967
51 1294
989 1902
5 1163
493 1868
284 43
8 1418
664 393
226 198
673 629
706 1364
485 1859
821 364
469 417
682 494
910 712
473 818
582 1526
437 364
110 1778
109 418
47 1...

output:

597537195

result:

ok 1 number(s): "597537195"

Test #56:

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

input:

1000 1000000000 40
77 103727882
653 318241889
946 349212567
393 387746557
885 713394545
863 439584423
809 84023534
125 492837794
326 987465290
296 889547838
698 216417880
662 236899348
679 329988738
116 920708460
251 927778395
14 489733306
495 238693006
282 638590509
569 679174340
40 787268400
274 6...

output:

723916280

result:

ok 1 number(s): "723916280"

Test #57:

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

input:

1000 1000000000 100
618 526348331
775 100181278
816 708261363
293 993365232
551 369890766
112 882347154
346 89786899
513 579936592
685 536753990
148 210330348
234 442777116
454 549159447
491 379099400
96 394301462
115 192337929
462 981936402
661 375633818
769 847174570
479 566659166
543 799533412
94...

output:

346357608

result:

ok 1 number(s): "346357608"

Test #58:

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

input:

1000 1000000000 500
962 8467247
494 810480042
243 726115118
91 482985432
499 340977533
595 898436821
868 792226569
782 369467379
904 744776050
225 337634255
541 328886116
354 48205162
738 812469843
552 590688103
880 584189468
768 644735576
892 783676704
690 340575073
264 412150093
230 620503903
129 ...

output:

670463729

result:

ok 1 number(s): "670463729"

Test #59:

score: 0
Accepted
time: 50ms
memory: 60788kb

input:

1000 1000000000 1500
565 597119310
705 944900872
380 439122090
539 233695406
4 109762178
22 999884242
981 387467107
541 871838968
399 164310220
124 623159092
91 11151400
656 990020054
786 871634647
298 193779180
224 507996155
589 678921029
865 463293945
499 444952960
82 966633948
528 229262266
673 8...

output:

404642399

result:

ok 1 number(s): "404642399"

Test #60:

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

input:

1000 1000000000 3000
669 742624131
547 569944515
990 407638161
242 493013012
455 552519263
195 638405322
112 997281231
244 29808191
257 88699430
55 175035772
451 854071755
100 427057109
981 939033361
507 72859590
931 127458077
985 964561516
153 340403071
144 323851623
455 333110611
947 681478231
884...

output:

446439892

result:

ok 1 number(s): "446439892"

Test #61:

score: 0
Accepted
time: 374ms
memory: 78552kb

input:

1000 1000000000 4999
960 920378562
671 176891727
773 833629257
691 388545713
2 58928654
93 844828956
913 938014994
742 163562054
10 158943367
868 351936808
846 542935214
297 328598938
231 423667676
256 18564423
143 148647753
117 647229760
230 919642136
490 736646191
683 615283665
694 175746533
474 4...

output:

791232707

result:

ok 1 number(s): "791232707"

Test #62:

score: -100
Wrong Answer
time: 379ms
memory: 79924kb

input:

1000 1000000000 5000
550 849187319
489 470045862
12 933139325
729 618761897
402 886454822
62 870780310
107 721501355
739 144429026
802 690136827
620 319255724
76 494530127
345 844823685
562 235764547
764 162755404
373 731266552
290 30389483
700 742271235
259 240927556
157 539631486
285 325440581
273...

output:

144278122

result:

wrong answer 1st numbers differ - expected: '446268006', found: '144278122'