QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56916#4823. No!KING_UT#AC ✓401ms26776kbC++202.1kb2022-10-21 21:39:562022-10-21 21:39:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-21 21:39:56]
  • 评测
  • 测评结果:AC
  • 用时:401ms
  • 内存:26776kb
  • [2022-10-21 21:39:56]
  • 提交

answer

#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)

#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)

#define bg begin()
#define ed end()
#define pb push_back
#define eb emplace_back
#define all(x) x.bg,x.ed
#define si(x) int(x.size())

template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;

template<class t,class u>bool chmin(t&a,u b){
	if(a>b){a=b;return true;}
	else return false;
}
template<class t,class u>bool chmax(t&a,u b){
	if(a<b){a=b;return true;}
	else return false;
}

const ll inf=LLONG_MAX/3;

#define a first
#define b second
using pi=pair<int,int>;

struct Line{
	mutable ll a,b,p;
	bool operator<(const Line&o)const{return a>o.a;}
	bool operator<(ll x)const{return p<x;}
};
struct LineContainer:multiset<Line,less<>>{
	ll div(ll a,ll b){return a/b-((a^b)<0&&a%b);}
	bool isect(iterator x, iterator y){
		if(y==end()){x->p=inf;return false;}
		if(x->a==y->a) x->p=x->b<y->b?inf:-inf;
		else x->p=div(x->a*y->b-y->a*x->b,x->a-y->a);
		return x->p>=y->p;
	}
	void add(ll a,ll b){
		auto z=insert({a,b,0}),y=z++,x=y;
		while(isect(y,z))z=erase(z);
		if(x!=bg&&isect(--x,y))isect(x,y=erase(y));
		while((y=x)!=bg&&(--x)->p>=y->p)isect(x,erase(y));
	}
	pi query(ll x){
		if(empty())return pi(0,1);
		auto l=lower_bound(x);
		return pi(l->b-x,l->a);
	}
};

bool fless(pi a,pi b){
	return a.a*b.b<a.b*b.a;
}

void slv(){
	int n,q;cin>>n>>q;
	vc<pi> hs(n+q);
	rep(i,n){
		int h,s;cin>>h>>s;
		hs[i]=pi(h,s);
	}
	rep(i,q){
		int h;cin>>h;
		hs[n+i]=pi(h,i-q);
	}
	sort(all(hs),greater<pi>());
	vc<pi> ans(q);
	pi pre(0,1);
	LineContainer lc;
	for(auto [h,s]:hs){
		pi g=lc.query(h);
		//cerr<<h<<" "<<s<<" "<<g.a<<" "<<g.b<<endl;
		if(fless(g,pre))g=pre;
		pre=g;
		if(s<0){
			ans[s+q]=g;
		}else{
			lc.add(s,h);
		}
	}
	for(auto [a,b]:ans){
		int g=gcd(a,b);
		cout<<b/g<<"/"<<a/g<<"\n";
	}
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	slv();
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3732kb

input:

4 5
3 5
4 3
2 5
6 3
5
2
3
7
2

output:

3/1
3/2
3/2
1/0
3/2

result:

ok 5 lines

Test #2:

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

input:

5 6
10 6
3 7
6 15
7 6
8 15
5
3
9
7
7
9

output:

3/1
3/1
6/1
3/1
3/1
6/1

result:

ok 6 lines

Test #3:

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

input:

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

output:

1/2
1/1
1/2
1/2
1/1
1/2

result:

ok 6 lines

Test #4:

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

input:

1 1
8 9
8

output:

1/0

result:

ok single line: '1/0'

Test #5:

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

input:

1 1
3 1
6

output:

1/0

result:

ok single line: '1/0'

Test #6:

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

input:

7 9
44 51
91 191
1 6
67 3
94 191
87 58
59 10
54
80
37
63
27
9
28
85
44

output:

191/37
191/11
191/47
191/28
3/1
191/82
51/16
191/6
191/47

result:

ok 9 lines

Test #7:

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

input:

7 9
56 11172
5 9
79 2674
31 3263
38 4607
36 5
82 1814
41
24
52
22
30
92
74
48
67

output:

2674/23
2674/23
2674/23
2674/23
2674/23
1/0
2674/5
2674/23
1337/6

result:

ok 9 lines

Test #8:

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

input:

10 10
1465292 914022939
2258868 101102159
265616 463724951
192430 946841485
2630886 977373286
2016747 443115809
3552227 644307708
3999290 745677354
424627 330625475
2046399 18914556
2263191
3680274
839068
1905778
257097
2496977
3578950
1400222
3781916
2618199

output:

644307708/921341
372838677/159508
644307708/921341
644307708/921341
644307708/921341
644307708/921341
372838677/210170
644307708/921341
124279559/36229
644307708/921341

result:

ok 10 lines

Test #9:

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

input:

10 10
3074356 448776337
2241681 10
3815624 6
2599227 5
2198509 29372688
1850943 1
3863175 588270797
2115696 233002550
2979224 10
3126325 1125164
699495
709378
709923
2237353
2178964
3523938
567329
540819
83920
2664198

output:

448776337/2374861
448776337/2364978
448776337/2364433
448776337/837003
448776337/875847
588270797/339237
448776337/2507027
448776337/2533537
588270797/3779255
588270797/788819

result:

ok 10 lines

Test #10:

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

input:

100 100
1701033 665952298
3762088 427918742
942820 11367751
2265136 280409781
3945575 817499835
1580704 296571569
3021728 261050042
2200976 533446489
2930927 46397514
3128777 340713103
2466856 779166152
280779 157964999
851989 377722211
1094216 226133388
227570 985055136
3969447 224992764
1453039 24...

output:

978266048/116645
445006427/124838
445006427/124838
445006427/124838
445006427/124838
445006427/124838
978266048/75311
445006427/124838
445006427/124838
439022287/181846
445006427/124838
978266048/226445
445006427/124838
445006427/124838
439022287/181846
445006427/124838
445006427/124838
445006427/12...

result:

ok 100 lines

Test #11:

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

input:

100 100
1538647 73653174
2121416 1188969
221052 112867
936487 1
2704755 32628191
3082143 5830772
1029494 33637913
187408 42136535
3600232 8
1964960 1931386
1140388 6
906191 22686835
2481683 38171667
2430939 7
281105 9
2058153 17144758
3620302 1
3455501 5508492
3756050 9
2396483 1
229129 2600234
2428...

output:

36584718/812549
36584718/812549
36584718/812549
1/0
36584718/812549
12194906/227019
36584718/812549
36584718/812549
36584718/812549
36584718/812549
36584718/812549
36584718/812549
36584718/812549
36584718/524615
36584718/812549
18292359/203452
1/0
36584718/812549
36584718/812549
36584718/812549
3658...

result:

ok 100 lines

Test #12:

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

input:

100 200
275140 342431416
1865891 306525899
1203517 452361556
757388 251060990
2335380 463964179
636396 588495459
3247740 824915306
1193607 435974321
2381803 841724020
64423 72946820
1814942 823160175
1012890 153794525
1761683 775531580
1341743 637259935
2623116 580089059
1696061 88113427
1194131 753...

output:

9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9466847/9758
9...

result:

ok 200 lines

Test #13:

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

input:

100 200
3635011 3
3770821 1137733
1116566 14933399
1471180 155855
3878735 63812925
3501514 1
2505194 24973663
849534 1061529
3554541 2756075
325393 8
730583 8841032
2983491 8
986748 41206661
3746939 8
1073913 4
370470 2602712
1412350 218641
834227 11671458
3355540 2748151
3487604 2
3713788 8145488
3...

output:

9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
1/0
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
9/7015
1/...

result:

ok 200 lines

Test #14:

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

input:

100 300
1106143 164134727
1002398 39908863
240023 893355362
3249640 221712200
916673 965204331
1435191 880419349
1730648 388780570
3153535 188759049
3767272 637050526
3967366 805180538
3228435 867154197
1936489 294848243
2671376 173340949
365079 903162290
1018663 439964198
3422676 506523690
3902518 ...

output:

870841585/496358
870841585/496358
870841585/496358
870841585/496358
870841585/496358
431492378/83185
870841585/413294
870841585/201357
870841585/496358
870841585/496358
870841585/496358
760021439/88748
388656931/20078
17659/1
870841585/496358
870841585/496358
870841585/496358
805180538/6123
87084158...

result:

ok 300 lines

Test #15:

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

input:

100 300
1518060 7
1715028 1632604
1327477 8600843
1199061 3005795
1779115 3110358
2874022 7
3924374 3
1774923 2
373143 4
843644 435119
2583241 3609188
2837307 5
293807 7
1840638 5074059
24442 5
2483483 6
1357921 15567289
3338418 8716843
950994 3
268456 8
2781367 8866806
3674062 6
3057495 7
171164 11...

output:

506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
506005/37118
5...

result:

ok 300 lines

Test #16:

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

input:

500 1000
1514048 834490429
3897049 711846341
2815482 960472060
3318809 661879828
1873276 106577491
1146074 664291094
2288706 668405272
555323 662595572
2407980 312708072
1059326 8852443
1573375 992154272
2859273 812910204
1456098 81207781
1192166 321337484
3483363 107982493
1425219 370141253
902512 ...

output:

664291094/83945
932232349/91582
664291094/83945
244018573/13900
664291094/83945
664291094/83945
932232349/91582
932232349/91582
448593191/29679
448593191/29679
664291094/83945
664291094/83945
932232349/91582
130744614/12625
130744614/12625
664291094/83945
932232349/91582
448593191/29679
664291094/83...

result:

ok 1000 lines

Test #17:

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

input:

500 1000
1195758 382940
1805321 3524271
1895595 2196225
3330916 3
1123557 4
2411351 736512
1027240 638829
3368921 8
1543366 7
1281934 9
384864 1035701
2070181 6998423
1220356 809911
3022613 5
2247262 3
234345 3
2880475 9
3305242 6
2783557 6
2991306 6
2500197 6
3022848 521766
1895778 81802
3721335 13...

output:

6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22159
6/22...

result:

ok 1000 lines

Test #18:

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

input:

500 2000
3073792 508750869
723483 649646431
263399 32699279
2790559 650160255
946028 274975509
1293852 811354843
354577 183512782
2865531 389942133
2832841 25802293
1359196 887342563
1859453 904897690
1835409 657219791
2050699 197042594
1422241 592204918
3240769 538602435
1786438 276324650
2436966 4...

output:

462952688/29061
333641490/20221
17906731/1767
17906731/1767
17906731/1767
17906731/1767
17906731/1767
17906731/1767
17906731/1767
493961863/54002
462952688/29061
17906731/1767
462952688/29061
462952688/29061
17906731/1767
333641490/20221
17906731/1767
17906731/1767
17906731/1767
17906731/1767
462952...

result:

ok 2000 lines

Test #19:

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

input:

500 2000
3891327 1578325
1651563 865109
3494059 2
3246630 356352
3884524 234264
2169847 4
434934 648663
3534311 1435688
2145370 2
1777073 473538
2797608 3
2260916 4781335
2280390 544578
2812323 2671607
593957 2
2397999 1725920
3059398 6
2499427 2203927
1650310 9
838485 2747321
2220819 51012
1150603 ...

output:

189763/9854
28309346/1528185
189763/9854
189763/9854
189763/9854
189763/9854
189763/9854
189763/9854
189763/9854
189763/9854
189763/9854
189763/9854
189763/9854
189763/9854
28309346/1528185
28309346/1528185
28309346/1528185
28309346/1528185
189763/9854
189763/9854
189763/9854
189763/9854
28309346/15...

result:

ok 2000 lines

Test #20:

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

input:

500 5000
1496127 236564892
3721694 317822510
1831342 138801736
3790130 790351806
2547263 190234971
512993 102802984
945022 583611117
2637372 602107896
2364320 605276444
1226103 813261308
1166072 647646857
3665706 160022472
353411 984738520
2112465 434933299
2321501 570139956
3383885 105454040
110573...

output:

607879103/52248
607879103/52248
607879103/52248
607879103/52248
607879103/52248
621533502/28105
607879103/52248
607879103/52248
607879103/52248
607879103/52248
607879103/52248
607879103/52248
607879103/52248
607879103/52248
607879103/52248
607879103/52248
607879103/52248
607879103/52248
607879103/52...

result:

ok 5000 lines

Test #21:

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

input:

500 5000
1849556 83939
1218116 1
3350884 1044818
1961507 1
2714066 3
3007532 2
3963390 1515757
3757546 43752
2343846 101891
925636 9
1085407 6
2234375 10
1920409 318484
815430 1
1485703 9
3415291 7
2928838 917164
1688159 205278
1876614 8
3629998 332557
672462 237392
2445402 4
1608368 3
2814785 6
155...

output:

6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715
6/3715...

result:

ok 5000 lines

Test #22:

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

input:

5000 1000
542122 784561924
2267164 369110352
2042600 423502066
1382933 912561458
1431510 193469070
578263 477011695
525530 827140892
334466 641845619
2768751 182264789
3926154 489191138
2623649 464643686
112693 582965010
365715 429844334
3210529 142897166
3995897 101067523
3003835 123321492
3237022 ...

output:

485685226/2727
60018953/572
564697373/9411
564697373/9411
564697373/9411
564697373/9411
515159587/5309
515159587/5309
564697373/9411
564697373/9411
120560639/866
515159587/5309
564697373/9411
564697373/9411
564697373/9411
564697373/9411
323566051/1460
60018953/572
515159587/5309
564697373/9411
51515...

result:

ok 1000 lines

Test #23:

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

input:

5000 1000
2910850 3
1985728 375397
142613 700070
3406565 2832480
1808068 7
3783822 2
2804284 2
1403892 4
1607141 6
3756962 4
620975 7
606094 10
129796 206796
1708971 57114
1826455 1
827065 385316
2468939 335392
1028961 44618
2056333 5
711150 476271
1961097 4
3872456 7
2988349 2317174
1085669 627186
...

output:

8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727
8/1727...

result:

ok 1000 lines

Test #24:

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

input:

5000 2500
2584305 717082019
902212 973825263
3056021 290632903
605545 194289421
836264 8773127
1042323 228919085
2819573 311317828
958104 582345131
3803386 17215732
3357761 319298229
1135979 11941536
1066953 432029393
93101 534725991
3262562 473916245
249948 446604921
3867312 421042414
1220037 51469...

output:

89705015/971
301478284/4177
417156871/2709
301478284/4177
301478284/4177
89705015/971
301478284/4177
89705015/971
301478284/4177
301478284/4177
417156871/2709
89705015/971
301478284/4177
301478284/4177
89705015/971
301478284/4177
301478284/4177
301478284/4177
301478284/4177
301478284/4177
301478284/...

result:

ok 2500 lines

Test #25:

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

input:

5000 2500
2113777 5
1736121 144270
2659470 10
660071 19432
2946023 9
1865510 10
2182953 594559
3188725 4
211259 10
1343174 121237
2290432 3
557675 1217279
2348422 1
3876049 2
1417268 7
1095996 4
3310967 5
923158 632496
1805669 10
1879432 25858
2544350 10
221698 76030
3897295 8
173114 1156687
2609231...

output:

1009153/13096
815261/16173
815261/16173
815261/16173
815261/16173
1009153/13096
1009153/13096
1009153/13096
815261/16173
815261/16173
815261/16173
815261/16173
815261/16173
815261/16173
815261/16173
815261/16173
1009153/13096
815261/16173
815261/16173
815261/16173
815261/16173
815261/16173
815261/16...

result:

ok 2500 lines

Test #26:

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

input:

5000 5000
524201 891669090
2091809 680119225
1058460 601831742
2886958 746066140
2105497 982159255
977886 60747777
3181847 37314034
2416516 436133751
1692386 329608970
1836035 588567299
2216347 974912078
919127 930077278
295731 68533857
322316 256492981
1609844 563224986
2186693 563666983
3631736 67...

output:

771055493/13778
820056187/10951
771055493/13778
820056187/10951
820056187/10951
820056187/10951
415119405/3023
820056187/10951
820056187/10951
820056187/10951
771055493/13778
820056187/10951
820056187/10951
820056187/10951
771055493/13778
820056187/10951
820056187/10951
771055493/13778
820056187/109...

result:

ok 5000 lines

Test #27:

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

input:

5000 5000
1724473 4881
3725384 1027507
3777018 8
1364148 53547
2448055 155895
3192466 7
1909202 8
3103542 21719
689263 216986
2727584 6
991257 8
3741719 7
2160966 5
2909808 238791
674558 406223
2266646 4
733318 32860
640087 10
2318305 771581
2621258 262547
2901235 4678
224504 234445
174792 8
1181344...

output:

126117/3572
126117/3572
126117/3572
635786/11063
126117/3572
126117/3572
635786/11063
126117/3572
126117/3572
126117/3572
635786/11063
126117/3572
34360/217
126117/3572
635786/11063
126117/3572
126117/3572
309240/1951
126117/3572
126117/3572
126117/3572
126117/3572
126117/3572
126117/3572
126117/357...

result:

ok 5000 lines

Test #28:

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

input:

10000 2000
67080 457909482
755989 755361604
3607069 114713504
1830329 196836201
2303770 420880590
279320 697035189
484490 333176816
2917592 557830830
2959053 417705779
3975601 79931595
210838 557117435
1069554 306951418
3690606 657250655
3466236 460808475
1698607 525837992
1579718 157305474
1713033 ...

output:

84908692/675
84908692/675
303868972/2065
84908692/675
84908692/675
303868972/2065
84908692/675
84908692/675
84908692/675
84908692/675
303868972/2065
303868972/2065
84908692/675
303868972/2065
84908692/675
84908692/675
84908692/675
84908692/675
84908692/675
84908692/675
84908692/675
84908692/675
8490...

result:

ok 2000 lines

Test #29:

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

input:

10000 2000
1171998 42901
3115318 4
3641805 7
90613 1
3930174 1653596
1579652 1
2056050 675377
3130088 88668
1145584 3
851758 720640
1317831 8
764134 145628
3534712 10
166672 886670
2271463 10
2129563 4
2050505 726735
1299825 7724
265759 6
3033329 23649
75906 6292
3618456 4
2203474 10
2065258 117635
...

output:

5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
1/0
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/112
5/...

result:

ok 2000 lines

Test #30:

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

input:

10000 4000
929671 806430362
1184664 630961785
3727095 703878342
582342 613588542
640764 757676626
1607580 991162686
3200553 218167642
379224 12523952
2065671 843894222
3351150 982136028
2007187 237380080
1989123 700603296
2622910 888920280
2893682 297510638
2246124 977012467
559051 229994571
781942 ...

output:

838153406/5017
916458779/5501
916458779/5501
916458779/5501
916458779/5501
838153406/5017
916458779/5501
838153406/5017
620216220/3167
916458779/5501
916458779/5501
838153406/5017
916458779/5501
916458779/5501
916458779/5501
916458779/5501
916458779/5501
916458779/5501
916458779/5501
916458779/5501
...

result:

ok 4000 lines

Test #31:

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

input:

10000 4000
2742200 8
3756509 9
1943947 9
3089152 921724
453649 10
780036 9
874224 4
1528917 5986
1249821 703517
1140581 2
1031645 1252928
1113492 159044
1405961 96368
3966605 143057
2890261 988872
1911881 1070449
590067 8536
997992 7
1147646 3576
404842 317171
1072452 1531500
2041573 459044
1360425 ...

output:

487887/8728
487887/8728
487887/8728
487887/8728
487887/8728
237519/4768
822033/19447
487887/8728
822033/19447
822033/19447
487887/8728
487887/8728
487887/8728
487887/8728
487887/8728
237519/4768
487887/8728
822033/19447
487887/8728
822033/19447
237519/4768
487887/8728
487887/8728
487887/8728
822033/...

result:

ok 4000 lines

Test #32:

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

input:

10000 6000
49158 714759753
580634 66370477
2622930 147818988
3334354 885116691
2977757 799505366
3646239 135547079
3140807 248382661
999641 57151666
139585 710274152
1885482 884340460
2770832 772418532
1875987 654063686
2587918 855748690
386536 134212801
1569449 133219646
571088 892618261
883555 867...

output:

420694583/2516
420694583/2516
440979593/2428
440979593/2428
420694583/2516
420694583/2516
369508871/1917
420694583/2516
420694583/2516
297664494/1631
297664494/1631
420694583/2516
420694583/2516
420694583/2516
297664494/1631
420694583/2516
420694583/2516
420694583/2516
420694583/2516
420694583/2516
...

result:

ok 6000 lines

Test #33:

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

input:

10000 6000
707995 8
1327234 26635
2511209 2516
3842859 324101
632736 786926
514793 7
1841695 53437
3065575 130044
1823489 98511
1646021 2
3418418 4
1612537 7
390510 649323
276874 2
40882 3
1714219 391783
93219 6
1817132 15320
1179400 880507
2175420 10
2234901 6
3571942 7
1478286 10
1236431 2024751
1...

output:

5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
5/679
...

result:

ok 6000 lines

Test #34:

score: 0
Accepted
time: 41ms
memory: 5624kb

input:

50000 50000
3090774 475118529
1294139 683936542
111089 80402503
137001 62424012
3460619 647352312
41649 307438370
2802904 408592194
1338580 703888583
436676 880652454
3363847 95453622
1711598 768624954
2544818 14444735
2994856 891342632
832946 306714887
1085433 905999917
2254040 793630851
2154267 39...

output:

79258935/122
956009339/1678
79258935/122
79258935/122
79258935/122
79258935/122
79258935/122
79258935/122
79258935/122
79258935/122
79258935/122
956009339/1678
956009339/1678
79258935/122
316731035/363
956009339/1678
79258935/122
316731035/363
79258935/122
79258935/122
79258935/122
79258935/122
9560...

result:

ok 50000 lines

Test #35:

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

input:

50000 50000
2091680 5
3965391 1
760505 4
2186065 129672
2867044 4
1922238 16095
3938180 2
439057 1
1055014 7
744028 47764
2592777 6
3980754 78467
3800633 26071
3690882 8
2029662 1
3641000 50524
3830380 29815
1842331 25763
921354 42989
2614493 1
1042124 249613
898667 3
809896 6
1386992 36273
2082975 ...

output:

1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
1/79
...

result:

ok 50000 lines

Test #36:

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

input:

500000 100000
2880224 685524965
3642785 561386795
2597095 529364615
1003199 892893149
153083 124406920
3395655 409779017
720510 394993019
989241 772927883
1924777 433585320
1616038 173731254
2114311 125423495
3786548 993087052
1644280 724314185
2165659 484435911
1736495 522047567
3983658 383925524
3...

output:

399215049/74
977826376/205
977826376/205
977826376/205
399215049/74
399215049/74
978609365/196
977826376/205
132725716/15
977826376/205
977826376/205
977826376/205
977826376/205
977826376/205
978609365/196
399215049/74
977826376/205
977826376/205
977826376/205
977826376/205
977826376/205
978609365/1...

result:

ok 100000 lines

Test #37:

score: 0
Accepted
time: 212ms
memory: 14252kb

input:

500000 100000
1054508 1638
1797986 4
1541527 3385
3401110 9
2188507 15474
3085937 1390
3847875 1
1216788 24405
2887572 3
2807495 4
3176418 3757
2733830 1552
3368649 8
2981665 16834
1718948 9
2597619 2839
813869 9
2219433 1550
2512901 5
2750612 5
2642910 2834
3240157 2
2797513 8
3205007 10487
2075483...

output:

7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
7/12
...

result:

ok 100000 lines

Test #38:

score: 0
Accepted
time: 261ms
memory: 17216kb

input:

500000 200000
680314 742052004
3870004 735956333
3069010 606812532
2433921 47140707
249535 418446969
2503165 884702602
67071 911834699
2083463 498013900
1639089 159234372
1135264 66031124
3456602 449709574
2588656 360063189
511714 966651889
3752896 48857474
952596 909804973
2957951 377510935
3677985...

output:

172436891/28
484912372/95
727368976/153
304640723/59
727368976/153
635140005/131
75969859/12
304640723/59
304640723/59
304640723/59
727368976/153
484912372/95
727368976/153
635140005/131
304640723/59
484912372/95
484912372/95
874347211/114
484912372/95
635140005/131
484912372/95
635140005/131
988908...

result:

ok 200000 lines

Test #39:

score: 0
Accepted
time: 235ms
memory: 17156kb

input:

500000 200000
1619537 6851
1813610 8
306700 4879
1359955 5
1301151 2
1333061 8
1715574 8342
113823 2030
1018970 1058
2572895 1463
3597312 3694
3352458 14379
2332255 1172
3363654 2
3497920 10
3341450 5097
2646654 7070
3864730 1885
1568103 2557
514073 2100
3837649 10
2247635 8
1156799 4
1169553 2641
1...

output:

5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
5/2
...

result:

ok 200000 lines

Test #40:

score: 0
Accepted
time: 314ms
memory: 20408kb

input:

500000 300000
2480404 503611748
807623 760782766
2316732 684260449
2831939 51645161
537476 562743913
1610674 504850380
2380928 133709082
2144980 73356812
129210 739659233
654491 958330994
2541997 919219844
3647661 316973917
1313740 764279193
2372838 878120253
2425593 2595084
1091028 930904857
383617...

output:

926694145/166
297203891/53
50706112/9
430825952/89
430825952/89
297203891/53
113547797/19
50706112/9
430825952/89
430825952/89
297203891/53
50706112/9
50706112/9
50706112/9
430825952/89
50706112/9
926694145/166
50706112/9
50706112/9
430825952/89
488502132/79
50706112/9
50706112/9
50706112/9
50706112...

result:

ok 300000 lines

Test #41:

score: 0
Accepted
time: 265ms
memory: 20416kb

input:

500000 300000
3388005 4805
2876404 4
558171 1038
3444719 5643
699748 1114
1526019 4
1004865 10
3704723 2943
1725991 4
2894167 16411
516987 2
3653863 5
1692998 10651
3261447 1887
286909 5
1720296 1421
1590107 4683
2081125 1
3863426 2
395998 2
567182 7890
863705 6
3383460 10
3838326 5
3278590 10
72909...

output:

2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
2/1
...

result:

ok 300000 lines

Test #42:

score: 0
Accepted
time: 366ms
memory: 26640kb

input:

500000 500000
3113289 881507043
1972462 665211440
3069073 839156283
660679 505364470
2664973 296048203
2601501 599921744
1265538 17649336
333422 813977228
3557835 45733147
917135 742930735
1226580 713016193
1251879 345893486
3048607 99211497
1547313 421547699
1049282 337918410
263806 623108382
39610...

output:

801402245/141
801402245/141
257210031/34
801402245/141
801402245/141
801402245/141
676383849/151
836109761/142
801402245/141
801402245/141
801402245/141
801402245/141
676383849/151
801402245/141
823310455/106
801402245/141
801402245/141
676383849/151
801402245/141
801402245/141
801402245/141
8014022...

result:

ok 500000 lines

Test #43:

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

input:

500000 500000
1302636 5
1862188 1
807400 1324
2444993 5
3318416 4181
3768545 1
2905358 2160
553586 3948
1024936 1910
450834 1485
1901647 3
895924 4095
3407779 1693
3368055 4
3298520 3120
1909203 3
2738493 14091
2466677 3437
2803576 20813
3004026 2749
1886371 2
3055573 8397
1324446 2238
1016600 1953
...

output:

35/1
35/1
591/20
591/20
591/20
11509/347
591/20
591/20
591/20
591/20
35/1
11509/347
591/20
591/20
767/30
591/20
591/20
767/30
591/20
591/20
767/30
591/20
767/30
11509/347
591/20
591/20
35/1
591/20
591/20
591/20
591/20
591/20
591/20
35/1
591/20
591/20
591/20
591/20
591/20
591/20
767/30
767/30
591/20
...

result:

ok 500000 lines

Test #44:

score: 0
Accepted
time: 190ms
memory: 11144kb

input:

500000 1
284066 374816519
1329791 431985341
1841539 24847009
366957 544249206
3464840 165859953
1562121 320480760
2851259 552300716
3492829 838794921
3247178 104377612
3452890 54798261
3599624 224930125
3348436 304339850
146666 128532401
1576196 130823004
268428 444941181
329348 439957410
3280298 64...

output:

74716471/19

result:

ok single line: '74716471/19'

Test #45:

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

input:

500000 1
1137130 1
1469218 4
3067926 2383
2606269 10
3867443 9
2621700 9
3153060 6
2757711 7
2264760 6
2648606 7
3866801 5470
762937 3423
3280281 2
1494933 5833
2334327 8
934572 1431
1798526 8
451491 1
3852401 32532
1185663 7
853800 2003
377206 1966
2029336 4
539193 5
2744564 23438
279346 10622
3692...

output:

8/1

result:

ok single line: '8/1'

Test #46:

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

input:

1 500000
601491 710622346
100505
497654
1068511
2823920
2677723
876271
680276
1727783
497380
1767097
2577594
1616657
1598874
1148047
3678504
3116904
3128934
1396942
1107579
2926671
198326
596346
1063889
1938119
1479033
1751224
1780493
1444411
2399654
411474
3488599
3687157
3745973
892982
3485337
183...

output:

355311173/250493
710622346/103837
1/0
1/0
1/0
1/0
1/0
1/0
101517478/14873
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
101517478/57595
101517478/735
1/0
1/0
1/0
1/0
1/0
1/0
1/0
710622346/190017
1/0
1/0
1/0
1/0
1/0
101517478/83307
1/0
355311173/162510
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
101517478/2274...

result:

ok 500000 lines

Test #47:

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

input:

1 500000
1539316 2415
238183
1048582
1877096
1792865
3511688
2814775
2958765
2546329
2674433
1657028
1944977
3135510
2250062
3689128
1838649
2667666
3637055
175322
258919
2681045
1468363
2757236
2308211
167406
163991
453743
1997953
3330843
3188815
2514431
2188306
3461855
3710801
3651784
1583800
2094...

output:

35/18857
805/163578
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
2415/1363994
805/426799
1/0
805/23651
1/0
1/0
483/274382
69/39295
2415/1085573
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
1/0
483/37033
1/0
1/0
1/0
2415/716903
2415/28016
1/0
805/482577
1/0
805/305454
21/5812
2415/46597...

result:

ok 500000 lines

Test #48:

score: 0
Accepted
time: 392ms
memory: 26532kb

input:

500000 500000
3740457 710140369
2451296 13181974
95235 625427045
269986 140114982
486536 870380295
3823628 569599539
874022 321007299
2265924 540224373
2385758 552491931
2008135 73286485
2900806 277758210
3961573 116327411
2716936 133851745
460096 773604513
1490273 492727701
1369425 804596325
321795...

output:

531425025/104
56508615/11
56508615/11
807757365/121
56508615/11
941235464/183
807757365/121
807757365/121
941235464/183
531425025/104
531425025/104
941235464/183
531425025/104
531425025/104
941235464/183
56508615/11
56508615/11
531425025/104
941235464/183
56508615/11
941235464/183
531425025/104
9412...

result:

ok 500000 lines

Test #49:

score: 0
Accepted
time: 322ms
memory: 26664kb

input:

500000 500000
1388644 23825
1239079 1
583243 15441
2962208 2170
2970829 1743
3150270 5399
1503618 9
1126042 5
1523520 4970
2926624 1
1331502 7310
3200897 1688
3906575 4
1189210 3630
3356461 1009
699497 2948
3847798 1270
3579955 2
2978836 3
2224313 3494
2818131 9
2387973 15637
20453 10
2498126 8
2909...

output:

1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068/37
1068...

result:

ok 500000 lines

Test #50:

score: 0
Accepted
time: 393ms
memory: 26656kb

input:

500000 500000
1289301 888223793
2337669 752186720
1798204 459552107
3453974 869886965
2790718 91314451
350667 243859979
1700455 258807390
3713841 202386184
1666020 980963845
1272376 946717207
1824392 424821958
1835956 926402216
1027144 156165602
884957 191731438
757439 76250525
1655503 867082847
128...

output:

170405351/37
170405351/37
170405351/37
170405351/37
170405351/37
170405351/37
170405351/37
170405351/37
277337089/45
170405351/37
170405351/37
170405351/37
170405351/37
277337089/45
170405351/37
170405351/37
170405351/37
170405351/37
170405351/37
170405351/37
170405351/37
170405351/37
170405351/37
1...

result:

ok 500000 lines

Test #51:

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

input:

500000 500000
953229 14877
1767159 3
2455161 8818
3562403 8
157096 3
762862 3
387693 9
513068 10
1007628 2536
570521 4
2634256 1102
1725352 2
2871971 6
2184510 5
1901040 1
2605694 6
368861 22036
2569547 5596
612516 7
204604 3132
2593640 2542
2395547 1037
275749 8
2733374 6892
269844 7867
73732 6
872...

output:

9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
9/11
...

result:

ok 500000 lines

Test #52:

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

input:

500000 500000
2838145 66307217
3967147 345967274
1244276 143934064
1605258 744883141
1094900 17281310
686219 918120418
269992 901640184
2194462 129389211
1137770 264211568
345129 820147929
3004874 571885707
934531 441509725
3145864 28736355
1309818 199792955
3833117 394932134
3165774 779826266
31048...

output:

153634919/29
443647037/105
6570306/1
443647037/105
443647037/105
721864345/131
693944684/107
721864345/131
6570306/1
443647037/105
153634919/29
775677081/119
721864345/131
443647037/105
721864345/131
443647037/105
751161998/139
443647037/105
443647037/105
751161998/139
693944684/107
443647037/105
72...

result:

ok 500000 lines

Test #53:

score: 0
Accepted
time: 318ms
memory: 26620kb

input:

500000 500000
2625908 8
3858400 4689
3019861 2938
610394 10
3039202 2
1098020 8
2154030 10
1803296 2798
1451864 1
3347248 2
574790 10
62155 5397
2646127 9
251467 2
1006145 3992
1533065 5
2127120 2407
3379664 14528
298808 5
3347223 10
2677000 5
12654 5
3631453 10
3586332 5770
1462018 1177
3302088 377...

output:

7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
7/9
...

result:

ok 500000 lines

Test #54:

score: 0
Accepted
time: 377ms
memory: 26664kb

input:

500000 500000
3162798 949423345
2629329 790004723
1723053 418250614
1821950 474655124
3399083 238215466
2245963 592380858
1096425 694216082
3642379 791551022
418033 692683482
642074 988545947
3152651 569206351
1776210 811393043
1456073 51050212
2958871 912887176
132988 273422254
1708748 547345492
10...

output:

515801187/107
515801187/107
515801187/107
515801187/107
515801187/107
457546311/95
515801187/107
515801187/107
515801187/107
515801187/107
515801187/107
515801187/107
515801187/107
515801187/107
515801187/107
457546311/95
457546311/95
515801187/107
515801187/107
515801187/107
982852310/183
515801187...

result:

ok 500000 lines

Test #55:

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

input:

500000 500000
2559852 7
98099 2552
3315501 1432
1640515 4511
2569791 13096
2814339 2903
1985076 2296
3169082 1909
765892 2314
3211212 2170
101239 7
2736229 2
69024 8
1943258 16844
629532 1166
2304102 5938
3590231 7509
2704441 4873
3505879 7
3208079 5719
3817451 9287
2900293 5
1907349 6
300177 1639
3...

output:

2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
2/3
...

result:

ok 500000 lines

Test #56:

score: 0
Accepted
time: 375ms
memory: 26532kb

input:

500000 500000
711642 832539473
258806 383785277
2201830 252375676
1005938 204427107
1703265 459149621
3805706 266641298
3665963 632016172
2314488 13521345
3889783 680963908
939018 302168157
2076237 716270100
683298 326500552
798985 73364069
416436 625981397
432858 592103863
962123 314864718
24388 33...

output:

112438331/27
112438331/27
112438331/27
445312433/105
112438331/27
112438331/27
445312433/105
112438331/27
112438331/27
20144317/3
445312433/105
112438331/27
112438331/27
112438331/27
112438331/27
112438331/27
112438331/27
112438331/27
112438331/27
112438331/27
20144317/3
112438331/27
112438331/27
11...

result:

ok 500000 lines

Test #57:

score: 0
Accepted
time: 329ms
memory: 26720kb

input:

500000 500000
742178 7
3527547 6
2222386 1665
980025 9
2183412 3667
1575166 2046
1254676 2975
1159143 1515
127582 7
693494 6
3998430 4715
2292077 7
3407077 1208
2073803 9
3319634 9
1440108 5899
998643 8
537407 4670
2139394 1334
1690431 7
3216077 2755
204177 1382
2999666 9
2396465 6
3079887 4101
3729...

output:

5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
5/11
...

result:

ok 500000 lines

Test #58:

score: 0
Accepted
time: 401ms
memory: 26748kb

input:

500000 500000
2260487 305590194
1888284 682598535
2872095 231724929
189926 784455986
7447 385116480
332746 500710249
492396 569816263
3762406 235491668
3170045 669244335
2979067 175598879
2224015 863333848
1524977 841608061
1885001 505743334
3808593 634042914
3700024 320850879
2472393 227608136
1967...

output:

683635096/143
874080703/182
874080703/182
683635096/143
874080703/182
683635096/143
683635096/143
874080703/182
683635096/143
683635096/143
874080703/182
874080703/182
874080703/182
683635096/143
874080703/182
874080703/182
874080703/182
683635096/143
683635096/143
874080703/182
874080703/182
874080...

result:

ok 500000 lines

Test #59:

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

input:

500000 500000
3107886 6
1590014 18301
3904870 5
1066613 8
2275959 8
1531311 1
2523834 1591
1361626 1891
1752609 9025
2376061 3
1339005 10374
3936692 2
2202941 1665
1880738 6
3820060 5417
2500351 2871
2767617 1
3669061 6559
6407 7
3700185 4959
3859533 5
511739 7
1036333 2
1985754 7
1790159 8986
19685...

output:

1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
1/13
...

result:

ok 500000 lines

Test #60:

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

input:

500000 500000
2776627 188706322
1774658 421603280
3350872 65849991
598106 809195266
3344333 606050636
1892490 174970689
94637 507616353
1210323 602686183
2641795 97716249
2243308 49029601
1339088 10397597
3399360 356715571
195209 528057191
2490350 347137136
2967190 199340999
2758472 995127362
371976...

output:

212007266/53
212007266/53
212007266/53
212007266/53
212007266/53
212007266/53
266655245/49
266655245/49
212007266/53
212007266/53
212007266/53
212007266/53
212007266/53
212007266/53
266655245/49
212007266/53
212007266/53
212007266/53
879125724/151
266655245/49
266655245/49
212007266/53
212007266/53
...

result:

ok 500000 lines

Test #61:

score: 0
Accepted
time: 358ms
memory: 26744kb

input:

500000 500000
594857 10319
2776757 9
596631 10
1826521 3
370923 6
683350 14038
3559452 8723
3050504 10
3358266 4626
955463 4
2408742 3341
1382799 4
1474234 7
760689 9
3928106 7
3092032 9
2914608 5057
2664387 10
1780520 1445
1850290 1
199708 1929
1700024 6
3525360 2
3578622 12413
1731817 3
1017786 31...

output:

16267/304
1529/50
5585/172
5902/191
1529/50
5585/172
22031/690
5902/191
1529/50
5902/191
1529/50
1529/50
5902/191
5902/191
5585/172
1529/50
1529/50
5902/191
1529/50
5585/172
1529/50
5585/172
1529/50
5585/172
1529/50
1529/50
22031/690
5902/191
1529/50
1529/50
1529/50
1529/50
5902/191
1529/50
1529/50
...

result:

ok 500000 lines

Test #62:

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

input:

500000 500000
325471 366789746
3404135 720416538
2796944 45199244
3782094 389224145
615812 532017495
1195337 554263832
921070 445416443
2658240 824656506
889354 380963972
2540253 217427620
1295378 7718241
1465231 726598888
2505418 550371048
2915211 355198653
3267061 518022608
268742 907870780
166319...

output:

196832274/43
196832274/43
196832274/43
952166533/219
340330211/55
952166533/219
952166533/219
952166533/219
196832274/43
952166533/219
196832274/43
952166533/219
731708919/128
731708919/128
952166533/219
952166533/219
42616046/7
952166533/219
731708919/128
952166533/219
196832274/43
952166533/219
95...

result:

ok 500000 lines

Test #63:

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

input:

500000 500000
987192 5
3938278 3
1512438 2
3284964 13384
369310 10
2221201 4707
1927901 3000
1213846 2
2201512 2833
1101238 5835
2753534 2433
3842379 1
2483962 6
1374587 10
3880218 6816
411837 7
792736 8283
2124830 1017
1571107 2122
521517 1
872666 8969
2914492 16121
2661075 1510
1051077 1655
153444...

output:

5817/167
2072/69
8569/255
8569/255
5817/167
8569/255
2072/69
5817/167
2072/69
5817/167
2072/69
8569/255
5817/167
4657/82
8569/255
8569/255
2072/69
2072/69
6659/199
2072/69
6659/199
2072/69
2072/69
8569/255
8569/255
8569/255
2072/69
2072/69
1381/35
1381/35
8569/255
6659/199
5817/167
2072/69
2072/69
5...

result:

ok 500000 lines

Test #64:

score: 0
Accepted
time: 398ms
memory: 26748kb

input:

500000 500000
1874316 249905874
1033613 459421284
499913 319515794
2966082 118996128
2919994 312760163
3787785 228524272
3490608 88249237
1138861 486818317
361104 809435886
580301 90858342
1443156 154781990
3339615 241706397
624138 277717609
3531560 68292874
3566931 101545432
554820 675390006
639333...

output:

443755290/83
443755290/83
775980751/167
443755290/83
725517537/146
443755290/83
443755290/83
443755290/83
443755290/83
855709136/161
443755290/83
443755290/83
443755290/83
725517537/146
443755290/83
443755290/83
725517537/146
725517537/146
443755290/83
443755290/83
443755290/83
443755290/83
72551753...

result:

ok 500000 lines

Test #65:

score: 0
Accepted
time: 335ms
memory: 26744kb

input:

500000 500000
943157 4654
594724 8
3166642 4307
2429254 1797
902501 1104
3155728 8
3420846 4
3499949 10
762100 5
2952155 10
1946037 11986
2301462 2
674768 4250
3438548 4593
124012 1320
2706939 9
1304863 1290
3490964 7
65887 1111
3021612 4
2382537 5
2238445 1208
2826565 5
2632059 10
1817680 5585
1896...

output:

799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
799/27
12458/349
799/27
799/27
799/27
22263/680
799/27
799/27
799/27
799/27
799/27
...

result:

ok 500000 lines

Test #66:

score: 0
Accepted
time: 371ms
memory: 26528kb

input:

500000 500000
2198968 722956594
2663090 53201837
2011394 153640855
2150070 848768112
2256880 533694318
314825 197752007
317041 880825136
3810970 413821344
3641366 797716313
877246 259256360
1590934 301845738
181294 756813906
2934346 300031466
989125 781387095
2834097 420227040
2065091 442909233
1550...

output:

30673931/5
142384350/29
142384350/29
160241447/31
160241447/31
160241447/31
142384350/29
142384350/29
30673931/5
142384350/29
30673931/5
142384350/29
160241447/31
195347179/29
142384350/29
160241447/31
160241447/31
142384350/29
493858859/71
142384350/29
160241447/31
160241447/31
142384350/29
1602414...

result:

ok 500000 lines

Test #67:

score: 0
Accepted
time: 376ms
memory: 26616kb

input:

500000 500000
3584037 1234
1427562 6
965747 7
111596 2125
1298259 10
3521731 7
1388732 7
2520882 3
2095885 1733
1695921 6396
1521244 17275
2651380 4
2951350 10
3855115 3187
3323857 2805
3033536 10143
3228920 7525
3013926 8
2757732 1683
3003843 3
3315661 10
2064350 3291
2008228 4
1098372 2132
187986 ...

output:

6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
6/13
...

result:

ok 500000 lines

Test #68:

score: 0
Accepted
time: 373ms
memory: 26616kb

input:

500000 500000
3747812 606072722
1325272 497239287
1457467 132990109
1334058 723764287
3528359 754628474
841864 577045151
110770 818625226
1258887 75983155
3113116 931220931
2917295 132687082
514519 594133679
2055677 126697224
2277258 322345323
1413985 494481316
1909776 298717161
1318465 650619947
52...

output:

55801451/10
96433726/19
55801451/10
96433726/19
321556321/63
321556321/63
96433726/19
834376239/131
613119963/100
96433726/19
96433726/19
55801451/10
55801451/10
55801451/10
96433726/19
613119963/100
96433726/19
321556321/63
55801451/10
834376239/131
321556321/63
96433726/19
96433726/19
96433726/19
...

result:

ok 500000 lines

Test #69:

score: 0
Accepted
time: 335ms
memory: 26532kb

input:

500000 500000
3270075 5
3598783 1853
1583651 8
1017949 1865
2957224 3
3451666 3
1349179 1
620211 2719
2217717 9
2543249 5
2102704 9
1338653 5
3934352 6
3375057 5293
2954066 2136
3547902 4302
1117776 8
3581603 6
3982534 3
2961615 3
2228555 2800
2626651 1201
3837024 2
758996 4807
1543740 1975
1772782 ...

output:

4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
4/7
...

result:

ok 500000 lines

Test #70:

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

input:

500000 500000
263953 784156146
178942 91019841
3160436 112339362
518046 158568974
1832541 680595333
2401608 251305591
3713011 461458020
2706804 2986182
2393378 214468654
3214240 301085100
662297 446230131
2897356 641804733
587467 344659180
3063038 207575537
2209646 322431473
3861440 418139173
246963...

output:

126189590/27
126189590/27
126189590/27
126189590/27
126189590/27
142543126/23
126189590/27
126189590/27
657526220/107
126189590/27
126189590/27
142543126/23
142543126/23
126189590/27
126189590/27
126189590/27
126189590/27
126189590/27
126189590/27
126189590/27
126189590/27
126189590/27
126189590/27
...

result:

ok 500000 lines

Test #71:

score: 0
Accepted
time: 313ms
memory: 26664kb

input:

500000 500000
505020 1336
2974019 3
2660024 3173
1969677 1902
3755504 3842
3881200 1786
487784 3
1923715 2
1463827 9
3912064 1219
2597903 1164
484902 3
3813285 3
1303089 28179
187945 5
1811081 9
909839 18935
1287293 4661
3697303 8
3157064 4
611056 7
2784916 7025
766773 13386
2240714 9285
824819 2461...

output:

7103/256
8280/197
7103/256
7103/256
7103/256
7103/256
7103/256
7103/256
7103/256
7103/256
8280/197
7103/256
7103/256
7103/256
7103/256
7103/256
7103/256
7103/256
3854/103
7103/256
7103/256
7103/256
7103/256
7103/256
7103/256
7103/256
7103/256
7103/256
7103/256
7103/256
439/12
7103/256
7103/256
7103/...

result:

ok 500000 lines

Test #72:

score: 0
Accepted
time: 368ms
memory: 26644kb

input:

500000 500000
1812797 962239570
2841123 684800394
3639212 946464424
734738 328532446
1169427 901529489
1704456 630598734
3506741 399258111
154721 519923801
1865129 642940568
2478481 174515822
1842779 593293880
1995931 451879538
2706187 777038445
3487899 920669758
2509516 200921593
147518 185658399
1...

output:

113691073/23
113691073/23
113691073/23
113691073/23
113691073/23
113691073/23
113691073/23
718172739/143
113691073/23
113691073/23
113691073/23
113691073/23
113691073/23
113691073/23
718172739/143
113691073/23
113691073/23
113691073/23
113691073/23
113691073/23
113691073/23
113691073/23
113691073/23...

result:

ok 500000 lines

Test #73:

score: 0
Accepted
time: 335ms
memory: 26720kb

input:

500000 500000
1995830 2
226086 2455
1468194 8
2680151 3773
1636537 5216
3616793 3
3038181 1908
2467813 5
2384210 12237
907157 9
2635661 1033
1415703 3026
2262824 10
912806 10
3478325 8113
3693339 5
873457 3029
3777085 10
1374367 1
2949877 2096
2242813 7
1774997 3840
3304631 9
1028388 3298
541298 158...

output:

3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
3/10
...

result:

ok 500000 lines

Test #74:

score: 0
Accepted
time: 366ms
memory: 26748kb

input:

500000 500000
3361641 845355698
470601 128837844
3085285 220780974
2886022 58304429
2440905 122463644
296903 159634982
141686 632025497
1602638 887118316
1145391 926188291
2583937 47946544
766365 885581821
3870315 672019752
1016395 799352302
3912760 928731276
2809386 224635906
625084 98401817
338919...

output:

724373140/133
724373140/133
133596413/25
724373140/133
724373140/133
724373140/133
724373140/133
724373140/133
724373140/133
724373140/133
724373140/133
552254292/109
724373140/133
724373140/133
724373140/133
552254292/109
724373140/133
724373140/133
724373140/133
724373140/133
724373140/133
5522542...

result:

ok 500000 lines

Test #75:

score: 0
Accepted
time: 340ms
memory: 26748kb

input:

500000 500000
2751886 3
3273228 5
1044835 6
1780082 5770
2354061 2753
1989497 3505
597145 2
80 8
647894 4447
176337 3734
3336299 5499
3493824 2095
1742032 3007
2225121 2
3434132 1398
864407 10
280812 1619
2895197 2261
1645338 1292
3627634 4
2859106 6565
3570176 8
2205678 3197
2314827 3476
63830 6
20...

output:

6770/189
9791/308
6485/186
6770/189
205/6
9791/308
172/5
9791/308
6770/189
6485/186
1073/39
205/6
205/6
4839/152
1073/39
6485/186
6485/186
6485/186
1073/39
172/5
205/6
9791/308
9791/308
9791/308
205/6
205/6
9791/308
1073/39
9791/308
205/6
205/6
1073/39
9791/308
6485/186
3253/94
6770/189
9791/308
362...

result:

ok 500000 lines