QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102508#5154. ETAw4p3r#AC ✓250ms47484kbC++201.7kb2023-05-03 14:07:032023-05-03 14:07:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-03 14:07:07]
  • 评测
  • 测评结果:AC
  • 用时:250ms
  • 内存:47484kb
  • [2023-05-03 14:07:03]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e - 6
#define FOR(i, a, b) for(int i = a;i <= b;i ++)
#define REP(i, a, b) for(int i = a;i >= b;i --)
#define pa pair<int, int>
#define fr first
#define sd second
#define pb push_back
#define db double
#define MEM(a) memset(a, 0, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch = getchar();
	ll s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
#define int ll
#define N 1000010
int d[N];
vector<int>v[N];
signed main()
{
	// freopen("E.out", "w", stdout);
	int a = read(), b = read();
	int ta = a, tb = b;
	if (a < b - 1) {cout << "impossible\n"; return 0;}
	else if (a == b - 1)
	{
		cout << b << " " << b - 1 << '\n';
		FOR(i, 2, b)cout << 1 << ' ' << i << '\n';
		return 0;
	}
	int t = int(1e6) / b;
	b *= t, a *= t;
	assert(b * (b - 1) / 2 >= a);
	swap(a, b);
	b -= a - 1;
	int l = 1, r = a, ans = 0;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (mid * (mid - 1) / 2 + (a - 1 - mid) * (mid - 1) >= b) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	for (int i = 2; i <= ans + 1; i++)d[i] = i - 2, b -= d[i];
	for (int i = ans + 2; i <= a; i++)
	{
		if (b >= ans - 1) {b -= ans - 1, d[i] = ans - 1;}
		else {d[i] = b; break;}
	}
	FOR(i, 2, a)d[i]++;
	FOR(i, 1, a)v[d[i]].pb(i);
	// FOR(i, 1, a)cout << d[i] << ' '; cout << endl;
	int s=0;
	FOR(i,1,a)s+=d[i];
	assert(s/__gcd(s,a)==ta&&a/__gcd(s,a)==tb);
	cout << a << " " << a - 1 <<'\n';
	FOR(p, 1, ans)for (int x : v[p])cout << v[p - 1][0] << ' ' << x << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1/2

output:

2 1
1 2

result:

ok 

Test #2:

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

input:

1/3

output:

impossible

result:

ok 

Test #3:

score: 0
Accepted
time: 142ms
memory: 44128kb

input:

7/4

output:

1000000 999999
1 2
1 750004
1 750005
1 750006
1 750007
1 750008
1 750009
1 750010
1 750011
1 750012
1 750013
1 750014
1 750015
1 750016
1 750017
1 750018
1 750019
1 750020
1 750021
1 750022
1 750023
1 750024
1 750025
1 750026
1 750027
1 750028
1 750029
1 750030
1 750031
1 750032
1 750033
1 750034
1 ...

result:

ok 

Test #4:

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

input:

974/975

output:

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

result:

ok 

Test #5:

score: 0
Accepted
time: 142ms
memory: 44092kb

input:

943/346

output:

999940 999939
1 2
1 862669
1 862670
1 862671
1 862672
1 862673
1 862674
1 862675
1 862676
1 862677
1 862678
1 862679
1 862680
1 862681
1 862682
1 862683
1 862684
1 862685
1 862686
1 862687
1 862688
1 862689
1 862690
1 862691
1 862692
1 862693
1 862694
1 862695
1 862696
1 862697
1 862698
1 862699
1 8...

result:

ok 

Test #6:

score: 0
Accepted
time: 142ms
memory: 42632kb

input:

912/7

output:

999999 999998
1 2
1 994573
1 994574
1 994575
1 994576
1 994577
1 994578
1 994579
1 994580
1 994581
1 994582
1 994583
1 994584
1 994585
1 994586
1 994587
1 994588
1 994589
1 994590
1 994591
1 994592
1 994593
1 994594
1 994595
1 994596
1 994597
1 994598
1 994599
1 994600
1 994601
1 994602
1 994603
1 9...

result:

ok 

Test #7:

score: 0
Accepted
time: 161ms
memory: 42668kb

input:

1/1

output:

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

result:

ok 

Test #8:

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

input:

1/1000

output:

impossible

result:

ok 

Test #9:

score: 0
Accepted
time: 146ms
memory: 42636kb

input:

1000/999

output:

999999 999998
1 2
1 1005
1 1006
1 1007
1 1008
1 1009
1 1010
1 1011
1 1012
1 1013
1 1014
1 1015
1 1016
1 1017
1 1018
1 1019
1 1020
1 1021
1 1022
1 1023
1 1024
1 1025
1 1026
1 1027
1 1028
1 1029
1 1030
1 1031
1 1032
1 1033
1 1034
1 1035
1 1036
1 1037
1 1038
1 1039
1 1040
1 1041
1 1042
1 1043
1 1044
1 ...

result:

ok 

Test #10:

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

input:

999/1000

output:

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

result:

ok 

Test #11:

score: 0
Accepted
time: 146ms
memory: 42624kb

input:

1000/1

output:

1000000 999999
1 2
1 999503
1 999504
1 999505
1 999506
1 999507
1 999508
1 999509
1 999510
1 999511
1 999512
1 999513
1 999514
1 999515
1 999516
1 999517
1 999518
1 999519
1 999520
1 999521
1 999522
1 999523
1 999524
1 999525
1 999526
1 999527
1 999528
1 999529
1 999530
1 999531
1 999532
1 999533
1 ...

result:

ok 

Test #12:

score: 0
Accepted
time: 146ms
memory: 42588kb

input:

999/2

output:

1000000 999999
1 2
1 999250
1 999251
1 999252
1 999253
1 999254
1 999255
1 999256
1 999257
1 999258
1 999259
1 999260
1 999261
1 999262
1 999263
1 999264
1 999265
1 999266
1 999267
1 999268
1 999269
1 999270
1 999271
1 999272
1 999273
1 999274
1 999275
1 999276
1 999277
1 999278
1 999279
1 999280
1 ...

result:

ok 

Test #13:

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

input:

1000/3

output:

999999 999998
1 2
1 998167
1 998168
1 998169
1 998170
1 998171
1 998172
1 998173
1 998174
1 998175
1 998176
1 998177
1 998178
1 998179
1 998180
1 998181
1 998182
1 998183
1 998184
1 998185
1 998186
1 998187
1 998188
1 998189
1 998190
1 998191
1 998192
1 998193
1 998194
1 998195
1 998196
1 998197
1 9...

result:

ok 

Test #14:

score: 0
Accepted
time: 131ms
memory: 42524kb

input:

26/3

output:

999999 999998
1 2
1 958339
1 958340
1 958341
1 958342
1 958343
1 958344
1 958345
1 958346
1 958347
1 958348
1 958349
1 958350
1 958351
1 958352
1 958353
1 958354
1 958355
1 958356
1 958357
1 958358
1 958359
1 958360
1 958361
1 958362
1 958363
1 958364
1 958365
1 958366
1 958367
1 958368
1 958369
1 9...

result:

ok 

Test #15:

score: 0
Accepted
time: 129ms
memory: 42620kb

input:

79/9

output:

999999 999998
1 2
1 972228
1 972229
1 972230
1 972231
1 972232
1 972233
1 972234
1 972235
1 972236
1 972237
1 972238
1 972239
1 972240
1 972241
1 972242
1 972243
1 972244
1 972245
1 972246
1 972247
1 972248
1 972249
1 972250
1 972251
1 972252
1 972253
1 972254
1 972255
1 972256
1 972257
1 972258
1 9...

result:

ok 

Test #16:

score: 0
Accepted
time: 144ms
memory: 42612kb

input:

80/9

output:

999999 999998
1 2
1 986117
1 986118
1 986119
1 986120
1 986121
1 986122
1 986123
1 986124
1 986125
1 986126
1 986127
1 986128
1 986129
1 986130
1 986131
1 986132
1 986133
1 986134
1 986135
1 986136
1 986137
1 986138
1 986139
1 986140
1 986141
1 986142
1 986143
1 986144
1 986145
1 986146
1 986147
1 9...

result:

ok 

Test #17:

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

input:

998/999

output:

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

result:

ok 

Test #18:

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

input:

997/999

output:

impossible

result:

ok 

Test #19:

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

input:

997/1000

output:

impossible

result:

ok 

Test #20:

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

input:

99/200

output:

impossible

result:

ok 

Test #21:

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

input:

101/200

output:

impossible

result:

ok 

Test #22:

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

input:

99/199

output:

impossible

result:

ok 

Test #23:

score: 0
Accepted
time: 132ms
memory: 44296kb

input:

2/1

output:

1000000 999999
1 2
1 500004
1 500005
1 500006
1 500007
1 500008
1 500009
1 500010
1 500011
1 500012
1 500013
1 500014
1 500015
1 500016
1 500017
1 500018
1 500019
1 500020
1 500021
1 500022
1 500023
1 500024
1 500025
1 500026
1 500027
1 500028
1 500029
1 500030
1 500031
1 500032
1 500033
1 500034
1 ...

result:

ok 

Test #24:

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

input:

200/99

output:

999999 999998
1 2
1 510105
1 510106
1 510107
1 510108
1 510109
1 510110
1 510111
1 510112
1 510113
1 510114
1 510115
1 510116
1 510117
1 510118
1 510119
1 510120
1 510121
1 510122
1 510123
1 510124
1 510125
1 510126
1 510127
1 510128
1 510129
1 510130
1 510131
1 510132
1 510133
1 510134
1 510135
1 5...

result:

ok 

Test #25:

score: 0
Accepted
time: 150ms
memory: 42580kb

input:

200/101

output:

999900 999899
1 2
1 980104
1 980105
1 980106
1 980107
1 980108
1 980109
1 980110
1 980111
1 980112
1 980113
1 980114
1 980115
1 980116
1 980117
1 980118
1 980119
1 980120
1 980121
1 980122
1 980123
1 980124
1 980125
1 980126
1 980127
1 980128
1 980129
1 980130
1 980131
1 980132
1 980133
1 980134
1 9...

result:

ok 

Test #26:

score: 0
Accepted
time: 167ms
memory: 42504kb

input:

199/100

output:

1000000 999999
1 2
1 990004
1 990005
1 990006
1 990007
1 990008
1 990009
1 990010
1 990011
1 990012
1 990013
1 990014
1 990015
1 990016
1 990017
1 990018
1 990019
1 990020
1 990021
1 990022
1 990023
1 990024
1 990025
1 990026
1 990027
1 990028
1 990029
1 990030
1 990031
1 990032
1 990033
1 990034
1 ...

result:

ok 

Test #27:

score: 0
Accepted
time: 143ms
memory: 44296kb

input:

201/100

output:

1000000 999999
1 2
1 505004
1 505005
1 505006
1 505007
1 505008
1 505009
1 505010
1 505011
1 505012
1 505013
1 505014
1 505015
1 505016
1 505017
1 505018
1 505019
1 505020
1 505021
1 505022
1 505023
1 505024
1 505025
1 505026
1 505027
1 505028
1 505029
1 505030
1 505031
1 505032
1 505033
1 505034
1 ...

result:

ok 

Test #28:

score: 0
Accepted
time: 152ms
memory: 42696kb

input:

999/500

output:

1000000 999999
1 2
1 998004
1 998005
1 998006
1 998007
1 998008
1 998009
1 998010
1 998011
1 998012
1 998013
1 998014
1 998015
1 998016
1 998017
1 998018
1 998019
1 998020
1 998021
1 998022
1 998023
1 998024
1 998025
1 998026
1 998027
1 998028
1 998029
1 998030
1 998031
1 998032
1 998033
1 998034
1 ...

result:

ok 

Test #29:

score: 0
Accepted
time: 150ms
memory: 42644kb

input:

333/167

output:

999996 999995
1 2
1 994012
1 994013
1 994014
1 994015
1 994016
1 994017
1 994018
1 994019
1 994020
1 994021
1 994022
1 994023
1 994024
1 994025
1 994026
1 994027
1 994028
1 994029
1 994030
1 994031
1 994032
1 994033
1 994034
1 994035
1 994036
1 994037
1 994038
1 994039
1 994040
1 994041
1 994042
1 9...

result:

ok 

Test #30:

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

input:

3/1

output:

1000000 999999
1 2
1 666671
1 666672
1 666673
1 666674
1 666675
1 666676
1 666677
1 666678
1 666679
1 666680
1 666681
1 666682
1 666683
1 666684
1 666685
1 666686
1 666687
1 666688
1 666689
1 666690
1 666691
1 666692
1 666693
1 666694
1 666695
1 666696
1 666697
1 666698
1 666699
1 666700
1 666701
1 ...

result:

ok 

Test #31:

score: 0
Accepted
time: 141ms
memory: 47484kb

input:

301/100

output:

1000000 999999
1 2
1 670005
1 670006
1 670007
1 670008
1 670009
1 670010
1 670011
1 670012
1 670013
1 670014
1 670015
1 670016
1 670017
1 670018
1 670019
1 670020
1 670021
1 670022
1 670023
1 670024
1 670025
1 670026
1 670027
1 670028
1 670029
1 670030
1 670031
1 670032
1 670033
1 670034
1 670035
1 ...

result:

ok 

Test #32:

score: 0
Accepted
time: 156ms
memory: 42492kb

input:

299/100

output:

1000000 999999
1 2
1 995004
1 995005
1 995006
1 995007
1 995008
1 995009
1 995010
1 995011
1 995012
1 995013
1 995014
1 995015
1 995016
1 995017
1 995018
1 995019
1 995020
1 995021
1 995022
1 995023
1 995024
1 995025
1 995026
1 995027
1 995028
1 995029
1 995030
1 995031
1 995032
1 995033
1 995034
1 ...

result:

ok 

Test #33:

score: 0
Accepted
time: 144ms
memory: 46456kb

input:

1000/333

output:

999999 999998
1 2
1 667672
1 667673
1 667674
1 667675
1 667676
1 667677
1 667678
1 667679
1 667680
1 667681
1 667682
1 667683
1 667684
1 667685
1 667686
1 667687
1 667688
1 667689
1 667690
1 667691
1 667692
1 667693
1 667694
1 667695
1 667696
1 667697
1 667698
1 667699
1 667700
1 667701
1 667702
1 6...

result:

ok 

Test #34:

score: 0
Accepted
time: 218ms
memory: 42708kb

input:

500/167

output:

999996 999995
1 2
1 997006
1 997007
1 997008
1 997009
1 997010
1 997011
1 997012
1 997013
1 997014
1 997015
1 997016
1 997017
1 997018
1 997019
1 997020
1 997021
1 997022
1 997023
1 997024
1 997025
1 997026
1 997027
1 997028
1 997029
1 997030
1 997031
1 997032
1 997033
1 997034
1 997035
1 997036
1 9...

result:

ok 

Test #35:

score: 0
Accepted
time: 159ms
memory: 43284kb

input:

14/5

output:

1000000 999999
1 2
1 900004
1 900005
1 900006
1 900007
1 900008
1 900009
1 900010
1 900011
1 900012
1 900013
1 900014
1 900015
1 900016
1 900017
1 900018
1 900019
1 900020
1 900021
1 900022
1 900023
1 900024
1 900025
1 900026
1 900027
1 900028
1 900029
1 900030
1 900031
1 900032
1 900033
1 900034
1 ...

result:

ok 

Test #36:

score: 0
Accepted
time: 160ms
memory: 47272kb

input:

16/5

output:

1000000 999999
1 2
1 733338
1 733339
1 733340
1 733341
1 733342
1 733343
1 733344
1 733345
1 733346
1 733347
1 733348
1 733349
1 733350
1 733351
1 733352
1 733353
1 733354
1 733355
1 733356
1 733357
1 733358
1 733359
1 733360
1 733361
1 733362
1 733363
1 733364
1 733365
1 733366
1 733367
1 733368
1 ...

result:

ok 

Test #37:

score: 0
Accepted
time: 155ms
memory: 44276kb

input:

15/4

output:

1000000 999999
1 2
1 916671
1 916672
1 916673
1 916674
1 916675
1 916676
1 916677
1 916678
1 916679
1 916680
1 916681
1 916682
1 916683
1 916684
1 916685
1 916686
1 916687
1 916688
1 916689
1 916690
1 916691
1 916692
1 916693
1 916694
1 916695
1 916696
1 916697
1 916698
1 916699
1 916700
1 916701
1 ...

result:

ok 

Test #38:

score: 0
Accepted
time: 172ms
memory: 44040kb

input:

5/2

output:

1000000 999999
1 2
1 750004
1 750005
1 750006
1 750007
1 750008
1 750009
1 750010
1 750011
1 750012
1 750013
1 750014
1 750015
1 750016
1 750017
1 750018
1 750019
1 750020
1 750021
1 750022
1 750023
1 750024
1 750025
1 750026
1 750027
1 750028
1 750029
1 750030
1 750031
1 750032
1 750033
1 750034
1 ...

result:

ok 

Test #39:

score: 0
Accepted
time: 155ms
memory: 42764kb

input:

409/19

output:

999989 999988
1 2
1 977446
1 977447
1 977448
1 977449
1 977450
1 977451
1 977452
1 977453
1 977454
1 977455
1 977456
1 977457
1 977458
1 977459
1 977460
1 977461
1 977462
1 977463
1 977464
1 977465
1 977466
1 977467
1 977468
1 977469
1 977470
1 977471
1 977472
1 977473
1 977474
1 977475
1 977476
1 9...

result:

ok 

Test #40:

score: 0
Accepted
time: 144ms
memory: 42596kb

input:

818/39

output:

999999 999998
1 2
1 998730
1 998731
1 998732
1 998733
1 998734
1 998735
1 998736
1 998737
1 998738
1 998739
1 998740
1 998741
1 998742
1 998743
1 998744
1 998745
1 998746
1 998747
1 998748
1 998749
1 998750
1 998751
1 998752
1 998753
1 998754
1 998755
1 998756
1 998757
1 998758
1 998759
1 998760
1 9...

result:

ok 

Test #41:

score: 0
Accepted
time: 131ms
memory: 42496kb

input:

409/20

output:

1000000 999999
1 2
1 972513
1 972514
1 972515
1 972516
1 972517
1 972518
1 972519
1 972520
1 972521
1 972522
1 972523
1 972524
1 972525
1 972526
1 972527
1 972528
1 972529
1 972530
1 972531
1 972532
1 972533
1 972534
1 972535
1 972536
1 972537
1 972538
1 972539
1 972540
1 972541
1 972542
1 972543
1 ...

result:

ok 

Test #42:

score: 0
Accepted
time: 129ms
memory: 42620kb

input:

818/41

output:

999990 999989
1 2
1 997435
1 997436
1 997437
1 997438
1 997439
1 997440
1 997441
1 997442
1 997443
1 997444
1 997445
1 997446
1 997447
1 997448
1 997449
1 997450
1 997451
1 997452
1 997453
1 997454
1 997455
1 997456
1 997457
1 997458
1 997459
1 997460
1 997461
1 997462
1 997463
1 997464
1 997465
1 9...

result:

ok 

Test #43:

score: 0
Accepted
time: 151ms
memory: 42676kb

input:

819/38

output:

999970 999969
1 2
1 978681
1 978682
1 978683
1 978684
1 978685
1 978686
1 978687
1 978688
1 978689
1 978690
1 978691
1 978692
1 978693
1 978694
1 978695
1 978696
1 978697
1 978698
1 978699
1 978700
1 978701
1 978702
1 978703
1 978704
1 978705
1 978706
1 978707
1 978708
1 978709
1 978710
1 978711
1 9...

result:

ok 

Test #44:

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

input:

21/1

output:

1000000 999999
1 2
1 952394
1 952395
1 952396
1 952397
1 952398
1 952399
1 952400
1 952401
1 952402
1 952403
1 952404
1 952405
1 952406
1 952407
1 952408
1 952409
1 952410
1 952411
1 952412
1 952413
1 952414
1 952415
1 952416
1 952417
1 952418
1 952419
1 952420
1 952421
1 952422
1 952423
1 952424
1 ...

result:

ok 

Test #45:

score: 0
Accepted
time: 139ms
memory: 42716kb

input:

819/40

output:

1000000 999999
1 2
1 973763
1 973764
1 973765
1 973766
1 973767
1 973768
1 973769
1 973770
1 973771
1 973772
1 973773
1 973774
1 973775
1 973776
1 973777
1 973778
1 973779
1 973780
1 973781
1 973782
1 973783
1 973784
1 973785
1 973786
1 973787
1 973788
1 973789
1 973790
1 973791
1 973792
1 973793
1 ...

result:

ok 

Test #46:

score: 0
Accepted
time: 153ms
memory: 42600kb

input:

819/41

output:

999990 999989
1 2
1 998719
1 998720
1 998721
1 998722
1 998723
1 998724
1 998725
1 998726
1 998727
1 998728
1 998729
1 998730
1 998731
1 998732
1 998733
1 998734
1 998735
1 998736
1 998737
1 998738
1 998739
1 998740
1 998741
1 998742
1 998743
1 998744
1 998745
1 998746
1 998747
1 998748
1 998749
1 9...

result:

ok 

Test #47:

score: 0
Accepted
time: 143ms
memory: 42636kb

input:

410/19

output:

999989 999988
1 2
1 979953
1 979954
1 979955
1 979956
1 979957
1 979958
1 979959
1 979960
1 979961
1 979962
1 979963
1 979964
1 979965
1 979966
1 979967
1 979968
1 979969
1 979970
1 979971
1 979972
1 979973
1 979974
1 979975
1 979976
1 979977
1 979978
1 979979
1 979980
1 979981
1 979982
1 979983
1 9...

result:

ok 

Test #48:

score: 0
Accepted
time: 129ms
memory: 42644kb

input:

820/39

output:

999999 999998
1 2
1 953615
1 953616
1 953617
1 953618
1 953619
1 953620
1 953621
1 953622
1 953623
1 953624
1 953625
1 953626
1 953627
1 953628
1 953629
1 953630
1 953631
1 953632
1 953633
1 953634
1 953635
1 953636
1 953637
1 953638
1 953639
1 953640
1 953641
1 953642
1 953643
1 953644
1 953645
1 9...

result:

ok 

Test #49:

score: 0
Accepted
time: 146ms
memory: 42708kb

input:

41/2

output:

1000000 999999
1 2
1 975013
1 975014
1 975015
1 975016
1 975017
1 975018
1 975019
1 975020
1 975021
1 975022
1 975023
1 975024
1 975025
1 975026
1 975027
1 975028
1 975029
1 975030
1 975031
1 975032
1 975033
1 975034
1 975035
1 975036
1 975037
1 975038
1 975039
1 975040
1 975041
1 975042
1 975043
1 ...

result:

ok 

Test #50:

score: 0
Accepted
time: 136ms
memory: 42628kb

input:

20/1

output:

1000000 999999
1 2
1 950013
1 950014
1 950015
1 950016
1 950017
1 950018
1 950019
1 950020
1 950021
1 950022
1 950023
1 950024
1 950025
1 950026
1 950027
1 950028
1 950029
1 950030
1 950031
1 950032
1 950033
1 950034
1 950035
1 950036
1 950037
1 950038
1 950039
1 950040
1 950041
1 950042
1 950043
1 ...

result:

ok 

Test #51:

score: 0
Accepted
time: 143ms
memory: 42600kb

input:

821/38

output:

999970 999969
1 2
1 981187
1 981188
1 981189
1 981190
1 981191
1 981192
1 981193
1 981194
1 981195
1 981196
1 981197
1 981198
1 981199
1 981200
1 981201
1 981202
1 981203
1 981204
1 981205
1 981206
1 981207
1 981208
1 981209
1 981210
1 981211
1 981212
1 981213
1 981214
1 981215
1 981216
1 981217
1 9...

result:

ok 

Test #52:

score: 0
Accepted
time: 154ms
memory: 42732kb

input:

821/39

output:

999999 999998
1 2
1 954836
1 954837
1 954838
1 954839
1 954840
1 954841
1 954842
1 954843
1 954844
1 954845
1 954846
1 954847
1 954848
1 954849
1 954850
1 954851
1 954852
1 954853
1 954854
1 954855
1 954856
1 954857
1 954858
1 954859
1 954860
1 954861
1 954862
1 954863
1 954864
1 954865
1 954866
1 9...

result:

ok 

Test #53:

score: 0
Accepted
time: 157ms
memory: 42636kb

input:

821/40

output:

1000000 999999
1 2
1 976263
1 976264
1 976265
1 976266
1 976267
1 976268
1 976269
1 976270
1 976271
1 976272
1 976273
1 976274
1 976275
1 976276
1 976277
1 976278
1 976279
1 976280
1 976281
1 976282
1 976283
1 976284
1 976285
1 976286
1 976287
1 976288
1 976289
1 976290
1 976291
1 976292
1 976293
1 ...

result:

ok 

Test #54:

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

input:

821/41

output:

999990 999989
1 2
1 951223
1 951224
1 951225
1 951226
1 951227
1 951228
1 951229
1 951230
1 951231
1 951232
1 951233
1 951234
1 951235
1 951236
1 951237
1 951238
1 951239
1 951240
1 951241
1 951242
1 951243
1 951244
1 951245
1 951246
1 951247
1 951248
1 951249
1 951250
1 951251
1 951252
1 951253
1 9...

result:

ok 

Test #55:

score: 0
Accepted
time: 137ms
memory: 42660kb

input:

512/1

output:

1000000 999999
1 2
1 998306
1 998307
1 998308
1 998309
1 998310
1 998311
1 998312
1 998313
1 998314
1 998315
1 998316
1 998317
1 998318
1 998319
1 998320
1 998321
1 998322
1 998323
1 998324
1 998325
1 998326
1 998327
1 998328
1 998329
1 998330
1 998331
1 998332
1 998333
1 998334
1 998335
1 998336
1 ...

result:

ok 

Test #56:

score: 0
Accepted
time: 155ms
memory: 42752kb

input:

729/1

output:

1000000 999999
1 2
1 998996
1 998997
1 998998
1 998999
1 999000
1 999001
1 999002
1 999003
1 999004
1 999005
1 999006
1 999007
1 999008
1 999009
1 999010
1 999011
1 999012
1 999013
1 999014
1 999015
1 999016
1 999017
1 999018
1 999019
1 999020
1 999021
1 999022
1 999023
1 999024
1 999025
1 999026
1 ...

result:

ok 

Test #57:

score: 0
Accepted
time: 163ms
memory: 42620kb

input:

625/1

output:

1000000 999999
1 2
1 998716
1 998717
1 998718
1 998719
1 998720
1 998721
1 998722
1 998723
1 998724
1 998725
1 998726
1 998727
1 998728
1 998729
1 998730
1 998731
1 998732
1 998733
1 998734
1 998735
1 998736
1 998737
1 998738
1 998739
1 998740
1 998741
1 998742
1 998743
1 998744
1 998745
1 998746
1 ...

result:

ok 

Test #58:

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

input:

127/626

output:

impossible

result:

ok 

Test #59:

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

input:

429/838

output:

impossible

result:

ok 

Test #60:

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

input:

563/710

output:

impossible

result:

ok 

Test #61:

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

input:

40/207

output:

impossible

result:

ok 

Test #62:

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

input:

145/298

output:

impossible

result:

ok 

Test #63:

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

input:

109/286

output:

impossible

result:

ok 

Test #64:

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

input:

219/305

output:

impossible

result:

ok 

Test #65:

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

input:

11/258

output:

impossible

result:

ok 

Test #66:

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

input:

59/105

output:

impossible

result:

ok 

Test #67:

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

input:

59/660

output:

impossible

result:

ok 

Test #68:

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

input:

209/210

output:

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

result:

ok 

Test #69:

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

input:

484/485

output:

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

result:

ok 

Test #70:

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

input:

178/179

output:

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

result:

ok 

Test #71:

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

input:

947/948

output:

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

result:

ok 

Test #72:

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

input:

635/636

output:

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

result:

ok 

Test #73:

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

input:

11/12

output:

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

result:

ok 

Test #74:

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

input:

451/452

output:

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

result:

ok 

Test #75:

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

input:

144/145

output:

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

result:

ok 

Test #76:

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

input:

478/479

output:

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

result:

ok 

Test #77:

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

input:

603/604

output:

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

result:

ok 

Test #78:

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

input:

34/897

output:

impossible

result:

ok 

Test #79:

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

input:

794/101

output:

999900 999899
1 2
1 980107
1 980108
1 980109
1 980110
1 980111
1 980112
1 980113
1 980114
1 980115
1 980116
1 980117
1 980118
1 980119
1 980120
1 980121
1 980122
1 980123
1 980124
1 980125
1 980126
1 980127
1 980128
1 980129
1 980130
1 980131
1 980132
1 980133
1 980134
1 980135
1 980136
1 980137
1 9...

result:

ok 

Test #80:

score: 0
Accepted
time: 177ms
memory: 44112kb

input:

303/169

output:

999973 999972
1 2
1 792882
1 792883
1 792884
1 792885
1 792886
1 792887
1 792888
1 792889
1 792890
1 792891
1 792892
1 792893
1 792894
1 792895
1 792896
1 792897
1 792898
1 792899
1 792900
1 792901
1 792902
1 792903
1 792904
1 792905
1 792906
1 792907
1 792908
1 792909
1 792910
1 792911
1 792912
1 7...

result:

ok 

Test #81:

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

input:

539/734

output:

impossible

result:

ok 

Test #82:

score: 0
Accepted
time: 197ms
memory: 44184kb

input:

725/603

output:

999774 999773
1 2
1 202280
1 202281
1 202282
1 202283
1 202284
1 202285
1 202286
1 202287
1 202288
1 202289
1 202290
1 202291
1 202292
1 202293
1 202294
1 202295
1 202296
1 202297
1 202298
1 202299
1 202300
1 202301
1 202302
1 202303
1 202304
1 202305
1 202306
1 202307
1 202308
1 202309
1 202310
1 2...

result:

ok 

Test #83:

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

input:

83/393

output:

impossible

result:

ok 

Test #84:

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

input:

713/855

output:

impossible

result:

ok 

Test #85:

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

input:

349/753

output:

impossible

result:

ok 

Test #86:

score: 0
Accepted
time: 204ms
memory: 42524kb

input:

505/87

output:

999978 999977
1 2
1 960904
1 960905
1 960906
1 960907
1 960908
1 960909
1 960910
1 960911
1 960912
1 960913
1 960914
1 960915
1 960916
1 960917
1 960918
1 960919
1 960920
1 960921
1 960922
1 960923
1 960924
1 960925
1 960926
1 960927
1 960928
1 960929
1 960930
1 960931
1 960932
1 960933
1 960934
1 9...

result:

ok 

Test #87:

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

input:

631/690

output:

impossible

result:

ok 

Test #88:

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

input:

357/104

output:

999960 999959
1 2
1 810870
1 810871
1 810872
1 810873
1 810874
1 810875
1 810876
1 810877
1 810878
1 810879
1 810880
1 810881
1 810882
1 810883
1 810884
1 810885
1 810886
1 810887
1 810888
1 810889
1 810890
1 810891
1 810892
1 810893
1 810894
1 810895
1 810896
1 810897
1 810898
1 810899
1 810900
1 8...

result:

ok 

Test #89:

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

input:

176/849

output:

impossible

result:

ok 

Test #90:

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

input:

616/757

output:

impossible

result:

ok 

Test #91:

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

input:

138/953

output:

impossible

result:

ok 

Test #92:

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

input:

152/389

output:

impossible

result:

ok 

Test #93:

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

input:

31/425

output:

impossible

result:

ok 

Test #94:

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

input:

91/550

output:

impossible

result:

ok 

Test #95:

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

input:

531/956

output:

impossible

result:

ok 

Test #96:

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

input:

283/737

output:

impossible

result:

ok 

Test #97:

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

input:

490/3

output:

999999 999998
1 2
1 995994
1 995995
1 995996
1 995997
1 995998
1 995999
1 996000
1 996001
1 996002
1 996003
1 996004
1 996005
1 996006
1 996007
1 996008
1 996009
1 996010
1 996011
1 996012
1 996013
1 996014
1 996015
1 996016
1 996017
1 996018
1 996019
1 996020
1 996021
1 996022
1 996023
1 996024
1 9...

result:

ok 

Test #98:

score: 0
Accepted
time: 157ms
memory: 42612kb

input:

473/1

output:

1000000 999999
1 2
1 998125
1 998126
1 998127
1 998128
1 998129
1 998130
1 998131
1 998132
1 998133
1 998134
1 998135
1 998136
1 998137
1 998138
1 998139
1 998140
1 998141
1 998142
1 998143
1 998144
1 998145
1 998146
1 998147
1 998148
1 998149
1 998150
1 998151
1 998152
1 998153
1 998154
1 998155
1 ...

result:

ok 

Test #99:

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

input:

980/1

output:

1000000 999999
1 2
1 999473
1 999474
1 999475
1 999476
1 999477
1 999478
1 999479
1 999480
1 999481
1 999482
1 999483
1 999484
1 999485
1 999486
1 999487
1 999488
1 999489
1 999490
1 999491
1 999492
1 999493
1 999494
1 999495
1 999496
1 999497
1 999498
1 999499
1 999500
1 999501
1 999502
1 999503
1 ...

result:

ok 

Test #100:

score: 0
Accepted
time: 231ms
memory: 42652kb

input:

926/5

output:

1000000 999999
1 2
1 995771
1 995772
1 995773
1 995774
1 995775
1 995776
1 995777
1 995778
1 995779
1 995780
1 995781
1 995782
1 995783
1 995784
1 995785
1 995786
1 995787
1 995788
1 995789
1 995790
1 995791
1 995792
1 995793
1 995794
1 995795
1 995796
1 995797
1 995798
1 995799
1 995800
1 995801
1 ...

result:

ok 

Test #101:

score: 0
Accepted
time: 197ms
memory: 42764kb

input:

457/1

output:

1000000 999999
1 2
1 998043
1 998044
1 998045
1 998046
1 998047
1 998048
1 998049
1 998050
1 998051
1 998052
1 998053
1 998054
1 998055
1 998056
1 998057
1 998058
1 998059
1 998060
1 998061
1 998062
1 998063
1 998064
1 998065
1 998066
1 998067
1 998068
1 998069
1 998070
1 998071
1 998072
1 998073
1 ...

result:

ok 

Test #102:

score: 0
Accepted
time: 204ms
memory: 42612kb

input:

909/2

output:

1000000 999999
1 2
1 999129
1 999130
1 999131
1 999132
1 999133
1 999134
1 999135
1 999136
1 999137
1 999138
1 999139
1 999140
1 999141
1 999142
1 999143
1 999144
1 999145
1 999146
1 999147
1 999148
1 999149
1 999150
1 999151
1 999152
1 999153
1 999154
1 999155
1 999156
1 999157
1 999158
1 999159
1 ...

result:

ok 

Test #103:

score: 0
Accepted
time: 143ms
memory: 42640kb

input:

156/1

output:

1000000 999999
1 2
1 993671
1 993672
1 993673
1 993674
1 993675
1 993676
1 993677
1 993678
1 993679
1 993680
1 993681
1 993682
1 993683
1 993684
1 993685
1 993686
1 993687
1 993688
1 993689
1 993690
1 993691
1 993692
1 993693
1 993694
1 993695
1 993696
1 993697
1 993698
1 993699
1 993700
1 993701
1 ...

result:

ok 

Test #104:

score: 0
Accepted
time: 229ms
memory: 42648kb

input:

486/1

output:

1000000 999999
1 2
1 998188
1 998189
1 998190
1 998191
1 998192
1 998193
1 998194
1 998195
1 998196
1 998197
1 998198
1 998199
1 998200
1 998201
1 998202
1 998203
1 998204
1 998205
1 998206
1 998207
1 998208
1 998209
1 998210
1 998211
1 998212
1 998213
1 998214
1 998215
1 998216
1 998217
1 998218
1 ...

result:

ok 

Test #105:

score: 0
Accepted
time: 172ms
memory: 42632kb

input:

249/2

output:

1000000 999999
1 2
1 996033
1 996034
1 996035
1 996036
1 996037
1 996038
1 996039
1 996040
1 996041
1 996042
1 996043
1 996044
1 996045
1 996046
1 996047
1 996048
1 996049
1 996050
1 996051
1 996052
1 996053
1 996054
1 996055
1 996056
1 996057
1 996058
1 996059
1 996060
1 996061
1 996062
1 996063
1 ...

result:

ok 

Test #106:

score: 0
Accepted
time: 222ms
memory: 42652kb

input:

948/1

output:

1000000 999999
1 2
1 999422
1 999423
1 999424
1 999425
1 999426
1 999427
1 999428
1 999429
1 999430
1 999431
1 999432
1 999433
1 999434
1 999435
1 999436
1 999437
1 999438
1 999439
1 999440
1 999441
1 999442
1 999443
1 999444
1 999445
1 999446
1 999447
1 999448
1 999449
1 999450
1 999451
1 999452
1 ...

result:

ok