QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#591548#4811. Be CarefulCryingAC ✓308ms9048kbC++144.7kb2024-09-26 16:22:302024-09-26 16:22:30

Judging History

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

  • [2024-09-26 16:22:30]
  • 评测
  • 测评结果:AC
  • 用时:308ms
  • 内存:9048kb
  • [2024-09-26 16:22:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 210,M = 22,mod = 998244353,INF = 1e9;
int addv(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
void add(int& x,int y){x = addv(x,y);}
//
int n,f[N][N],C[N][N],tag[N];

int pre[N][N],pw[N][N],deg[N];

vector<int> e[N];

int arr[N],tot,cnt,rx,rw;
int barr[N],id[N],bg[N][N],cur;

int dp[2][1<<M];
vector<int> dp2[2][N];

void dfs(int u,int fa){
    tag[u] = (e[u].size() == 1 && fa);
    if(tag[u])return;
    for(auto v : e[u])if(v^fa)dfs(v,u),deg[u]++;
    tot = cnt = 0; 
    for(auto v : e[u])if(v^fa){
        if(tag[v])cnt++;
        else arr[++tot] = v;
    }
    if(!tot){ //特判菊花图
        for(int i=0;i<=cnt;i++){ //mex = i
            for(int j=i;j<=cnt;j++){
                add(f[u][i],1ll*C[cnt][j]*pre[i][j]%mod*pw[n-i][cnt-j]%mod);
            }
        }
        return;
    }
    rx = -1,rw = INF;
    for(int b=0;b<=n;b++){
        int c = 0; for(int i=1;i<=tot;i++)c += deg[arr[i]] > b;
        if(b+1+c < rw){
            rx = b,rw = b+c+1;
        }
    }
    assert(rx != -1);
    cur = 0; 
    for(int i=1;i<=tot;i++){
        int v = arr[i];
        if(deg[v] <= rx)continue;
        id[v] = cur,barr[cur++] = v;
        bg[v][n+1] = 0;
        for(int j=n;j>=0;j--)bg[v][j] = addv(bg[v][j+1],f[v][j]);
    }
    //<=rx的分一类,>rx的分一类
    for(int i=0;i<2;i++)fill(dp[i],dp[i]+(1<<rw),0);
    dp[0][0] = 1;
    for(int i=1;i<=tot;i++){
        int p = (i-1)&1,q = p^1,v = arr[i];
        for(int S=0;S<(1<<rw);S++){
            int& w = dp[p][S]; if(!w)continue;
            if(deg[v] <= rx){
                for(int j=0;j<=deg[v];j++)if(f[v][j]){
                    add(dp[q][S|(1<<j)],1ll*w*f[v][j]%mod);
                }
            }else{
                add(dp[q][S],w);
                for(int j=0;j<=rx;j++)if(f[v][j]){
                    add(dp[q][S|(1<<j)|(1<<id[v]+rx+1)],1ll*w*f[v][j]%mod);
                }
            }
            w = 0;
        }
    }
    for(int i=0;i<2;i++)for(int j=0;j<=cnt;j++){
        dp2[i][j].clear();
        dp2[i][j].resize(1<<cur,0);
    }
    for(int S=0;S<(1<<rw);S++){
        int w = dp[tot&1][S]; if(!w)continue;
        //1. 处理mex <= rx的情况
        {
            int mul = w;
            for(int i=0;i<cur;i++)if(!(S>>(rx+i+1)&1)){
                mul = 1ll*mul*bg[barr[i]][rx+1]%mod;
            }
            for(int x=0;x<=rx;x++)if(!(S>>x&1)){
                int r = 0;
                for(int y=0;y<x;y++)r += !(S>>y&1);
                for(int i=r;i<=cnt;i++)add(f[u][x],1ll*mul*C[cnt][i]%mod*pre[r][i]%mod*pw[n-r][cnt-i]%mod);
            }
        }
        //2. 处理mex > rx的情况(此时空位都由叶子节点替代)
        {
            int r = 0; for(int y=0;y<=rx;y++)r += !(S>>y&1);
            int T = 0; for(int i=0;i<cur;i++)if(S>>(rx+i+1)&1)T ^= 1<<i;
            for(int i=r;i<=cnt;i++)for(int j=0;i+j<=cnt;j++){
                add(dp2[rx&1][i+j][T],1ll*w*pre[r][i]%mod*pw[rx+1-r][j]%mod*C[i+j][j]%mod);
            }
        }
    }
    //按照值域dp
    for(int i=rx+1;i<=deg[u];i++){
        int p = (i-1)&1,q = p^1;
        //mex = i
        for(int S=0;S<(1<<cur);S++){
            int mul = 1;
            for(int j=0;j<cur;j++)if(!(S>>j&1))mul = 1ll*mul*bg[barr[j]][i+1]%mod;
            for(int j=0;j<=cnt;j++){
                int w = dp2[p][j][S]; if(!w)continue;
                add(f[u][i],1ll*w*mul%mod*C[cnt][j]%mod*pw[n-i][cnt-j]%mod);
            }
        }
        //mex > i
        for(int j=0;j<=cnt;j++)for(int S=0;S<(1<<cur);S++){
            int w = dp2[p][j][S]; if(!w)continue;
            for(int k=1;j+k<=cnt;k++)add(dp2[q][j+k][S],1ll*w*C[j+k][k]%mod);
        }
        for(int j=0;j<=cnt;j++){
            for(int k=0;k<cur;k++)for(int S=0;S<(1<<cur);S++)if(S>>k&1){
                int sum = addv(dp2[q][j][S^(1<<k)],dp2[p][j][S^(1<<k)]);
                add(dp2[q][j][S],1ll*sum*f[barr[k]][i]%mod);
            }
        }
        for(int j=0;j<=cnt;j++)fill(dp2[p][j].begin(),dp2[p][j].end(),0); //clear
    }
}

int main(){
    cin>>n;
    for(int i=0;i<=n;i++){
        C[i][0] = 1;
        for(int j=1;j<=i;j++)C[i][j] = addv(C[i-1][j-1],C[i-1][j]);
    }
    for(int i=0;i<=n;i++){
        pw[i][0] = 1;
        for(int j=1;j<=n;j++)pw[i][j] = 1ll*pw[i][j-1]*i%mod;
    }
    if(n==1)return (cout<<"1 1"),0;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    pre[0][0] = 1;
    for(int i=0;i<n;i++)for(int j=0;j<=n;j++)for(int k=1;j+k<=n;k++)add(pre[i+1][j+k],1ll*pre[i][j]*C[j+k][k]%mod);
    dfs(1,0);

    for(int i=0;i<=n;i++)cout<<f[1][i]<<"\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 2
1 3
2 4
2 5

output:

55
127
34
0
0
0

result:

ok 6 numbers

Test #2:

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

input:

8
1 2
1 3
1 4
1 5
1 6
6 7
6 8

output:

69632
265534
133905
47790
12636
1944
0
0
0

result:

ok 9 numbers

Test #3:

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

input:

3
1 2
2 3

output:

1
3
0
0

result:

ok 4 number(s): "1 3 0 0"

Test #4:

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

input:

2
1 2

output:

2
1
0

result:

ok 3 number(s): "2 1 0"

Test #5:

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

input:

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

output:

1755647
612579511
359376750
200038110
104287680
49974120
21379680
7771680
2177280
362880
0

result:

ok 11 numbers

Test #6:

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

input:

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

output:

114358881
100000000
0
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #7:

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

input:

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

output:

10
1
0
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #8:

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

input:

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

output:

27510
31142
102399
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #9:

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

input:

14
10 3
6 2
2 8
3 13
1 3
1 2
3 14
4 2
9 3
12 3
2 5
7 2
11 3

output:

930962871
780146137
253920328
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 15 numbers

Test #10:

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

input:

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

output:

572808214
694156482
763085092
958730326
465749894
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 21 numbers

Test #11:

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

input:

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

output:

778184256
242901486
277265229
855621813
564317020
918444623
408876720
314039448
593931360
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 22 numbers

Test #12:

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

input:

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

output:

142157709
5878180
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 23 numbers

Test #13:

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

input:

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

output:

7619809
175546557
7936610
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 24 numbers

Test #14:

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

input:

24
7 10
2 5
2 1
17 20
1 4
16 13
7 4
19 16
23 20
11 8
10 13
1 3
22 19
5 8
3 6
17 14
21 18
24 21
18 15
9 6
9 12
14 11
15 12

output:

24
576
15025
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 25 numbers

Test #15:

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

input:

24
22 16
17 11
15 9
13 7
8 2
1 3
5 1
6 12
9 3
14 8
21 15
17 23
19 13
7 1
24 18
2 1
5 11
1 4
4 10
18 12
20 14
10 16
1 6

output:

24
7962624
236177977
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 25 numbers

Test #16:

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

input:

200
1 199
95 1
1 75
177 1
66 1
157 1
85 1
1 193
1 26
8 1
38 1
151 1
1 56
63 1
1 138
1 59
190 1
1 36
1 120
156 1
115 1
1 118
171 1
6 1
113 1
20 1
83 1
1 176
33 1
153 1
1 169
22 1
1 159
1 27
87 1
1 129
1 44
174 1
1 93
77 1
1 122
1 125
1 23
1 81
112 1
173 1
1 51
32 1
96 1
184 1
116 1
67 1
1 94
1 104
19...

output:

211917199
369375874
201944418
582671162
183066248
639389350
952947539
137147613
216366713
398936459
73236543
354059031
727857197
121548413
610762100
573534011
706945631
286154195
226699593
267771858
823273748
233587424
176942776
226493975
707601105
339075191
694353149
944734662
932707579
934386415
4...

result:

ok 201 numbers

Test #17:

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

input:

200
2 199
95 2
2 75
177 2
66 2
157 2
85 2
2 193
2 26
8 2
38 2
151 2
2 56
63 2
2 138
2 59
190 2
2 36
2 120
156 2
115 2
2 118
171 2
6 2
113 2
20 2
83 2
2 176
33 2
153 2
2 169
22 2
2 159
2 27
87 2
2 129
2 44
174 2
2 93
77 2
2 122
2 125
2 23
2 81
112 2
173 2
2 51
32 2
96 2
184 2
116 2
67 2
2 94
2 104
19...

output:

356210711
85910356
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #18:

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

input:

200
198 199
95 94
74 75
177 176
66 65
157 156
85 84
192 193
25 26
8 7
38 37
151 150
55 56
63 62
137 138
58 59
190 189
35 36
119 120
156 155
115 114
117 118
171 170
6 5
113 112
20 19
83 82
175 176
33 32
153 152
168 169
22 21
158 159
26 27
87 86
128 129
43 44
174 173
92 93
77 76
121 122
124 125
22 23
...

output:

200
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #19:

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

input:

199
176 177
115 116
47 48
29 30
120 119
7 8
93 94
158 159
118 117
28 29
185 186
133 132
24 25
76 77
55 54
68 69
96 95
65 66
172 171
114 113
127 128
91 92
106 107
70 71
135 136
83 82
187 188
146 147
23 22
36 37
195 196
166 165
81 80
109 108
8 9
21 20
41 42
125 124
46 47
87 86
133 134
38 37
174 173
12...

output:

1
199
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200 numbers

Test #20:

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

input:

200
28 56
82 165
53 107
94 188
67 134
51 102
69 139
18 37
10 20
33 66
179 89
156 78
53 106
93 186
113 56
9 19
8 16
65 130
33 16
41 82
37 74
197 98
26 53
18 36
195 97
30 60
132 66
81 162
61 30
40 81
26 52
168 84
79 39
128 64
27 54
68 136
91 45
40 20
122 61
108 54
3 6
118 59
91 182
177 88
15 31
133 66...

output:

115157040
769068498
218666068
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #21:

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

input:

200
51 153
118 39
23 68
26 9
163 54
7 2
21 62
174 58
125 42
50 150
15 46
32 95
186 62
53 158
7 22
29 88
165 55
47 140
9 3
18 6
20 59
131 44
90 30
149 50
35 12
11 32
15 5
4 13
110 37
160 53
3 10
51 152
154 51
37 12
94 31
119 40
49 146
196 65
16 48
46 138
4 12
116 39
74 25
27 81
105 35
61 182
18 55
19...

output:

96831322
243739289
839032182
347339046
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #22:

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

input:

200
4 1
40 159
6 22
16 65
7 29
7 2
10 39
103 26
24 97
180 45
24 6
47 186
50 200
140 35
15 61
10 38
127 32
93 23
18 73
185 46
23 91
29 115
126 32
35 9
120 30
22 86
20 79
7 27
35 139
148 37
26 105
18 70
198 50
190 48
136 34
147 37
25 98
39 155
40 158
199 50
67 17
75 19
8 2
109 27
160 40
176 44
23 90
1...

output:

868579713
768926703
473674519
835466001
35818891
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #23:

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

input:

200
124 21
53 9
5 28
33 199
145 24
20 119
24 140
31 5
86 15
30 176
12 69
172 29
116 20
14 3
11 66
3 15
75 13
13 76
144 24
79 13
72 12
80 14
1 7
70 12
23 135
178 30
33 197
30 179
9 55
27 159
18 3
25 151
11 62
18 107
82 14
30 180
23 138
31 182
16 94
97 16
93 16
173 29
32 190
10 2
8 2
18 104
6 35
111 1...

output:

298503373
243520600
324348437
233414660
209600209
600025942
504289019
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #24:

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

input:

200
6 61
5 47
14 141
16 161
144 15
48 5
115 12
147 15
175 18
19 186
86 9
75 8
109 11
158 16
169 17
62 7
135 14
97 10
1 6
3 23
9 87
42 5
73 8
20 200
152 16
14 132
90 9
21 2
4 34
4 37
181 18
71 7
1 9
84 9
180 18
56 6
127 13
6 52
12 121
137 14
7 64
11 105
156 16
15 146
6 59
1 4
83 9
8 74
6 60
69 7
10 1...

output:

107615921
75193607
506753286
400364397
127708406
597309377
407829846
269700097
404852842
311884298
159659723
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #25:

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

input:

200
83 7
8 92
107 9
31 3
19 2
6 72
140 12
186 16
22 2
131 11
6 66
14 169
21 2
120 10
16 193
39 4
85 7
15 177
155 13
183 16
176 15
4 47
4 38
110 10
12 143
3 37
11 122
171 15
69 6
195 17
9 102
144 12
158 14
1 8
166 14
117 10
13 154
179 15
17 194
88 8
6 64
2 23
15 181
14 160
17 197
173 15
81 7
147 13
8...

output:

820487232
168056104
389303904
786803166
747859949
163201436
184471655
286943236
734039879
217802148
477672105
313993286
576453384
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #26:

score: 0
Accepted
time: 19ms
memory: 6380kb

input:

200
101 8
56 5
140 11
15 193
10 129
5 54
6 68
200 16
13 161
13 169
170 13
162 13
102 8
134 11
1 6
130 10
3 33
15 188
2 17
13 163
71 6
4 51
22 2
149 12
8 96
3 30
7 82
143 11
34 3
119 10
6 76
67 6
46 4
9 108
78 6
113 9
4 50
11 132
3 29
172 14
13 167
16 199
5 62
4 1
144 11
10 121
26 2
15 194
11 1
39 3
...

output:

941560284
156408143
117860855
71504118
286002901
82236540
656386501
984288699
392292354
375678581
525101177
448561345
88856629
222487029
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #27:

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

input:

200
50 4
2 21
175 13
181 13
13 178
9 121
2 17
2 22
169 12
1 5
5 62
11 1
10 138
141 10
185 14
85 6
70 5
3 40
109 8
9 124
67 5
173 13
180 13
42 3
15 199
81 6
7 87
3 39
2 24
79 6
9 117
143 11
187 14
8 111
14 191
12 162
72 6
6 1
184 14
12 166
149 11
1 2
125 9
3 31
192 14
2 26
37 3
4 54
6 73
10 128
76 6
...

output:

306791307
41136979
825727064
348896251
156923421
279326908
271414153
908884019
949859290
556906447
15321817
192929720
228240965
575859246
416336706
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #28:

score: 0
Accepted
time: 24ms
memory: 8440kb

input:

200
80 6
161 11
171 12
1 8
149 10
199 14
3 35
23 2
10 137
181 12
14 197
194 13
6 1
170 12
11 163
40 3
2 22
98 7
2 1
112 8
13 189
10 146
5 75
152 11
4 60
7 1
1 12
5 68
13 195
7 96
5 1
7 99
191 13
192 13
85 6
12 180
8 115
84 6
5 65
62 5
7 94
12 176
7 93
91 6
13 193
52 4
97 7
169 12
175 12
119 8
27 2
1...

output:

375700468
841467400
95878319
402414369
68557938
507243391
676135012
644304562
901473491
929659471
585508574
712959512
934381768
127474324
178642636
136722763
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #29:

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

input:

200
5 67
12 183
27 2
61 4
3 42
11 1
9 145
195 13
70 5
6 88
90 6
9 131
11 177
150 10
9 134
181 12
6 91
66 5
8 117
41 3
13 194
12 192
5 79
8 116
153 10
57 4
11 167
11 174
5 68
8 114
104 7
10 160
4 63
111 7
2 33
8 128
1 12
7 106
84 6
10 146
64 4
9 142
6 86
2 28
196 13
11 169
69 5
3 49
180 12
197 13
44 ...

output:

454407602
674233339
454140458
700043053
911075695
40301477
62906126
431577241
416730741
66443526
398638542
414791907
770049972
283660406
297155821
660719567
642885794
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #30:

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

input:

200
11 198
5 83
147 8
2 25
151 8
100 6
11 195
10 190
2 32
106 6
129 7
97 6
2 24
10 191
8 150
45 3
86 5
9 156
42 3
78 5
163 9
8 142
1 16
11 196
135 8
80 5
107 6
6 103
145 8
11 1
8 140
10 174
5 85
8 139
10 183
120 7
5 93
9 159
20 1
171 9
185 10
10 175
5 84
96 5
179 10
6 111
9 165
47 3
4 65
10 173
68 4...

output:

193649645
70858212
117077553
972546030
132069817
476552562
7144257
322512914
697824020
128753868
398911725
186468018
642094064
222958766
245919119
683616925
245324017
957573487
310792461
691433383
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #31:

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

input:

200
59 3
3 46
9 180
49 3
31 2
4 66
187 10
7 132
35 2
7 122
117 6
10 188
197 10
1 18
4 72
9 177
107 6
5 83
82 5
198 10
5 93
1 8
6 109
8 156
20 1
141 7
133 7
1 10
4 76
10 186
30 2
94 5
4 74
152 8
1 19
9 171
3 45
65 4
145 8
143 8
189 10
161 8
48 3
163 9
13 1
127 7
3 44
194 10
55 3
1 21
4 1
81 4
2 24
8 ...

output:

710868772
164314667
884964622
975464568
409864565
201789956
689019709
595324454
388273171
607706268
428445229
156837390
750235524
920745519
846235936
448135763
701107222
850826991
373542500
109127930
11115067
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers

Test #32:

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

input:

200
109 6
89 5
10 194
7 131
5 92
4 66
78 4
160 8
8 155
172 9
2 41
8 165
7 137
5 87
8 166
180 9
1 2
111 6
2 36
6 123
2 43
125 6
8 161
40 2
46 3
77 4
30 2
4 67
124 6
9 186
200 10
7 1
94 5
57 3
6 122
1 5
5 96
3 50
27 2
48 3
175 9
149 8
10 195
7 143
2 39
145 7
8 159
7 148
1 15
193 10
47 3
197 10
3 62
3 ...

output:

589299572
711374004
615598294
983529100
358673338
312937893
930608366
909949430
977618408
932093348
577149932
707746443
251092517
346761579
29623312
413323345
120814904
78533207
378550832
296015215
828125562
872771575
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #33:

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

input:

200
34 2
2 24
3 52
147 7
181 9
6 117
157 8
73 4
135 7
6 113
3 61
194 9
140 7
9 189
51 3
56 3
4 76
167 8
7 151
148 7
121 6
43 2
110 5
160 8
5 1
134 7
162 8
8 165
180 9
5 100
7 142
1 22
126 6
5 94
161 8
159 8
47 3
193 9
8 163
5 102
9 184
95 5
154 7
93 5
2 33
9 185
190 9
6 119
13 1
4 69
50 3
192 9
6 12...

output:

657825616
670287277
620562235
736801593
620581720
228667287
251139676
782759940
459024714
306272751
821693501
314901003
862367800
178756849
980118605
883290020
115363626
435098615
641796307
845444375
940816514
175663934
691200571
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #34:

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

input:

200
3 134
193 4
87 2
176 4
72 2
4 169
18 1
42 1
108 3
3 129
1 20
15 1
3 130
1 29
162 4
2 94
149 3
3 133
4 172
1 17
2 56
75 2
1 12
154 4
31 1
5 1
64 2
2 70
165 4
199 4
57 2
90 2
105 3
1 21
4 178
4 195
109 3
117 3
3 150
3 142
4 183
61 2
49 1
38 1
1 16
2 74
192 4
121 3
131 3
185 4
4 188
194 4
110 3
1 2...

output:

46240861
498171459
402036732
579388118
259125433
495589906
429698219
340722708
733610152
358173413
119793681
838693192
45543933
397258724
448293950
500014466
198818313
858870106
446869816
546921778
553128778
477830275
625303924
572890740
503018381
712825198
53316664
494664316
821189148
409097501
223...

result:

ok 201 numbers

Test #35:

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

input:

200
14 199
95 9
8 75
177 13
66 8
157 12
85 9
13 193
5 26
8 2
38 6
151 12
7 56
63 7
11 138
7 59
190 13
6 36
10 120
156 12
115 10
10 118
171 13
6 2
113 10
20 4
83 9
13 176
33 5
153 12
13 169
22 4
12 159
5 27
87 9
11 129
6 44
174 13
9 93
77 8
11 122
11 125
4 23
9 81
112 10
173 13
7 51
32 5
96 9
184 13
...

output:

552182524
796256111
780619245
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #36:

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

input:

200
183 17
96 179
28 138
95 40
41 10
172 14
22 40
111 147
124 55
56 82
91 15
46 149
32 9
22 48
3 2
26 45
19 133
62 10
167 66
111 166
34 37
171 133
173 130
15 69
119 126
25 21
14 16
6 28
16 108
3 99
42 27
39 44
5 11
83 57
164 115
190 4
74 160
23 19
20 21
48 123
100 118
188 48
13 59
55 72
152 135
132 ...

output:

502325211
397619682
444276060
938021691
869851039
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #37:

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

input:

200
1 23
20 12
1 103
122 1
142 40
105 1
164 41
196 1
1 83
1 16
41 31
55 41
173 1
82 81
46 49
12 1
163 177
96 61
139 1
53 48
2 1
179 123
1 113
48 87
114 1
66 12
26 5
198 146
61 1
13 50
75 1
128 1
28 1
120 1
1 150
151 1
1 140
1 129
33 10
1 193
1 81
2 126
60 50
123 155
85 1
1 71
124 16
69 1
94 15
195 4...

output:

756486061
432597718
834856165
538897905
637157314
330778730
994332114
774959646
694860402
620168155
318344771
140066635
478673837
296859826
93676003
952475290
436328849
560680066
94945155
129366422
202481039
858161049
549877490
481538365
273161227
864676976
462811795
352357809
669778072
59370993
883...

result:

ok 201 numbers

Test #38:

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

input:

200
22 23
20 12
102 103
122 121
142 40
105 104
164 41
196 195
82 83
15 16
41 31
55 41
173 172
82 81
46 49
12 11
163 177
96 61
139 138
53 48
2 1
179 123
112 113
48 87
114 113
66 12
26 5
198 146
61 60
13 50
75 74
128 127
28 27
120 1
149 150
151 150
139 140
128 129
33 10
192 193
80 81
2 126
60 50
123 1...

output:

645084685
706127650
915088882
653721114
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #39:

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

input:

200
199 180
82 95
75 64
159 177
55 66
140 157
73 85
193 174
26 20
5 8
30 38
135 151
56 46
53 63
138 122
59 49
171 190
36 28
120 105
139 156
101 115
118 104
153 171
3 6
99 113
15 20
71 83
176 158
26 33
136 153
169 152
16 22
159 142
27 21
75 87
129 114
44 36
156 174
93 80
66 77
122 107
125 110
23 17
8...

output:

888543341
598846205
907553363
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #40:

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

input:

200
54 56
163 165
105 107
186 188
132 134
100 102
137 139
35 37
18 20
64 66
179 177
156 154
104 106
184 186
113 111
17 19
14 16
128 130
33 31
80 82
72 74
197 195
51 53
34 36
195 193
58 60
132 130
160 162
61 59
79 81
50 52
168 166
79 77
128 126
52 54
134 136
91 89
40 38
122 120
108 106
4 6
118 116
18...

output:

200
200
40001
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #41:

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

input:

200
4 1
155 159
18 22
61 65
25 29
7 3
35 39
103 99
93 97
180 176
24 20
182 186
196 200
140 136
57 61
34 38
127 123
93 89
69 73
185 181
87 91
111 115
126 122
35 31
120 116
82 86
75 79
23 27
135 139
148 144
101 105
66 70
198 194
190 186
136 132
147 143
94 98
151 155
154 158
199 195
67 63
75 71
8 4
109...

output:

200
8000000
625996248
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #42:

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

input:

200
51 61
37 47
131 141
151 161
144 134
48 38
115 105
147 137
175 165
176 186
86 76
75 65
109 99
158 148
169 159
62 52
135 125
97 87
1 6
13 23
77 87
42 32
73 63
190 200
152 142
122 132
90 80
21 11
24 34
27 37
181 171
71 61
1 9
84 74
180 170
56 46
127 117
42 52
111 121
137 127
54 64
95 105
156 146
13...

output:

200
272622225
812489269
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #43:

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

input:

200
84 54
109 139
65 95
66 96
156 126
151 181
59 29
87 57
5 1
148 118
80 50
1 14
170 140
138 108
53 23
72 102
49 79
45 15
14 44
77 47
123 153
1 9
198 168
7 37
103 133
119 149
64 94
33 63
62 32
4 1
69 39
69 99
109 79
98 68
88 118
182 152
105 75
1 18
73 43
58 88
196 166
176 146
160 190
91 61
72 42
13 ...

output:

801436979
67687828
61628260
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #44:

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

input:

200
84 134
193 143
87 37
176 126
72 22
119 169
18 1
42 1
108 58
79 129
1 20
15 1
80 130
1 29
162 112
44 94
149 99
83 133
122 172
1 17
6 56
75 25
1 12
154 104
31 1
5 1
64 14
20 70
165 115
199 149
57 7
90 40
105 55
1 21
128 178
145 195
109 59
117 67
100 150
92 142
133 183
61 11
49 1
38 1
1 16
24 74
19...

output:

200
877701485
380326836
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #45:

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

input:

200
1 89
1 99
185 85
152 52
141 41
147 47
113 13
1 75
129 29
110 10
34 1
1 84
32 132
119 19
1 19
150 50
45 145
73 173
142 42
27 127
79 1
39 139
112 12
14 1
1 50
1 38
106 6
66 1
7 1
70 170
5 1
122 22
57 1
156 56
183 83
108 8
1 72
134 34
2 102
167 67
91 1
1 44
1 37
1 15
47 1
84 184
104 4
1 43
85 1
124...

output:

200
827017373
355449420
918668966
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #46:

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

input:

200
1 50
50 86
66 1
66 29
66 84
36 66
1 116
116 44
103 116
62 116
1 18
52 18
17 18
18 176
18 22
39 1
39 174
39 59
45 39
139 39
165 1
165 194
87 165
71 165
165 31
165 97
165 166
1 138
157 138
138 113
138 126
177 138
158 138
54 138
1 136
136 12
65 136
42 136
172 136
136 134
136 198
136 125
1 112
112 1...

output:

424608209
477311328
278561706
931897378
655258322
76420166
867707271
987603450
332960845
320531937
117194277
73024931
734414872
906228068
89998113
691658396
548755434
367595814
34221023
66656211
986113700
153883869
459338935
706316770
608998197
373891518
538040382
868717419
812454293
574734978
84499...

result:

ok 201 numbers

Test #47:

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

input:

200
1 76
1 140
140 75
140 190
140 87
1 185
8 185
160 185
185 55
185 118
1 191
191 46
191 69
191 177
192 191
191 107
191 162
1 2
2 61
115 2
2 17
141 2
2 198
2 39
106 2
147 1
143 147
147 184
147 128
147 101
147 112
196 147
147 146
147 12
147 26
126 147
134 1
134 188
81 134
134 73
134 173
134 163
134 1...

output:

960970248
264283297
933920103
29961257
159617624
443277810
229680181
645417622
101637212
847228861
568679194
872527395
733188391
773748859
157331092
301447524
605757643
925025069
767010058
307865010
704392596
715048214
604593784
344010700
288266683
479214474
202962675
616905762
839278281
890759754
4...

result:

ok 201 numbers

Test #48:

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

input:

200
1 21
176 1
176 45
123 1
123 147
188 1
137 188
78 1
78 117
78 94
162 78
118 78
124 78
1 193
193 13
1 164
164 195
164 8
164 173
154 1
44 154
154 91
154 172
23 154
154 139
119 1
119 96
119 152
24 119
1 55
55 100
55 179
55 185
130 55
22 1
22 191
22 159
22 197
22 92
148 22
22 19
22 165
199 1
71 199
1...

output:

98220592
266712720
475004158
333155648
811691051
555590867
21432684
1356292
673797469
831923418
685806286
255169328
106996204
501373658
822612055
78237330
649240500
265897663
647719595
964920278
20555908
466742569
442158482
735457609
363351186
122495676
472108738
285239332
327500305
780241920
178013...

result:

ok 201 numbers

Test #49:

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

input:

200
84 1
1 48
48 112
152 1
188 152
1 2
191 2
63 1
66 63
1 92
143 92
118 1
118 108
164 118
133 118
1 42
42 90
42 109
177 42
125 42
198 42
79 42
42 43
42 59
42 93
131 42
171 1
171 103
195 171
171 97
171 114
171 37
171 189
171 184
171 22
157 171
171 104
171 26
110 171
38 171
194 171
136 171
105 171
154...

output:

107494908
776695677
475806178
208473430
313796405
398417500
226327160
716126972
607936731
569311828
12567940
367917963
981477735
804789826
867897017
714516781
152242107
925157321
88844970
480344032
329708277
161810498
7035952
187472671
560808647
343592960
124670865
800406176
859623228
547024020
5338...

result:

ok 201 numbers

Test #50:

score: 0
Accepted
time: 220ms
memory: 8464kb

input:

200
194 1
184 1
184 151
75 1
75 98
1 124
124 162
1 38
38 127
38 161
38 50
192 1
142 192
126 192
24 192
67 192
190 1
190 175
5 190
190 167
81 190
190 136
104 190
168 1
168 63
168 99
29 168
55 168
19 168
168 66
1 86
144 86
86 116
86 91
143 86
47 86
131 86
86 114
181 86
170 1
123 170
76 170
170 179
170...

output:

177417302
106995503
389340824
490370699
466289252
352570768
287333024
887763775
39026550
36231208
423502749
960761043
413093671
31619382
977308763
326837054
514614117
767913925
971527535
769803066
860275107
529645347
744150719
770113295
948821440
623819617
322096707
936281811
219589390
678944801
337...

result:

ok 201 numbers

Test #51:

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

input:

200
88 1
88 127
1 34
170 34
34 80
1 48
142 48
48 73
134 1
134 37
187 134
134 72
134 178
28 1
28 157
28 16
173 28
28 69
56 28
98 28
181 28
193 28
87 28
1 94
124 94
20 94
50 94
185 94
8 94
68 94
94 57
94 26
94 136
139 1
139 47
163 139
195 139
139 39
139 191
139 116
38 139
112 139
129 139
110 139
139 8...

output:

523113308
214318589
117572022
786534946
7109784
724963744
95145157
174077463
6003774
282431565
553458461
623789326
791351623
392397012
592394941
607054169
544396066
105914087
635586330
957355428
208073853
619268608
676234625
7057352
759022301
338238772
968468424
585974175
926175708
735511525
3316428...

result:

ok 201 numbers

Test #52:

score: 0
Accepted
time: 24ms
memory: 6292kb

input:

200
184 1
28 1
153 28
1 32
108 32
32 178
1 81
105 81
81 39
81 102
176 1
176 73
168 176
172 176
176 63
197 1
151 197
197 171
197 177
1 123
40 123
123 90
45 123
123 124
123 191
34 1
34 149
134 34
167 34
66 34
34 9
115 1
115 3
115 42
78 115
188 115
1 86
86 57
46 86
86 98
86 48
62 86
86 94
86 103
157 86...

output:

47151332
832939154
213433285
565203609
145574132
352316056
250030197
226805084
216099955
592382514
636828991
844399197
64756312
134906334
297687387
67921368
558506071
875410727
932803599
567753877
667094227
582881441
559184755
364081229
128639584
660676028
438885075
863693217
479778621
564013378
724...

result:

ok 201 numbers

Test #53:

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

input:

200
1 62
62 83
171 1
171 200
1 38
8 38
1 173
173 17
123 1
123 150
66 123
123 92
1 39
39 192
39 139
39 129
39 170
197 39
39 158
1 130
130 157
130 125
74 130
130 44
130 5
41 130
1 167
4 167
12 167
167 179
167 64
134 167
63 167
167 65
174 167
167 144
167 42
167 78
1 91
73 91
149 91
47 91
91 124
91 181
...

output:

275829285
63140766
346645436
48715605
114220999
250204997
217706874
44251556
94922070
810246758
933089921
432717141
868648393
242216037
583974499
13224660
193009788
345380473
581229851
151065031
913007231
699360097
74021963
560961768
617988303
232684496
919175990
439811565
688979161
390717161
319519...

result:

ok 201 numbers

Test #54:

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

input:

200
1 157
200 157
39 157
170 157
196 157
157 82
165 1
110 165
32 165
88 165
165 160
5 165
165 129
165 193
34 165
75 165
1 179
180 179
24 179
179 163
179 149
66 179
147 179
179 115
179 28
179 37
162 179
79 179
179 133
195 179
179 46
179 11
1 198
198 126
145 198
198 121
106 198
198 197
124 198
187 198...

output:

872853208
749733227
487100108
885840063
726574283
190972801
332926436
413139613
828533078
950487222
106408665
943639236
398008078
203030118
528194013
853792057
60799200
240118905
796306529
674764488
935813250
111494931
351987733
909591646
936509272
418593137
460461727
981027609
848028885
798086674
1...

result:

ok 201 numbers

Test #55:

score: 0
Accepted
time: 51ms
memory: 8612kb

input:

200
9 1
9 69
185 1
185 115
7 185
84 185
185 56
1 51
128 51
51 75
51 151
51 105
100 1
100 126
200 100
100 178
100 145
44 100
146 1
146 10
146 92
146 3
45 146
146 71
146 50
146 17
146 30
146 160
146 33
146 90
1 144
98 144
144 77
144 161
95 144
52 144
144 73
144 189
173 144
78 144
87 144
135 144
12 144...

output:

431442037
373965749
954559306
329205543
611302454
81467246
157588878
877689074
622496633
403436795
825151826
823605890
922444152
334140139
369960328
86380771
191221539
644421401
928207460
608688074
144301684
937386932
642555369
321288358
481098254
626625617
34782813
338515714
181675355
99168051
7306...

result:

ok 201 numbers

Test #56:

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

input:

200
1 9
158 1
188 158
1 179
179 65
134 179
179 95
179 61
1 156
156 149
156 104
152 156
156 182
1 91
91 64
91 143
91 27
91 22
91 186
1 94
162 94
94 191
39 94
94 42
94 47
1 40
157 40
40 81
40 125
130 40
40 138
105 1
184 105
13 105
105 17
105 23
116 105
8 105
1 101
82 101
101 99
101 83
66 101
101 122
1...

output:

915646270
287527289
925794506
173842206
502376266
204929098
171022579
954661571
580048880
771094335
951358337
766650278
921127164
974517014
74984882
257353574
50285571
611720495
771182090
695192449
854854439
345982847
193313188
909090437
286492120
282588595
378920816
538421806
345572911
124014829
26...

result:

ok 201 numbers

Test #57:

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

input:

200
152 1
1 200
200 175
118 1
159 118
32 118
87 1
52 87
197 87
22 87
120 1
120 58
120 90
120 180
120 65
1 78
154 78
78 157
105 78
78 28
1 140
140 64
69 140
140 72
148 140
1 115
115 146
115 131
115 103
115 169
59 115
195 1
195 116
195 127
20 195
85 195
195 66
1 160
130 160
160 49
10 160
39 160
160 19...

output:

542194627
768746014
979545120
281829288
642933891
246087569
995673316
504464909
182341097
543688842
232545930
50292871
833101537
189162403
653813074
413876296
585566276
994273448
846329701
995007461
505778286
178994237
59208331
647915880
532935005
617611968
529783050
897817039
564958294
80976084
499...

result:

ok 201 numbers

Test #58:

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

input:

200
45 1
45 175
1 15
15 108
1 82
82 98
1 38
38 77
1 11
11 83
8 11
1 46
46 69
144 46
198 1
198 61
198 164
195 198
49 1
49 23
49 118
3 49
17 1
147 17
17 76
17 110
189 17
1 191
191 194
52 191
191 64
102 191
115 1
115 161
115 32
124 115
115 55
106 1
106 196
106 96
106 185
148 106
174 1
156 174
150 174
7...

output:

662193916
669095926
9246527
952290490
628174678
731002911
235877589
598494827
746248667
982570960
394281726
607073837
290680213
412407974
539784170
483052666
646939575
272040327
356960126
880201796
964962548
695485193
605693323
810700922
471647656
898295984
638118415
918593061
486495273
134925774
56...

result:

ok 201 numbers

Test #59:

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

input:

200
95 1
31 1
105 1
105 185
98 1
144 98
32 1
32 13
1 113
113 128
1 44
56 44
157 44
1 18
18 14
108 18
1 156
156 29
140 156
169 1
169 150
146 169
85 1
200 85
67 85
1 131
131 147
57 131
131 83
1 82
195 82
155 82
82 172
75 1
180 75
75 8
17 75
175 1
65 175
199 175
175 30
176 1
100 176
36 176
176 107
1 61...

output:

696367969
617661761
756151686
885347242
269258032
547568187
448677273
846716732
88930092
23868622
820590495
827621994
736063059
341192424
985281756
3329970
593798473
281619893
334077779
95248457
348231777
602299338
736041778
348759890
459150420
258767909
454024877
142816748
941685807
754298916
83328...

result:

ok 201 numbers

Test #60:

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

input:

200
1 150
64 150
150 69
150 54
150 70
42 150
85 1
29 85
68 85
57 85
12 85
151 85
18 85
153 85
95 1
95 81
95 182
135 95
95 8
101 95
95 72
142 95
173 95
34 95
188 1
188 27
152 188
163 188
76 188
188 136
14 188
188 97
179 188
139 188
84 188
170 188
171 188
188 23
188 154
47 188
147 188
165 188
190 188
...

output:

601897646
290882591
182570351
766041198
422495344
246104852
175542019
270213501
141122991
816891087
212667902
253536995
756635022
598737022
438373834
709684511
911949265
350908360
979292424
568976900
299608330
746936666
632418895
500265452
695924987
858831961
452131963
558517120
575027027
412599983
...

result:

ok 201 numbers

Test #61:

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

input:

200
1 134
134 181
1 16
48 16
137 1
137 109
141 137
1 38
38 31
113 38
7 38
98 38
38 37
103 1
103 41
164 103
100 103
136 103
51 103
153 103
1 116
116 144
116 69
34 116
125 116
162 116
116 28
186 116
116 12
140 116
40 116
145 1
145 102
145 148
97 145
74 145
199 145
194 145
145 166
145 107
56 145
145 14...

output:

70993027
93883358
488126449
51997200
822126001
54868633
944119747
801383581
477442093
145393755
806754242
630311682
303357069
137703457
576652618
792934734
393064322
658649985
425671690
76558292
242424769
399458986
421717321
573984220
994593059
209617286
292168920
333686983
932088752
235190055
32982...

result:

ok 201 numbers

Test #62:

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

input:

200
1 35
48 35
1 191
102 191
191 42
1 178
7 178
1 32
32 70
32 176
151 1
116 151
151 144
140 1
126 140
25 140
83 140
68 140
140 187
55 1
118 55
114 55
55 179
130 1
130 101
130 6
130 73
130 200
130 46
1 104
84 104
104 72
135 104
104 188
44 104
104 134
1 47
121 47
97 47
47 145
47 162
103 47
47 27
1 37
...

output:

773846976
292676984
227217667
308936000
706899675
645848433
370930792
409068292
162225968
400663404
490131342
516800551
11184294
555601216
276256057
325623271
940171808
330637576
960469059
975599404
321173379
296182284
349382330
332612024
59692513
872339429
970247667
494585067
865876179
194636168
92...

result:

ok 201 numbers

Test #63:

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

input:

200
1 122
1 155
200 155
8 1
8 111
1 33
129 33
1 125
57 125
1 9
135 9
9 65
1 45
45 82
183 1
198 183
183 85
1 137
137 98
137 51
23 137
1 116
116 19
116 121
123 116
136 116
116 88
1 29
52 29
199 29
158 29
194 29
29 184
29 42
112 1
96 112
86 112
112 36
112 60
112 159
112 189
1 191
191 27
69 191
13 191
1...

output:

632624224
240586287
622155354
116123651
913302037
479239547
249189520
609565475
258446395
798166327
737158563
223051681
158884946
173594717
940038913
73485178
497731969
398766059
788990011
426051720
626947242
309652848
154715657
989434264
697269413
137070828
38384809
726082696
358130415
768136331
94...

result:

ok 201 numbers

Test #64:

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

input:

200
1 162
1 132
132 125
41 1
41 11
1 70
82 70
81 1
81 32
1 188
188 59
188 116
1 8
8 186
8 141
134 8
1 165
165 169
138 165
47 165
1 14
154 14
14 143
14 56
14 164
21 1
21 90
1 124
74 124
71 124
124 23
1 20
156 20
20 150
75 1
31 75
75 95
75 115
176 75
75 33
1 37
37 148
1 139
102 139
139 7
159 139
161 1...

output:

95748073
713725219
75013822
303285871
898441017
64342034
418627235
727108369
430289029
382780334
715268857
732531226
520580849
479456252
969633121
306690600
878388369
735764848
510423603
132566036
617213531
911955428
10299398
103053804
964652036
279403826
464143031
593274484
306681985
828985609
7938...

result:

ok 201 numbers

Test #65:

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

input:

200
1 56
82 1
154 1
119 1
124 1
124 149
1 150
96 150
66 1
66 195
1 95
135 95
1 74
74 16
74 182
1 11
11 130
11 32
1 137
103 137
1 46
46 7
1 35
35 189
145 1
145 183
145 72
43 1
180 43
175 43
43 181
1 29
29 165
102 29
29 21
23 1
113 23
122 23
23 141
23 199
1 176
176 55
176 89
168 176
97 176
1 143
170 1...

output:

850171225
78756830
477773067
942575152
993511664
514920769
231626770
572110972
343531436
299753636
536865020
713869971
788534243
726332665
355379891
781503062
214426935
424025423
71511286
467001484
559824537
572220794
354695293
309759881
876652149
51574068
283224545
176704668
43327995
32525772
51565...

result:

ok 201 numbers

Test #66:

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

input:

200
1 65
1 176
129 1
129 171
1 96
161 96
133 1
133 52
133 41
76 1
76 39
89 76
46 76
181 76
70 76
74 76
76 198
1 24
24 112
18 24
24 16
97 24
24 36
197 24
24 186
143 24
1 12
124 12
64 12
12 149
188 12
174 12
71 12
12 62
12 85
1 158
160 158
61 158
158 78
158 191
111 158
136 158
158 86
158 87
158 81
158...

output:

164777153
447832293
567465007
4704441
102286993
199075745
442655458
694500630
257546818
774293997
402176523
913310899
166331190
662002661
507953722
511207346
656290657
146142888
559624745
398945236
703958597
959897256
104317818
127725824
680484042
716078653
724637174
73783572
152470849
181886454
152...

result:

ok 201 numbers

Test #67:

score: 0
Accepted
time: 308ms
memory: 9048kb

input:

200
24 1
24 188
76 1
76 10
172 1
172 118
172 193
160 1
123 160
5 160
25 160
181 1
93 181
45 181
68 181
181 148
15 181
181 159
1 55
32 55
190 55
55 191
55 11
177 55
55 86
107 1
107 98
77 107
107 140
33 107
107 41
176 107
107 102
54 1
54 79
122 54
96 54
54 163
157 54
54 189
54 196
1 125
125 71
18 125
...

output:

766471844
173471180
807473699
567719093
626507644
484731382
235169605
51074147
962419414
886597311
120028168
528359060
294292523
196137538
680220876
468772643
623113192
597966750
933215770
647103590
575986161
183154177
223791814
160311949
567382633
924306135
728418309
685442131
572635980
216461470
8...

result:

ok 201 numbers

Test #68:

score: 0
Accepted
time: 68ms
memory: 6488kb

input:

200
2 1
79 2
199 1
199 103
67 199
1 157
157 88
157 60
157 64
1 146
42 146
146 28
113 146
97 146
195 1
195 132
195 26
56 195
91 195
178 1
178 143
184 178
178 99
148 178
178 106
44 1
119 44
182 44
44 53
44 35
44 16
44 21
1 95
84 95
191 95
95 164
95 63
95 131
165 95
95 49
86 1
86 135
86 121
86 62
66 86...

output:

259258820
531063828
589862011
436277826
330071431
598261368
839832410
436504755
945112834
339945575
639259086
790534182
432494811
486945256
319092163
824902694
353078129
723146809
913574967
895677768
929191259
301799605
956151420
255846540
833680591
86115429
443738441
506131228
983163698
153813683
4...

result:

ok 201 numbers

Test #69:

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

input:

200
1 17
96 17
17 40
17 119
1 4
27 4
4 45
4 107
166 4
1 52
95 52
52 37
52 136
52 109
125 1
125 79
125 157
97 125
125 83
1 124
46 124
121 124
124 24
143 124
1 26
26 31
147 26
26 182
26 128
26 57
1 92
77 92
92 140
92 145
59 92
101 92
200 1
129 200
169 200
200 179
200 162
200 117
170 200
115 1
115 116
...

output:

434884657
804512493
283318530
536797634
844855123
297747856
527897039
52960063
608290221
905607137
658621360
921429707
239853464
157370916
464233478
334423783
184640177
252862608
902404882
176100801
952802913
33355651
284652921
436734616
335713370
522023447
952585540
382364033
942256774
417475392
42...

result:

ok 201 numbers

Test #70:

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

input:

200
181 1
179 181
1 36
45 36
36 175
103 1
103 33
104 103
1 62
87 62
62 10
62 39
62 54
1 164
164 47
164 198
118 164
164 130
1 99
46 99
99 136
99 101
121 99
99 64
99 55
1 96
77 96
96 52
96 42
50 96
30 96
193 96
165 1
102 165
72 165
165 13
97 165
165 11
165 73
8 165
165 40
1 22
76 22
43 22
161 22
91 22...

output:

647851972
883513027
150297118
976163075
744277232
980590419
353789344
124910989
701540567
626215139
568244282
919262487
183321171
415570609
135267439
39216014
640865052
391798278
528671624
532807104
722821266
273934557
145617706
54329363
954944386
514654326
662345545
669852698
648197953
328227188
86...

result:

ok 201 numbers

Test #71:

score: 0
Accepted
time: 31ms
memory: 6352kb

input:

200
1 160
1 176
176 145
1 18
18 71
174 18
1 10
10 154
10 2
79 10
195 1
146 195
195 25
195 147
1 28
38 28
28 139
63 28
28 78
1 103
103 192
103 91
103 21
103 4
27 103
83 103
178 1
48 178
178 161
178 68
178 32
116 178
178 69
8 1
8 88
8 191
152 8
113 8
8 151
31 8
115 8
1 76
110 76
81 76
76 41
76 120
14 ...

output:

696143612
697626141
639950654
551046716
335313673
801094194
247070096
68718279
944283866
677028940
23658607
242533712
185214467
346900270
795253118
629294947
478434517
931267319
842828971
328043631
116890566
499161532
354466783
775760024
61538236
877645836
178107942
738814523
697877812
402026000
184...

result:

ok 201 numbers

Test #72:

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

input:

200
168 1
168 89
168 80
23 1
182 23
180 23
71 1
71 60
71 163
71 196
2 71
71 141
71 170
71 38
188 71
29 71
111 71
71 146
75 71
46 71
14 71
1 107
183 107
19 107
69 107
107 100
41 107
107 145
107 144
99 107
107 33
107 124
5 107
107 105
102 107
107 77
1 92
92 140
42 92
92 49
92 85
92 83
117 92
92 129
50...

output:

812430084
482951065
633173621
260847743
936764503
648565490
331938
971908917
606524687
500679870
553568628
595865043
887368347
222467953
729981538
334168459
647740302
350808908
785892098
123143567
681142976
593928845
962517072
77968073
645028006
915064123
868613619
22771937
142098954
617948047
73879...

result:

ok 201 numbers

Test #73:

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

input:

200
124 1
48 1
48 63
1 72
72 194
72 162
72 4
1 127
112 127
169 127
127 23
1 85
33 85
85 114
88 85
85 170
85 91
166 85
161 85
85 31
84 1
44 84
84 37
42 84
84 179
84 13
84 69
84 115
84 119
84 108
97 1
97 152
97 143
97 19
97 133
131 97
109 97
20 97
126 97
196 97
97 22
173 97
89 97
97 27
97 36
122 97
28...

output:

395281256
483636032
44470315
764274255
768052736
172694762
50838859
156746114
244891434
863727019
813260101
485593277
478254883
518976274
641070905
996965890
5686802
768465347
1559198
841243941
58707679
454112478
223277062
223885387
907437049
795048480
596043388
423066416
865205173
44024428
65729859...

result:

ok 201 numbers

Test #74:

score: 0
Accepted
time: 51ms
memory: 8084kb

input:

200
182 1
1 159
191 159
73 1
73 118
97 1
33 97
165 1
69 165
165 155
114 165
119 165
1 120
120 108
121 120
65 120
120 144
32 120
180 1
132 180
173 180
180 192
84 180
24 180
180 16
180 102
180 152
1 194
194 115
194 177
186 194
194 101
40 194
116 194
194 78
125 194
185 194
164 1
164 66
77 164
164 169
1...

output:

640296034
160017816
409757750
882935094
894677558
136393447
117425395
552638575
554232690
880142431
397236555
616570637
536318183
1923134
290340881
541061556
922153535
524676857
295725489
710790204
192846240
979470484
567080445
516357171
317406267
729149468
957747853
99884604
819178433
657890855
174...

result:

ok 201 numbers

Test #75:

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

input:

200
194 1
194 198
194 94
1 2
2 81
186 2
2 116
1 46
46 110
196 46
80 46
1 170
115 170
112 170
124 170
6 170
1 154
154 35
154 171
154 34
154 136
44 1
44 122
183 44
173 44
5 44
108 44
1 96
87 96
61 96
96 79
96 142
83 96
96 9
104 1
118 104
13 104
104 131
104 168
191 104
10 104
1 190
190 69
25 190
190 12...

output:

729584871
827690409
100298473
301716579
244567849
735511386
720406872
376993559
204378486
183087914
781720770
701525100
815857081
923456287
888924673
95900981
168169141
686014061
690762897
774843911
961785343
411267702
923664603
483844259
403738940
600708740
446545615
66269133
710514984
308411098
76...

result:

ok 201 numbers

Test #76:

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

input:

200
1 153
200 153
69 1
69 142
1 122
192 122
1 55
55 181
55 148
55 6
175 1
175 150
175 85
76 175
175 137
1 71
71 121
71 75
71 107
11 71
71 63
1 46
109 46
5 46
46 44
57 46
46 177
46 25
1 186
186 127
186 133
14 186
162 186
186 172
186 115
1 21
23 21
21 29
21 35
21 86
159 21
21 158
48 21
19 1
3 19
194 1...

output:

414345378
103972789
959767594
218642750
164961057
133874572
431632445
310126374
286943669
31792833
945900085
331600880
23187267
963463709
823620104
579581311
246494656
339728162
636268796
83411975
879923560
447007159
310515553
309376220
536290097
636878267
303677477
87827816
828980276
541445235
3666...

result:

ok 201 numbers

Test #77:

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

input:

200
1 137
103 1
54 1
52 54
54 25
1 74
74 156
184 74
183 74
1 42
118 42
35 42
42 131
42 49
1 5
186 5
5 50
46 5
5 175
100 1
41 100
100 24
18 100
100 172
64 1
64 106
64 96
64 197
149 64
171 64
1 7
7 31
166 7
135 7
163 7
7 116
1 182
196 182
126 182
82 182
136 182
92 182
195 182
140 1
140 192
32 140
152 ...

output:

559181622
820914974
15501901
611647829
829595761
842385301
688740966
689797404
80511479
929685110
428709580
962461955
709190512
116760400
884843971
980911605
75717268
599529861
412953511
504296981
84900258
532831754
960181037
729497963
896887579
787752634
451513744
391693832
482475699
556758753
3783...

result:

ok 201 numbers

Test #78:

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

input:

200
1 27
72 1
1 76
76 197
33 1
30 33
120 1
120 167
31 1
186 31
73 1
73 77
73 8
1 123
145 123
123 184
193 1
193 66
135 193
141 193
107 1
107 127
86 107
107 168
1 109
62 109
109 137
67 109
1 185
185 173
185 29
171 185
1 113
63 113
70 113
113 128
78 113
1 16
16 99
55 16
38 16
179 16
1 150
160 150
150 1...

output:

788186584
58598484
744654504
246879241
479765573
947592708
467982628
592512586
330025094
620135132
105808671
220783508
874444538
881920827
652864836
165178115
815172407
566981700
623342833
793329660
684375007
264749199
630530223
954623358
615885728
594546766
403482919
405600543
836213388
917571608
8...

result:

ok 201 numbers

Test #79:

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

input:

200
1 31
139 1
1 135
1 80
1 30
154 30
1 184
184 89
41 1
41 173
1 169
169 128
26 1
42 26
170 26
1 155
155 25
110 155
193 1
65 193
149 193
126 1
48 126
126 138
1 133
133 167
133 118
1 39
39 15
163 39
99 39
92 1
92 176
159 92
181 92
1 183
183 51
100 183
183 64
183 187
50 1
120 50
50 43
50 53
158 50
1 1...

output:

191955394
827424615
846649676
191961314
325483704
176750113
329653947
498037096
602942267
987278474
700703314
975212309
837152269
612221851
880394528
938436056
411210636
216671241
382532918
2187400
769963135
818572891
278119518
27872742
989548766
801641911
506305165
309580898
128398187
647036219
737...

result:

ok 201 numbers

Test #80:

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

input:

200
164 1
164 182
1 143
143 79
143 103
128 143
143 140
129 143
23 143
143 7
173 1
28 173
173 133
173 94
173 35
146 173
78 173
173 186
1 85
85 30
91 85
120 85
85 102
192 85
85 144
85 21
85 22
100 85
54 85
183 85
85 118
32 85
85 170
5 85
39 85
85 4
85 14
149 1
149 148
108 149
149 191
149 98
43 149
149...

output:

739989489
595273423
233637593
919368796
81911249
975490850
796818119
840546457
616668117
783376731
435142835
427464467
425208593
543484756
849285900
69496097
854279484
956376809
524815268
817124164
162808521
342618660
857134465
884737884
245858053
469177569
345704639
695004841
863928279
657155059
21...

result:

ok 201 numbers

Test #81:

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

input:

200
1 108
143 108
1 118
133 118
118 61
94 1
122 94
101 94
94 36
172 94
53 94
1 175
192 175
58 175
44 175
18 175
29 175
157 1
157 189
146 157
15 157
92 157
157 177
157 59
90 157
71 1
71 10
71 105
182 71
80 71
167 71
71 123
71 91
1 72
149 72
72 141
179 72
33 72
72 136
72 82
1 140
193 140
140 111
140 4...

output:

509425917
772082292
588750475
117726817
764168440
213966683
996439760
342616654
356669292
913851793
773731841
354571222
943932424
205204305
696828656
895039822
39024556
28733664
955149267
666289039
804481145
248762722
384301719
579717137
108989622
238576435
796587575
304242285
503143750
2241628
1421...

result:

ok 201 numbers

Test #82:

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

input:

200
71 1
102 1
145 102
160 1
124 160
1 51
30 51
11 1
11 163
134 1
156 134
134 20
1 27
27 53
27 116
137 27
65 1
65 59
104 65
1 93
93 112
93 2
159 93
135 93
93 133
93 188
12 1
91 12
87 12
12 10
12 153
12 45
174 12
180 1
180 191
180 118
180 141
40 180
1 44
44 101
136 44
190 44
44 157
44 154
96 44
44 19...

output:

351410052
106591323
263433604
149257998
862490735
384582808
917274564
182221209
69654473
324362419
602981526
37094944
106416765
70936528
785462187
573137842
463733059
446699638
139723084
412137528
500686852
215526824
422372435
371643902
911002583
133841770
755003515
572161388
806084699
745626959
353...

result:

ok 201 numbers

Test #83:

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

input:

200
87 1
87 35
1 102
102 8
1 172
172 180
196 1
91 196
107 196
116 1
116 164
116 131
114 1
111 114
25 1
58 25
25 149
1 191
92 191
191 200
1 56
145 56
36 56
56 57
158 56
75 1
75 41
75 70
24 75
161 75
1 93
93 156
55 93
93 163
47 93
179 93
48 1
48 189
48 192
101 48
48 151
1 40
40 129
40 185
40 144
110 4...

output:

47475654
6487663
698179434
32467313
910556719
105080631
70504102
988140147
93709742
185078941
653271014
878067535
198144013
387766498
25783505
914674612
119067257
733211621
32730486
658348483
920709040
157915195
703709826
615976595
603974535
172801509
67871532
455367125
770452155
473168244
215381567...

result:

ok 201 numbers

Test #84:

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

input:

200
109 1
42 1
1 66
66 137
1 90
90 36
79 1
100 79
79 173
27 1
27 52
107 1
145 107
81 1
166 81
92 1
169 92
1 144
144 34
144 135
116 1
76 116
116 186
87 116
178 116
1 47
47 6
47 198
199 47
67 47
1 29
29 32
29 8
187 29
33 29
29 41
1 77
77 103
77 184
77 164
77 185
1 57
57 65
85 57
197 57
57 110
1 189
28...

output:

316521766
218225699
734518753
480488056
62715196
762899692
885529146
321420177
97939883
453232375
718750281
631176464
760690875
458203379
95864281
483144222
900927963
487625118
198146811
812427725
189029557
821408557
80631568
207289061
539906514
236493107
550318489
125582813
504138844
731402310
6325...

result:

ok 201 numbers

Test #85:

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

input:

200
32 1
1 33
33 68
161 1
161 103
188 1
188 158
1 24
189 24
55 1
83 55
1 173
173 73
120 1
149 120
131 120
112 1
112 19
112 81
126 1
78 126
115 1
135 115
160 1
194 160
1 2
5 2
7 1
7 6
136 7
1 16
16 64
119 16
16 42
1 90
90 91
90 175
167 90
66 1
66 145
66 36
75 66
174 1
40 174
148 174
198 174
174 152
1...

output:

384059382
235969744
333877837
642421946
646842323
582356888
341117949
938176648
228698292
818577227
40137680
386989627
915777251
163491525
936558002
683469762
658605724
26847788
42257514
801232386
972527096
740032589
749902457
272031492
859833296
777123370
306573335
895920253
674525856
283324517
313...

result:

ok 201 numbers

Test #86:

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

input:

200
35 67
8 95
102 36
126 157
53 23
177 110
180 14
73 112
178 171
163 4
136 52
13 192
186 119
136 150
145 8
40 11
138 14
124 34
71 106
126 159
34 56
147 28
21 198
46 163
68 60
172 53
60 195
126 74
183 90
75 8
170 118
19 158
67 47
12 187
188 168
48 174
153 176
155 112
98 58
89 18
183 182
66 193
66 39...

output:

689133582
932046675
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #87:

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

input:

200
166 187
114 190
133 93
189 61
110 179
195 26
75 29
98 185
162 157
152 111
197 7
100 52
174 183
94 151
83 111
129 47
94 45
187 108
155 23
125 167
123 69
161 191
83 48
189 96
44 147
96 99
102 113
138 32
56 126
67 164
108 107
72 62
66 31
24 197
80 155
113 41
28 143
88 170
43 6
104 4
99 84
52 128
58...

output:

100123754
416940958
910752220
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 numbers

Test #88:

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

input:

200
21 196
29 179
131 186
38 113
94 156
170 20
168 186
157 166
185 68
128 11
58 85
76 81
23 15
62 127
106 54
68 57
125 30
139 117
128 43
98 40
143 69
145 192
177 24
60 36
172 32
60 67
164 3
156 198
164 118
99 65
121 185
154 85
66 5
146 35
193 188
151 161
38 182
59 43
8 117
43 126
85 55
70 180
106 11...

output:

837251928
242170315
482321517
59436497
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 201 numbers