QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#176378#7181. Graph CutszhouhuanyiAC ✓532ms16540kbC++142.7kb2023-09-11 16:26:102023-09-11 16:26:10

Judging History

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

  • [2023-09-11 16:26:10]
  • 评测
  • 测评结果：AC
  • 用时：532ms
  • 内存：16540kb
查看
  • [2023-09-11 16:26:10]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cassert>
#define N 100000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,data;
};
struct node
{
	int num,data,nxt;
};
int n,m,q,len,length,head[N+1],X[N+1],Y[N+1],L[N+1],R[N+1],deg[N+1],delta[N+1],cnt[N+1],cl[N+1],num[N+1];
bool used[N+1];
vector<reads>ES[N+1];
node edge[N+1];
void add(int x,int y,int z)
{
	ES[x].push_back((reads){y,z}),delta[x]++;
	return;
}
void add2(int x,int y,int z)
{
	edge[++len]=(node){y,z,head[x]},head[x]=len;
	return;
}
bool check(int x)
{
	if (!cl[x]) return cnt[x];
	else return cnt[x]!=delta[x];
}
struct blocks
{
	int len,sz,block[N+1],a[N+1],s[N+1];
	void build(int x)
	{
		len=x,sz=sqrt(len);
		for (int i=1;i<=len;++i) block[i]=(i-1)/sz+1;
		return;
	}
	void change(int x,int d)
	{
		if (a[x]!=d) s[block[x]]+=d-a[x],a[x]=d;
		return;
	}
	bool any()
	{
		for (int i=1;i<=block[len];++i)
			if (s[i])
				return 1;
		return 0;
	}
	int get(int x)
	{
		for (int i=x;i<=min(block[x]*sz,len);++i)
			if (a[i])
				return i;
		for (int i=block[x]+1;i<=block[len];++i)
			if (s[i])
			{
				for (int j=(i-1)*sz+1;j<=min(i*sz,len);++j)
					if (a[j])
						return j;
			}
		return -1;
	}
};
blocks B,B2,B3;
int main()
{
	char c;
	int x,d;
	n=read(),m=read(),B.build(n),B2.build(m),B3.build(m);
	for (int i=1;i<=m;++i) X[i]=read(),Y[i]=read(),deg[X[i]]++,deg[Y[i]]++;
	for (int i=1;i<=m;++i)
	{
		if (deg[X[i]]<=deg[Y[i]]) add(Y[i],X[i],i);
		else add(X[i],Y[i],i);
	}
	for (int i=1;i<=n;++i)
	{
		L[i]=length+1;
		for (int j=0;j<ES[i].size();++j) add2(ES[i][j].num,i,++length),num[length]=ES[i][j].data;
		R[i]=length;
	}
	for (int i=1;i<=length;++i) B3.change(i,1);
	q=read();
	while (q--)
	{
		cin>>c;
		if (c=='+')
		{
			x=read();
			for (int i=head[x];i>0;i=edge[i].nxt)
				if (!used[edge[i].data])
					cnt[edge[i].num]++,B.change(edge[i].num,check(edge[i].num)),B2.change(edge[i].data,1),B3.change(edge[i].data,0);
			cl[x]=1,B.change(x,check(x));
		}
		else if (c=='-')
		{
			x=read();
			for (int i=head[x];i>0;i=edge[i].nxt)
				if (!used[edge[i].data])
					cnt[edge[i].num]--,B.change(edge[i].num,check(edge[i].num)),B2.change(edge[i].data,0),B3.change(edge[i].data,1);
			cl[x]=0,B.change(x,check(x));
		}
		else if (c=='?')
		{
			if (!B.any()) puts("0");
			else
			{
				x=B.get(1);
				if (!cl[x]) d=B2.get(L[x]);
				else d=B3.get(L[x]);
				printf("%d\n",num[d]),used[d]=1,B2.change(d,0),B3.change(d,0),delta[x]--,cnt[x]-=cl[X[num[d]]^Y[num[d]]^x],B.change(x,check(x));
			}
		}
	}
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 5
1 2
1 3
1 4
2 3
2 4
10
+ 1
+ 2
?
?
?
?
?
- 2
?
?

output:

2
3
4
5
0
1
0

result:

ok q=10

Test #2:

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

input:

0 0
0

output:

result:

ok q=0

Test #3:

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

input:

0 0
1
?

output:

0

result:

ok q=1

Test #4:

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

input:

1000 2000
1 50
1 88
331 1
1 352
1 497
2 32
2 282
550 2
989 2
334 3
3 665
4 38
4 69
4 343
4 451
589 4
917 4
89 5
5 162
675 5
681 6
7 22
127 7
7 592
7 672
787 7
8 310
107 9
9 137
184 9
9 244
378 9
446 9
9 658
883 9
65 10
75 10
414 10
10 468
686 10
245 11
269 11
11 386
403 11
493 11
394 12
493 12
565 1...

output:

1
4
5
8
9
12
29
33
39
42
49
59
69
70
71
73
75
81
82
83
84
87
89
91
94
107
114
118
120
125
129
131
132
133
135
145
148
152
155
163
173
185
190
199
200
201
202
203
204
205
206
208
211
213
214
218
233
234
238
251
252
181
254
255
262
253
263
264
265
270
271
272
34
274
275
285
287
291
292
174
295
296
297...

result:

ok q=100000

Test #5:

score: 0
Accepted
time: 512ms
memory: 14952kb

input:

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

output:

8

result:

ok q=100000

Test #6:

score: 0
Accepted
time: 442ms
memory: 14616kb

input:

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

output:

256
44
113
161
202
350
85
282
377
530
21
176
450
466
40
46
47
41
18
55
3
82
37
69
114
117
126
2
127
4
6
7
8
9
10
12
13
14
17
20
22
23
25
26
27
30
31
34
36
39
45
48
49
57
60
63
67
71
74
83
84
87
89
92
95
105
112
111
116
120
122
123
130
134
137
139
141
144
149
155
159
138
160
162
163
164
165
42
169
17...

result:

ok q=100000

Test #7:

score: 0
Accepted
time: 356ms
memory: 14760kb

input:

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

output:

625
107
186
137
154
220
305
57
54
71
78
200
188
224
193
267
145
103
126
160
189
271
281
306
307
318
323
298
333
328
236
340
68
342
77
94
368
376
380
237
392
106
128
172
287
413
62
205
418
434
7
20
222
227
130
173
144
33
59
152
174
191
192
212
290
322
361
161
320
365
373
395
389
45
399
410
35
153
127...

result:

ok q=100000

Test #8:

score: 0
Accepted
time: 224ms
memory: 14480kb

input:

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

output:

0
141
93
27
152
240
189
191
20
151
220
375
379
414
441
465
472
538
565
572
264
596
686
737
303
369
648
739
748
99
32
477
544
909
169
614
916
353
757
320
765
919
921
29
474
747
823
918
988
787
1007
601
731
1009
47
185
1
3
5
9
13
14
17
19
21
23
25
26
28
31
33
34
36
37
38
39
41
42
44
49
50
51
56
58
59
...

result:

ok q=100000

Test #9:

score: 0
Accepted
time: 176ms
memory: 14540kb

input:

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

output:

0
0
0
0
0
0
0
0
81
102
379
547
1711
364
378
809
1696
1855
1876
184
583
629
1516
1523
322
767
1620
838
1282
1654
281
726
1170
1912
861
1305
1427
2055
2096
2138
2152
2153
371
237
882
1703
2167
2211
2310
611
753
43
131
488
546
111
556
576
656
1000
1020
310
755
1055
1197
1375
1443
535
1498
1543
712
1156...

result:

ok q=100000

Test #10:

score: 0
Accepted
time: 116ms
memory: 14740kb

input:

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

output:

0
0
0
0
1062
1947
2828
3705
4142
5880
6312
6743
884
2213
3094
5279
5713
6146
493
937
1078
1380
1822
2263
2703
3142
946
3151
3580
3589
4017
4026
4158
4453
4462
4888
4897
5331
5755
274
1606
3368
4243
5114
5548
5896
6187
6578
6759
6844
7009
7048
7057
7173
7189
7274
7477
7486
7703
7868
7905
261
706
821
...

result:

ok q=100000

Test #11:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #12:

score: 0
Accepted
time: 483ms
memory: 15700kb

input:

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

output:

3

result:

ok q=100000

Test #13:

score: 0
Accepted
time: 395ms
memory: 15468kb

input:

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

output:

9
10
15
16
20
21
25
33
39
50
52
45
53
58
42
61
63
64
71
72
81
2
3
4
8
13
14
26
29
32
34
36
38
40
46
48
55
56
59
60
65
66
82
86
90
103
113
114
125
130
144
146
148
149
151
84
155
156
139
165
173
174
177
187
27
132
189
194
143
196
201
96
209
212
213
137
92
147
157
176
200
112
163
214
182
215
216
217
22...

result:

ok q=100000

Test #14:

score: 0
Accepted
time: 350ms
memory: 14536kb

input:

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

output:

5
12
14
20
27
28
32
36
39
44
48
49
60
62
66
70
71
73
80
81
85
94
22
98
107
108
109
115
123
29
128
95
129
50
130
137
144
145
150
152
154
162
163
169
178
164
188
189
182
193
198
206
209
220
196
223
190
216
226
227
229
232
235
243
247
263
266
269
271
272
274
275
279
283
286
290
320
326
331
334
351
208
...

result:

ok q=100000

Test #15:

score: 0
Accepted
time: 278ms
memory: 14828kb

input:

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

output:

2
3
6
8
10
14
17
20
21
22
27
31
34
38
39
42
43
48
52
58
59
61
68
80
81
93
97
102
103
113
119
134
136
142
147
150
151
95
157
158
159
160
91
164
168
169
173
174
186
191
192
40
73
146
183
200
180
202
204
205
210
217
221
223
125
224
225
227
229
233
118
238
242
245
250
251
264
265
26
270
279
290
296
302
...

result:

ok q=100000

Test #16:

score: 0
Accepted
time: 169ms
memory: 15368kb

input:

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

output:

1
3
7
11
15
19
26
27
29
30
32
38
39
41
43
45
47
49
62
63
69
70
68
78
80
81
82
83
84
88
89
99
103
104
114
115
116
124
126
127
130
131
136
138
141
144
145
151
152
156
157
160
161
169
170
173
178
179
180
182
187
188
191
202
208
211
230
232
235
239
241
250
254
255
263
264
271
273
276
281
288
294
295
297...

result:

ok q=100000

Test #17:

score: 0
Accepted
time: 76ms
memory: 14836kb

input:

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

output:

1
2
6
7
9
10
11
23
24
28
34
42
50
56
58
72
73
77
80
86
96
98
104
112
114
120
124
130
138
143
146
148
149
160
162
165
167
174
177
180
182
192
205
209
220
224
226
230
233
235
240
241
246
252
255
258
263
274
279
281
283
298
299
300
310
313
318
325
326
329
337
345
348
351
353
354
358
359
360
361
363
365...

result:

ok q=100000

Test #18:

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

input:

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

output:

8
9
10
14
16
17
19
22
23
24
25
31
37
38
45
53
66
71
77
78
79
82
90
91
107
108
110
111
112
115
118
119
123
130
135
140
143
159
161
171
173
179
182
191
197
207
211
217
221
222
229
234
237
238
241
242
244
248
254
260
267
270
274
276
278
280
283
284
297
299
302
306
307
308
310
311
321
324
326
331
335
34...

result:

ok q=100000

Test #19:

score: 0
Accepted
time: 532ms
memory: 15544kb

input:

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

output:

1

result:

ok q=100000

Test #20:

score: 0
Accepted
time: 427ms
memory: 15328kb

input:

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

output:

16
44
38
62
76
43
85
32
69
61
83
86
92
104
64
39
72
105
108
126
22
40
131
46
136
143
90
146
137
151
41
149
152
12
20
172
174
52
56
4
28
109
139
161
182
198
212
235
245
270
154
273
256
280
107
285
194
289
75
292
305
205
249
5
53
138
308
3
111
181
199
133
227
213
197
231
244
267
269
318
17
322
323
325...

result:

ok q=100000

Test #21:

score: 0
Accepted
time: 338ms
memory: 14404kb

input:

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

output:

1
447
448
449
83
359
375
376
428
443
208
236
57
77
260
10
90
305
126
142
43
274
196
13
21
30
155
206
234
279
158
299
59
119
232
320
48
321
354
356
18
235
141
179
231
176
148
20
28
215
288
93
293
257
319
335
360
368
371
374
380
381
382
416
417
420
242
421
128
282
146
427
434
435
438
445
450
402
99
31...

result:

ok q=100000

Test #22:

score: 0
Accepted
time: 267ms
memory: 14380kb

input:

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

output:

0
0
81
376
526
35
480
870
686
164
220
609
639
750
805
264
345
66
303
308
511
709
753
790
863
1033
1083
1130
1029
1153
1197
691
191
94
321
366
6
235
408
435
451
538
572
680
714
824
72
607
756
835
199
361
719
806
452
65
862
102
124
487
547
569
880
895
896
931
22
467
320
937
161
198
223
222
252
317
325...

result:

ok q=100000

Test #23:

score: 0
Accepted
time: 187ms
memory: 14860kb

input:

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

output:

254
186
631
699
1075
1586
1440
1681
1831
1882
147
567
576
592
253
1036
1142
1463
490
934
483
927
1377
1819
14
459
1346
1896
1921
2028
305
750
1637
2070
2123
2253
2337
327
740
772
931
214
292
1546
1627
1659
96
644
1088
420
499
622
865
1066
1428
416
380
613
143
588
730
825
861
1269
1500
1531
370
401
8...

result:

ok q=100000

Test #24:

score: 0
Accepted
time: 84ms
memory: 15860kb

input:

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

output:

0
0
0
0
1231
1674
2997
3436
3874
5616
1494
1936
2377
2817
1091
1534
1976
2417
2857
3296
3734
4131
4171
4607
5436
6341
6732
1502
4139
423
318
1207
1312
1484
1650
910
386
831
1466
1718
1908
547
1434
1658
1197
151
596
1040
841
1401
1483
1640
1876
1075
1926
460
1347
1789
2134
2160
1284
2169
2197
2230
87...

result:

ok q=100000

Test #25:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #26:

score: 0
Accepted
time: 524ms
memory: 15592kb

input:

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

output:

1

result:

ok q=100000

Test #27:

score: 0
Accepted
time: 413ms
memory: 16188kb

input:

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

output:

242
78
523
278
282
40
196
186
234
247
284
300
317
99
49
170
277
129
203
212
28
111
184
215
158
30
52
48
144
21
197
239
257
322
304
328
340
352
360
390
393
161
413
24
280
50
416
417
44
271
124
236
357
365
422
389
408
55
171
420
206
312
91
302
359
423
113
154
177
152
380
382
425
368
266
431
433
61
351...

result:

ok q=100000

Test #28:

score: 0
Accepted
time: 332ms
memory: 15408kb

input:

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

output:

9
83
304
454
483
528
210
656
737
305
750
751
598
12
53
54
279
283
457
498
499
534
536
458
551
557
149
448
580
354
581
324
58
245
366
312
389
239
466
503
555
561
547
142
230
318
488
405
587
591
592
594
603
609
100
545
90
535
413
42
123
27
131
433
175
322
409
355
96
472
20
29
33
36
50
56
65
79
80
87
8...

result:

ok q=100000

Test #29:

score: 0
Accepted
time: 243ms
memory: 14644kb

input:

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

output:

5225
8670
859
1304
2631
2
446
508
524
580
645
670
892
893
895
161
472
602
606
655
516
637
466
525
725
779
798
804
810
639
885
886
896
738
897
818
898
899
486
901
836
902
903
904
905
906
907
511
679
908
773
499
586
800
476
507
871
909
910
913
915
918
920
430
608
707
709
846
876
816
610
922
923
924
92...

result:

ok q=100000

Test #30:

score: 0
Accepted
time: 173ms
memory: 15444kb

input:

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

output:

0
246
692
1137
1581
2023
253
699
2464
328
2471
134
580
213
659
1025
1469
2352
408
118
854
348
76
522
523
607
794
967
968
207
653
1098
191
369
815
1082
1239
1299
399
845
119
81
527
364
565
418
428
550
576
810
864
870
874
972
126
10
215
456
572
79
154
600
286
31
477
579
901
922
1017
1045
1177
1255
131...

result:

ok q=100000

Test #31:

score: 0
Accepted
time: 101ms
memory: 14784kb

input:

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

output:

0
0
0
0
0
0
777
1222
1552
1666
2109
2877
2991
3868
761
2093
2975
3852
50
495
872
233
678
940
1123
1142
682
1384
1567
1571
1761
1827
2010
2014
2029
2204
2452
2709
2892
2896
3586
3769
63
39
457
484
508
929
953
1070
1373
1397
1514
1816
1840
2258
2282
2671
2698
2722
683
1572
1850
2839
2897
3087
3138
357...

result:

ok q=100000

Test #32:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #33:

score: 0
Accepted
time: 523ms
memory: 15512kb

input:

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

output:

11

result:

ok q=100000

Test #34:

score: 0
Accepted
time: 417ms
memory: 15852kb

input:

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

output:

10
57
70
74
141
142
156
6
7
19
68
88
97
134
222
242
324
380
402
410
434
1
176
447
457
462
463
466
474
476
337
385
477
482
485
487
488
491
493
446
450
451
452
362
453
454
456
468
471
473
475
478
479
480
489
490
492
498
499
505
508
509
220
241
366
377
444
512
517
519
522
494
523
527
532
541
546
551
55...

result:

ok q=100000

Test #35:

score: 0
Accepted
time: 343ms
memory: 15640kb

input:

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

output:

14
15
18
22
24
25
26
36
37
38
39
40
41
43
5
49
51
53
54
57
60
61
68
71
75
70
80
81
86
90
91
95
96
97
101
106
112
113
62
114
117
118
119
124
125
129
133
135
136
140
141
143
146
147
150
153
155
149
156
162
165
160
157
181
9
182
23
45
184
185
188
195
109
196
198
6
17
21
104
199
12
89
174
66
201
205
148...

result:

ok q=100000

Test #36:

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

input:

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

output:

26
55
71
107
123
216
251
305
347
443
446
447
450
451
456
462
465
467
469
470
472
474
476
478
479
480
492
496
503
504
508
512
515
516
518
522
526
528
533
525
534
535
538
539
542
545
546
16
460
464
549
477
551
396
556
557
562
564
566
567
574
578
582
561
585
587
588
590
352
559
592
229
595
606
607
609
...

result:

ok q=100000

Test #37:

score: 0
Accepted
time: 186ms
memory: 15460kb

input:

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

output:

4
5
7
12
14
15
20
23
24
27
29
32
33
36
41
46
47
48
43
51
53
69
72
79
81
82
83
85
91
97
62
99
100
105
106
112
115
119
123
125
126
131
133
135
136
139
140
141
145
147
148
150
151
152
155
162
165
166
168
174
175
177
80
178
179
183
49
184
188
190
191
195
201
206
207
66
211
212
213
215
217
219
224
225
22...

result:

ok q=100000

Test #38:

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

input:

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

output:

1
9
11
16
22
27
31
34
42
48
49
50
51
53
57
60
61
65
67
72
73
76
79
80
83
85
88
90
91
95
101
107
109
110
111
112
114
117
119
120
125
126
127
129
132
133
136
140
142
143
147
149
151
153
154
155
156
158
160
162
163
171
173
174
176
178
180
184
185
186
187
188
118
191
194
196
199
202
208
212
214
218
220
...

result:

ok q=100000

Test #39:

score: 0
Accepted
time: 59ms
memory: 15872kb

input:

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

output:

1
11
12
15
17
19
20
25
27
28
29
30
34
36
37
38
40
43
45
48
49
52
53
56
58
59
60
64
67
69
72
73
75
78
81
82
83
86
87
89
90
92
93
95
97
98
104
107
109
110
112
115
116
125
128
139
140
141
143
145
146
147
150
152
155
156
160
162
164
170
174
177
184
185
189
196
199
200
201
202
205
207
213
219
222
223
224...

result:

ok q=100000

Test #40:

score: 0
Accepted
time: 519ms
memory: 15096kb

input:

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

output:

2

result:

ok q=100000

Test #41:

score: 0
Accepted
time: 452ms
memory: 15740kb

input:

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

output:

2739
3
5
11
19
26
38
45
50
61
81
142
144
35
66
118
151
160
169
9
123
43
74
155
216
22
46
91
117
8
104
172
47
24
7
69
29
32
94
126
1
20
58
70
100
87
128
79
154
23
157
161
159
162
163
165
51
116
176
13
15
53
131
153
166
147
135
158
164
28
136
63
124
149
167
173
137
175
59
92
64
143
171
188
199
201
68
...

result:

ok q=100000

Test #42:

score: 0
Accepted
time: 353ms
memory: 15732kb

input:

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

output:

0
32
55
99
108
162
167
206
208
248
6
70
82
102
116
190
258
286
141
118
288
300
315
318
114
25
131
176
239
8
166
210
80
101
224
231
106
235
127
150
194
244
265
273
290
291
304
323
126
21
38
154
180
312
329
330
332
276
168
314
336
233
337
338
344
189
346
350
223
285
358
359
227
298
121
353
4
9
22
13
2...

result:

ok q=100000

Test #43:

score: 0
Accepted
time: 250ms
memory: 15068kb

input:

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

output:

0
0
0
0
0
0
0
183
2401
3717
820
1708
314
351
760
239
258
14
685
704
797
1129
1148
1241
1573
84
530
328
396
547
774
102
548
2
184
308
372
377
87
333
426
439
448
630
754
148
169
594
197
615
643
51
497
779
398
800
823
205
154
75
59
115
117
133
196
505
521
1
449
237
303
450
452
217
440
453
125
212
454
4...

result:

ok q=100000

Test #44:

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

input:

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

output:

109
555
1443
1886
258
117
550
563
1438
1451
1573
1894
2016
2768
2776
2898
560
184
630
1518
10
168
325
456
614
771
1215
178
224
345
90
427
187
122
381
447
190
568
624
667
356
791
797
802
808
827
466
342
873
1
247
448
449
451
452
76
253
302
453
455
292
457
458
459
460
462
465
467
468
469
470
471
473
4...

result:

ok q=100000

Test #45:

score: 0
Accepted
time: 111ms
memory: 15608kb

input:

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

output:

0
667
1112
1997
2878
3318
3467
4193
4629
5065
5214
5500
5934
6367
6516
6799
583
1028
984
617
1947
1970
3234
3291
3515
4501
4579
4602
4826
4981
5015
5262
5372
871
4833
5269
5473
5697
5704
5850
724
2054
3375
5557
6131
6138
6340
6424
6715
6772
6856
6948
6996
7146
7180
7203
7230
882
1327
2212
3093
3533
...

result:

ok q=100000

Test #46:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #47:

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

input:

100000 100000
5722 1
35633 1
76503 1
2 8454
2 93428
3 91414
4 55025
21132 5
6 22400
6 80941
7 22043
7 29361
7 73158
78568 7
8 24159
8 26175
27612 9
39375 9
5454 10
24262 10
40601 10
11 8620
59525 11
11 79781
11 92891
64034 12
33728 14
14 59378
14 79826
560 16
16 31445
35262 16
17911 17
28509 17
9364...

output:

2

result:

ok q=100000

Test #48:

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

input:

100000 100000
32763 1
1 41318
52251 1
66464 2
83572 2
67186 5
7 64990
34545 8
8 96178
8628 9
10 8181
94794 15
16 33467
16 34451
85594 16
17 20413
31799 17
17 41753
18 61787
71853 18
19 5788
19 49136
97968 19
34661 20
20 61751
95244 20
20211 21
31082 21
22 96882
53538 23
53831 24
81268 24
25 52202
61...

output:

48490
48487
22645
30537
13512
1066
8174
13513
9533
27929
27930
12728
17100
21764
21765
21766
21767
21768
23825
24251
8756
19557
24252
12032
13522
17391
18077
189
1844
8750
18078
5177
5176
15970
15971
10158
18080
13628
1084
2924
4460
8664
18634
18985
24798
539
540
541
5293
900
19634
15619
22070
19288...

result:

ok q=100000

Test #49:

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

input:

100000 100000
98 1
1 39536
2 7197
2 36925
64304 2
3 90981
4 55694
4 58594
6 14112
6 61223
49657 7
49961 8
9 63064
84290 9
9616 10
10 26834
10 81424
11 28592
66665 11
11 67518
12 65671
12 77007
13 83518
88724 13
14 22525
28934 14
38904 15
18454 16
16 34371
33103 17
63576 17
46939 18
67514 18
18 72374...

output:

17512
3764
15688
15689
249
250
251
252
253
254
4317
10918
15690
15691
8018
8019
16066
16067
16068
17940
10169
21537
23848
26126
23847
29360
29566
31330
28220
22718
31397
32562
36043
10188
38578
3597
34478
12992
38283
24130
10520
39031
39032
39033
39034
39162
38840
16596
34795
40210
40673
2198
35416
...

result:

ok q=100000

Test #50:

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

input:

100000 100000
1 30554
51310 1
1 71883
94585 1
2 40250
59351 2
2 60517
72989 3
4 3248
14035 4
4 90751
5 786
6 10125
87221 6
22862 7
7 57323
67940 7
40455 8
8 66854
9 34854
9 87440
43694 10
10 57462
82982 10
94968 10
47934 11
11 71829
24007 12
44565 12
48286 12
70260 12
12 70368
98761 12
20547 14
7549...

output:

40431
11901
49549
49550
49551
50261
26532
45418
52035
58649
35164
14555
3268
3269
3270
35452
35453
35454
8106
16879
9191
26073
31354
31355
41475
18489
34109
41209
18538
56894
48037
71477
71478
3678
60494
22737
29370
21390
33367
57130
63519
71439
25349
17118
36518
76838
55161
14848
16052
12467
16897
...

result:

ok q=100000

Test #51:

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

input:

100000 100000
26140 1
46196 2
2 54845
78912 3
3 90871
4 12358
5 33609
5 43410
5 78393
47818 6
7 48862
13216 8
8 36636
8 40979
52931 8
8 80000
94821 8
52306 10
14072 12
36807 12
66342 12
344 13
13 4469
13 14570
13 52573
15 29037
15 38532
86576 15
16 9718
43023 16
16 86523
19 16448
20 15703
20 62471
8...

output:

0
0
0
0
33676
0
0
0
3296
56000
25081
25082
25083
38370
38371
28482
38372
43568
64094
70591
81127
1281
6360
12953
12954
9126
9128
12955
12956
61668
9074
9127
76367
8056
48282
34967
13771
62237
14145
62238
28457
81468
81469
23814
845
90104
11407
35692
40004
59096
67816
88272
88273
90105
90102
90103
19...

result:

ok q=100000

Test #52:

score: 0
Accepted
time: 52ms
memory: 16184kb

input:

100000 100000
2005 1
1 15170
57799 2
4 38977
4 57240
42542 5
5 53318
5 75678
6 88650
65147 7
8 53626
8 70633
22352 10
11 49862
12 14548
12 50661
12 69416
13 22675
13 57792
3230 14
61629 16
16 94304
19 4752
11292 19
19 23963
47970 19
3280 20
20 13431
37640 20
20 43437
22 59910
69629 22
94875 22
23 52...

output:

0
0
63811
63812
0
0
0
0
0
0
0
0
0
0
0
0
0
64070
0
0
0
0
0
0
0
0
0
0
0
0
0
17930
17931
0
0
0
0
0
0
0
0
0
0
22976
25298
25349
0
46890
63870
79011
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
23473
49655
54550
57471
74503
0
0
0
0
55883
79931
79932
0
0
0
0
0
0
0
0
94320
95578
95579
0
0
72970
93452
0
0
0
0
0
0
...

result:

ok q=100000

Test #53:

score: 0
Accepted
time: 47ms
memory: 16304kb

input:

100000 100000
40394 1
75982 2
3 18844
73366 3
88698 3
4020 6
6 73638
7 22013
65853 7
8 75952
8 91846
8 92431
35947 9
25852 10
60988 10
84698 10
49696 11
60792 11
94447 12
29797 13
14 32289
14 45866
85823 14
15 5953
19579 15
9976 16
16 26641
17 70399
80811 17
18 57277
19 24826
19 72978
15405 20
64474...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #54:

score: 0
Accepted
time: 28ms
memory: 16432kb

input:

100000 100000
1 46719
1 85926
2 31507
3 10325
25701 3
4 20660
4 24390
5 28826
5 32895
5 65707
5 85849
26769 6
35848 6
8 31592
9 6175
10 10273
10 49762
8543 11
12 1257
12 49533
67310 12
12 85402
4042 13
13 91901
14 36759
95374 14
40235 16
16 95131
17 47185
49412 17
86267 17
30733 18
19 36525
99630 20...

output:

4

result:

ok q=100000

Test #55:

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

input:

100000 100000
1 14816
1 36843
1 67254
69974 1
3 22460
4 94861
51245 5
5 53683
54692 6
6 91387
6 91712
8 56288
8 88631
9 4475
23107 9
9 37340
18545 10
10 32507
10 37510
86500 10
57406 11
11 96238
486 12
12 44026
51175 13
14 92685
14 94886
14 99844
66818 15
58293 16
16 92531
17 32186
36963 18
18 53409...

output:

1
3
4
9
10
13
33
36
38
41
48
49
50
52
55
57
63
64
65
80
83
89
91
92
94
99
101
104
105
110
117
119
124
126
127
138
139
140
141
143
147
149
150
151
153
154
160
162
172
181
182
183
189
192
195
196
197
199
200
202
207
213
221
229
241
249
252
253
254
262
272
273
274
275
277
279
281
293
298
299
302
306
30...

result:

ok q=100000

Test #56:

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

input:

100000 100000
1 92961
32241 2
2 81221
4608 3
16927 3
18769 3
3 43374
22317 4
55044 4
18810 5
6 72739
61007 7
9 25577
9 27864
34366 9
10 16913
30734 10
40980 10
60805 10
74697 10
82279 10
10021 11
23696 12
36468 12
51197 12
86124 12
12 89628
14 6535
14 21742
14 36158
57841 14
15 81216
15 84873
16 457...

output:

4
6
8
18
25
26
28
29
31
37
42
48
49
50
52
57
60
67
68
69
70
72
81
86
92
95
97
98
109
111
112
119
123
125
128
130
131
134
135
144
145
146
147
148
149
156
169
172
174
179
180
185
192
196
197
199
202
206
209
210
218
228
230
240
241
245
258
263
272
275
278
293
300
301
302
306
308
312
315
319
322
323
327...

result:

ok q=100000

Test #57:

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

input:

100000 100000
1 27333
1 84324
96084 1
9114 2
85952 2
3 5372
4 6733
9091 4
58622 4
4 86657
14441 5
55881 5
77265 5
5 80838
6 348
8 52617
8 61683
11583 9
9 73540
93581 9
94661 9
9 98721
46654 10
10 52226
12 55380
12 79729
13 40841
13 58505
80468 13
57058 14
14 59095
23508 15
68757 15
6286 17
17 39373
...

output:

9
11
12
13
20
21
22
24
33
44
45
46
48
49
69
70
73
74
83
87
92
93
101
104
106
107
118
121
126
131
133
135
136
155
156
157
158
159
172
178
182
189
193
200
202
208
210
217
218
219
220
222
228
229
230
233
237
238
239
240
241
242
243
248
250
252
253
262
272
273
278
291
292
295
298
303
304
305
308
311
312...

result:

ok q=100000

Test #58:

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

input:

100000 100000
60818 1
1 61357
77477 1
3 45025
59533 3
46950 4
78991 4
97104 4
36194 5
6 64485
1740 7
5623 8
23553 8
16292 9
62566 9
9 98158
10 23566
10 47129
84382 10
10 89508
11 12522
54918 11
82691 14
89591 14
15 22620
22939 16
56415 16
16 83923
18 29619
18 83502
19 24669
79130 19
43646 20
21 6966...

output:

3
13
14
15
23
26
27
36
37
38
39
40
43
44
55
58
60
65
67
74
76
78
82
87
90
91
112
113
115
116
117
119
124
127
130
133
134
137
153
154
166
171
174
178
184
186
193
194
195
199
206
212
219
222
225
234
235
236
237
251
254
258
260
261
262
270
272
273
277
288
293
294
297
303
307
314
319
326
331
334
346
347...

result:

ok q=100000

Test #59:

score: 0
Accepted
time: 59ms
memory: 15968kb

input:

100000 100000
34616 1
58002 1
1 70045
10303 2
2 39631
40632 2
10056 3
41853 3
70173 3
4 92959
5 47483
16468 6
50684 6
67732 6
84535 7
47014 8
59046 9
10 65208
10 78362
11266 11
24545 11
12 21449
66415 12
92002 12
13 19643
13 23316
96267 14
91298 15
17801 16
49544 16
69757 16
4694 17
17 24548
221 18
...

output:

14
26
29
30
42
47
48
54
59
60
71
73
74
81
84
86
94
100
101
109
112
115
116
120
137
145
154
160
161
167
169
170
175
177
178
184
187
188
189
193
194
211
219
221
225
228
229
231
232
233
236
238
241
244
245
246
252
254
264
272
274
278
280
285
288
289
300
306
307
309
310
311
315
317
321
326
330
332
333
3...

result:

ok q=100000

Test #60:

score: 0
Accepted
time: 44ms
memory: 16204kb

input:

100000 100000
1 14279
25034 1
1 25644
1 33907
55554 1
32635 2
48898 2
67742 2
30821 3
62159 3
62878 4
4 99567
5427 5
81073 5
40389 6
68943 6
86783 6
7 7357
8 43901
8 49165
66447 8
15193 10
10 27651
52896 10
11 21927
31071 11
65058 11
1885 12
12 86604
13 34951
13 57211
73415 13
76672 13
31146 14
4934...

output:

1
3
10
17
20
22
24
32
33
40
44
46
48
50
61
68
69
70
71
73
75
76
88
104
109
117
126
128
129
131
133
135
144
151
155
159
164
166
168
171
174
178
181
182
186
187
191
192
201
216
217
218
219
224
228
233
242
243
249
251
253
255
257
259
269
270
271
273
275
277
280
281
285
290
292
295
304
309
310
311
312
3...

result:

ok q=100000

Test #61:

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

input:

100000 100000
36686 1
2 28317
3 43331
58975 3
9005 5
5 38587
85424 5
87253 5
91242 6
7 12636
7 28747
43112 7
56525 7
95056 7
8 67866
8 96414
15486 9
9 17569
9 27913
9 45216
57385 9
12037 10
10 26847
68194 10
10 69558
91082 10
1181 11
29864 11
11 51315
74564 11
11 99360
50347 12
12 70424
80616 12
810...

output:

result:

ok q=100000

Test #62:

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

input:

100000 100000
19575 1
26203 1
72508 1
1 97963
14667 2
16976 2
3 6175
3 67390
3 85817
3 95274
61098 4
5 63076
48837 6
6 85456
8 11139
8053 9
9 14304
9 42080
78302 9
87001 9
95714 9
10 11640
10 38250
11 68261
33284 12
34067 13
37576 13
13 83578
15 23823
35578 16
57809 16
17 35284
43161 17
17 47477
516...

output:

result:

ok q=100000

Test #63:

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

input:

100000 100000
36059 1
46485 1
23653 2
73424 2
2 74494
51828 3
4 33328
53661 4
34793 5
6 51871
55444 6
6 65656
8 16246
8 34477
10425 9
62445 9
21534 10
10 30313
60761 10
96061 10
7597 11
11 15469
63367 12
40382 13
14 75126
15 56288
15 84929
53927 16
64468 16
17 53139
18 5845
76176 18
19 24677
19 5891...

output:

result:

ok q=100000

Test #64:

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

input:

100000 100000
20177 2
2 98955
3 46743
3 46866
62628 3
12631 4
75181 4
5 54593
27546 6
6 31901
6 83336
6 90688
7 32220
7 63366
8 61776
37721 9
9 48206
9 70008
96585 9
10 62990
98079 10
11 11607
21944 11
11 80964
13 9208
13 49235
13 69968
13 85800
38176 14
57272 14
15 3765
16 67576
17 40546
17 44435
1...

output:

result:

ok q=100000

Test #65:

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

input:

100000 100000
1 33218
2 26924
4 22063
4 72727
83189 4
5 26165
50928 5
6 12110
17480 7
39161 7
7 76692
20436 8
36025 8
9 52297
9 58874
67940 9
10 17168
10 40179
10665 11
11 26766
11 26798
28558 11
41443 11
91932 11
11 96520
12 38384
89050 13
14 44040
14 60933
63286 14
14 91796
38298 15
83369 15
20977...

output:

result:

ok q=100000

Test #66:

score: 0
Accepted
time: 21ms
memory: 16164kb

input:

100000 100000
97038 1
2 12394
73478 2
27345 3
3 52828
3 94198
17649 4
34700 4
4 48092
90308 4
4 92571
5 73178
5 96066
1197 6
79796 6
6 95080
7 6897
7 96564
8 57604
8 70048
29738 10
10 42975
10 99064
11 20156
11 25952
51206 11
11 97949
38714 12
92965 12
10950 13
15 6617
8272 15
17383 15
37580 15
5035...

output:

result:

ok q=100000

Test #67:

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

input:

100000 100000
1 43054
1 66061
45045 4
81759 5
15827 6
6 40801
78430 6
6 83704
3488 9
32237 9
10 8261
10 37635
98555 10
82566 11
30294 12
68894 12
13 32989
92708 14
94972 14
15 41948
16 28327
20490 17
52712 17
18 23230
18 77251
9533 19
66382 19
20 10583
23214 22
32369 22
24 32167
75443 24
26 9052
278...

output:

result:

ok q=100000

Test #68:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #69:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #70:

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

input:

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

output:

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

result:

ok q=100000

Test #71:

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

input:

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

output:

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

result:

ok q=100000

Test #72:

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

input:

99970 100000
2 1
1 3
5 1
7 1
9 1
1 11
13 1
15 1
1 17
1 19
1 21
1 23
1 25
27 1
1 29
31 1
1 33
1 35
37 1
1 39
1 41
1 43
45 1
47 1
1 49
51 1
1 53
55 1
57 1
59 1
1 61
63 1
65 1
1 67
69 1
71 1
73 1
75 1
77 1
79 1
81 1
1 83
85 1
1 87
1 89
91 1
1 93
1 95
1 97
99 1
1 101
1 103
1 105
107 1
109 1
111 1
1 113
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #73:

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

input:

99970 100000
2 1
3 1
5 1
7 1
1 9
1 11
1 13
15 1
1 17
19 1
21 1
23 1
1 25
27 1
29 1
1 31
33 1
1 35
37 1
1 39
1 41
1 43
45 1
47 1
1 49
1 51
53 1
1 55
1 57
59 1
61 1
63 1
65 1
67 1
69 1
1 71
73 1
1 75
1 77
79 1
1 81
1 83
85 1
1 87
89 1
91 1
1 93
1 95
97 1
99 1
1 101
103 1
1 105
1 107
1 109
1 111
113 1
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #74:

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

input:

99970 100000
2 1
3 1
5 1
7 1
9 1
11 1
1 13
1 15
1 17
19 1
1 21
1 23
1 25
1 27
1 29
1 31
1 33
1 35
37 1
39 1
1 41
1 43
1 45
47 1
1 49
51 1
1 53
55 1
57 1
59 1
1 61
63 1
1 65
1 67
1 69
1 71
73 1
75 1
77 1
1 79
1 81
1 83
1 85
1 87
89 1
91 1
93 1
1 95
1 97
1 99
101 1
103 1
1 105
1 107
1 109
111 1
1 113
...

output:

1
2
3
4
49986
0
49987
5
6
7
49988
0
8
0
9
10
49989
0
49990
0
11
12
49991
0
49992
13
49993
14
49994
15
16
17
18
19
49995
20
21
22
23
0
24
25
49996
26
49997
0
49998
27
49999
0
28
29
30
0
31
0
50000
0
50001
0
50002
32
33
34
35
36
50003
0
37
0
38
39
50004
0
50005
40
41
42
43
44
50006
0
50007
45
46
47
48...

result:

ok q=100000

Test #75:

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

input:

99970 100000
2 1
3 1
5 1
7 1
1 9
11 1
13 1
1 15
1 17
1 19
21 1
1 23
25 1
27 1
1 29
1 31
1 33
1 35
37 1
1 39
41 1
43 1
1 45
1 47
1 49
51 1
53 1
1 55
1 57
59 1
1 61
63 1
65 1
1 67
69 1
1 71
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
1 97
99 1
101 1
103 1
1 105
1 107
1 109
1 111
113 1
...

output:

0
0
0
1
49986
49987
49988
49989
49990
49991
0
2
0
0
49992
49993
3
4
0
0
0
0
0
0
5
6
7
8
9
10
11
49994
12
13
14
15
49995
49996
49997
49998
49999
0
50000
0
0
0
0
50001
0
16
17
18
19
50002
20
21
50003
50004
50005
22
23
24
25
26
27
28
29
30
0
0
31
32
33
34
50006
35
36
37
50007
0
50008
50009
50010
50011
...

result:

ok q=100000

Test #76:

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

input:

99970 100000
1 2
3 1
4 1
1 7
1 10
1 13
16 1
19 1
1 22
25 1
1 28
1 31
34 1
1 37
40 1
1 43
1 46
1 49
52 1
1 55
1 58
61 1
64 1
1 67
70 1
73 1
76 1
1 79
82 1
1 85
88 1
1 91
1 94
97 1
100 1
1 103
106 1
109 1
112 1
115 1
118 1
1 121
124 1
1 127
130 1
1 133
1 136
139 1
1 142
1 145
1 148
1 151
1 154
1 157
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #77:

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

input:

99970 100000
3 1
1 4
1 7
1 10
1 13
16 1
1 19
1 22
1 25
1 28
1 31
34 1
1 37
40 1
43 1
46 1
1 49
1 52
1 55
58 1
1 61
64 1
67 1
70 1
1 73
1 76
79 1
1 82
85 1
1 88
91 1
94 1
1 97
1 100
1 103
106 1
109 1
1 112
115 1
1 118
121 1
1 124
127 1
130 1
1 133
136 1
139 1
142 1
1 145
1 148
151 1
1 154
157 1
1 160...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #78:

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

input:

99970 100000
3 1
1 4
1 7
1 10
1 13
16 1
19 1
22 1
25 1
1 28
1 31
1 34
1 37
1 40
1 43
46 1
49 1
1 52
55 1
1 58
1 61
1 64
67 1
70 1
1 73
76 1
1 79
1 82
1 85
88 1
1 91
94 1
97 1
100 1
1 103
1 106
1 109
1 112
1 115
118 1
121 1
1 124
127 1
130 1
1 133
1 136
139 1
142 1
145 1
148 1
1 151
154 1
1 157
1 160...

output:

1
0
33325
2
66648
0
33326
33327
33328
3
33329
4
33330
33331
33332
0
5
6
7
8
9
33333
10
33334
11
12
33335
13
33336
14
33337
15
16
17
18
19
20
33338
33339
21
33340
33341
22
23
24
25
33342
33343
26
27
28
29
66649
33344
66650
33345
66651
33346
33347
33348
30
31
32
0
33349
0
33
34
35
33350
66652
0
66653
...

result:

ok q=100000

Test #79:

score: 0
Accepted
time: 52ms
memory: 15160kb

input:

99970 100000
1 2
3 1
4 1
7 1
1 10
1 13
16 1
1 19
22 1
25 1
1 28
1 31
1 34
1 37
40 1
1 43
1 46
1 49
1 52
55 1
1 58
61 1
64 1
67 1
70 1
1 73
76 1
79 1
82 1
85 1
88 1
91 1
94 1
1 97
1 100
103 1
106 1
109 1
1 112
115 1
1 118
1 121
124 1
127 1
130 1
1 133
136 1
1 139
1 142
1 145
1 148
151 1
154 1
1 157
1...

output:

1
2
3
4
0
0
0
0
0
0
5
6
0
0
0
0
0
0
0
33326
7
8
9
10
11
12
13
33327
33328
33329
33330
33331
14
15
16
17
18
19
20
21
22
23
33332
33333
33334
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
0
0
41
42
43
44
45
0
33335
0
66648
0
0
33336
33337
33338
33339
33340
33341
33342
33343
33344
46
33345
47
48
3...

result:

ok q=100000

Test #80:

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

input:

99970 100000
1 2
1 4
5 1
9 1
13 1
1 17
21 1
1 25
1 29
33 1
1 37
41 1
45 1
1 49
1 53
1 57
1 61
65 1
1 69
1 73
1 77
81 1
85 1
89 1
1 93
97 1
101 1
105 1
109 1
113 1
1 117
121 1
1 125
1 129
133 1
137 1
141 1
1 145
149 1
1 153
157 1
161 1
165 1
1 169
1 173
177 1
181 1
185 1
189 1
193 1
1 197
1 201
1 205...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #81:

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

input:

99970 100000
1 2
1 4
5 1
9 1
13 1
17 1
21 1
1 25
1 29
1 33
37 1
1 41
1 45
1 49
53 1
1 57
1 61
1 65
1 69
73 1
77 1
81 1
1 85
89 1
93 1
97 1
101 1
105 1
1 109
1 113
1 117
121 1
1 125
129 1
133 1
137 1
141 1
145 1
1 149
1 153
1 157
1 161
1 165
169 1
173 1
177 1
181 1
185 1
1 189
1 193
1 197
201 1
1 205...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #82:

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

input:

99970 100000
4 1
1 5
9 1
1 13
17 1
1 21
25 1
29 1
33 1
37 1
41 1
1 45
1 49
53 1
57 1
61 1
1 65
69 1
1 73
77 1
1 81
85 1
89 1
1 93
1 97
1 101
105 1
109 1
113 1
1 117
121 1
1 125
129 1
133 1
1 137
141 1
145 1
149 1
153 1
1 157
161 1
165 1
1 169
1 173
1 177
181 1
185 1
189 1
193 1
1 197
201 1
205 1
209...

output:

24994
1
2
24996
24995
0
49988
0
3
4
74979
0
5
6
7
0
8
9
10
11
12
49989
74980
0
49990
24997
49991
0
24998
24999
25000
25001
74981
0
13
14
15
16
17
18
19
49992
49993
49994
49995
0
49996
20
21
22
23
24
25002
25003
49997
25
26
25004
25005
27
28
29
30
31
32
33
34
35
36
25006
37
38
39
40
41
42
43
25007
49...

result:

ok q=100000

Test #83:

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

input:

99970 100000
4 1
5 1
1 9
13 1
17 1
21 1
25 1
29 1
33 1
37 1
41 1
45 1
1 49
53 1
1 57
61 1
65 1
69 1
1 73
1 77
1 81
85 1
1 89
93 1
97 1
1 101
1 105
1 109
1 113
117 1
121 1
1 125
1 129
1 133
1 137
1 141
1 145
1 149
153 1
157 1
1 161
165 1
169 1
1 173
1 177
181 1
1 185
189 1
1 193
1 197
1 201
205 1
1 2...

output:

1
2
49987
24994
24995
74979
0
0
3
4
0
49988
49989
5
6
7
24996
24997
24998
24999
25000
49990
49991
8
9
10
11
12
13
14
15
16
25001
25002
25003
25004
25005
25006
25007
17
25008
25009
18
19
20
21
22
25010
25011
25012
25013
25014
25015
49992
49993
49994
23
24
49995
49996
25
26
49997
49998
27
28
29
30
31
...

result:

ok q=100000

Test #84:

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

input:

99970 100000
1 2
4 1
6 1
11 1
1 16
21 1
26 1
31 1
36 1
1 41
46 1
1 51
56 1
61 1
66 1
1 71
1 76
81 1
86 1
1 91
96 1
101 1
106 1
111 1
1 116
121 1
126 1
1 131
136 1
1 141
1 146
1 151
1 156
1 161
1 166
171 1
176 1
181 1
186 1
1 191
1 196
1 201
206 1
211 1
216 1
221 1
226 1
1 231
1 236
241 1
246 1
251 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #85:

score: 0
Accepted
time: 21ms
memory: 14896kb

input:

99970 100000
1 2
3 1
6 1
1 11
1 16
21 1
1 26
1 31
1 36
1 41
46 1
1 51
56 1
61 1
1 66
1 71
76 1
1 81
86 1
91 1
1 96
1 101
1 106
111 1
1 116
121 1
126 1
131 1
136 1
1 141
1 146
1 151
1 156
1 161
166 1
171 1
176 1
1 181
186 1
1 191
1 196
201 1
206 1
1 211
216 1
221 1
226 1
231 1
236 1
241 1
246 1
251 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #86:

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

input:

99970 100000
3 1
4 1
5 1
1 6
11 1
1 16
1 21
1 26
1 31
36 1
1 41
46 1
1 51
1 56
1 61
66 1
1 71
1 76
81 1
1 86
91 1
96 1
1 101
106 1
111 1
1 116
121 1
126 1
131 1
136 1
141 1
146 1
151 1
1 156
1 161
166 1
1 171
1 176
181 1
186 1
191 1
1 196
201 1
206 1
1 211
216 1
221 1
226 1
231 1
236 1
1 241
246 1
2...

output:

2
1
39991
39992
59985
3
4
19998
5
6
7
8
9
10
59986
39993
59987
11
12
13
14
15
19997
16
17
18
19
20
21
19999
20000
20001
22
23
59984
20002
79978
24
25
59988
26
27
28
39994
79979
39995
20003
20004
20005
39996
39997
29
30
31
32
0
33
34
35
36
37
38
39
40
41
59989
59990
20006
20007
20008
42
43
44
20009
2...

result:

ok q=100000

Test #87:

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

input:

99970 100000
1 3
5 1
6 1
1 11
1 16
1 21
1 26
31 1
1 36
41 1
1 46
51 1
56 1
1 61
1 66
1 71
76 1
81 1
1 86
1 91
1 96
1 101
1 106
111 1
116 1
1 121
1 126
1 131
136 1
1 141
1 146
151 1
1 156
161 1
1 166
171 1
1 176
181 1
1 186
1 191
196 1
1 201
1 206
1 211
216 1
1 221
1 226
1 231
236 1
241 1
246 1
1 251...

output:

1
39991
0
19997
19998
19999
20000
20001
0
0
0
0
0
20002
3
4
5
6
7
8
9
10
11
12
13
14
15
20003
20004
20005
20006
20007
20008
20009
20010
20011
0
20012
20013
20014
20015
16
17
20016
20017
20018
20019
20020
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
20021
20022
200...

result:

ok q=100000

Test #88:

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

input:

99970 100000
1 3
1 4
1 5
1 6
7 1
1 13
1 19
25 1
31 1
1 37
1 43
49 1
55 1
1 61
1 67
1 73
79 1
85 1
91 1
1 97
103 1
109 1
115 1
121 1
1 127
133 1
139 1
145 1
1 151
157 1
1 163
169 1
1 175
181 1
1 187
1 193
1 199
1 205
1 211
1 217
223 1
229 1
1 235
1 241
1 247
253 1
259 1
1 265
271 1
277 1
1 283
1 289
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #89:

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

input:

99970 100000
3 1
1 4
5 1
6 1
7 1
13 1
19 1
1 25
1 31
37 1
43 1
1 49
1 55
1 61
1 67
73 1
1 79
1 85
1 91
1 97
1 103
109 1
115 1
121 1
127 1
133 1
139 1
1 145
151 1
1 157
1 163
1 169
1 175
1 181
187 1
1 193
1 199
1 205
1 211
1 217
223 1
229 1
235 1
1 241
247 1
1 253
1 259
1 265
1 271
1 277
1 283
289 1
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #90:

score: 0
Accepted
time: 28ms
memory: 14936kb

input:

99970 100000
1 2
1 3
1 4
7 1
13 1
1 19
25 1
31 1
37 1
1 43
1 49
55 1
61 1
1 67
73 1
1 79
85 1
1 91
97 1
1 103
109 1
115 1
121 1
1 127
1 133
139 1
1 145
1 151
1 157
1 163
169 1
1 175
181 1
187 1
1 193
1 199
205 1
1 211
1 217
1 223
229 1
1 235
1 241
1 247
253 1
1 259
1 265
271 1
1 277
1 283
289 1
1 29...

output:

33327
49989
1
16666
16667
2
49990
3
66652
0
49991
49992
16665
33328
33329
16668
16669
16670
16671
16672
16673
4
5
6
7
16674
16675
8
9
33330
33331
49993
49994
0
83313
16676
16677
16678
83314
66653
66654
0
49995
49996
49997
49998
33332
16679
16680
33333
33334
10
11
12
16681
16682
16683
16684
16685
166...

result:

ok q=100000

Test #91:

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

input:

99970 100000
3 1
6 1
1 7
13 1
19 1
25 1
1 31
1 37
1 43
1 49
55 1
61 1
67 1
1 73
1 79
1 85
1 91
97 1
103 1
109 1
1 115
121 1
127 1
133 1
139 1
145 1
151 1
157 1
163 1
169 1
175 1
181 1
187 1
193 1
199 1
205 1
1 211
217 1
223 1
229 1
1 235
1 241
247 1
1 253
259 1
265 1
271 1
277 1
1 283
1 289
295 1
1 ...

output:

16665
16666
16667
16668
2
3
4
5
6
7
8
9
10
11
12
1
16664
33328
33329
33330
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
16669
16670
33331
33332
49992
49993
49994
49991
33
34
35
36
37
38
39
40
33333
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
33334
33335
33336
16671
16672
16673
...

result:

ok q=100000

Test #92:

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

input:

99970 100000
3 1
1 4
5 1
1 8
15 1
22 1
1 29
1 36
1 43
50 1
1 57
1 64
71 1
78 1
1 85
1 92
99 1
1 106
1 113
1 120
1 127
1 134
1 141
1 148
1 155
162 1
169 1
176 1
1 183
190 1
197 1
1 204
1 211
218 1
225 1
232 1
239 1
1 246
1 253
260 1
1 267
274 1
1 281
288 1
295 1
302 1
309 1
316 1
1 323
330 1
1 337
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #93:

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

input:

99970 100000
1 3
1 5
6 1
7 1
1 8
15 1
22 1
29 1
36 1
1 43
50 1
57 1
64 1
1 71
1 78
1 85
92 1
1 99
106 1
113 1
1 120
127 1
134 1
141 1
148 1
155 1
1 162
169 1
176 1
1 183
190 1
197 1
204 1
211 1
1 218
1 225
232 1
239 1
246 1
1 253
1 260
267 1
274 1
1 281
1 288
1 295
1 302
1 309
316 1
323 1
1 330
337 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #94:

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

input:

99970 100000
2 1
1 3
1 5
1 7
8 1
15 1
1 22
1 29
36 1
43 1
50 1
57 1
1 64
1 71
78 1
85 1
1 92
1 99
106 1
113 1
120 1
127 1
134 1
141 1
1 148
1 155
162 1
169 1
1 176
1 183
190 1
197 1
204 1
1 211
218 1
225 1
1 232
239 1
1 246
253 1
1 260
267 1
274 1
1 281
288 1
1 295
302 1
1 309
1 316
1 323
330 1
337 ...

output:

4
3
14288
14286
1
5
6
2
28572
14287
14289
7
8
28571
9
10
11
12
13
14
15
16
17
18
19
20
28570
14290
14291
14292
14293
14294
14295
14296
14297
14298
14299
14300
14301
42853
14302
14303
14304
14305
14306
14307
42855
21
22
71415
14308
14309
23
24
14310
14311
14312
14313
14314
14315
14316
28573
25
26
27
...

result:

ok q=100000

Test #95:

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

input:

99970 100000
2 1
3 1
4 1
1 6
7 1
8 1
1 15
1 22
29 1
1 36
1 43
50 1
1 57
1 64
71 1
78 1
1 85
1 92
1 99
106 1
113 1
1 120
1 127
1 134
141 1
1 148
155 1
1 162
1 169
176 1
1 183
1 190
197 1
1 204
1 211
218 1
1 225
1 232
239 1
246 1
253 1
1 260
267 1
1 274
281 1
1 288
1 295
1 302
1 309
1 316
323 1
330 1
...

output:

0
0
4
14288
5
2
3
28571
28572
28573
42853
57134
28574
28575
28576
28577
28578
28579
71415
71416
71417
71418
71419
71420
71421
14287
1
6
7
8
9
10
28580
28581
28582
28583
28584
28585
28586
28587
28588
28589
28590
28591
28592
28593
28594
28595
28596
28597
28598
28599
28600
28601
28602
28603
28604
28605...

result:

ok q=100000

Test #96:

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

input:

99970 100000
2 1
3 1
4 1
1 5
1 6
9 1
17 1
25 1
33 1
1 41
49 1
57 1
65 1
73 1
1 81
89 1
1 97
1 105
113 1
1 121
1 129
137 1
145 1
153 1
1 161
1 169
1 177
1 185
1 193
1 201
1 209
217 1
1 225
1 233
1 241
1 249
1 257
1 265
1 273
281 1
1 289
297 1
1 305
313 1
321 1
1 329
337 1
1 345
1 353
361 1
369 1
1 37...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #97:

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

input:

99970 100000
1 2
1 4
1 5
1 6
1 9
1 17
25 1
33 1
41 1
1 49
57 1
1 65
1 73
81 1
89 1
97 1
1 105
113 1
1 121
129 1
137 1
145 1
1 153
161 1
169 1
1 177
185 1
193 1
1 201
209 1
217 1
1 225
1 233
1 241
249 1
257 1
1 265
273 1
281 1
289 1
297 1
305 1
1 313
321 1
329 1
337 1
345 1
353 1
1 361
369 1
377 1
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #98:

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

input:

99970 100000
4 1
5 1
1 8
1 9
17 1
25 1
1 33
1 41
1 49
57 1
65 1
1 73
1 81
1 89
97 1
105 1
1 113
1 121
1 129
137 1
145 1
1 153
1 161
169 1
177 1
185 1
1 193
1 201
1 209
217 1
1 225
1 233
241 1
1 249
1 257
265 1
1 273
1 281
289 1
297 1
305 1
1 313
1 321
329 1
337 1
345 1
1 353
1 361
1 369
377 1
1 385
...

output:

1
12500
12501
12502
2
4
5
6
12503
12504
37499
37500
37501
37502
37498
25001
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
12505
12506
12507
27
28
29
30
31
32
33
25003
34
35
36
37
38
39
40
41
42
43
44
45
46
47
12508
12509
12510
74987
74988
12511
12512
12513
48
49
50
51
52
12514
12515
53
54...

result:

ok q=100000

Test #99:

score: 0
Accepted
time: 52ms
memory: 14948kb

input:

99970 100000
6 1
9 1
1 17
1 25
1 33
41 1
1 49
1 57
1 65
73 1
1 81
89 1
97 1
1 105
113 1
1 121
129 1
137 1
1 145
1 153
1 161
169 1
1 177
1 185
1 193
201 1
209 1
217 1
1 225
1 233
1 241
249 1
257 1
265 1
1 273
281 1
1 289
1 297
1 305
313 1
321 1
1 329
337 1
345 1
353 1
361 1
369 1
1 377
1 385
393 1
1 ...

output:

0
0
0
12500
37496
12502
49994
49995
12498
12499
12503
12504
12505
12506
12501
1
25000
2
3
49993
62490
62489
62491
62492
62493
62494
62495
62496
74987
74988
37498
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
37499
37500
37501
37502
37503
37504
37505
25001
25002
25003
12507
12508
12509
12510
12511
125...

result:

ok q=100000

Test #100:

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

input:

10000 100000
62 1
1 552
818 1
1 1204
1993 1
1 4007
1 4095
5262 1
1 5367
5784 1
1 6036
6091 1
1 6559
8108 1
1 8154
1 9191
9482 1
41 2
2 294
1572 2
1852 2
2 1895
3322 2
4360 2
4905 2
2 5027
5934 2
6198 2
6504 2
2 6870
8364 2
722 3
812 3
1347 3
1856 3
1990 3
2008 3
2578 3
3 3019
3 3248
3 3495
3 3616
3 ...

output:

4

result:

ok q=100000

Test #101:

score: 0
Accepted
time: 28ms
memory: 15828kb

input:

10000 100000
1 278
1 1411
1906 1
2107 1
2178 1
1 2299
2526 1
1 2856
1 3613
3796 1
1 4128
1 4196
1 4250
1 4631
5135 1
5224 1
1 5279
6206 1
1 6985
1 7310
1 7357
7722 1
7815 1
1 8282
9362 1
9571 1
1 9782
1 9999
874 2
2 1055
1187 2
2010 2
2 2173
2250 2
2511 2
2699 2
2756 2
2876 2
2 3802
4047 2
4937 2
2 ...

output:

3249
3251
3252
72
1040
1701
1762
259
3253
3255
3256
3257
3262
3263
3265
427
610
2430
2798
2855
2
3266
2171
3267
725
727
732
733
737
739
182
1199
1731
2159
1074
1856
3357
1023
67
3284
105
1255
801
561
2752
2740
3697
3737
1754
3868
3881
2406
3854
3321
256
263
708
104
711
712
426
460
714
510
688
691
24...

result:

ok q=100000

Test #102:

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

input:

10000 100000
1 257
1 1150
1 2495
4714 1
5052 1
5128 1
5130 1
1 5235
1 6273
1 7279
7296 1
1 7899
8429 1
8895 1
9133 1
1 9402
2 378
2 434
1060 2
2991 2
5009 2
5316 2
2 5857
2 5984
2 6490
2 6494
6963 2
2 7560
2 7816
7996 2
8202 2
2 8218
2 9608
893 3
3 1127
3 1318
1863 3
3136 3
3 3927
4162 3
4273 3
3 49...

output:

0
41711
1614
251
1910
2359
2498
1693
3254
4517
4675
4790
1369
4791
4792
4793
4794
966
2401
1960
2403
2405
2406
2410
2411
2418
4795
4796
1997
2324
2763
3076
1224
3031
3399
3584
694
3580
1581
3601
1809
3602
3603
3604
3605
1210
2251
3606
3608
3609
249
1837
1374
1625
2322
2551
2552
2553
1383
2171
2173
1...

result:

ok q=100000

Test #103:

score: 0
Accepted
time: 52ms
memory: 16000kb

input:

10000 100000
1 32
366 1
1164 1
1 1881
2317 1
2931 1
1 2932
3853 1
4011 1
1 4090
1 5006
5656 1
5696 1
1 6055
6674 1
7367 1
7599 1
8265 1
2 1468
2 1486
1670 2
2375 2
2 2729
3116 2
2 3202
2 3560
2 4047
2 4643
2 4645
4794 2
4958 2
5887 2
5947 2
2 6549
2 6992
2 7179
7436 2
2 7513
2 8130
2 8703
2 9686
514...

output:

0
17657
17567
29228
19215
25819
5148
12807
1807
5396
4181
5400
5403
2369
299
5406
5409
5410
5411
5413
5414
5415
5416
6555
6609
494
1182
1471
5438
6653
6658
6660
6663
6664
6668
8145
5397
11052
5398
1785
10686
3900
6151
11500
5639
11830
12305
402
3675
3804
4526
568
4995
4999
5003
5005
5008
4994
5313
1...

result:

ok q=100000

Test #104:

score: 0
Accepted
time: 52ms
memory: 15164kb

input:

10000 100000
1 1173
1 2045
1 2146
1 2314
2389 1
1 2586
1 2796
1 3622
3650 1
1 3692
1 3985
4433 1
4520 1
5493 1
1 5514
6563 1
7220 1
1 7472
1 8043
1 8385
8565 1
9622 1
1 9735
2 97
2 131
167 2
1663 2
3416 2
2 4187
2 4386
2 4447
2 5022
5025 2
5179 2
2 5885
2 6919
8335 2
8400 2
2 8671
8807 2
9147 2
3 83...

output:

0
0
0
0
32850
33276
3646
6002
9968
5064
11350
3102
5902
423
3857
5489
5701
606
1525
2127
6095
910
2662
4591
6456
6598
7766
7953
8697
8858
9449
9907
11186
11346
651
737
2695
2918
3573
7406
10359
9268
9273
9274
9276
9278
2235
2871
5761
9279
9281
3810
3257
5305
9282
4530
9283
9284
10968
11032
11362
130...

result:

ok q=100000

Test #105:

score: 0
Accepted
time: 69ms
memory: 15012kb

input:

10000 100000
1 380
1 873
1 1618
1838 1
1 2767
3506 1
1 4453
4602 1
4754 1
4880 1
1 5778
1 5811
1 6230
7868 1
1 7911
8126 1
1 8233
9049 1
9356 1
2 10
2 537
658 2
2 1129
1461 2
2 2035
2237 2
3097 2
3513 2
2 3524
2 3931
2 4956
5072 2
2 5204
2 5302
2 5454
2 5562
5607 2
5774 2
2 5909
6017 2
2 6193
6622 2...

output:

0
27150
30684
36735
39253
49145
64431
67374
12441
15385
21325
23949
24041
41975
5091
15944
35025
54021
55281
55524
55535
57930
6692
18808
30169
32734
58783
58998
59698
60468
2886
9528
9529
9534
9535
9536
9537
9539
9543
621
9527
12244
18699
21880
22923
5105
6046
13778
17566
19198
24932
26012
26423
30...

result:

ok q=100000

Test #106:

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

input:

10000 100000
1 223
924 1
1010 1
1 2164
1 2599
3130 1
3294 1
1 3555
1 3759
4080 1
1 4841
4948 1
1 5358
1 6539
7363 1
1 7747
9377 1
1 9393
1 9596
1 9941
376 2
2 623
878 2
1665 2
1759 2
2 1941
2135 2
3573 2
3685 2
3843 2
2 4021
5156 2
2 6157
2 6758
6934 2
2 7220
2 7354
7620 2
2 7815
2 8287
2 8564
8772 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #107:

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

input:

10000 100000
1 246
483 1
1 766
1 1389
1 1977
1 2314
2563 1
2637 1
2826 1
1 4125
4414 1
4737 1
1 5172
1 5460
1 5727
1 6441
1 6611
1 6654
1 7016
7208 1
1 7265
1 7459
7666 1
1 7680
1 7784
8265 1
8518 1
9031 1
2 1115
2 1194
2 1496
1533 2
2 1578
1655 2
2455 2
2 2537
2785 2
2 3661
2 5953
2 6095
2 6250
728...

output:

1

result:

ok q=100000

Test #108:

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

input:

10000 100000
1 4
1 262
480 1
1661 1
1942 1
3141 1
3242 1
1 4520
5039 1
5322 1
5617 1
5702 1
6596 1
7549 1
8091 1
1 8150
1 8300
8880 1
8976 1
9057 1
1 9615
2 361
986 2
2 1260
1571 2
1831 2
2903 2
2 3659
2 4398
4775 2
4780 2
2 5425
6353 2
2 6520
2 7157
2 7742
2 8973
9025 2
50 3
3 677
3 816
924 3
1742 ...

output:

1
4
11
16
25
27
46
47
51
52
53
54
57
60
75
79
80
85
86
107
112
139
152
153
157
158
165
166
171
193
196
198
199
200
205
206
207
225
236
239
244
250
253
254
260
264
268
276
277
287
295
298
308
309
311
327
328
329
335
337
340
355
363
364
372
378
388
389
390
392
394
396
397
399
405
243
408
410
418
419
4...

result:

ok q=100000

Test #109:

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

input:

10000 100000
637 1
1879 1
1 2512
1 3578
3828 1
4117 1
1 4420
4468 1
4698 1
1 6029
6048 1
6553 1
6615 1
1 6970
7457 1
7626 1
1 7647
1 9559
9862 1
2 362
2 2514
2764 2
2 2982
3679 2
6566 2
2 8237
8441 2
8654 2
8754 2
8796 2
2 8905
9184 2
3 1285
3 1795
2932 3
3 3025
3 3149
3 3537
5987 3
3 6361
3 6710
3 ...

output:

6
17
24
67
68
70
73
74
75
76
81
82
83
84
85
87
88
90
91
94
95
99
111
118
121
127
136
149
151
152
154
158
161
163
166
167
191
193
194
197
200
201
203
206
216
230
232
244
260
263
279
285
297
298
299
301
305
309
310
312
314
315
319
339
344
345
351
353
361
368
79
371
374
389
390
396
399
403
405
411
412
...

result:

ok q=100000

Test #110:

score: 0
Accepted
time: 45ms
memory: 15216kb

input:

10000 100000
6 1
1 399
891 1
1 1247
1269 1
1 1839
1 4072
4089 1
1 4245
1 4901
5339 1
1 7182
7459 1
8149 1
8208 1
1 8881
8937 1
1 9259
2 997
2 1065
2 2100
2 2796
2 3802
2 4857
2 5518
2 5539
5952 2
2 5973
7487 2
2 8574
2 9917
61 3
3 70
591 3
3 594
3 1502
3 1606
3 1616
3106 3
3 3523
3 3742
3 4162
4550 ...

output:

5
8
11
36
40
41
49
51
53
59
68
88
102
103
117
125
129
130
133
137
139
144
148
155
156
157
163
167
169
175
219
227
231
233
239
245
251
253
255
263
266
267
286
305
309
314
334
336
341
343
351
358
364
366
369
370
371
372
373
374
376
378
379
380
381
382
390
392
396
399
419
420
422
425
427
428
430
431
43...

result:

ok q=100000

Test #111:

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

input:

10000 100000
1 362
793 1
1 2340
1 2929
1 3619
1 3663
1 3789
6135 1
6331 1
6700 1
1 6901
7815 1
8192 1
1 8615
8676 1
1 8849
1 9273
1 9310
323 2
512 2
2 847
2 967
2 970
1006 2
1716 2
2102 2
2 2739
3298 2
2 3444
2 3472
3889 2
2 4569
2 5985
6892 2
7135 2
7675 2
7854 2
7871 2
8179 2
8656 2
8719 2
2 8799
...

output:

7
12
17
25
27
31
33
34
38
39
40
42
60
65
67
73
75
85
93
98
99
109
112
144
149
153
156
160
162
187
192
193
194
196
197
198
199
200
204
205
206
207
208
209
212
230
232
243
251
268
280
282
284
286
287
295
297
298
301
303
304
332
345
348
362
367
368
369
370
373
376
380
384
386
394
397
400
404
411
413
41...

result:

ok q=100000

Test #112:

score: 0
Accepted
time: 28ms
memory: 14812kb

input:

10000 100000
1 53
1 1122
1949 1
1965 1
1 2760
1 6345
6354 1
1 6764
1 7825
1 8453
8734 1
9046 1
1 9160
9875 1
2 29
167 2
754 2
2 867
1007 2
1040 2
2 1421
2752 2
2 3046
2 3444
2 3627
2 4830
2 5453
2 6492
2 8157
2 8480
2 9226
2 9460
9525 2
369 3
572 3
3 648
1053 3
3 1356
3 2369
3153 3
3155 3
3 5471
604...

output:

2
20
22
28
33
57
62
70
85
99
114
122
134
137
140
141
142
147
151
154
157
160
162
163
168
170
171
175
179
182
191
192
193
195
196
198
206
227
237
248
273
284
286
290
295
296
299
300
303
304
305
309
310
318
319
321
324
337
101
107
340
344
346
351
359
360
361
364
365
369
377
397
401
402
413
416
438
445...

result:

ok q=100000

Test #113:

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

input:

10000 100000
303 1
1 306
1 309
603 1
1 624
1 713
1 954
1019 1
1921 1
2013 1
1 2239
2768 1
1 2899
4285 1
4773 1
1 5281
1 5596
5739 1
5755 1
5849 1
6228 1
1 7029
1 7255
7597 1
7679 1
9099 1
1 9342
966 2
2 1630
2 1984
2339 2
2 2603
2 3021
2 3661
2 3766
6428 2
2 7230
2 7652
7773 2
7997 2
9437 2
9475 2
9...

output:

1
2
3
7
8
11
13
15
17
21
23
24
26
31
37
83
86
93
96
101
108
111
112
113
114
119
126
136
138
156
178
180
183
185
187
189
191
195
197
198
200
202
203
206
208
210
213
216
217
226
228
231
242
243
247
250
257
260
261
262
265
269
272
284
292
293
294
300
301
303
305
309
310
316
319
321
322
324
328
329
332
...

result:

ok q=100000

Test #114:

score: 0
Accepted
time: 33ms
memory: 15280kb

input:

10000 100000
1 687
1 2238
2339 1
2540 1
3744 1
1 4048
1 5868
1 6041
7833 1
8786 1
9222 1
935 2
2 1185
2 1659
1973 2
2 2048
2 2569
3163 2
3286 2
2 4612
5511 2
2 5535
5942 2
2 6222
2 6365
2 6547
6954 2
2 7976
8670 2
9133 2
2 9507
1116 3
1283 3
3 1886
3 2675
4460 3
5444 3
3 6072
3 7681
8072 3
8104 3
3 ...

output:

15

result:

ok q=100000

Test #115:

score: 0
Accepted
time: 37ms
memory: 15864kb

input:

10000 100000
16 1
1 226
1 546
1 751
1 1332
1 2446
2702 1
2853 1
4522 1
4669 1
1 4771
1 5035
5108 1
1 5221
1 5265
5519 1
8583 1
1 8612
1 9249
1 9798
20 2
2 312
534 2
689 2
1484 2
2304 2
2351 2
2 3520
2 3886
4324 2
4432 2
4630 2
4977 2
6737 2
7547 2
2 7610
2 7638
7669 2
7678 2
7894 2
2 8781
2 8824
904...

output:

1040
2110
489
774
1989
93
995
826
1073
326
2417
238
353
1036
1575
1616
2156
447
1176
2354
2418
2420
2425
2426
55
2428
869
1556
2088
2371
2372
2373
2374
2375
2376
2377
2378
398
2380
2381
2150
485
902
1705
2208
2367
2382
2383
2384
2385
2386
2387
2388
2390
1996
516
2391
2392
2393
237
1456
1809
1811
181...

result:

ok q=100000

Test #116:

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

input:

10000 100000
1 634
1 773
973 1
1993 1
1 2206
1 2258
1 2674
2934 1
3289 1
1 3486
1 3665
3870 1
1 4202
1 4222
4916 1
1 5131
5341 1
1 5589
1 7234
1 7419
1 7603
1 7647
1 7871
1 7887
8704 1
2 165
2 334
2 896
2 1110
1438 2
1649 2
1824 2
2158 2
2 2205
2781 2
2 2912
2 4077
2 4501
4528 2
2 5391
2 5496
2 5811...

output:

0
1508
7890
9687
9421
11407
12294
13881
16220
236
1465
5906
6512
3772
29
5621
5755
5490
1975
2119
2393
2153
2933
261
584
2935
2936
2938
2939
2940
2941
368
2942
2944
2946
2947
2948
744
2950
2951
2952
3046
3220
3326
3609
322
3734
3737
232
351
1602
3957
2077
4353
3311
4792
4935
5360
5528
5744
1460
5745...

result:

ok q=100000

Test #117:

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

input:

10000 100000
141 1
1 864
1 1515
1 1659
1 1665
1 1986
1 2432
2546 1
1 2598
1 2721
2792 1
3557 1
3736 1
1 7164
7510 1
1 9187
9424 1
2 2738
2 2936
3033 2
2 4575
4971 2
2 5719
6196 2
2 6465
2 6500
2 6665
2 7093
7520 2
2 7675
2 9723
3 130
3 279
755 3
3 964
1475 3
1750 3
3 1879
3 1961
3 2223
3 3125
3 3484...

output:

0
7607
3862
1280
3863
3864
3866
3867
3870
4294
1883
6131
110
6133
6140
6145
6146
6148
6232
8961
218
8964
1814
8968
4543
4990
6693
8969
8977
8978
8980
9779
9837
1824
3165
3901
5470
6743
9737
11861
7746
12139
318
1627
3595
5041
9810
10176
3946
7395
10185
10235
3304
306
4169
4400
10094
12265
8352
6812
...

result:

ok q=100000

Test #118:

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

input:

10000 100000
1 496
1 976
1674 1
1 2091
1 2796
1 3047
1 3734
1 4361
1 4620
6855 1
1 6896
1 8073
8352 1
1 8572
8781 1
1 8857
1 8915
1 9035
1 9294
9490 1
9985 1
673 2
855 2
2 1012
1711 2
2 1902
2426 2
2 2597
2960 2
2 4925
2 5659
7946 2
7990 2
2 8450
2 8638
2 8646
2 8918
9379 2
3 443
3 458
3 1247
3 1405...

output:

20635
29135
4243
18271
19650
24146
29967
3482
5947
11811
7597
10929
11217
15330
5669
14125
11208
2766
897
3439
4434
12332
19919
14537
19921
10534
19922
19923
19924
19925
18204
19926
19927
19929
19930
19931
19933
10371
349
9777
19935
19936
16976
19937
20086
21443
10523
14364
21445
21592
10539
4230
10...

result:

ok q=100000

Test #119:

score: 0
Accepted
time: 59ms
memory: 15684kb

input:

10000 100000
155 1
1 312
458 1
1 1772
1 2247
2334 1
1 2939
1 3031
4298 1
1 4460
1 6773
6873 1
7230 1
7285 1
7408 1
8385 1
1 8469
1 9022
9310 1
245 2
883 2
2 1068
1159 2
2 1844
2 2177
2 2407
2670 2
2820 2
2 2948
3701 2
3801 2
2 4259
2 4406
4662 2
5265 2
2 6295
7931 2
9316 2
2 9595
88 3
125 3
1259 3
3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
6177
12294
19229
19563
20671
38728
4129
42526
42527
42528
42531
42534
3917
7655
10294
23079
13776
13764
26817
32063
13765
33469
35596
35661
40843
42879
48024
49179
42521
9738
14398
14499
26952
53530
53535
53537
42522
42523
14267
26737
27224
31762
45375
49540
10293
30590
417...

result:

ok q=100000

Test #120:

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

input:

10000 100000
121 1
1 242
1 1247
1325 1
1 1445
2211 1
2687 1
3212 1
1 3458
1 4405
1 4473
5781 1
1 5987
6973 1
7680 1
1 9000
9059 1
1 9514
9600 1
51 2
2 693
1286 2
1391 2
2 1705
2 3339
3471 2
2 3864
2 5097
2 5130
5658 2
2 6647
6819 2
2 7138
2 7764
2 7810
8298 2
2 8369
8894 2
2 9880
3 53
3 625
3 779
14...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #121:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #122:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #123:

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

input:

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

output:

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

result:

ok q=100000

Test #124:

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

input:

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

output:

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

result:

ok q=100000

Test #125:

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

input:

9970 100000
1 2
3 1
1 5
7 1
1 9
11 1
1 13
15 1
17 1
19 1
21 1
1 23
25 1
1 27
1 29
1 31
1 33
35 1
37 1
39 1
1 41
43 1
45 1
47 1
1 49
1 51
1 53
1 55
1 57
1 59
61 1
1 63
65 1
1 67
69 1
71 1
1 73
1 75
77 1
1 79
1 81
83 1
1 85
1 87
1 89
1 91
1 93
1 95
1 97
1 99
101 1
1 103
1 105
1 107
109 1
111 1
113 1
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #126:

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

input:

9970 100000
2 1
3 1
5 1
1 7
9 1
1 11
13 1
1 15
17 1
19 1
1 21
23 1
1 25
1 27
29 1
1 31
33 1
35 1
37 1
1 39
41 1
43 1
1 45
1 47
49 1
1 51
53 1
55 1
1 57
1 59
61 1
63 1
1 65
1 67
1 69
1 71
73 1
1 75
1 77
79 1
1 81
1 83
1 85
87 1
89 1
91 1
93 1
95 1
1 97
1 99
1 101
103 1
105 1
107 1
109 1
111 1
1 113
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #127:

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

input:

9970 100000
1 2
1 3
1 5
1 7
9 1
11 1
13 1
1 15
1 17
19 1
1 21
1 23
25 1
1 27
1 29
1 31
1 33
35 1
37 1
1 39
41 1
1 43
45 1
1 47
1 49
51 1
53 1
55 1
1 57
59 1
1 61
1 63
1 65
1 67
1 69
1 71
1 73
75 1
77 1
79 1
1 81
83 1
85 1
87 1
89 1
1 91
93 1
1 95
97 1
1 99
101 1
103 1
1 105
1 107
1 109
111 1
1 113
1...

output:

2
0
1
3
4
5
6
0
4986
7
4987
8
9
10
11
0
4988
0
4989
0
4990
12
4991
13
4992
14
4993
0
4994
0
15
16
4995
17
18
0
4996
19
20
0
21
22
23
0
24
25
4997
26
4998
27
28
0
4999
0
5000
0
5001
0
5002
0
29
30
31
0
32
0
33
34
5003
35
36
37
38
39
5004
0
5005
0
5006
40
41
42
43
44
45
0
5007
0
5008
46
47
48
5009
0
5...

result:

ok q=100000

Test #128:

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

input:

9970 100000
1 2
1 3
1 5
7 1
1 9
1 11
1 13
1 15
17 1
1 19
21 1
23 1
25 1
1 27
1 29
1 31
33 1
35 1
1 37
39 1
1 41
1 43
1 45
47 1
49 1
1 51
53 1
1 55
57 1
59 1
61 1
63 1
65 1
67 1
1 69
1 71
1 73
1 75
1 77
79 1
81 1
1 83
85 1
87 1
1 89
1 91
93 1
1 95
1 97
1 99
101 1
103 1
1 105
107 1
109 1
1 111
1 113
1...

output:

0
0
0
0
1
4986
4987
4988
2
3
4989
4
5
4990
4991
4992
0
6
7
4993
4994
8
9
10
11
12
13
14
15
16
17
18
0
19
0
4995
4996
20
21
0
0
22
23
24
4997
0
4998
0
0
25
26
0
0
0
0
0
0
27
28
29
30
31
32
33
34
4999
5000
5001
5002
0
0
35
36
37
38
0
39
0
40
41
42
43
44
5003
5004
5005
45
46
47
48
49
50
51
52
53
54
55
...

result:

ok q=100000

Test #129:

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

input:

9970 100000
3 1
1 4
7 1
1 10
13 1
16 1
1 19
22 1
25 1
1 28
31 1
1 34
37 1
1 40
43 1
1 46
49 1
52 1
1 55
58 1
1 61
1 64
1 67
1 70
73 1
1 76
1 79
1 82
1 85
1 88
91 1
94 1
97 1
100 1
103 1
1 106
109 1
112 1
1 115
1 118
121 1
124 1
1 127
130 1
133 1
136 1
139 1
1 142
145 1
1 148
1 151
1 154
1 157
160 1
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #130:

score: 0
Accepted
time: 28ms
memory: 15624kb

input:

9970 100000
3 1
1 4
7 1
10 1
13 1
1 16
19 1
1 22
25 1
1 28
1 31
1 34
1 37
1 40
43 1
1 46
1 49
1 52
1 55
1 58
1 61
1 64
1 67
1 70
73 1
1 76
79 1
1 82
1 85
1 88
1 91
1 94
1 97
1 100
1 103
1 106
1 109
1 112
1 115
118 1
1 121
124 1
127 1
130 1
1 133
1 136
1 139
1 142
1 145
1 148
151 1
154 1
1 157
1 160
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #131:

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

input:

9970 100000
2 1
3 1
1 4
1 7
10 1
1 13
1 16
19 1
22 1
25 1
1 28
1 31
1 34
37 1
1 40
1 43
1 46
49 1
1 52
1 55
1 58
1 61
1 64
67 1
1 70
73 1
1 76
1 79
82 1
1 85
1 88
91 1
94 1
97 1
100 1
1 103
1 106
109 1
1 112
115 1
118 1
121 1
1 124
1 127
1 130
133 1
1 136
139 1
1 142
145 1
1 148
1 151
1 154
1 157
16...

output:

2
1
6648
3
6649
3326
6650
0
3327
3328
3329
4
5
3330
3331
6
3332
7
3333
3334
6651
8
6652
3335
3336
9
10
11
6653
0
6654
12
13
14
15
16
17
18
3337
19
3338
0
6655
3339
3340
0
6656
0
3341
20
3342
21
3343
22
23
3344
24
25
26
3345
3346
0
3347
3348
6657
3349
3350
27
28
0
3351
0
3352
29
30
31
32
33
34
3353
3...

result:

ok q=100000

Test #132:

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

input:

9970 100000
1 2
1 3
4 1
7 1
1 10
13 1
16 1
1 19
22 1
25 1
1 28
1 31
1 34
1 37
40 1
43 1
46 1
1 49
1 52
1 55
1 58
1 61
64 1
1 67
70 1
1 73
76 1
1 79
82 1
1 85
1 88
91 1
1 94
1 97
1 100
1 103
1 106
109 1
1 112
1 115
118 1
121 1
124 1
127 1
130 1
133 1
1 136
1 139
142 1
145 1
1 148
151 1
1 154
1 157
1 ...

output:

2
1
6648
3326
6649
6650
0
0
3327
3328
3329
3
3330
3331
3332
3333
4
3334
3335
3336
3337
3338
5
6
7
8
9
10
11
12
13
14
15
3339
16
17
18
19
20
21
22
23
24
3340
6651
6652
0
0
3341
25
3342
3343
3344
3345
3346
3347
3348
3349
6653
26
27
28
29
0
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
3350
3351
3352...

result:

ok q=100000

Test #133:

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

input:

9970 100000
3 1
1 5
1 9
1 13
17 1
21 1
25 1
1 29
33 1
1 37
1 41
45 1
49 1
53 1
57 1
61 1
65 1
1 69
1 73
1 77
1 81
85 1
1 89
93 1
97 1
101 1
105 1
1 109
113 1
117 1
121 1
125 1
1 129
133 1
1 137
1 141
1 145
149 1
1 153
157 1
1 161
1 165
1 169
1 173
1 177
181 1
185 1
189 1
193 1
1 197
201 1
1 205
209 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #134:

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

input:

9970 100000
1 2
1 3
1 5
9 1
1 13
1 17
1 21
1 25
29 1
1 33
37 1
1 41
45 1
1 49
1 53
1 57
1 61
65 1
69 1
73 1
1 77
1 81
1 85
1 89
1 93
1 97
101 1
105 1
109 1
1 113
1 117
121 1
125 1
1 129
1 133
137 1
1 141
145 1
1 149
153 1
1 157
1 161
1 165
169 1
173 1
1 177
1 181
1 185
1 189
193 1
1 197
1 201
205 1
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #135:

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

input:

9970 100000
1 2
1 5
9 1
13 1
17 1
1 21
25 1
1 29
33 1
1 37
41 1
1 45
1 49
1 53
1 57
61 1
65 1
69 1
73 1
77 1
1 81
85 1
89 1
93 1
1 97
101 1
1 105
1 109
1 113
1 117
1 121
1 125
129 1
1 133
1 137
1 141
1 145
1 149
153 1
1 157
1 161
165 1
169 1
1 173
177 1
181 1
1 185
189 1
193 1
197 1
1 201
205 1
1 20...

output:

2494
2
3
4
5
6
7
8
9
10
1
2495
2496
2497
11
12
13
14
7479
4988
4989
0
4990
2498
15
16
17
2499
2500
2501
4991
4992
7480
2502
7481
18
7482
0
4993
4994
4995
4996
2503
2504
2505
19
2506
4997
4998
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
4999
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
25...

result:

ok q=100000

Test #136:

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

input:

9970 100000
1 3
5 1
9 1
13 1
1 17
21 1
25 1
1 29
33 1
1 37
1 41
1 45
1 49
53 1
57 1
61 1
65 1
69 1
73 1
77 1
1 81
85 1
1 89
1 93
1 97
1 101
105 1
109 1
113 1
1 117
1 121
1 125
129 1
1 133
137 1
141 1
145 1
1 149
153 1
157 1
1 161
1 165
1 169
1 173
1 177
181 1
1 185
1 189
193 1
1 197
1 201
1 205
1 20...

output:

0
0
0
0
4987
7479
1
2494
4988
4989
7480
2495
2496
2497
2
3
4
5
6
7
8
7481
4990
4991
4992
7482
7483
4993
4994
7484
4995
4996
7485
7486
9
7487
4997
10
11
12
2498
2499
2500
13
14
15
16
17
18
19
0
0
4998
4999
5000
5001
5002
0
0
0
20
21
22
23
24
25
26
27
28
29
30
31
32
5003
5004
5005
33
34
35
36
37
38
39...

result:

ok q=100000

Test #137:

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

input:

9970 100000
3 1
4 1
1 5
6 1
11 1
1 16
1 21
1 26
1 31
36 1
41 1
1 46
1 51
1 56
61 1
66 1
1 71
76 1
81 1
86 1
91 1
1 96
101 1
106 1
111 1
1 116
1 121
1 126
131 1
136 1
1 141
146 1
151 1
156 1
1 161
1 166
171 1
176 1
181 1
186 1
1 191
196 1
201 1
206 1
211 1
216 1
221 1
226 1
231 1
1 236
1 241
1 246
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #138:

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

input:

9970 100000
3 1
6 1
11 1
1 16
1 21
26 1
1 31
1 36
1 41
46 1
51 1
56 1
61 1
1 66
1 71
1 76
81 1
86 1
1 91
96 1
1 101
1 106
1 111
116 1
1 121
126 1
131 1
1 136
141 1
1 146
151 1
156 1
161 1
166 1
1 171
176 1
1 181
186 1
1 191
196 1
1 201
206 1
1 211
1 216
1 221
1 226
1 231
1 236
241 1
1 246
251 1
1 25...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #139:

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

input:

9970 100000
1 2
1 6
11 1
16 1
1 21
26 1
31 1
1 36
41 1
46 1
51 1
56 1
1 61
66 1
1 71
1 76
81 1
1 86
91 1
1 96
1 101
106 1
111 1
116 1
121 1
126 1
1 131
1 136
141 1
1 146
151 1
156 1
161 1
166 1
171 1
176 1
181 1
186 1
191 1
1 196
1 201
206 1
1 211
1 216
1 221
1 226
1 231
1 236
241 1
246 1
1 251
256 ...

output:

1995
0
1996
5985
3990
3991
3992
3993
2
3994
3
4
5
6
7
3995
3996
8
9
10
11
12
1
1997
1998
1999
3997
3998
13
14
15
3999
5986
0
16
0
5984
2000
17
18
19
20
21
22
5987
0
23
0
2001
2002
2003
24
25
26
27
4000
4001
2004
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
2005
2006
...

result:

ok q=100000

Test #140:

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

input:

9970 100000
1 2
3 1
6 1
1 11
1 16
1 21
1 26
31 1
36 1
41 1
1 46
51 1
56 1
1 61
1 66
71 1
1 76
81 1
86 1
91 1
96 1
1 101
106 1
111 1
116 1
121 1
126 1
131 1
136 1
1 141
1 146
151 1
1 156
1 161
1 166
1 171
1 176
1 181
1 186
191 1
1 196
201 1
206 1
1 211
216 1
221 1
226 1
231 1
1 236
1 241
1 246
251 1
...

output:

0
5985
5986
5987
5988
5989
5990
1
5991
5992
5993
5994
1997
1998
1999
2000
2001
2002
2003
2004
2005
5995
5996
5997
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2...

result:

ok q=100000

Test #141:

score: 0
Accepted
time: 29ms
memory: 15792kb

input:

9970 100000
2 1
1 6
1 7
13 1
19 1
1 25
1 31
1 37
1 43
1 49
1 55
1 61
1 67
73 1
79 1
1 85
91 1
1 97
103 1
109 1
115 1
121 1
127 1
1 133
1 139
145 1
151 1
157 1
1 163
1 169
175 1
181 1
187 1
1 193
199 1
1 205
1 211
1 217
223 1
1 229
1 235
241 1
247 1
253 1
1 259
1 265
271 1
277 1
1 283
289 1
1 295
301...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3327
4991
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #142:

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

input:

9970 100000
2 1
1 3
4 1
1 6
7 1
1 13
1 19
1 25
1 31
1 37
43 1
1 49
1 55
61 1
67 1
1 73
79 1
85 1
1 91
1 97
1 103
109 1
115 1
121 1
1 127
133 1
1 139
145 1
1 151
157 1
163 1
1 169
175 1
181 1
187 1
193 1
1 199
205 1
1 211
217 1
223 1
229 1
1 235
241 1
1 247
1 253
259 1
265 1
271 1
1 277
1 283
289 1
2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #143:

score: 0
Accepted
time: 28ms
memory: 15032kb

input:

9970 100000
4 1
1 5
6 1
7 1
1 13
1 19
25 1
31 1
37 1
1 43
49 1
55 1
61 1
67 1
1 73
1 79
85 1
1 91
97 1
103 1
1 109
1 115
121 1
1 127
133 1
1 139
1 145
151 1
1 157
163 1
1 169
175 1
181 1
187 1
1 193
1 199
1 205
211 1
1 217
1 223
229 1
235 1
1 241
247 1
253 1
1 259
265 1
1 271
1 277
1 283
1 289
1 295...

output:

2
0
1665
3
1666
1
4
5
1668
1669
1667
1670
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
4991
3329
3330
3331
4992
3332
4993
3333
3334
4990
26
27
6652
3335
28
29
30
31
32
1671
3336
33
34
3337
3338
4994
3339
4995
4996
1672
1673
1674
35
36
37
38
39
40
41
42
43
4997
1675
1676
1677
1678
1679
168...

result:

ok q=100000

Test #144:

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

input:

9970 100000
3 1
1 4
5 1
1 7
13 1
19 1
1 25
1 31
37 1
43 1
1 49
55 1
61 1
67 1
73 1
79 1
1 85
1 91
1 97
1 103
109 1
1 115
1 121
1 127
1 133
139 1
1 145
151 1
1 157
163 1
1 169
175 1
181 1
187 1
1 193
199 1
205 1
211 1
217 1
1 223
1 229
235 1
1 241
1 247
1 253
259 1
1 265
271 1
1 277
283 1
1 289
295 1...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
3328
3329
21
22
23
24
25
26
27
28
29
30
31
32
33
34
4991
4992
4993
6652
3327
1666
4990
6653
6654
4994
4995
4996
4997
3330
3331
3332
3333
3334
3335
3336
3337
3338
35
3339
3340
3341
3342
3343
3344
3345
3346
3347
4998
1665
8313
8314
6655
6656
3348
1667...

result:

ok q=100000

Test #145:

score: 0
Accepted
time: 29ms
memory: 15248kb

input:

9970 100000
3 1
6 1
1 7
1 8
15 1
1 22
29 1
1 36
43 1
1 50
1 57
1 64
71 1
1 78
1 85
92 1
1 99
1 106
1 113
1 120
1 127
1 134
141 1
148 1
1 155
162 1
169 1
176 1
183 1
190 1
197 1
204 1
211 1
1 218
225 1
1 232
239 1
246 1
1 253
1 260
1 267
1 274
281 1
1 288
1 295
302 1
309 1
1 316
1 323
330 1
1 337
344...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #146:

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

input:

9970 100000
1 3
5 1
6 1
1 8
15 1
22 1
29 1
36 1
1 43
50 1
57 1
64 1
1 71
1 78
1 85
92 1
99 1
106 1
113 1
1 120
127 1
134 1
141 1
1 148
1 155
1 162
169 1
1 176
1 183
1 190
197 1
1 204
1 211
218 1
1 225
1 232
1 239
1 246
253 1
1 260
1 267
274 1
1 281
288 1
1 295
302 1
1 309
1 316
1 323
1 330
1 337
344...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1430
2856
7128
0
0
0
0
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 q=100000

Test #147:

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

input:

9970 100000
3 1
4 1
6 1
8 1
1 15
1 22
1 29
36 1
43 1
50 1
1 57
64 1
1 71
78 1
1 85
1 92
99 1
106 1
113 1
120 1
127 1
134 1
1 141
1 148
155 1
162 1
1 169
1 176
183 1
1 190
197 1
1 204
1 211
218 1
1 225
232 1
1 239
1 246
1 253
260 1
267 1
1 274
1 281
288 1
1 295
1 302
1 309
1 316
323 1
1 330
1 337
1 3...

output:

1428
1
2
4
5
6
7
3
1429
4280
2856
1430
8
9
10
11
12
4281
4282
1431
1432
1433
1434
2857
2858
2859
13
14
15
0
16
17
5703
1435
18
19
20
2860
21
22
23
24
25
26
27
28
29
30
31
1436
1437
1438
1439
1440
4283
4279
2861
32
33
5705
4284
4285
7129
1441
1442
34
35
36
37
38
2862
2863
5706
7130
7131
0
4286
4287
2...

result:

ok q=100000

Test #148:

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

input:

9970 100000
3 1
5 1
1 8
15 1
1 22
1 29
36 1
43 1
50 1
57 1
64 1
1 71
1 78
85 1
1 92
1 99
106 1
1 113
120 1
127 1
1 134
141 1
1 148
155 1
1 162
169 1
176 1
1 183
190 1
197 1
1 204
211 1
218 1
225 1
1 232
239 1
1 246
253 1
260 1
1 267
274 1
1 281
288 1
295 1
1 302
1 309
316 1
323 1
330 1
337 1
344 1
3...

output:

0
0
2855
1427
1429
1430
1431
1432
3
4
5
6
7
8
9
10
11
12
13
14
1433
1434
1435
1436
1437
4281
5705
8552
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1
2856
2857
2858
2859
2860
2861
2862
2863
2864
4279
1464
1465
1466
...

result:

ok q=100000

Test #149:

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

input:

9970 100000
2 1
1 3
1 4
5 1
7 1
8 1
1 9
1 17
25 1
1 33
1 41
1 49
1 57
1 65
73 1
1 81
1 89
1 97
1 105
1 113
121 1
1 129
137 1
145 1
1 153
161 1
169 1
177 1
1 185
193 1
201 1
209 1
1 217
1 225
233 1
241 1
1 249
257 1
265 1
1 273
1 281
289 1
297 1
305 1
1 313
321 1
329 1
1 337
345 1
353 1
1 361
1 369
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #150:

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

input:

9970 100000
1 4
1 5
6 1
8 1
9 1
17 1
25 1
1 33
1 41
1 49
57 1
65 1
1 73
81 1
89 1
97 1
105 1
1 113
121 1
1 129
137 1
145 1
1 153
1 161
1 169
177 1
1 185
1 193
1 201
209 1
217 1
1 225
233 1
1 241
249 1
257 1
265 1
1 273
1 281
289 1
1 297
305 1
1 313
321 1
1 329
1 337
345 1
1 353
361 1
369 1
377 1
385...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
1254
7486
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #151:

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

input:

9970 100000
1 3
1 6
8 1
1 9
17 1
25 1
33 1
1 41
1 49
57 1
65 1
73 1
81 1
89 1
1 97
105 1
113 1
121 1
1 129
1 137
1 145
1 153
161 1
169 1
177 1
1 185
193 1
1 201
209 1
1 217
1 225
233 1
1 241
249 1
257 1
265 1
1 273
281 1
289 1
1 297
1 305
1 313
1 321
1 329
1 337
345 1
353 1
1 361
1 369
1 377
385 1
1...

output:

1
2500
2502
2
2503
2504
2505
2506
2507
2508
2509
6241
1250
6242
2499
1253
1254
3747
3749
1255
4
5
6
7
8
9
10
11
12
13
14
15
16
1256
1257
1258
17
18
19
20
21
22
23
24
25
26
27
28
29
3750
30
31
32
33
34
35
36
37
38
1259
1260
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
1261
1262
56
57
1263
1264
...

result:

ok q=100000

Test #152:

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

input:

9970 100000
2 1
1 3
5 1
1 9
17 1
25 1
1 33
41 1
1 49
1 57
65 1
73 1
81 1
89 1
1 97
105 1
1 113
121 1
1 129
1 137
145 1
153 1
1 161
1 169
1 177
185 1
193 1
201 1
1 209
1 217
225 1
1 233
241 1
249 1
257 1
265 1
1 273
1 281
1 289
297 1
1 305
1 313
1 321
1 329
337 1
345 1
353 1
1 361
1 369
377 1
1 385
1...

output:

0
0
3749
1252
3747
6242
6243
4
5
6244
6245
6246
6247
6248
4995
1250
2
2501
2502
4994
6249
6250
6251
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
3750
3
1251
2499
2503
2504
2505
2506
3751
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
1
1253
1254
1255
52
53
5...

result:

ok q=100000

Test #153:

score: 0
Accepted
time: 242ms
memory: 15200kb

input:

1000 100000
1 5
17 1
22 1
33 1
1 34
35 1
41 1
1 55
1 56
60 1
75 1
76 1
1 77
88 1
1 89
1 93
1 95
1 96
97 1
98 1
1 103
1 105
108 1
1 112
1 115
116 1
143 1
1 147
156 1
164 1
1 168
183 1
188 1
197 1
198 1
199 1
210 1
1 213
215 1
1 217
223 1
224 1
225 1
228 1
1 233
236 1
240 1
249 1
250 1
258 1
259 1
1 2...

output:

1

result:

ok q=100000

Test #154:

score: 0
Accepted
time: 203ms
memory: 15196kb

input:

1000 100000
1 10
1 16
21 1
23 1
1 28
30 1
1 31
1 36
39 1
1 44
1 45
1 48
1 57
61 1
62 1
1 63
67 1
69 1
77 1
1 78
1 84
1 91
94 1
96 1
1 100
1 104
112 1
115 1
1 120
1 124
128 1
130 1
137 1
148 1
1 161
164 1
170 1
1 173
1 185
188 1
189 1
1 192
1 195
1 200
207 1
1 210
1 219
230 1
237 1
239 1
245 1
247 1
...

output:

262
307
500
514
523
544
464
512
140
413
281
444
104
238
300
41
224
386
397
5
16
23
416
443
318
426
174
343
347
396
442
203
368
380
105
417
342
388
447
449
452
160
454
457
463
466
468
490
476
497
502
505
509
515
42
215
225
529
531
539
541
548
356
405
434
453
540
554
555
557
560
208
377
381
530
553
55...

result:

ok q=100000

Test #155:

score: 0
Accepted
time: 178ms
memory: 15564kb

input:

1000 100000
1 10
1 13
14 1
16 1
1 19
21 1
32 1
1 39
40 1
1 44
49 1
1 51
52 1
1 54
1 56
61 1
63 1
70 1
1 73
1 83
1 87
1 99
101 1
104 1
111 1
114 1
119 1
121 1
122 1
126 1
1 130
133 1
135 1
1 146
150 1
158 1
170 1
183 1
1 184
185 1
186 1
187 1
1 190
192 1
196 1
205 1
208 1
223 1
227 1
1 235
1 242
244 ...

output:

26260
654
67
1228
1043
1635
2043
1726
17
795
1092
1284
1503
33
186
1854
1135
582
62
137
209
95
501
412
85
840
150
878
917
115
65
933
986
118
608
689
1034
114
120
131
601
859
832
898
976
1181
1183
66
40
462
630
953
103
1042
885
1070
1080
788
991
266
1188
160
1013
5
47
130
193
585
588
590
593
598
599
...

result:

ok q=100000

Test #156:

score: 0
Accepted
time: 122ms
memory: 15964kb

input:

1000 100000
1 2
3 1
5 1
1 8
9 1
10 1
1 11
19 1
21 1
42 1
44 1
45 1
1 46
1 67
69 1
1 75
1 87
1 88
100 1
103 1
114 1
121 1
1 123
127 1
131 1
1 143
1 149
151 1
153 1
159 1
1 163
1 174
176 1
1 185
1 186
191 1
1 194
1 205
210 1
1 215
1 217
1 219
1 220
222 1
1 229
232 1
234 1
1 237
240 1
1 241
245 1
1 247...

output:

0
0
0
0
0
0
0
686
186
20
228
4
240
33
387
419
781
1351
1354
1356
1382
767
1389
116
355
713
1257
1398
1399
6
608
754
1408
1409
62
1418
1425
467
657
1432
1447
715
1259
34
1451
1470
141
344
845
204
280
620
919
1195
174
318
709
768
1248
1345
1482
1280
1493
249
1201
1507
291
1509
92
295
670
802
595
1510
...

result:

ok q=100000

Test #157:

score: 0
Accepted
time: 93ms
memory: 15208kb

input:

1000 100000
1 6
1 12
18 1
19 1
34 1
1 37
41 1
53 1
58 1
1 63
1 66
1 70
73 1
1 80
1 82
94 1
1 104
1 110
1 112
1 114
1 115
118 1
121 1
126 1
131 1
136 1
1 137
139 1
1 145
146 1
148 1
1 149
1 159
1 161
164 1
170 1
186 1
189 1
191 1
193 1
1 197
1 206
207 1
208 1
212 1
224 1
1 225
1 226
228 1
229 1
233 1...

output:

2257
3823
1020
1458
1680
1962
239
1489
1822
1831
1890
179
1158
83
1165
1464
1569
1963
1973
2035
1005
983
2172
999
1236
1976
1445
1845
2259
2276
2446
1433
1631
2426
2686
2751
2757
2964
3145
1127
2330
1800
1943
2194
1916
3366
3443
3507
3514
3528
3540
3583
3686
3765
3813
3842
3876
3887
2579
2774
2776
2...

result:

ok q=100000

Test #158:

score: 0
Accepted
time: 83ms
memory: 14720kb

input:

1000 100000
1 10
1 20
23 1
26 1
32 1
35 1
1 41
47 1
1 52
1 54
57 1
1 58
61 1
68 1
71 1
1 82
1 85
90 1
103 1
1 114
1 124
125 1
129 1
1 133
1 135
139 1
140 1
1 143
1 158
1 160
1 161
164 1
1 169
174 1
181 1
186 1
187 1
188 1
189 1
199 1
1 208
1 227
1 228
1 232
1 240
1 243
250 1
1 255
260 1
270 1
272 1
...

output:

0
0
4522
6322
7500
8680
9253
9840
372
700
769
1157
2475
4672
4738
4881
5093
1308
5152
5938
6058
6669
7273
2652
5649
7424
7513
7840
7905
8219
9386
3943
9586
9593
9780
10055
10335
821
1016
1217
3583
3995
4178
4797
3540
2251
3414
3634
4638
4755
5391
153
746
946
2938
3127
3713
5522
5593
5638
5834
6234
6...

result:

ok q=100000

Test #159:

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

input:

1000 100000
5 1
1 11
1 20
1 37
43 1
44 1
47 1
48 1
54 1
1 63
69 1
1 70
72 1
73 1
83 1
84 1
1 86
1 93
1 94
1 95
1 101
1 108
114 1
115 1
124 1
137 1
1 141
1 144
1 151
158 1
159 1
160 1
167 1
175 1
181 1
1 183
1 191
1 196
1 198
1 203
1 213
1 215
216 1
239 1
245 1
246 1
249 1
1 254
261 1
264 1
277 1
289...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #160:

score: 0
Accepted
time: 239ms
memory: 14956kb

input:

1000 100000
2 1
15 1
1 18
21 1
1 23
33 1
52 1
54 1
55 1
1 56
1 57
1 61
62 1
1 66
69 1
1 72
1 73
1 75
79 1
1 85
87 1
1 88
1 89
95 1
104 1
121 1
1 123
1 127
1 131
1 135
1 136
137 1
1 139
1 148
150 1
1 156
1 162
1 189
192 1
193 1
1 194
1 197
1 209
1 213
1 216
1 218
220 1
221 1
222 1
1 230
248 1
1 249
1...

output:

4

result:

ok q=100000

Test #161:

score: 0
Accepted
time: 208ms
memory: 15932kb

input:

1000 100000
5 1
11 1
1 15
23 1
25 1
1 26
1 27
1 30
35 1
39 1
1 49
1 53
1 57
1 72
1 73
1 78
1 81
83 1
1 85
1 87
88 1
96 1
101 1
1 107
110 1
1 112
116 1
118 1
1 121
1 123
124 1
125 1
131 1
134 1
1 137
1 140
141 1
143 1
155 1
1 157
1 168
171 1
177 1
182 1
184 1
185 1
1 187
193 1
1 206
207 1
1 208
209 1...

output:

3
4
5
7
10
12
13
15
16
20
21
23
26
29
40
41
43
44
46
47
48
49
52
57
59
60
64
65
66
69
77
79
14
72
25
54
61
70
80
82
85
97
98
102
90
95
107
99
108
109
110
111
112
116
121
123
125
126
130
62
28
94
118
32
131
134
122
135
138
139
11
67
141
144
146
148
101
156
157
160
161
162
163
164
165
30
6
167
169
170...

result:

ok q=100000

Test #162:

score: 0
Accepted
time: 183ms
memory: 15320kb

input:

1000 100000
1 6
7 1
1 12
1 22
1 25
1 29
1 31
36 1
45 1
1 67
75 1
1 81
85 1
1 89
95 1
97 1
1 103
115 1
123 1
125 1
1 129
133 1
137 1
148 1
1 155
158 1
178 1
179 1
1 181
1 187
1 188
205 1
207 1
208 1
1 211
1 214
1 219
1 223
231 1
1 237
239 1
1 242
243 1
251 1
256 1
1 260
262 1
269 1
270 1
271 1
275 1
...

output:

1
3
4
8
9
10
11
12
17
19
20
22
26
30
37
39
44
49
50
51
52
61
64
66
71
72
79
83
87
18
23
28
36
40
56
57
63
69
70
75
81
86
94
98
99
111
117
121
122
127
133
142
144
146
151
152
129
158
160
162
166
167
168
172
180
124
183
186
108
187
192
199
208
209
210
214
215
216
218
221
224
225
29
229
230
234
236
238...

result:

ok q=100000

Test #163:

score: 0
Accepted
time: 95ms
memory: 14960kb

input:

1000 100000
3 1
8 1
9 1
1 16
28 1
45 1
1 49
1 55
1 56
57 1
66 1
68 1
1 70
1 74
78 1
1 84
1 85
86 1
87 1
97 1
99 1
103 1
105 1
1 107
1 111
1 112
1 127
130 1
1 133
1 134
142 1
143 1
149 1
161 1
167 1
1 168
172 1
1 174
1 179
1 190
193 1
1 195
1 202
205 1
1 209
216 1
217 1
218 1
1 219
1 229
1 234
236 1
...

output:

3
4
5
7
8
9
10
12
14
17
31
37
38
39
40
41
47
49
52
55
61
68
71
77
27
87
98
99
102
108
109
110
96
111
119
126
129
135
144
149
150
151
154
117
155
159
161
163
165
167
168
171
173
175
176
177
180
182
185
186
192
204
207
210
226
227
252
253
254
256
263
75
269
271
276
277
280
284
285
292
298
299
303
306
...

result:

ok q=100000

Test #164:

score: 0
Accepted
time: 127ms
memory: 14764kb

input:

1000 100000
1 13
16 1
17 1
1 22
1 24
29 1
1 30
1 55
57 1
1 58
59 1
1 72
73 1
75 1
77 1
1 85
87 1
1 89
90 1
1 93
1 99
101 1
1 103
1 106
1 119
1 122
125 1
145 1
1 151
1 158
1 163
1 167
170 1
179 1
184 1
1 187
1 193
1 201
202 1
204 1
1 207
1 211
213 1
216 1
222 1
224 1
226 1
234 1
1 242
246 1
259 1
1 2...

output:

10
15
30
38
68
69
72
78
81
82
97
112
142
151
154
166
181
194
196
199
208
211
217
219
224
234
241
242
245
246
250
251
258
260
261
264
271
273
278
280
288
289
192
294
296
298
301
303
305
306
308
310
311
313
315
316
319
320
321
322
326
330
232
335
336
345
346
348
351
352
354
357
369
373
374
375
382
284...

result:

ok q=100000

Test #165:

score: 0
Accepted
time: 67ms
memory: 15612kb

input:

1000 100000
2 1
3 1
9 1
11 1
22 1
1 33
1 39
1 42
1 43
1 44
1 49
67 1
68 1
73 1
76 1
78 1
81 1
1 84
85 1
87 1
88 1
1 93
1 99
108 1
128 1
1 129
1 132
134 1
135 1
138 1
1 142
144 1
1 150
1 155
158 1
160 1
1 170
1 175
183 1
1 193
1 197
213 1
1 215
216 1
222 1
1 225
1 233
234 1
235 1
242 1
258 1
268 1
1 ...

output:

1
8
17
20
21
22
26
27
33
35
36
38
41
43
50
66
67
69
71
73
74
78
64
79
80
84
86
88
94
95
101
102
108
117
119
121
125
133
135
136
145
153
154
157
160
163
165
171
172
173
176
177
179
183
184
185
189
191
202
203
207
208
209
210
214
216
217
219
223
224
226
229
231
236
237
240
259
263
265
267
269
273
274
...

result:

ok q=100000

Test #166:

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

input:

1000 100000
13 1
22 1
1 24
1 29
32 1
42 1
46 1
50 1
1 56
1 62
66 1
1 68
1 69
71 1
1 73
1 75
81 1
1 87
88 1
94 1
1 96
101 1
107 1
1 108
110 1
111 1
126 1
1 143
148 1
1 150
160 1
166 1
176 1
1 180
1 183
1 195
1 206
211 1
1 213
1 216
219 1
236 1
1 238
1 242
1 249
251 1
252 1
256 1
266 1
1 277
1 293
295...

output:

7
9
15
17
22
23
25
32
37
38
43
47
51
55
56
62
63
66
70
73
74
78
81
86
87
91
95
98
102
107
108
114
118
122
124
129
132
141
150
151
154
164
170
171
181
192
199
208
210
211
212
216
217
224
227
228
229
231
232
234
235
237
238
239
241
242
243
251
252
253
254
255
257
258
259
260
261
262
263
265
271
275
27...

result:

ok q=100000

Test #167:

score: 0
Accepted
time: 230ms
memory: 15552kb

input:

1000 100000
1 4
1 7
8 1
14 1
16 1
1 17
20 1
22 1
1 28
1 29
34 1
1 35
1 38
1 41
1 49
1 53
1 57
1 58
1 74
1 84
85 1
1 90
95 1
103 1
104 1
1 107
108 1
110 1
1 117
1 118
1 126
1 141
142 1
1 145
1 147
1 152
153 1
154 1
1 163
1 165
166 1
173 1
175 1
180 1
1 184
188 1
1 189
194 1
201 1
204 1
207 1
1 210
21...

output:

1

result:

ok q=100000

Test #168:

score: 0
Accepted
time: 214ms
memory: 15636kb

input:

1000 100000
15 1
18 1
1 26
31 1
1 37
1 40
42 1
1 46
1 48
1 49
1 53
55 1
1 68
75 1
82 1
83 1
89 1
92 1
102 1
106 1
1 113
1 114
1 119
1 121
1 123
128 1
129 1
130 1
1 133
140 1
1 143
1 153
1 154
1 163
1 167
168 1
171 1
176 1
178 1
1 190
191 1
1 192
1 200
201 1
204 1
205 1
1 206
212 1
1 215
1 218
1 223
...

output:

185
22
23
45
49
65
88
89
107
137
92
156
173
144
72
40
46
149
159
162
177
59
123
119
133
178
30
71
87
95
146
126
1
82
15
155
176
181
12
85
182
187
143
110
20
52
73
127
47
34
129
140
44
101
51
154
170
19
175
189
191
221
223
54
58
102
96
106
150
164
42
61
63
166
198
202
14
225
21
81
99
121
226
227
229
...

result:

ok q=100000

Test #169:

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

input:

1000 100000
5 1
14 1
1 17
33 1
40 1
55 1
1 58
59 1
1 61
1 66
70 1
1 71
1 75
76 1
79 1
1 81
90 1
95 1
1 102
1 104
1 109
119 1
130 1
1 131
142 1
144 1
147 1
1 154
158 1
1 161
170 1
178 1
1 182
187 1
189 1
1 211
217 1
1 229
1 233
245 1
248 1
1 249
254 1
256 1
1 257
258 1
271 1
1 273
1 277
286 1
1 287
1...

output:

0
0
193
231
129
602
749
636
691
305
77
388
575
283
323
209
4
396
432
355
206
498
566
594
687
83
284
695
220
453
237
360
699
704
130
733
745
787
281
697
328
343
748
750
796
99
495
802
807
156
368
425
584
39
361
362
474
290
476
564
609
611
352
621
634
298
644
669
262
321
333
381
419
593
350
626
267
33...

result:

ok q=100000

Test #170:

score: 0
Accepted
time: 123ms
memory: 15080kb

input:

1000 100000
1 5
1 13
1 19
26 1
1 29
34 1
35 1
38 1
39 1
45 1
1 46
1 67
79 1
1 92
94 1
1 97
108 1
1 111
1 120
122 1
1 129
131 1
140 1
1 143
148 1
159 1
1 169
175 1
180 1
185 1
187 1
1 189
1 192
1 195
200 1
205 1
1 208
1 213
1 228
1 232
243 1
244 1
1 245
1 246
1 263
271 1
274 1
1 281
292 1
299 1
301 1...

output:

0
806
1988
425
378
491
834
851
457
1021
1072
526
675
869
584
919
522
421
1045
1086
1098
852
477
906
1039
711
1111
1125
403
1031
724
1131
1143
470
790
877
1147
1167
1198
1240
1329
1386
1468
181
585
1199
827
870
136
1321
1477
1533
1572
1660
1788
1807
1811
1818
1876
1910
1962
2010
1795
1996
412
2025
48...

result:

ok q=100000

Test #171:

score: 0
Accepted
time: 108ms
memory: 15764kb

input:

1000 100000
1 3
4 1
1 5
8 1
1 11
1 21
1 24
1 27
36 1
45 1
1 51
1 74
1 75
79 1
1 80
83 1
1 86
1 93
1 95
98 1
101 1
106 1
109 1
110 1
117 1
127 1
1 130
1 131
1 137
1 141
145 1
1 154
155 1
160 1
1 164
166 1
168 1
169 1
172 1
1 173
174 1
181 1
1 185
1 188
198 1
1 202
1 212
217 1
1 228
230 1
1 234
1 235
...

output:

0
0
1393
2599
561
944
1948
733
2515
2683
2712
3328
3655
4149
4426
4547
2392
1327
2420
3230
3315
4145
228
2390
2593
3163
4338
4532
624
1192
1443
2010
424
2008
2436
3198
3201
3281
3242
3572
4207
4542
4650
1927
1828
378
2146
2340
2341
2342
2343
212
787
1370
2344
2345
1975
2351
1974
2353
2354
2355
2356
...

result:

ok q=100000

Test #172:

score: 0
Accepted
time: 55ms
memory: 14740kb

input:

1000 100000
4 1
1 6
8 1
1 9
12 1
16 1
1 20
1 32
50 1
1 62
70 1
1 72
1 74
1 77
78 1
1 79
1 84
88 1
89 1
94 1
95 1
1 97
107 1
114 1
1 115
126 1
130 1
132 1
1 138
1 144
1 156
1 162
1 163
165 1
178 1
1 181
1 185
1 192
200 1
214 1
1 215
1 218
1 221
1 226
1 232
1 235
1 237
246 1
1 249
1 256
1 269
279 1
28...

output:

0
0
0
0
0
2163
793
1765
2177
1467
1536
2801
2991
3089
4168
4643
4933
5234
5327
5424
510
715
1298
274
1501
1875
1912
2888
3020
3127
3333
3873
4549
4673
4953
5506
5543
5626
5834
5955
6038
6071
6527
7070
7111
7206
7494
104
1911
3126
4096
4865
5858
6634
7769
7804
7805
7860
7878
7983
8100
8409
8471
1469
...

result:

ok q=100000

Test #173:

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

input:

1000 100000
4 1
7 1
10 1
1 11
1 15
19 1
20 1
25 1
1 37
40 1
41 1
1 45
1 49
1 55
62 1
67 1
68 1
1 70
1 84
1 87
98 1
102 1
1 122
1 131
141 1
1 148
149 1
1 150
1 155
1 165
1 171
1 179
183 1
185 1
1 189
191 1
1 193
201 1
1 205
217 1
218 1
219 1
1 237
1 240
1 251
257 1
261 1
268 1
274 1
1 285
286 1
1 289...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #174:

score: 0
Accepted
time: 63ms
memory: 14924kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #175:

score: 0
Accepted
time: 69ms
memory: 14632kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #176:

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

input:

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

output:

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

result:

ok q=100000

Test #177:

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

input:

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

output:

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

result:

ok q=100000

Test #178:

score: 0
Accepted
time: 63ms
memory: 15200kb

input:

970 100000
2 1
3 1
1 5
1 7
1 9
11 1
1 13
15 1
1 17
19 1
1 21
23 1
1 25
1 27
29 1
31 1
1 33
35 1
37 1
39 1
1 41
1 43
1 45
1 47
1 49
51 1
1 53
55 1
1 57
59 1
61 1
63 1
1 65
67 1
1 69
1 71
73 1
75 1
77 1
79 1
1 81
83 1
1 85
1 87
89 1
91 1
93 1
1 95
1 97
1 99
101 1
1 103
1 105
1 107
1 109
1 111
113 1
11...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok q=100000

Test #179:

score: 0
Accepted
time: 77ms
memory: 14712kb

input:

970 100000
2 1
1 3
1 5
7 1
1 9
11 1
13 1
1 15
17 1
1 19
1 21
23 1
1 25
27 1
29 1
31 1
1 33
1 35
1 37
1 39
1 41
1 43
1 45
47 1
1 49
1 51
1 53
55 1
57 1
59 1
61 1
63 1
1 65
1 67
1 69
1 71
1 73
1 75
77 1
79 1
1 81
83 1
1 85
87 1
89 1
1 91
1 93
1 95
97 1
99 1
1 101
1 103
1 105
107 1
109 1
111 1
113 1
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #180:

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

input:

970 100000
1 2
3 1
1 5
7 1
9 1
11 1
13 1
15 1
17 1
1 19
21 1
1 23
1 25
1 27
1 29
1 31
33 1
35 1
37 1
1 39
1 41
43 1
1 45
1 47
49 1
51 1
1 53
55 1
57 1
1 59
1 61
1 63
65 1
67 1
1 69
1 71
1 73
1 75
1 77
79 1
1 81
1 83
1 85
1 87
89 1
1 91
93 1
95 1
97 1
1 99
1 101
103 1
105 1
107 1
1 109
111 1
1 113
1 ...

output:

1
0
486
0
487
0
488
2
3
0
4
5
6
7
8
0
489
9
10
11
490
12
13
14
15
16
17
0
491
0
18
0
492
19
20
21
493
0
22
23
24
25
494
26
495
0
27
28
29
0
496
30
31
32
497
0
33
34
35
36
498
37
38
0
39
0
499
40
500
0
501
0
41
0
42
43
44
45
46
47
502
0
48
49
503
0
50
51
52
0
53
54
55
0
56
57
58
0
59
0
504
0
505
60
5...

result:

ok q=100000

Test #181:

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

input:

970 100000
2 1
3 1
5 1
1 7
9 1
11 1
1 13
15 1
1 17
19 1
21 1
23 1
1 25
1 27
29 1
1 31
1 33
1 35
1 37
39 1
41 1
1 43
45 1
1 47
1 49
51 1
53 1
1 55
1 57
59 1
1 61
63 1
1 65
67 1
69 1
71 1
73 1
75 1
1 77
1 79
1 81
83 1
1 85
87 1
89 1
1 91
1 93
95 1
1 97
1 99
1 101
103 1
105 1
107 1
1 109
111 1
113 1
11...

output:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
0
0
0
0
486
487
0
0
14
0
15
0
488
16
17
18
489
0
19
20
21
490
0
22
23
24
25
26
491
492
493
0
0
0
27
0
28
29
0
0
30
0
0
0
0
0
494
31
32
0
0
0
495
0
0
0
0
496
497
498
499
500
501
502
503
0
0
33
0
504
34
505
506
0
0
507
508
509
510
511
0
35
36
37
38
39
0
0
40
0
512
513
5...

result:

ok q=100000

Test #182:

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

input:

970 100000
1 3
4 1
1 10
1 13
16 1
19 1
22 1
1 25
28 1
1 31
34 1
40 1
43 1
58 1
61 1
1 64
70 1
73 1
76 1
82 1
85 1
1 91
94 1
1 100
1 103
1 109
1 112
115 1
118 1
1 127
1 130
1 133
136 1
1 139
142 1
157 1
1 160
1 163
1 166
1 178
1 184
1 187
1 190
193 1
1 196
199 1
1 205
208 1
217 1
1 220
223 1
226 1
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #183:

score: 0
Accepted
time: 65ms
memory: 15304kb

input:

970 100000
2 1
10 1
13 1
16 1
22 1
25 1
1 28
31 1
1 34
1 37
40 1
1 46
49 1
55 1
70 1
1 76
1 79
1 82
85 1
1 88
106 1
1 109
1 112
1 115
1 118
124 1
127 1
130 1
1 136
1 139
1 145
1 154
1 157
1 160
163 1
166 1
1 172
1 175
181 1
184 1
193 1
1 196
1 208
211 1
214 1
220 1
223 1
229 1
232 1
1 235
1 238
247 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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
...

result:

ok q=100000

Test #184:

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

input:

970 100000
3 1
4 1
1 7
10 1
13 1
16 1
19 1
1 22
1 25
1 28
37 1
1 40
43 1
46 1
1 49
52 1
1 55
1 58
1 64
1 67
1 70
73 1
76 1
79 1
1 85
91 1
94 1
97 1
106 1
1 109
1 112
115 1
1 118
1 124
127 1
133 1
139 1
1 142
1 148
1 154
157 1
160 1
1 163
166 1
169 1
172 1
175 1
181 1
1 184
187 1
1 190
1 193
199 1
1 ...

output:

1
0
214
0
216
0
210
3
413
0
6
10
11
13
217
14
220
225
15
227
414
0
17
18
20
22
23
24
25
26
27
29
30
0
31
0
32
33
34
0
37
38
39
40
415
0
231
0
235
0
236
42
43
45
46
48
245
49
248
52
54
0
252
258
56
58
59
260
416
60
62
64
68
0
69
71
72
261
263
0
73
74
78
81
417
0
418
269
270
0
272
273
274
275
82
279
4...

result:

ok q=100000

Test #185:

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

input:

970 100000
1 2
1 4
1 7
10 1
1 13
16 1
1 19
1 22
1 25
28 1
1 37
49 1
1 52
1 55
1 67
1 70
1 73
79 1
85 1
1 88
1 91
1 94
1 97
1 100
103 1
1 106
112 1
118 1
124 1
1 133
1 136
139 1
142 1
145 1
1 154
160 1
1 163
1 172
1 175
178 1
181 1
184 1
193 1
1 196
199 1
1 205
208 1
211 1
1 220
223 1
232 1
1 235
238...

output:

1
211
212
218
222
232
236
2
3
4
6
7
8
9
423
424
0
0
0
10
11
15
431
437
239
244
247
0
0
16
18
19
249
251
252
253
254
261
264
265
267
269
271
276
448
0
278
281
282
288
294
298
449
20
22
23
24
25
300
301
302
305
306
0
26
27
29
31
32
33
34
309
35
36
37
310
315
318
450
458
319
38
39
320
43
45
46
47
331
3...

result:

ok q=100000

Test #186:

score: 0
Accepted
time: 40ms
memory: 14716kb

input:

970 100000
3 1
5 1
1 9
13 1
17 1
21 1
29 1
1 33
1 37
1 41
1 49
53 1
57 1
69 1
1 73
1 77
1 81
85 1
1 89
93 1
97 1
1 101
1 105
1 117
121 1
125 1
1 129
133 1
137 1
141 1
1 145
1 149
153 1
157 1
1 161
169 1
1 173
1 181
185 1
189 1
193 1
1 197
201 1
209 1
213 1
217 1
1 221
225 1
229 1
1 233
241 1
1 245
2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #187:

score: 0
Accepted
time: 63ms
memory: 14720kb

input:

970 100000
1 3
1 4
5 1
9 1
13 1
17 1
1 21
25 1
29 1
33 1
1 37
1 49
1 53
1 57
61 1
65 1
69 1
1 73
81 1
1 85
89 1
1 105
1 113
1 117
1 121
1 125
129 1
133 1
1 137
141 1
1 145
149 1
153 1
1 157
1 161
1 165
1 189
1 193
197 1
201 1
1 205
209 1
1 213
1 217
221 1
225 1
229 1
237 1
1 241
1 245
1 249
1 253
26...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
210
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #188:

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

input:

970 100000
2 1
1 3
4 1
1 5
1 9
1 13
17 1
1 21
1 25
33 1
1 37
41 1
1 45
49 1
57 1
61 1
1 65
69 1
1 73
81 1
1 85
1 89
1 97
1 101
105 1
1 113
1 117
1 121
125 1
1 129
133 1
137 1
1 141
149 1
153 1
1 157
1 161
1 165
169 1
1 173
1 177
1 181
185 1
189 1
197 1
1 201
205 1
1 209
1 213
217 1
1 221
1 229
233 1...

output:

1
0
3
0
2
5
6
8
9
212
422
0
423
424
627
214
628
10
11
12
14
0
629
16
17
215
18
19
216
20
218
21
221
224
225
227
425
426
228
431
22
432
229
232
23
24
25
26
27
28
433
233
434
31
32
34
35
36
37
0
38
39
234
0
235
236
238
435
631
239
240
241
242
437
438
40
41
42
43
44
45
46
47
48
49
243
440
50
51
52
244
...

result:

ok q=100000

Test #189:

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

input:

970 100000
2 1
1 3
4 1
1 5
1 9
13 1
1 17
1 21
1 33
1 37
1 41
45 1
49 1
53 1
57 1
1 61
1 65
1 69
73 1
1 77
1 81
85 1
1 89
1 93
97 1
1 101
105 1
1 109
1 117
1 121
125 1
1 129
137 1
1 141
145 1
1 149
1 153
161 1
1 169
1 173
1 177
181 1
1 185
1 189
1 193
197 1
1 201
205 1
1 209
213 1
217 1
1 229
233 1
2...

output:

3
2
4
5
6
425
627
628
7
8
9
11
12
13
14
15
16
17
428
20
21
22
23
430
435
436
29
30
31
32
36
438
439
629
630
445
450
631
633
455
1
210
211
212
457
636
213
214
215
216
217
458
460
461
464
467
469
476
478
218
219
220
221
222
223
224
225
226
227
228
229
230
638
231
232
233
480
234
235
236
237
238
239
24...

result:

ok q=100000

Test #190:

score: 0
Accepted
time: 55ms
memory: 14728kb

input:

970 93610
1 3
1 4
1 6
1 11
16 1
21 1
1 26
1 31
36 1
1 41
46 1
1 51
56 1
1 61
1 66
1 71
76 1
81 1
86 1
1 91
96 1
101 1
106 1
1 111
1 116
121 1
126 1
1 131
136 1
141 1
1 146
1 151
1 156
161 1
1 166
171 1
176 1
181 1
186 1
1 191
1 196
1 201
1 206
211 1
216 1
1 221
1 226
1 231
236 1
241 1
246 1
1 251
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #191:

score: 0
Accepted
time: 73ms
memory: 14404kb

input:

970 93610
5 1
6 1
1 11
16 1
1 21
26 1
1 31
36 1
41 1
46 1
1 51
56 1
1 61
1 66
1 71
1 76
81 1
86 1
1 91
96 1
1 101
106 1
1 111
1 116
121 1
1 126
1 131
1 136
1 141
146 1
1 151
1 156
161 1
1 166
1 171
176 1
1 181
1 186
1 191
196 1
1 201
1 206
1 211
1 216
1 221
226 1
1 231
236 1
1 241
1 246
1 251
1 256
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
196
584
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #192:

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

input:

970 93610
1 2
1 3
4 1
1 5
6 1
1 11
16 1
21 1
1 26
1 31
1 36
41 1
46 1
1 51
1 56
61 1
1 66
1 71
76 1
1 81
86 1
1 91
1 96
1 101
106 1
111 1
116 1
121 1
1 126
1 131
1 136
141 1
146 1
1 151
156 1
1 161
1 166
171 1
1 176
1 181
186 1
1 191
196 1
201 1
1 206
1 211
1 216
1 221
1 226
231 1
1 236
1 241
246 1
...

output:

2
1
392
3
4
5
6
199
200
201
7
202
203
204
8
205
9
10
11
198
12
13
14
15
16
17
18
19
20
585
393
21
22
23
24
25
26
27
28
206
207
29
30
31
32
33
34
35
36
37
38
39
40
208
209
41
42
210
211
586
778
0
212
213
214
0
43
44
779
215
216
217
218
394
395
396
219
45
220
46
47
48
221
222
223
224
225
49
50
51
52
5...

result:

ok q=100000

Test #193:

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

input:

970 93610
1 3
1 6
1 11
1 16
21 1
26 1
1 31
36 1
41 1
46 1
51 1
1 56
61 1
66 1
1 71
1 76
81 1
1 86
91 1
96 1
1 101
106 1
1 111
116 1
1 121
1 126
1 131
1 136
141 1
146 1
151 1
156 1
1 161
166 1
1 171
1 176
1 181
1 186
1 191
1 196
201 1
1 206
1 211
216 1
221 1
226 1
231 1
1 236
1 241
1 246
1 251
1 256
...

output:

197
2
3
4
5
6
7
8
198
199
200
201
202
203
0
0
0
0
1
195
391
392
393
394
395
204
396
390
585
0
0
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
205
196
778
779
780
781
24
25
26
27
206
397
398
399
400
207
208
209
210
211
212
213
28
29
30
31
32
33
34
35
214
215
36
37
38
39
40
41
42
43
216
217
218
219
220
...

result:

ok q=100000

Test #194:

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

input:

970 77288
1 2
3 1
1 4
5 1
1 7
13 1
1 19
1 25
31 1
37 1
43 1
1 49
1 55
61 1
1 67
1 73
1 79
1 85
91 1
97 1
103 1
1 109
115 1
121 1
1 127
133 1
139 1
1 145
1 151
1 157
1 163
169 1
175 1
181 1
187 1
193 1
199 1
205 1
1 211
217 1
1 223
1 229
1 235
241 1
1 247
253 1
259 1
1 265
271 1
1 277
1 283
289 1
1 2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
165
487
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #195:

score: 0
Accepted
time: 44ms
memory: 14464kb

input:

970 77288
1 2
5 1
1 6
7 1
13 1
19 1
1 25
31 1
37 1
43 1
49 1
55 1
61 1
1 67
1 73
1 79
1 85
91 1
1 97
103 1
109 1
115 1
1 121
127 1
1 133
139 1
145 1
151 1
157 1
1 163
1 169
175 1
1 181
1 187
1 193
199 1
1 205
1 211
1 217
223 1
1 229
235 1
1 241
1 247
253 1
1 259
1 265
1 271
1 283
289 1
295 1
301 1
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
164
326
327
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
487
0
0
0
0
0
0
1
165
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok q=100000

Test #196:

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

input:

970 77288
2 1
1 5
1 6
1 7
1 13
1 19
1 25
1 31
37 1
43 1
1 49
1 55
61 1
67 1
73 1
79 1
1 85
91 1
97 1
103 1
109 1
1 115
1 121
127 1
133 1
139 1
145 1
1 151
157 1
1 163
169 1
175 1
1 181
187 1
1 193
199 1
1 205
1 211
1 217
223 1
229 1
235 1
1 241
247 1
253 1
1 259
265 1
271 1
277 1
1 283
1 289
295 1
3...

output:

164
1
328
2
165
166
167
168
169
170
648
330
649
0
327
3
4
488
331
489
487
171
172
650
333
5
6
7
173
174
334
335
808
8
9
10
175
176
177
336
11
12
178
179
180
181
182
183
184
13
185
651
14
15
16
17
18
19
20
652
809
653
21
654
490
186
187
188
491
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40...

result:

ok q=100000

Test #197:

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

input:

970 77288
2 1
1 4
1 5
1 7
13 1
1 25
31 1
37 1
43 1
1 49
1 55
61 1
67 1
73 1
1 79
1 85
1 91
97 1
1 103
1 109
1 115
121 1
127 1
1 133
1 139
1 145
1 151
1 157
163 1
169 1
175 1
1 181
1 187
193 1
199 1
1 205
211 1
1 217
223 1
229 1
235 1
1 241
1 247
1 253
1 259
1 265
1 271
1 277
283 1
1 289
295 1
301 1
...

output:

1
5
6
7
163
164
165
167
8
9
10
13
15
18
20
21
29
30
31
32
33
161
321
322
323
482
3
0
0
2
320
483
484
485
486
168
169
37
40
41
43
44
171
172
173
174
175
176
177
324
325
326
46
49
51
54
56
57
58
59
61
63
64
66
67
71
72
75
76
77
78
79
80
83
85
86
91
179
182
94
95
99
100
102
104
183
186
187
189
327
328
...

result:

ok q=100000

Test #198:

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

input:

970 66182
2 1
1 3
4 1
1 6
7 1
1 8
15 1
1 22
1 29
36 1
43 1
50 1
1 57
1 64
1 71
1 85
1 92
99 1
1 106
113 1
1 120
1 127
1 134
1 141
148 1
155 1
162 1
1 169
1 176
1 183
190 1
1 197
204 1
1 218
225 1
232 1
239 1
246 1
1 253
1 260
1 267
1 274
281 1
1 288
1 295
302 1
1 309
316 1
323 1
1 330
337 1
1 344
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
140
557
0
0
0
0
0
141
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #199:

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

input:

970 66182
1 4
5 1
1 6
7 1
8 1
15 1
1 22
29 1
36 1
43 1
1 50
1 57
1 64
71 1
1 78
1 85
92 1
1 99
1 106
1 113
1 120
127 1
134 1
1 141
1 148
1 155
162 1
1 169
1 176
183 1
1 190
197 1
1 204
211 1
1 218
1 225
232 1
239 1
246 1
253 1
260 1
267 1
274 1
281 1
288 1
295 1
1 302
309 1
1 316
1 323
330 1
337 1
3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
144
56...

result:

ok q=100000

Test #200:

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

input:

970 66182
1 2
1 5
1 7
8 1
1 15
22 1
1 29
1 36
43 1
1 57
64 1
1 71
1 78
85 1
1 92
1 99
106 1
1 113
1 120
1 127
134 1
141 1
148 1
155 1
1 162
1 169
1 176
1 183
1 190
197 1
204 1
211 1
1 218
225 1
232 1
1 239
1 246
253 1
260 1
267 1
274 1
281 1
1 288
295 1
1 302
1 309
316 1
1 323
1 330
1 337
344 1
351 ...

output:

279
281
282
283
284
285
4
5
6
7
8
9
418
419
278
1
420
286
142
287
288
421
143
422
289
423
424
425
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
558
32
3
144
33
34
35
36
37
38
290
696
141
2
426
427
428
39
40
429
291
292
293
294
295
296
430
41
42
297
298
299
431
432
43
433
145
146
...

result:

ok q=100000

Test #201:

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

input:

970 66182
4 1
1 5
6 1
1 8
15 1
1 22
1 29
1 36
43 1
1 50
1 57
1 64
1 71
78 1
85 1
92 1
1 99
106 1
1 113
120 1
1 127
134 1
1 141
148 1
155 1
162 1
169 1
1 176
183 1
1 190
197 1
204 1
1 211
1 218
225 1
232 1
1 239
1 246
1 253
1 260
267 1
274 1
1 281
288 1
295 1
302 1
309 1
316 1
323 1
330 1
337 1
344 1...

output:

0
142
284
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
145
25
26
27
28
29
30
31
32
146
147
148
149
150
33
34
35
36
37
38
39
40
41
151
152
153
154
155
156
157
158
42
159
160
161
162
163
164
165
166
167
168
169
170
43
44
45
46
171
172
287
288
417
418
1
281
419
2
557
695
420
421
422
423
4...

result:

ok q=100000

Test #202:

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

input:

970 58094
3 1
1 4
1 5
1 7
8 1
1 9
17 1
1 25
33 1
1 41
49 1
1 57
1 65
73 1
81 1
1 89
97 1
105 1
113 1
1 121
1 129
137 1
145 1
153 1
161 1
169 1
1 177
1 185
193 1
1 201
1 209
1 217
1 225
233 1
1 241
249 1
1 257
265 1
273 1
1 281
1 289
297 1
1 305
1 313
321 1
329 1
1 337
1 345
1 353
1 361
369 1
1 377
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
248
610
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 q=100000

Test #203:

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

input:

970 58094
3 1
5 1
1 9
17 1
25 1
33 1
1 41
49 1
57 1
1 65
1 73
1 81
1 89
1 97
105 1
1 113
121 1
1 129
137 1
1 145
1 153
1 161
1 169
1 177
1 185
193 1
1 201
209 1
217 1
225 1
233 1
1 241
1 249
1 257
1 265
1 273
1 281
289 1
297 1
305 1
313 1
1 321
329 1
1 337
1 345
353 1
1 361
1 369
1 377
1 385
1 393
4...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
0
0
0
0
0
125
249
371
493
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
124
248
494
0
0
0
0
0
0
0
...

result:

ok q=100000

Test #204:

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

input:

970 58094
2 1
5 1
1 6
7 1
1 8
1 9
17 1
25 1
1 33
41 1
1 49
1 57
1 65
1 73
1 81
89 1
97 1
1 105
113 1
1 121
1 129
137 1
1 145
1 153
1 161
1 169
1 177
1 185
193 1
1 201
209 1
217 1
1 225
233 1
241 1
1 249
257 1
265 1
273 1
1 281
1 289
297 1
305 1
1 313
321 1
329 1
337 1
345 1
1 353
1 361
369 1
377 1
1...

output:

1
2
4
3
127
252
253
129
254
130
131
5
132
133
255
256
257
258
370
371
128
249
6
7
8
9
10
11
12
134
135
136
137
13
14
15
138
139
16
17
18
140
19
20
21
22
23
141
142
143
259
144
24
25
26
145
146
147
148
149
150
151
260
250
492
27
28
29
30
31
32
33
34
152
153
35
36
37
38
39
40
41
42
43
44
45
46
47
48
4...

result:

ok q=100000

Test #205:

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

input:

970 58094
4 1
5 1
7 1
8 1
9 1
1 17
1 25
33 1
41 1
1 49
1 57
1 65
1 73
81 1
89 1
1 97
1 105
113 1
121 1
129 1
1 137
1 145
153 1
1 161
1 169
1 177
1 185
1 193
201 1
209 1
217 1
225 1
233 1
241 1
249 1
257 1
265 1
1 273
1 281
1 289
297 1
1 305
313 1
1 321
1 329
1 337
1 345
1 353
1 361
1 369
377 1
385 1...

output:

0
126
0
4
130
254
375
2
495
496
1
127
252
376
377
378
379
497
253
255
256
257
258
259
260
261
262
263
264
3
129
265
266
732
733
734
735
736
737
128
738
739
740
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
131
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
267
268
269
270...

result:

ok q=100000

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-03 20:12:51 | OpenSource Project