QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#818273#9860. Light of StarsSGColinAC ✓290ms10864kbC++202.2kb2024-12-17 18:10:452024-12-17 18:10:46

Judging History

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

  • [2024-12-17 18:10:46]
  • 评测
  • 测评结果:AC
  • 用时:290ms
  • 内存:10864kb
  • [2024-12-17 18:10:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef tuple<int, int, int> tii;

#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

constexpr int N = 100007;
constexpr db eps = 1e-9;
constexpr db PI = 3.1415926535897932384626433832795;

int n, q, ans[N], X[N], Y[N], x[N], y[N];

struct BIT {
	int c[N];
	inline void clear() {memset(c, 0, sizeof(c));}
	inline int lowbit(int x) {return x & (-x);}
	inline void add(int x) {
		for (; x < N; x += lowbit(x)) ++c[x];
	}
	inline int sum(int x) {
		int ret = 0;
		for (; x; x -= lowbit(x)) ret += c[x];
		return ret;
	}
} bit;

inline void work() {
	int l = rd(), r = rd();
	db a = cos(r * PI / 180);
	db b = -sin(r * PI / 180);
	db c = cos(l * PI / 180);
	db d = -sin(l * PI / 180);

	vector<tii> pts;
	
	vector<pair<db, int>> tmp;

	auto discretize = [&](int *a) {
		sort(all(tmp)); 
		db lst = -1e18;
		int cnt = 0;
		for (auto [w, id] : tmp) {
			if (abs(w - lst) > eps) ++cnt;
			a[id] = cnt; lst = w;
		}
		tmp.clear();
	};

	if (l == r) {
		if (l == 90) rep(i, 1, n) pts.eb(X[i], Y[i], i);
		else if (l == 0) rep(i, 1, n) pts.eb(Y[i], -X[i], i);
		else {
			rep(i, 1, n) tmp.eb(Y[i] - b * X[i] / a, i);
			discretize(x);
			rep(i, 1, n) pts.eb(x[i], Y[i], i);
		}
		sort(all(pts));
		reverse(all(pts));
		int lstx = -1e9, cnt = 0;
		for (auto [x, y, id] : pts) {
			if (x != lstx) lstx = x, cnt = 0;
			else ans[id] += cnt; 
			++cnt;
		}
		return;
	}
	
	rep(i, 1, n) tmp.eb((c * Y[i] - d * X[i]) / (b * c - a * d), i);
	discretize(x);

	rep(i, 1, n) tmp.eb((a * Y[i] - b * X[i]) / (a * d - b * c), i);
	discretize(y);

	rep(i, 1, n) pts.eb(x[i], y[i], i);
	sort(all(pts));

	bit.clear();
	for (auto [x, y, id] : pts) {
		ans[id] += bit.sum(y);
		bit.add(y);
	}
}

int main() {
	n = rd(), q = rd();
	rep(i, 1, n) X[i] = rd(), Y[i] = rd();
	rep(i, 1, q) work();
	rep(i, 1, n) printf("%d ", ans[i]);
	return 0;
}

详细

Test #1:

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

input:

4 2
0 0
4 5
2 4
1 5
0 45
120 150

output:

1 1 1 0 

result:

ok single line: '1 1 1 0 '

Test #2:

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

input:

3000 10
44972 48171
30241 41392
24297 21452
42706 42506
19480 39475
8769 45623
47439 45915
17463 26926
14966 24009
21288 3192
599 17221
18111 1118
20153 30842
37473 29893
20947 46060
36233 5528
28751 17812
23199 46350
24068 29630
22664 16335
19304 43933
42559 46163
2279 11754
12826 16304
32165 24656...

output:

98 404 1262 451 362 65 248 860 967 2062 849 2054 756 1078 117 2352 1550 116 887 1495 181 217 1140 1236 1266 1326 2110 1226 1473 132 1363 1875 1660 762 582 916 1761 1000 1670 83 1652 1254 1181 755 1739 969 1219 1578 602 4 16 46 948 966 11 167 792 692 2037 1714 2259 1957 797 1584 2151 513 1608 41 1889...

result:

ok single line: '98 404 1262 451 362 65 248 860...036 1166 117 1290 2616 400 214 '

Test #3:

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

input:

3000 10
25116 28527
12269 47809
41407 49789
6250 3129
10917 15869
16391 45424
19848 44903
36350 7694
31 13717
2532 20408
19540 15613
18692 16331
5082 6823
25042 37243
46127 17531
18955 37376
33321 4339
39970 23142
33262 6099
28338 34417
37272 4454
16932 36602
22205 28996
348 42442
24696 9172
35526 9...

output:

912 26 1 1723 1264 86 110 2202 1047 858 1500 1407 1469 503 1778 421 2322 1345 2235 669 2391 442 902 52 1898 2075 1412 1478 2277 866 1673 1703 1154 1466 522 1853 259 1211 1610 70 1882 1010 417 205 2430 34 219 134 278 425 1962 22 723 923 977 552 1271 385 2794 383 1300 2249 1349 759 149 1199 2591 208 1...

result:

ok single line: '912 26 1 1723 1264 86 110 2202...775 1314 1814 1288 925 450 283 '

Test #4:

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

input:

3000 10
38028 49299
17481 33121
20563 46270
43617 24889
22547 30215
39933 36027
12834 46469
16900 124
32632 32321
19648 47208
33823 7908
13175 25831
13693 38900
29458 11824
21804 39002
13338 19226
19779 11998
3750 6413
32633 24008
19004 34739
5766 26111
41304 3331
44596 46238
33998 7444
22938 47560
...

output:

4 102 36 392 168 193 20 195 194 21 544 91 58 414 82 117 206 9 310 100 14 719 60 538 26 115 223 28 101 106 254 112 780 717 30 545 337 40 313 211 143 219 593 1 789 698 8 1 56 461 36 86 51 898 27 184 1 1 284 95 493 36 298 805 4 609 125 3 716 479 174 166 500 124 336 123 414 470 91 100 3 509 116 562 127 ...

result:

ok single line: '4 102 36 392 168 193 20 195 19...588 511 634 61 214 514 455 188 '

Test #5:

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

input:

3000 10
21164 40791
8565 18292
10856 41839
18823 41465
13984 24368
36801 15107
44299 6978
47451 30892
9521 30317
38844 31657
17419 23531
16220 14228
36192 17874
17027 16069
15624 48811
40107 27890
44188 7083
15337 27636
35876 38814
41912 32596
30597 3866
30332 43770
14522 42375
38753 39678
15468 467...

output:

73 142 35 58 145 550 865 362 90 261 208 238 484 260 2 371 854 159 144 295 626 63 42 138 23 523 0 282 737 199 160 48 940 327 339 54 160 343 538 607 240 909 287 55 14 233 219 69 560 74 89 276 782 84 949 332 786 1065 799 297 239 403 501 159 330 672 62 565 281 0 14 303 141 370 753 4 45 415 773 62 216 11...

result:

ok single line: '73 142 35 58 145 550 865 362 9...3 549 83 327 18 108 137 72 114 '

Test #6:

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

input:

3000 10
39261 14669
37488 29893
22781 11504
41422 40041
13951 12425
30182 26956
25764 20207
1570 43900
27354 37258
2855 48874
10071 16211
37520 17
9458 43855
31028 2313
26148 14712
10780 42507
1365 28983
17454 4428
6733 4147
27393 152
48564 1812
37472 915
30962 42383
49986 1575
46478 13986
4783 2004...

output:

588 343 366 197 183 324 314 2 165 1 96 770 33 606 364 41 8 272 56 527 1009 734 117 1047 709 40 69 791 175 866 943 991 53 477 210 666 495 1 225 4 636 378 18 766 459 432 210 347 457 29 25 60 276 749 75 191 25 37 774 99 608 34 56 16 275 102 336 35 204 300 134 134 388 144 335 91 301 147 441 70 198 9 620...

result:

ok single line: '588 343 366 197 183 324 314 2 ...9 21 304 274 100 1 146 265 147 '

Test #7:

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

input:

3000 10
10349 29871
7853 27254
45459 16657
19734 23848
38156 867
14860 5511
9694 39773
23064 12619
36243 47303
19971 45514
14771 26266
20341 47997
38436 47038
35829 32846
7920 12472
5163 7122
46879 42213
28655 46755
9975 36185
11963 10057
38162 23996
40741 15036
3352 9626
16404 33809
8848 48887
4371...

output:

117 104 1056 314 1250 399 60 553 79 69 214 35 83 463 172 100 285 70 89 277 691 966 48 178 6 26 9 202 124 329 538 359 59 1004 879 539 718 630 0 210 12 272 673 276 346 14 122 687 420 16 0 987 1145 1060 132 153 216 464 1076 647 510 742 321 1067 485 744 1493 1170 129 1582 203 137 81 0 385 742 587 5 1063...

result:

ok single line: '117 104 1056 314 1250 399 60 5... 687 719 285 362 222 339 507 4 '

Test #8:

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

input:

3000 10
11598 38596
39881 29272
12568 3556
21228 40424
2777 29868
8241 5697
29111 3387
3615 17098
4076 30532
15456 29963
48366 24657
20394 24731
37991 46730
23013 31139
36205 45992
11595 38587
21816 14113
16004 35210
4161 39470
11685 48331
6129 24934
27161 26195
14223 14819
21158 45706
37250 30796
3...

output:

53 377 314 86 41 224 606 94 55 130 519 232 97 170 98 53 379 105 19 12 89 272 257 57 324 219 17 586 215 214 670 126 584 581 9 136 29 255 5 97 612 458 8 681 260 80 197 779 50 252 269 247 552 180 67 451 435 17 64 775 43 5 424 161 232 71 514 141 36 11 62 319 80 71 867 1 207 639 12 59 299 825 211 30 307 ...

result:

ok single line: '53 377 314 86 41 224 606 94 55...867 382 526 43 504 453 243 370 '

Test #9:

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

input:

3000 10
27117 45241
45093 35689
41725 31892
20644 39000
14407 11446
31398 13147
45808 40327
16023 32713
30965 14289
46700 6763
2681 22521
20975 22183
38073 28807
22246 11672
47256 17463
23212 47251
38048 26430
27206 44770
30588 4275
23456 16412
42624 23408
13197 33340
45670 49293
23335 48660
32388 1...

output:

56 299 338 88 250 492 204 129 468 835 31 233 316 387 625 30 376 67 616 332 455 94 9 21 525 285 47 228 640 445 1 158 27 3 447 9 180 347 193 122 648 290 118 117 35 14 25 153 1 86 8 27 404 377 272 99 293 270 265 231 528 131 691 425 346 5 624 14 31 50 542 444 631 501 437 105 6 513 129 23 271 484 32 491 ...

result:

ok single line: '56 299 338 88 250 492 204 129 ...53 268 128 325 577 712 532 362 '

Test #10:

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

input:

3000 10
7261 3966
3410 38234
8834 45606
45850 22808
5844 11551
4940 13333
15610 44357
20285 1433
13565 41948
37527 26971
36277 15343
39170 8500
40234 34070
27047 19021
14260 21702
9037 11868
12843 10378
29323 21562
33831 28664
46362 43024
22639 1162
23330 23778
18588 49301
16042 36845
21574 12230
25...

output:

1652 147 48 1565 1284 1157 111 2183 171 1185 1823 2287 808 1465 1042 1377 1527 1355 1033 323 2265 1144 4 409 1645 286 901 341 729 35 2428 1466 1352 172 755 2925 1465 1065 1864 1410 284 1646 66 1639 2029 1525 52 2214 1531 1617 849 1486 586 1813 162 1798 9 1131 554 569 882 2680 1598 665 2276 1484 1573...

result:

ok single line: '1652 147 48 1565 1284 1157 111... 748 34 1364 208 1604 2165 354 '

Test #11:

score: 0
Accepted
time: 269ms
memory: 10448kb

input:

100000 10
16686 15682
8622 17835
37464 23942
24161 39383
29522 37945
19039 3551
25971 19634
18067 5911
16743 16121
27826 3244
40977 42488
18503 35234
49372 995
41047 8610
1601 48742
29709 10949
20020 20615
40525 40178
48208 10702
7748 29218
17422 31876
18421 40507
26851 4496
11740 10023
23161 17850
...

output:

9380 3632 18583 4558 6345 13966 14388 12554 9372 22393 5183 5233 45565 32073 30 20827 10413 7040 36520 2390 5878 3164 21029 6454 13323 1165 1961 226 4942 14905 42384 28430 6839 15497 124 1589 284 10525 37365 28 21127 2516 1969 1627 5068 17314 5250 1494 21520 86 2932 18739 12100 21585 7642 10587 2004...

result:

ok single line: '9380 3632 18583 4558 6345 1396...471 5715 2362 35364 20801 4472 '

Test #12:

score: 0
Accepted
time: 270ms
memory: 10376kb

input:

100000 10
29599 46038
28987 29437
4573 43608
46760 37959
32622 38050
4244 44680
9901 33248
36955 9863
13471 26166
14255 14509
9917 23646
39803 32687
36879 15841
28617 6903
33372 43925
3374 49277
6477 6644
28401 44168
42395 46612
33646 20484
42252 33340
42794 42467
10905 21737
22973 42257
45114 2367
...

output:

1074 7602 415 6216 4492 311 2611 20775 5062 8558 4454 8576 17031 19097 2264 32 5868 1870 799 13181 8351 3555 5261 2009 30024 2716 15085 14495 11957 2090 10661 8463 13524 605 2209 6224 9985 4837 2749 1647 9648 4236 1253 13939 25086 12312 142 16817 7581 9814 7093 11711 17035 11762 24864 16987 6380 316...

result:

ok single line: '1074 7602 415 6216 4492 311 26...6 9187 10012 7915 519 4658 428 '

Test #13:

score: 0
Accepted
time: 272ms
memory: 10528kb

input:

100000 10
38639 25868
34199 15135
33729 22472
7839 12711
6300 43339
15738 40995
6901 31709
17505 37639
5128 42163
5082 5437
43513 6885
1905 364
15857 41822
33033 37436
17608 7220
30525 7941
39943 23359
21462 20961
45638 23608
16136 30389
42987 31287
31822 26428
10111 26930
39391 13211
37644 34276
23...

output:

18879 22733 18510 2179 788 2871 1609 4305 699 929 35819 146 2639 9023 9978 22885 21487 11355 24624 5911 17097 15006 3302 27959 12709 409 24701 7946 34580 5584 28634 1023 23651 29864 2165 9144 5224 32334 3790 4264 8519 3265 2264 40861 4996 14377 3703 2552 5608 15168 20352 15328 1961 7280 29 17997 266...

result:

ok single line: '18879 22733 18510 2179 788 287...2856 19486 21813 2217 362 2091 '

Test #14:

score: 0
Accepted
time: 271ms
memory: 10496kb

input:

100000 10
21775 17360
16227 17153
839 18426
277 31864
35690 19733
9119 26028
5600 16042
48055 18407
22961 43152
45382 39886
30981 39742
13621 7400
6355 45004
20602 12018
28659 45923
42141 39791
38064 36204
14904 30521
4832 5646
17938 18663
34666 9041
6195 16867
20982 17883
11378 45445
35887 13607
47...

output:

9587 7435 54 4 14843 3143 2298 21362 2686 8265 5370 8215 460 10776 2204 7678 8757 3952 1706 7667 19544 2714 8949 821 17510 8605 28930 9981 13495 13759 13652 19945 9716 14998 2283 1735 10387 9591 8998 29785 16678 19686 6088 702 458 22917 8246 15576 19539 3212 11587 30718 29465 26796 667 17623 2792 83...

result:

ok single line: '9587 7435 54 4 14843 3143 2298...314 9739 15245 439 19527 11533 '

Test #15:

score: 0
Accepted
time: 270ms
memory: 10864kb

input:

100000 10
14832 6440
12523 26115
8625 10476
1188 9064
33046 42360
13994 22001
47284 39780
11621 14789
32451 27752
5405 24846
34044 42476
29790 5298
34888 17191
1067 40843
9820 48450
1631 24208
5908 29863
40270 16488
19493 12073
2615 1308
4279 29556
28651 47219
30532 7551
39029 27528
33138 1138
10047...

output:

5301 3716 1849 32 5431 4658 10797 3304 13019 717 5593 19202 19473 27 323 74 810 23670 9022 164 445 1797 19577 16407 23620 1293 6824 9148 2163 13473 352 3991 583 31098 17738 21258 6701 28795 12679 1728 2328 17208 3245 1103 1725 26558 15397 196 1768 33649 7494 1791 11885 2138 8656 962 325 14780 6075 1...

result:

ok single line: '5301 3716 1849 32 5431 4658 10...2197 9316 86 912 2631 220 1102 '

Test #16:

score: 0
Accepted
time: 270ms
memory: 10520kb

input:

100000 10
18687 15165
6073 22948
16679 29757
35450 48057
33539 42465
49199 39035
23037 3394
1227 45557
26572 37796
12938 47774
38744 40867
20787 8320
34970 32037
26588 38609
46633 25490
5071 32872
39374 42707
33331 43280
16639 3695
8816 19390
17062 24925
14687 19517
38795 40327
43783 15714
21797 356...

output:

15562 3579 8043 1619 6235 13193 25885 130 7285 704 8630 20847 14020 6937 25544 1987 7050 5508 18453 6200 10124 10824 9279 34218 7152 4231 15642 17211 2677 23744 10885 2453 14456 969 35127 23542 39033 3054 11825 17566 40526 10683 32331 31017 29279 4682 1573 12533 1989 25700 9826 67 755 661 28822 2866...

result:

ok single line: '15562 3579 8043 1619 6235 1319...59 15213 4889 42561 44775 9049 '

Test #17:

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

input:

100000 10
16065 18704
38101 8261
45836 46431
2098 31864
36113 18859
46067 12405
21735 1855
49010 26325
27172 21026
41190 14991
22340 12443
42086 44637
17292 8018
25821 31332
40453 20673
28735 47489
8599 26655
9158 24086
19882 47396
22666 2479
23893 28968
42052 15908
40081 24801
22249 21659
41144 331...

output:

44700 70081 2448 19007 51699 67485 73242 41163 45577 59328 57101 5578 61138 28104 49286 1347 29580 33493 1456 72797 31516 58156 41973 42786 86490 29957 25227 45660 20609 14747 12899 51354 2192 1724 44884 42572 49264 60317 57335 49597 8001 30602 49706 17817 44270 72320 15415 63544 53609 15397 3393 49...

result:

ok single line: '44700 70081 2448 19007 51699 6... 21876 74464 47345 56967 49831 '

Test #18:

score: 0
Accepted
time: 284ms
memory: 10444kb

input:

100000 10
28977 4245
43313 31910
12944 39040
10072 25256
10318 45253
4074 17775
3200 27132
20890 9172
27005 28493
8306 44255
47758 43601
4188 15801
34221 22863
18574 29098
42449 33968
23119 29337
33008 12683
25930 33646
40357 48074
22389 43859
15572 27442
4903 32636
22055 29995
38667 36660
19048 322...

output:

76782 32592 9071 27039 2491 32644 18393 61530 33014 2811 10245 35710 46357 27035 28399 29392 64363 23387 1608 6139 27718 12415 27784 22495 22239 58605 21577 39269 7232 69380 27076 67124 0 68182 49030 10308 4414 4255 65389 65131 52603 41845 89233 28277 36493 43267 12396 67600 69193 61593 11173 38208 ...

result:

ok single line: '76782 32592 9071 27039 2491 32... 23228 28654 75563 46529 70553 '

Test #19:

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

input:

100000 10
12976 45791
30553 19626
23837 13858
10982 30824
25433 15415
36146 31890
39314 39207
49223 29764
38959 33431
30377 29216
12343 25231
40196 13699
33858 1147
5517 34213
46793 6191
49456 43035
26642 6869
12433 40717
43737 7492
18729 12262
41137 9620
27360 18172
14373 47245
21887 27799
27054 40...

output:

2149 46485 51573 16375 50196 27636 14813 33572 25365 30374 25338 61658 80277 8987 80322 6982 64839 6114 75541 50061 69453 47088 1178 28307 10475 29408 78074 50495 50697 48934 40438 29948 17654 15372 5877 61987 67486 50966 67733 30328 14918 22129 14163 59813 37301 62532 2983 2559 22324 778 7055 36204...

result:

ok single line: '2149 46485 51573 16375 50196 2...41 3263 47202 10743 5107 74715 '

Test #20:

score: 0
Accepted
time: 283ms
memory: 10400kb

input:

100000 10
34065 5042
918 13995
26177 42195
39293 12167
49110 3858
14872 10972
60 47251
878 33331
13383 11090
25862 46433
4994 17143
23017 43537
36020 27129
10319 15273
34133 48382
36049 34467
31212 42897
21028 17509
8643 5065
41635 48456
9631 15743
1733 46949
13580 19671
12016 24162
4959 39519
10609...

output:

76685 29501 8896 67187 88933 49285 192 7499 47686 3143 29832 6355 38081 38162 839 24834 8834 44848 51189 729 36737 420 34931 27220 4798 56341 59783 40487 1902 48270 345 5385 59232 66142 44802 19525 29943 730 24222 37101 68295 3190 11220 1524 58173 53194 58334 36870 1123 34821 22793 53064 45755 56075...

result:

ok single line: '76685 29501 8896 67187 88933 4...806 68835 51800 6826 361 52590 '

Test #21:

score: 0
Accepted
time: 277ms
memory: 10476kb

input:

100000 10
35314 34871
6130 10829
5334 11861
14500 45975
1684 91
77 39526
33990 22001
48660 37809
31217 44319
30817 7698
30414 33534
1966 40990
26518 15158
47503 13039
15905 25422
47665 27979
5622 35902
26137 27069
23021 8350
27117 16011
15935 9032
40760 13677
23923 27857
16771 39164
29489 6802
6019 ...

output:

24566 52018 49981 2833 65027 6045 48251 19439 6966 72936 26172 5209 57657 68750 34758 39136 13719 36465 67815 56312 62250 65093 34345 12942 73812 17052 61344 28214 74854 50135 45769 19731 43125 30065 36187 48532 3933 77982 79193 17307 58131 13231 17792 37175 67049 16494 55061 21161 49445 43194 53503...

result:

ok single line: '24566 52018 49981 2833 65027 6...57 54042 8507 6625 29084 84232 '

Test #22:

score: 0
Accepted
time: 280ms
memory: 10352kb

input:

100000 10
15443 33009
31707 19791
27889 30200
15410 25255
16799 14542
4952 20874
46920 22940
12226 37297
7939 11305
26185 9891
18710 41453
18134 9992
2059 5985
16305 41864
11193 39469
15713 41677
26073 32168
39456 7851
26401 5194
11409 14191
49677 41210
18402 3085
34000 33059
37943 9583
26741 5996
2...

output:

6113 22144 12599 8897 13456 2516 27461 3555 6040 24560 3375 16368 394 2768 2736 2777 10488 38483 27674 9117 7195 19166 12213 35494 27433 1358 45880 10542 11734 5073 609 10790 21359 4439 3930 881 4089 1108 20201 263 8135 195 12850 9784 2659 18684 729 8294 21502 365 13533 49686 24127 14 3163 20062 440...

result:

ok single line: '6113 22144 12599 8897 13456 25...32386 5839 281 1140 11943 9953 '

Test #23:

score: 0
Accepted
time: 270ms
memory: 10392kb

input:

100000 10
7635 15444
34454 4577
44998 49480
25961 35878
43582 2984
28109 5525
1569 9353
1832 24016
2060 12294
7429 3396
29121 39844
9131 1493
2141 29006
3874 49214
48534 34651
30434 33109
21586 16116
44945 17411
46876 20526
40412 32273
9995 6916
37590 37045
6391 26589
49176 7352
3736 20672
21789 419...

output:

3471 23958 28 5498 31264 18724 179 269 308 4229 4028 5735 372 53 10151 7765 11015 22236 21108 10052 5594 6495 2056 31612 1142 2346 5213 2924 1294 10227 477 17028 3535 16711 7465 22469 526 6400 625 5900 4980 1400 12314 13058 2779 181 3315 1 3705 1318 443 25430 20418 145 26566 2339 5552 25976 2629 154...

result:

ok single line: '3471 23958 28 5498 31264 18724...225 9842 19224 4584 18760 2138 '

Test #24:

score: 0
Accepted
time: 280ms
memory: 10376kb

input:

100000 10
44258 45273
28003 19170
47339 5018
4657 19686
8203 8273
45201 43663
267 46678
49615 4783
29476 39953
15489 38754
21773 49372
18768 1938
42640 43325
41058 46979
32770 6123
24818 14958
45996 46193
38006 5866
41063 44388
46086 32594
13721 7855
23625 39005
38365 5495
12107 15378
17513 31862
76...

output:

2251 20466 49649 2643 7152 3640 14 51893 5879 3940 40 22295 3888 1181 34273 20843 1844 39718 2813 16547 14076 5476 40539 10309 7573 4836 25398 1187 31211 5773 3455 8000 37864 20021 14607 2106 3606 7708 1006 25220 13546 5745 9448 14072 285 24745 14206 12169 33148 28826 0 13169 7729 21282 23180 5332 2...

result:

ok single line: '2251 20466 49649 2643 7152 364...203 31600 7895 3964 5582 39674 '

Test #25:

score: 0
Accepted
time: 270ms
memory: 10372kb

input:

100000 10
12355 42862
10031 13539
14448 24299
29863 24214
46649 22619
6694 19640
43253 48244
9447 23503
44317 5950
43741 12067
26473 9811
42533 49391
19010 31354
48467 28040
47308 48698
28643 46807
41510 860
8264 15427
257 14905
24704 23974
43736 6327
990 5734
37572 5503
37581 30379
12651 49146
3139...

output:

2396 13370 12043 22133 34224 8035 1038 8742 55947 46811 33588 116 10417 27447 566 2417 59926 11018 4762 19053 54845 8313 49786 20004 250 45231 10693 15653 7568 16814 26163 40930 35521 12967 20007 20183 8185 2513 5050 25797 814 30436 40227 13713 3024 3235 15990 29496 29967 3339 57858 9142 21406 47307...

result:

ok single line: '2396 13370 12043 22133 34224 8... 33901 15904 25198 58041 13777 '

Test #26:

score: 0
Accepted
time: 277ms
memory: 10396kb

input:

100000 10
1924 5126
35608 34022
37003 40060
30773 32886
34948 40062
49521 15612
6184 43086
46836 31933
33087 40168
48580 37444
29009 41441
16878 24104
21254 39414
36 3874
7749 20537
1875 2470
44201 35463
21968 46209
11926 33381
33092 13097
46118 14795
28631 36085
47121 45170
27280 33566
3423 3908
47...

output:

2406 15046 10412 13692 9642 43631 1016 23264 9216 17212 6985 10654 5904 1 5409 2431 18042 2426 4894 30603 41142 10370 6599 11542 4585 31854 32662 18570 4466 10264 16717 4436 23484 25572 15293 11201 42825 17225 4587 17682 1064 6522 10760 2324 34794 5975 1698 4041 34996 61 6888 5246 26534 18878 18785 ...

result:

ok single line: '2406 15046 10412 13692 9642 43...181 84 32413 29085 13208 24026 '

Test #27:

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

input:

100000 10
5781 13851
28772 7671
48927 36014
9085 49462
26386 7399
46774 15413
22882 41547
39434 653
15160 23925
44065 31477
33709 7065
11362 9894
11752 21491
42790 25350
18274 39401
23075 1552
19138 19411
23587 5769
12064 15419
12477 46186
14085 39445
26715 43757
29096 12413
10930 15801
25377 3960
2...

output:

610 11483 11417 130 10050 19817 3118 19770 3449 12632 14465 2464 2560 14116 2528 8965 5414 9024 2729 789 1790 2885 10985 2256 10173 5010 1895 1618 8162 21380 9358 8549 19043 9436 8544 22941 732 14359 9813 1644 4549 7828 1940 15247 9631 22328 744 16602 1803 5044 2285 85 930 1984 13384 18032 16212 155...

result:

ok single line: '610 11483 11417 130 10050 1981...4529 13495 273 3162 1878 12077 '

Test #28:

score: 0
Accepted
time: 290ms
memory: 10492kb

input:

100000 10
9636 11440
49137 42457
45317 5295
19636 10086
11726 45456
37163 38783
4347 16824
49265 4605
3713 7153
34365 15926
73 49745
2358 48291
46794 12128
42022 32700
29326 1816
5796 16168
47419 5440
8471 41617
15307 7040
29433 40557
5763 14206
33855 43253
30383 12421
15685 44930
44196 26813
34399 ...

output:

44999 14092 84660 55274 2932 18838 33808 89739 44760 56731 3 274 72992 30933 75261 35604 87035 5589 55519 13863 38120 10465 59584 4131 42447 20667 62273 34755 58497 7314 44485 50611 43235 56920 17864 1886 7946 41819 21911 13701 75575 33128 4370 19528 44559 61681 56328 89402 59587 18511 27447 54938 1...

result:

ok single line: '44999 14092 84660 55274 2932 1...7 58662 59436 32248 1227 76392 '

Test #29:

score: 0
Accepted
time: 269ms
memory: 10400kb

input:

100000 10
39780 43875
13405 7050
35610 28065
16473 14614
12220 21850
22368 23049
47860 42101
3000 44429
15594 2573
25192 42726
42724 9799
11995 34608
37293 38494
29206 13232
37386 6055
17412 48017
39060 48444
36906 12840
18549 39987
35107 17168
12594 36776
49172 12446
38646 34847
17862 47884
16149 4...

output:

4570 7156 12139 7455 4430 8563 7194 225 9326 3318 24901 2587 7554 15159 23388 608 1713 19629 2930 16708 2307 28266 9788 668 1736 9558 1608 4631 279 33298 110 7950 4324 12747 16994 24452 256 22247 814 7084 4557 5801 242 25868 12604 6023 14156 3049 6747 9 19929 898 2136 27875 10606 6828 10436 0 6639 2...

result:

ok single line: '4570 7156 12139 7455 4430 8563...7 24228 24202 23412 8328 26254 '

Test #30:

score: 0
Accepted
time: 285ms
memory: 10456kb

input:

100000 10
12118 9245
38982 21964
49109 26067
28520 17222
26808 3533
27243 37549
1207 4176
2437 17627
31035 25509
34688 44392
31020 6055
18580 32505
22304 29321
48008 42058
32674 37334
32853 12242
3799 18421
17842 37144
27114 22703
39623 35572
38160 429
42348 7566
30963 2098
39034 18303
39690 43147
3...

output:

54096 48159 45123 51709 71881 18565 52259 36694 39480 8136 70684 24035 30428 13142 20108 61976 36463 16306 42707 24381 84130 75692 76657 54438 10834 22568 60799 63806 441 61164 8023 10787 64577 29750 29278 48925 61944 65740 56141 57795 35061 58849 42106 40051 47999 55953 56982 178 14850 17556 25842 ...

result:

ok single line: '54096 48159 45123 51709 71881 ...802 40559 23 48082 67568 43274 '

Extra Test:

score: 0
Extra Test Passed