QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#606951#1173. Knowledge Is...masterhuangWA 97ms13528kbC++231.0kb2024-10-03 13:11:442024-10-03 13:11:45

Judging History

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

  • [2024-10-03 13:11:45]
  • 评测
  • 测评结果:WA
  • 用时:97ms
  • 内存:13528kb
  • [2024-10-03 13:11:44]
  • 提交

answer

//qoj 1173
//https://qoj.ac/contest/537/problem/1173
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=5e5+5;
int n,m,p[N];
struct Node{int l,r,id;bool operator<(Node X){return (P){l,r}<(P){X.l,X.r};}}a[N];
struct node{int x,id;bool operator<(const node &X)const{return x>X.x;}};
priority_queue<node>q,Q;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r,a[i].id=i;
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)
	{
		auto [l,r,id]=a[i];
		if(q.size()&&q.top().x<l)
		{
			p[q.top().id]=p[id]=m--,q.pop(),Q.push({r,id});
			if(!m) break;
		}
		else if(Q.size()&&Q.top().x<r)
		{
			p[id]=p[Q.top().id];p[Q.top().id]=0;
			q.push(Q.top()),Q.pop(),Q.push({r,id});
		}
		else q.push({r,id});
	}
	for(int i=1;i<=n;i++) if(!p[i]){p[i]=m--;if(!m) break;}
	for(int i=1;i<=n;i++) cout<<p[i]<<" ";
	return 0;
}

详细

Test #1:

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

input:

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

output:

3 2 5 4 4 5 3 

result:

ok answer = 7

Test #2:

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

input:

2 2
1 2
3 4

output:

2 2 

result:

ok answer = 2

Test #3:

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

input:

2 1
1 2
2 3

output:

1 0 

result:

ok answer = 1

Test #4:

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

input:

1 1
4 26

output:

1 

result:

ok answer = 1

Test #5:

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

input:

500 258
1 3
3 5
2 4
3 5
4 5
4 5
1 4
1 2
3 5
2 5
2 5
4 5
4 5
4 5
2 3
1 4
1 4
1 4
4 5
4 5
2 3
4 5
3 5
3 5
1 5
1 4
2 5
1 5
3 5
3 4
4 5
2 3
3 5
3 5
4 5
2 3
1 5
1 5
2 3
2 3
3 4
3 5
3 4
1 3
1 2
1 5
4 5
2 3
2 4
1 3
4 5
4 5
4 5
1 3
3 5
4 5
3 5
1 5
1 2
1 2
3 5
3 5
4 5
3 4
3 5
2 3
2 5
2 4
2 5
3 5
2 3
1 5
4 5
...

output:

213 256 140 252 196 194 139 228 234 138 137 191 190 188 165 136 135 134 187 186 172 198 232 253 133 132 131 130 244 129 177 183 240 225 183 175 128 127 168 164 126 251 125 219 249 124 211 149 123 218 212 208 206 147 235 203 250 122 240 245 239 238 213 121 249 161 120 119 118 254 202 117 116 115 114 ...

result:

ok answer = 376

Test #6:

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

input:

500 242
8 9
9 10
2 9
8 10
9 10
6 10
4 8
4 5
2 6
7 10
3 8
1 8
1 6
5 9
7 8
8 10
8 9
8 10
2 9
2 3
6 8
3 10
5 9
1 3
6 8
4 10
9 10
8 9
8 10
1 9
3 9
3 7
2 3
6 10
3 6
6 10
3 4
3 6
9 10
5 7
8 10
6 10
5 6
5 7
7 8
1 3
4 7
9 10
4 9
2 4
8 9
1 3
8 10
3 4
9 10
4 9
5 10
8 9
1 3
1 5
8 10
3 4
8 9
3 9
3 6
3 10
6 7
7 ...

output:

13 69 12 93 73 176 61 174 161 155 44 34 173 215 56 220 115 89 11 235 15 10 9 230 27 236 35 122 119 8 7 84 234 183 140 184 215 137 29 102 84 181 146 97 73 224 123 39 233 205 127 229 100 211 20 228 204 126 238 185 77 216 116 6 129 242 98 65 5 63 164 130 225 172 103 56 23 4 119 3 35 67 66 2 51 169 83 1...

result:

ok answer = 471

Test #7:

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

input:

500 250
50 84
36 68
94 98
13 88
4 62
45 74
80 89
56 87
65 89
44 52
69 78
29 76
61 90
91 99
16 98
69 92
50 77
86 95
73 79
83 90
78 89
1 79
81 86
14 37
91 94
27 48
11 73
94 97
49 80
15 60
26 39
34 76
69 77
22 72
6 78
92 96
46 83
83 94
62 95
77 80
32 72
46 90
41 88
47 91
68 75
14 36
26 43
14 87
49 74
2...

output:

190 99 154 30 130 18 58 156 120 172 110 71 142 116 249 107 2 39 87 50 144 60 54 216 26 189 77 146 187 140 210 70 3 81 62 155 201 49 136 73 80 212 213 195 13 218 199 32 72 211 191 123 126 100 158 167 17 138 5 63 212 85 119 246 10 202 35 111 30 235 83 196 17 15 217 92 239 19 61 159 101 222 52 143 51 1...

result:

ok answer = 500

Test #8:

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

input:

500 250
614 964
380 709
272 969
626 788
156 927
270 842
448 984
184 224
602 953
249 887
665 904
212 300
715 787
557 948
906 977
117 824
504 567
848 884
817 824
462 930
768 816
890 940
193 784
653 897
973 974
21 64
515 700
361 595
670 1000
854 943
530 739
816 828
918 979
270 354
288 369
56 697
622 92...

output:

119 32 227 5 247 232 183 235 197 242 171 215 7 141 26 45 134 42 49 179 62 191 55 142 7 250 39 124 96 159 26 201 23 211 208 91 115 81 234 129 230 12 194 67 82 167 199 47 209 175 224 50 126 168 79 95 57 205 217 116 37 93 247 147 215 59 157 236 92 117 118 240 94 138 140 200 34 214 204 199 144 102 72 22...

result:

ok answer = 500

Test #9:

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

input:

500 250
7369 7544
7194 8983
8758 9759
1077 5486
8604 9375
9468 9854
9259 9276
6147 7585
2527 2818
1034 2634
1382 3694
1863 8040
5952 6207
685 3506
3618 9242
1204 3382
569 8063
6515 6861
6025 7856
2053 7457
961 3813
87 9321
2787 9389
4754 8473
6781 7817
7113 9489
6831 9207
5210 9788
7003 8417
9361 99...

output:

34 93 197 172 110 19 114 33 238 242 221 66 139 225 224 228 65 92 12 83 219 23 240 192 17 97 169 179 101 150 109 204 89 199 90 207 213 152 250 48 211 26 169 121 138 69 156 226 24 38 130 182 22 177 128 234 51 12 197 244 85 155 50 187 120 68 206 34 243 58 44 101 203 82 229 195 212 235 176 144 78 28 184...

result:

ok answer = 500

Test #10:

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

input:

500 250
94664 97792
42412 79567
78199 93246
1309 6050
21787 62661
32852 47312
72165 96025
22335 87724
98737 98949
32333 45109
98197 98696
66004 84303
64971 93765
48220 78217
75132 77121
3250 99214
76296 83179
18937 19783
24224 29268
76617 77302
64571 88215
56891 67172
32945 97861
75 35393
74113 9254...

output:

12 205 61 247 129 185 94 238 66 197 5 119 121 1 7 250 70 239 226 4 133 105 224 217 124 130 166 45 11 169 241 23 193 45 184 189 119 110 85 234 114 153 99 198 8 225 140 218 20 247 149 37 59 196 237 230 38 160 75 143 186 39 19 148 161 208 36 1 154 152 81 151 57 17 142 15 182 30 181 28 207 55 229 82 65 ...

result:

ok answer = 500

Test #11:

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

input:

500 250
249258 633953
692064 923461
236526 494453
63236 665418
813697 915066
231324 853677
850867 946695
354813 439441
555846 920488
978644 998640
280905 357712
300337 869138
111591 375301
754196 825433
681966 906746
566646 913535
958025 996696
122927 989918
162477 948024
464228 474279
735561 874801...

output:

121 101 170 112 64 46 110 188 165 163 213 227 209 127 108 153 9 247 243 176 84 199 192 74 53 38 78 57 3 163 207 105 142 95 158 238 221 195 79 143 13 169 79 45 142 63 164 38 139 36 145 69 145 186 129 45 13 116 120 196 76 194 71 171 205 198 100 167 22 85 138 140 156 133 77 115 118 224 74 241 174 168 9...

result:

ok answer = 500

Test #12:

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

input:

500 250
6592945 8873042
9610368 9920200
3224618 6472104
7312354 9075859
366928 6614625
7107690 8990826
4712035 4850963
8634845 9127832
7054047 9358572
9187658 9589004
6621468 7586829
7375455 9328669
2076424 5016969
8848028 9107864
6625184 7368290
801465 9195989
3228163 3972918
3386844 9342995
366556...

output:

133 13 128 178 121 158 200 143 111 30 31 161 195 100 53 28 216 238 122 218 149 199 77 79 233 9 91 231 234 99 67 208 52 126 42 94 76 123 40 120 113 5 22 221 4 77 168 31 108 29 88 95 124 115 117 174 144 194 39 202 203 245 95 200 153 233 2 78 68 174 98 155 23 141 249 82 222 105 50 190 165 83 136 184 23...

result:

ok answer = 500

Test #13:

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

input:

500 250
80571694 85803063
51768736 93848632
66413497 76615996
83050382 99992350
8073944 91324998
18047715 58689728
8708611 51201572
29489394 73271018
24239602 65348190
64220050 71579063
50414980 65877100
86190696 92867069
34515283 94334986
8551872 68258618
18296336 36436754
94799273 95174013
8666001...

output:

65 165 10 59 30 132 166 45 113 58 99 51 224 104 216 98 48 150 203 190 174 169 135 182 131 8 184 194 3 80 160 96 56 32 245 192 60 18 106 238 191 201 183 12 170 83 81 183 23 163 68 243 149 139 138 140 239 95 107 127 58 230 213 48 147 101 249 143 212 130 22 161 210 5 55 19 102 163 222 79 72 243 166 211...

result:

ok answer = 500

Test #14:

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

input:

500 250
966174904 986708402
946554500 952001265
914838165 993300555
89795526 975540133
235762788 364735276
340662053 547524158
330027012 366955963
633114013 756706517
868314624 992777729
843328851 965147665
943958099 956095329
243336632 710281553
576757478 948905845
778782824 978759308
370097409 470...

output:

225 131 212 6 213 155 212 31 192 230 17 96 147 74 182 3 19 205 75 30 39 182 247 190 187 110 238 152 47 163 203 98 122 200 233 2 179 5 178 199 61 238 115 165 173 102 153 145 105 82 66 122 6 209 51 78 138 146 114 129 144 11 15 19 86 81 33 246 28 189 64 89 128 250 35 176 154 11 132 159 126 214 125 14 8...

result:

ok answer = 500

Test #15:

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

input:

500 67
1 2
1 2
2 3
1 2
2 3
1 3
1 3
2 3
2 3
1 2
1 3
2 3
1 2
1 2
2 3
2 3
2 3
1 3
2 3
1 2
1 3
2 3
2 3
2 3
2 3
1 2
2 3
2 3
1 3
2 3
1 3
2 3
1 2
1 2
1 2
2 3
1 2
2 3
2 3
2 3
1 2
2 3
1 3
2 3
1 2
1 2
2 3
1 2
1 3
1 2
2 3
2 3
1 3
1 3
1 2
1 2
1 2
1 2
2 3
2 3
1 2
2 3
1 2
1 3
1 3
2 3
1 3
1 3
2 3
1 3
1 3
2 3
1 3
1...

output:

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

result:

ok answer = 67

Test #16:

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

input:

500 379
2 5
2 4
4 5
4 5
4 5
1 4
2 5
4 5
4 5
4 5
1 5
4 5
3 5
3 5
3 5
1 3
1 5
3 5
1 2
4 5
4 5
4 5
3 4
4 5
4 5
4 5
3 5
3 5
1 3
2 4
1 2
4 5
2 3
1 5
2 5
2 5
1 3
1 4
4 5
1 2
3 5
4 5
1 3
1 5
1 5
3 5
4 5
3 4
4 5
4 5
3 5
3 4
2 4
4 5
1 4
1 3
1 4
4 5
1 4
4 5
1 4
4 5
4 5
4 5
2 3
1 2
3 4
1 3
3 4
2 5
1 3
3 4
1 5
...

output:

275 274 346 337 347 273 272 311 314 315 271 317 351 270 269 338 268 267 357 331 333 335 266 332 325 323 265 264 342 263 354 316 298 262 261 260 345 259 310 349 359 309 347 258 257 348 344 256 345 342 255 254 253 339 252 281 251 250 249 248 247 246 245 244 287 365 243 326 242 241 330 240 239 322 238 ...

result:

ok answer = 483

Test #17:

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

input:

500 273
1 9
7 10
1 2
2 9
5 6
9 10
8 10
5 6
2 3
3 10
4 8
4 7
9 10
8 9
1 9
1 4
3 5
9 10
9 10
1 6
2 10
7 9
8 9
9 10
5 8
7 10
4 8
5 6
8 9
1 2
1 5
6 8
7 10
9 10
3 7
7 9
3 8
1 9
2 9
3 6
5 10
4 5
5 9
3 9
5 8
1 8
5 8
7 10
7 8
9 10
1 8
7 9
5 9
7 9
7 10
9 10
1 8
2 4
7 8
1 8
3 6
4 7
6 8
7 10
2 7
9 10
2 3
6 8
1...

output:

52 197 269 51 184 82 128 192 263 267 57 123 83 165 50 232 224 84 85 168 49 189 164 86 48 192 101 186 163 270 231 61 200 87 167 172 54 47 46 208 243 230 247 45 62 87 86 204 111 88 100 182 44 183 191 89 95 234 112 83 207 122 43 209 156 90 250 103 272 209 242 266 217 91 223 196 190 141 131 148 240 187 ...

result:

ok answer = 494

Test #18:

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

input:

500 250
47 82
75 84
56 61
27 57
32 48
28 85
15 38
36 39
56 65
88 94
87 97
64 79
15 51
50 93
83 100
74 77
59 74
66 99
57 78
51 90
47 76
64 68
89 97
15 71
38 54
57 83
26 91
90 94
98 100
70 73
40 75
52 82
67 100
14 85
57 62
47 53
40 63
79 97
3 33
16 61
4 94
94 99
68 80
23 30
41 81
54 81
51 52
36 45
54 ...

output:

197 80 131 149 192 233 216 213 111 26 30 128 177 186 175 7 17 113 1 178 64 44 98 78 163 155 234 117 4 18 70 191 106 34 128 167 115 54 224 134 10 12 104 229 209 166 173 199 171 74 6 210 200 163 79 50 18 220 129 181 108 28 93 139 29 168 190 105 55 182 49 156 71 21 148 7 223 170 60 112 31 47 142 52 124...

result:

ok answer = 500

Test #19:

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

input:

500 250
151 592
747 974
832 938
56 960
567 882
851 900
338 901
168 265
916 964
581 880
177 284
456 921
298 540
378 651
190 785
908 992
180 371
271 823
245 983
328 603
211 425
561 996
61 134
820 934
934 975
595 945
896 982
245 443
208 487
567 945
999 1000
483 748
882 887
383 459
607 910
57 797
12 771...

output:

130 73 45 10 142 39 214 223 80 136 219 186 152 108 59 21 207 224 230 126 199 145 247 48 16 130 25 191 168 173 1 23 30 185 126 54 64 231 178 29 167 121 192 214 227 172 114 181 244 119 95 170 232 137 111 245 66 134 44 203 153 125 131 6 63 122 187 43 3 22 79 37 33 81 186 12 182 57 235 239 14 210 151 23...

result:

ok answer = 500

Test #20:

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

input:

500 250
8878 9054
7943 8545
9886 9945
6698 8053
3466 6453
8106 8870
7114 9642
4807 4824
2334 4079
2778 3817
5111 7104
1252 4542
3555 6851
3663 5645
5567 7655
324 2086
4056 8603
1406 7470
9064 9448
1484 5836
7466 7945
2607 3711
5253 6112
3192 4008
9549 9852
9198 9709
4169 8558
2268 7806
5575 6209
826...

output:

30 60 3 105 111 54 91 159 202 208 48 185 99 142 22 238 205 74 24 137 78 212 121 204 13 21 203 65 118 160 227 76 24 229 45 207 188 96 236 214 40 6 219 23 5 48 246 134 61 170 77 115 119 35 78 240 166 109 133 153 200 49 168 178 185 28 224 101 219 11 53 56 147 152 70 158 135 191 9 165 176 61 84 155 163 ...

result:

ok answer = 500

Test #21:

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

input:

500 251
46165 49590
70151 85269
27899 40324
62135 64549
79159 94410
75003 79189
50178 81874
56192 88209
21577 95025
84261 96039
18414 90970
81196 83290
83331 83488
14574 39965
4268 32434
88164 89600
12144 29112
870 72365
9975 51580
92179 98369
28511 57700
33237 75390
24902 28700
94544 95300
65682 97...

output:

176 104 201 93 65 81 175 162 241 48 242 217 179 202 222 32 232 91 167 18 147 15 233 12 117 40 58 109 112 99 153 209 194 11 55 84 110 113 81 58 5 103 243 248 163 180 141 180 98 87 17 191 195 163 98 147 212 55 45 238 230 198 145 48 228 229 46 88 44 36 185 171 160 93 237 76 7 151 173 4 210 95 153 53 24...

result:

ok answer = 500

Test #22:

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

input:

500 250
997100 999305
50160 723310
530874 700434
482814 725372
898138 942005
227563 606578
465297 983061
288595 865469
971584 983736
84196 662089
716660 851207
874207 995804
742642 760966
412491 418432
721831 897885
453604 941851
404413 589262
363242 694198
71736 189776
340057 706243
591745 899767
9...

output:

1 75 37 28 177 132 188 222 7 100 90 172 6 199 88 189 144 86 235 84 145 9 130 4 96 97 9 63 243 155 105 41 239 128 70 97 6 244 159 117 26 51 157 86 223 207 39 16 38 79 173 50 62 39 136 247 129 208 223 206 127 14 125 215 15 107 248 94 213 134 94 11 32 232 8 132 36 18 148 158 66 21 156 209 188 184 144 2...

result:

ok answer = 500

Test #23:

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

input:

500 250
816808 8979893
577273 5159166
6890110 9974354
7539249 9013575
7780990 9685125
284302 8308896
2859745 8347237
5896988 9556377
4465806 5463028
8279297 8819929
1361353 5720171
2467636 8115256
5879674 7044297
661648 5198202
4725290 5204346
2612798 8161805
9812485 9996590
2285372 4614496
1962475 ...

output:

27 167 99 171 70 49 231 146 154 169 144 7 52 166 165 2 6 186 242 68 223 106 193 87 20 134 219 139 243 81 60 237 242 24 131 61 169 249 221 220 95 55 108 84 117 203 125 152 73 188 136 79 71 3 75 196 128 165 226 1 32 71 215 51 191 105 66 29 163 238 160 216 200 107 235 25 34 15 127 182 31 196 230 91 96 ...

result:

ok answer = 500

Test #24:

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

input:

500 250
81661382 94717306
89850268 94839225
72615579 73753927
19190949 39608724
129611 33966748
36897319 96344937
77381982 94746565
49637131 94881993
71774738 87773217
5955861 68864001
55863683 69339123
25998069 29895468
85528105 96959461
12833512 31610705
4726009 31932075
18119656 87239085
31722731...

output:

190 125 26 192 207 199 177 166 72 84 63 217 36 213 212 31 213 150 59 195 156 241 40 47 15 229 80 66 193 178 208 154 183 32 38 106 27 153 250 186 170 133 234 108 229 83 132 105 129 180 136 45 39 236 179 152 154 77 90 135 20 46 235 22 164 114 244 169 191 71 107 126 233 111 13 173 236 223 16 225 34 202...

result:

ok answer = 500

Test #25:

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

input:

500 250
159147753 849387872
678679305 958626578
736410066 762171088
51820203 846735349
483826312 744440062
76859389 682174032
127183476 195547079
339099076 948562984
46616987 234754210
871306758 893541852
261351936 390635591
441516403 995769500
522385081 715755202
729932064 859205804
998688267 99968...

output:

38 113 20 39 27 96 242 222 240 34 213 198 66 83 2 93 116 75 87 202 152 9 216 196 67 135 57 79 172 8 36 145 179 225 17 94 44 145 114 10 129 29 132 75 208 65 233 59 121 128 147 106 229 65 45 139 244 249 137 160 43 28 178 6 225 113 200 54 219 14 96 91 62 173 221 142 195 230 38 181 199 250 134 238 164 1...

result:

ok answer = 500

Test #26:

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

input:

500 236
1 3
1 3
1 2
2 3
2 3
1 3
1 3
2 3
2 3
1 3
2 3
1 2
1 2
2 3
2 3
1 2
1 2
2 3
2 3
2 3
2 3
1 3
2 3
1 2
2 3
1 2
1 2
1 3
1 3
2 3
2 3
1 3
2 3
2 3
2 3
2 3
1 2
1 2
1 3
2 3
2 3
2 3
1 2
1 3
1 2
1 2
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
1 3
2 3
1 2
2 3
1 3
1 2
1 3
1 2
2 3
2 3
2 3
1 3
2 3
2 3
1 2
2 3
2 3
2 3
2 3
...

output:

236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 162 ...

result:

ok answer = 236

Test #27:

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

input:

500 450
1 5
4 5
4 5
3 5
2 5
3 4
4 5
4 5
1 3
1 4
4 5
3 4
3 4
3 4
3 4
2 3
4 5
4 5
1 5
3 4
2 3
3 4
1 3
2 5
2 4
4 5
1 3
1 2
2 4
3 5
4 5
2 5
4 5
4 5
2 3
1 5
1 4
2 5
2 3
4 5
2 4
1 3
2 4
1 5
4 5
3 5
3 4
4 5
1 3
4 5
4 5
3 5
2 3
4 5
3 4
2 4
4 5
1 4
2 3
1 3
3 4
1 4
2 4
4 5
2 3
1 5
4 5
3 4
1 2
2 4
2 4
4 5
1 3
...

output:

345 365 364 450 344 343 363 362 400 342 361 341 340 339 338 367 360 359 337 336 369 335 399 334 333 358 409 442 332 449 357 331 356 355 379 330 329 328 383 354 327 419 326 325 353 324 323 352 351 366 350 322 378 349 321 320 348 319 415 397 318 317 316 347 418 315 346 314 428 313 312 311 371 310 347 ...

result:

ok answer = 500

Test #28:

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

input:

500 321
6 10
3 6
4 6
5 10
5 7
5 10
3 7
3 8
3 8
4 8
7 8
6 8
3 5
5 9
8 9
4 7
4 9
3 9
9 10
1 8
3 9
5 10
8 9
6 8
4 9
8 10
9 10
2 4
1 10
4 5
5 8
1 7
7 8
7 9
8 9
6 9
4 8
8 9
5 9
1 9
9 10
7 8
1 10
5 9
7 10
7 8
5 6
4 7
9 10
5 8
4 8
3 4
7 9
5 9
2 8
5 9
2 3
3 10
9 10
9 10
6 8
9 10
7 10
1 5
5 10
3 9
2 5
4 6
5 ...

output:

283 247 230 307 196 317 213 167 171 162 169 149 277 118 216 190 117 116 150 147 115 299 208 137 114 173 139 290 113 264 139 177 161 232 199 261 145 194 112 111 128 110 109 108 244 107 237 215 152 126 156 296 226 290 106 302 316 105 166 161 132 156 276 272 288 104 269 235 242 121 184 225 142 130 103 ...

result:

ok answer = 500

Test #29:

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

input:

500 282
8 65
78 90
26 99
97 99
94 95
1 56
62 73
41 87
46 51
70 78
81 99
15 52
98 100
39 54
31 53
20 34
9 77
75 84
2 29
4 79
92 96
6 34
23 28
4 7
11 65
3 90
63 69
48 72
82 95
41 93
47 53
65 92
46 76
39 87
25 60
87 97
18 53
10 18
68 100
31 69
38 74
15 57
40 54
16 33
46 68
77 78
42 88
45 72
14 47
2 10
...

output:

131 88 261 163 45 171 64 229 199 33 77 193 35 181 190 244 88 102 254 84 50 243 255 282 130 52 77 68 75 228 191 146 42 238 156 64 184 272 128 110 58 164 179 245 115 36 233 104 213 281 227 212 149 82 231 34 264 129 246 126 161 143 61 169 213 117 178 65 168 177 258 119 104 129 142 273 180 115 60 55 188...

result:

ok answer = 500

Test #30:

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

input:

500 300
510 553
741 866
603 700
36 128
503 944
356 533
43 466
917 960
375 678
38 84
603 748
900 954
951 972
25 548
965 980
204 928
541 594
362 453
904 939
4 547
322 583
870 911
359 470
397 896
772 953
95 483
527 853
631 748
886 955
178 468
127 202
249 912
869 887
154 386
688 948
847 853
783 908
881 ...

output:

141 130 97 295 219 206 235 156 149 300 65 142 63 197 59 288 139 239 77 198 182 255 231 252 239 227 246 69 81 234 288 279 89 252 149 96 117 83 94 56 186 187 127 79 137 249 228 152 107 171 97 222 276 260 179 172 87 119 153 233 157 203 287 237 188 206 207 244 223 180 95 131 160 274 258 82 242 258 189 2...

result:

ok answer = 500

Test #31:

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

input:

500 324
9666 9764
5 7711
5764 6747
2737 5398
4206 7020
351 4635
4073 5399
3611 9328
1945 8418
7455 9537
4107 8882
1584 6200
3868 4517
9853 9898
2506 4277
4014 7539
3274 7131
4991 9996
9163 9430
3958 6082
4305 9426
1905 6005
545 3515
7652 9689
1027 1438
1658 2555
3483 3669
3645 9546
3339 6780
368 978...

output:

196 145 136 236 164 260 235 295 123 166 278 203 268 271 274 107 160 267 286 209 274 214 293 157 319 312 289 290 176 79 202 156 202 198 270 141 231 137 192 181 298 256 242 253 190 156 284 104 178 264 91 305 211 87 247 206 224 187 207 223 122 215 154 122 186 172 203 108 193 126 319 77 138 118 135 254 ...

result:

ok answer = 500

Test #32:

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

input:

500 470
48935 84694
99749 99923
67360 75782
2621 28649
97920 99396
43999 62734
31792 93093
27130 95814
86217 97217
96404 98372
24819 99995
19043 61210
48522 67115
9948 85463
68373 86119
41827 44815
3885 70986
61638 63427
71822 81341
44961 51570
35696 82618
54669 54869
24868 37898
67579 83939
10309 5...

output:

387 221 238 444 224 329 439 448 407 340 451 335 288 256 317 401 294 308 343 378 430 365 422 309 379 416 276 380 361 394 405 396 452 317 257 448 267 291 239 260 272 423 469 436 262 283 470 221 362 348 235 460 419 295 280 305 355 253 441 270 322 331 234 402 395 411 394 368 435 312 381 227 431 278 396 ...

result:

ok answer = 500

Test #33:

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

input:

500 365
45762 693754
534202 559740
475894 692574
187566 781410
918494 925845
248194 930644
769148 995474
849975 944570
274210 388210
809281 978707
881685 943753
593867 809666
941967 942436
917009 921677
623403 694445
14648 44821
973042 987690
275841 883296
587146 857139
601250 981414
602336 913679
2...

output:

211 274 169 174 135 352 181 152 329 166 145 260 127 136 166 364 122 343 263 259 258 288 198 176 219 291 277 247 324 142 333 271 139 172 315 265 314 248 275 234 164 212 282 167 365 134 142 345 328 343 255 338 215 146 197 229 153 185 286 267 278 178 188 223 195 311 206 128 270 177 232 316 168 342 359 ...

result:

ok answer = 500

Test #34:

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

input:

500 435
8942882 9009137
2960339 4249642
6469497 9548984
1335505 1977271
8656424 8708138
8855830 9941526
120428 6845949
4297409 6050960
4211118 5999754
5292184 6371662
1257452 1532520
4172544 8586887
420009 9449705
9256685 9947310
6863833 8506653
5057204 7529960
4548338 8379192
3876868 8854349
331804...

output:

297 373 288 418 216 349 266 306 308 293 424 379 435 203 304 212 367 384 388 386 419 244 329 393 343 412 261 241 259 256 356 276 242 372 215 402 396 239 219 365 190 259 246 353 296 322 367 379 265 229 190 218 357 208 278 339 394 187 359 345 306 398 410 326 270 304 382 220 384 213 399 407 410 392 323 ...

result:

ok answer = 500

Test #35:

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

input:

500 331
9630011 57589654
22572747 68645689
38328399 81622066
94933642 97311408
58050148 62455346
37318915 88117879
68029610 74080275
87750454 92553676
46660595 74511474
32473872 49596859
63350036 89789394
75407776 80074289
80027461 88388093
61349773 99476335
69370190 83482845
70440345 73157341
67787...

output:

219 180 291 99 187 293 111 117 103 248 198 156 137 207 276 119 104 320 135 174 162 206 240 277 293 174 280 201 306 267 151 94 130 172 170 201 213 139 186 247 270 290 165 218 274 216 251 188 146 142 202 211 261 245 113 257 246 86 164 96 272 277 225 181 158 121 306 242 254 243 89 121 171 257 141 126 1...

result:

ok answer = 500

Test #36:

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

input:

500 477
343566419 927547482
827556406 860923139
786265094 867699424
768873550 983848460
587486802 980298997
991532621 996136199
878431940 941182908
689945290 738517801
517657626 628309437
983790110 985304593
272482247 338862765
740802646 818566102
938911500 949187177
185204729 426499829
724561978 76...

output:

441 462 285 292 396 295 253 270 347 233 440 387 242 422 246 279 384 425 275 274 320 436 244 378 459 335 426 258 367 413 349 410 275 254 236 316 298 261 377 302 470 346 379 344 249 410 239 433 452 247 266 371 346 363 289 258 450 340 282 333 385 338 420 273 318 406 383 235 374 305 232 453 229 447 335 ...

result:

ok answer = 500

Test #37:

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

input:

500 500
2 3
1 2
2 3
2 3
1 2
1 2
2 3
1 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
1 2
1 3
1 3
2 3
2 3
2 3
1 2
1 2
2 3
1 2
1 2
1 2
2 3
2 3
2 3
2 3
1 3
1 3
1 3
1 3
1 2
2 3
2 3
2 3
1 2
2 3
2 3
2 3
2 3
2 3
2 3
1 2
1 2
2 3
2 3
2 3
1 2
2 3
1 2
2 3
2 3
1 2
1 2
1 2
1 2
1 2
2 3
1 3
2 3
2 3
1 2
2 3
2 3
2 3
2 3
1 2
...

output:

500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 427 426 ...

result:

ok answer = 500

Test #38:

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

input:

300000 167770
1 5
1 3
1 2
2 3
2 5
2 4
1 2
4 5
4 5
2 5
4 5
4 5
3 4
4 5
3 5
4 5
1 4
2 4
2 5
3 4
4 5
4 5
1 3
4 5
4 5
2 5
4 5
2 3
3 4
3 4
1 3
2 5
2 4
4 5
2 5
3 5
2 5
2 3
4 5
4 5
4 5
3 4
2 4
3 4
4 5
2 5
1 2
2 4
3 4
2 3
1 3
2 5
2 5
2 4
1 3
4 5
3 4
1 3
4 5
3 4
4 5
1 4
2 4
1 3
2 3
1 5
1 2
4 5
4 5
1 4
3 4
2 ...

output:

105309 144654 153670 137455 105308 105307 153522 144863 144845 105306 144928 144938 105305 144895 105304 144746 105303 105302 105301 105300 144754 144765 109387 144770 144723 105299 144742 138357 105298 105297 108939 105296 105295 144813 105294 105293 105292 137820 144791 144795 145107 105291 105290...

result:

ok answer = 230231

Test #39:

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

input:

300000 158833
1 7
8 9
6 8
4 5
7 8
6 7
2 9
3 10
7 9
4 8
9 10
5 7
9 10
8 10
2 4
7 8
1 5
6 10
9 10
5 9
3 6
6 7
8 9
4 8
2 9
5 6
2 9
7 9
6 9
5 6
5 7
1 10
5 6
4 6
4 9
4 10
1 7
5 10
7 8
2 4
3 6
5 9
8 10
8 10
7 10
4 8
8 10
6 8
7 10
1 7
9 10
1 7
9 10
3 7
2 9
2 8
9 10
6 7
9 10
2 5
2 7
2 3
5 7
1 7
8 10
4 9
9 1...

output:

69356 82588 57796 129094 47562 80291 25105 25104 103668 25103 55879 91451 55882 60807 139162 47615 134362 119458 55886 139625 96821 75466 84632 40331 25102 93599 25101 104119 126570 108630 90990 25100 108858 100346 25099 151627 75010 144043 47459 139148 97620 137493 60780 60824 112232 30430 60839 39...

result:

ok answer = 292561

Test #40:

score: 0
Accepted
time: 71ms
memory: 12784kb

input:

300000 150009
55 66
55 72
76 99
74 95
20 64
60 85
52 62
54 100
62 73
30 62
60 96
99 100
66 76
10 23
4 20
59 76
67 76
54 95
2 93
18 56
98 100
59 64
63 100
16 29
95 97
40 83
84 93
41 84
37 92
34 51
53 100
98 99
80 88
18 34
68 76
20 74
54 55
16 78
38 55
86 89
8 47
18 81
66 75
60 69
22 66
44 89
19 71
4 ...

output:

65243 34390 71179 107269 69723 83726 77114 99051 27916 75458 85458 1471 15760 142208 144012 18806 15967 99367 9780 91393 2324 71182 74496 136430 128671 124423 94128 123074 129320 104270 101347 2967 94249 130894 16068 45909 94824 36725 93454 23599 111252 31202 19745 48523 63230 118365 51449 69292 940...

result:

ok answer = 299930

Test #41:

score: 0
Accepted
time: 79ms
memory: 13164kb

input:

300000 150001
494 988
672 774
243 913
828 988
37 677
885 943
710 899
735 934
920 922
965 966
140 442
673 881
899 974
326 433
1 144
518 752
965 990
177 532
625 672
530 670
899 994
856 986
262 864
146 442
771 873
671 978
813 927
449 894
888 965
785 926
508 798
502 849
521 735
503 886
119 511
840 894
2...

output:

106725 9881 140434 71348 59253 133318 111008 117741 12467 5317 115173 70264 134359 116869 146685 18908 38371 96861 52354 53662 15788 23334 138797 115179 84740 77773 108501 114226 125224 36539 211 103861 26000 103611 101713 58382 116162 90625 51122 61716 26322 90176 30288 124377 133558 11135 56622 11...

result:

ok answer = 300000

Test #42:

score: 0
Accepted
time: 81ms
memory: 12812kb

input:

300000 150000
3973 6094
9736 9998
70 8639
5326 8325
3999 7450
3662 6854
4709 4858
9516 9896
9504 9728
1704 4105
4802 6265
5454 9534
9173 9814
1798 4071
2241 3267
6925 9683
2779 4274
2065 9713
6068 8558
1614 8165
1662 4784
7247 9243
8942 9067
8742 9131
4327 8619
4359 4989
6812 8809
5706 7074
2583 708...

output:

77140 4080 21931 96757 21406 57136 106945 62241 75569 120421 72184 93806 13080 120959 131947 83422 117602 143117 77854 30434 108449 48404 16886 125015 116734 104191 79582 36952 51849 117715 72936 75963 10739 118478 65297 68112 93192 29742 94947 29202 114454 71498 87360 77921 10199 135315 114269 1122...

result:

ok answer = 300000

Test #43:

score: 0
Accepted
time: 88ms
memory: 12756kb

input:

300000 150000
12903 16631
31740 87010
65263 66809
76325 96234
6447 96997
93658 98279
37116 45312
40450 92176
39259 44730
68790 89767
37526 84109
33305 42208
63474 88851
92816 93071
32193 50697
34927 62503
48938 97474
32975 63610
1315 17769
30877 52937
60916 91584
14355 34674
63709 64927
6280 33513
5...

output:

145552 133024 54307 54834 149371 9903 113014 121180 114059 56745 125496 118286 70044 11250 102311 72817 106075 69644 144902 97442 77368 129454 63139 130897 94221 137420 2199 90611 1870 132927 67068 75662 130420 79387 90982 35260 149788 106200 77739 43640 74190 131580 134347 22944 86585 63549 96702 9...

result:

ok answer = 300000

Test #44:

score: 0
Accepted
time: 86ms
memory: 12852kb

input:

300000 150000
567775 666457
837755 984411
718168 903846
272041 566674
845286 892912
657558 706979
979998 984740
897850 920288
573988 604802
125953 702072
763586 844301
293648 334208
270686 660835
362992 482276
789500 805601
843735 845131
733248 894850
241109 377437
254656 819746
559713 638355
309262...

output:

54634 98036 49953 88740 25208 37159 3003 16179 78614 53508 125159 130915 63258 107491 35455 25488 46689 125257 139269 67664 63707 90373 115508 82931 67488 128603 70507 69366 4401 15634 118538 58999 82 145525 59300 147312 64636 25553 134974 124416 120160 1679 120449 132021 45554 108645 27209 59603 14...

result:

ok answer = 300000

Test #45:

score: 0
Accepted
time: 88ms
memory: 12828kb

input:

300000 150000
7170989 7769844
956107 2663875
9166687 9506653
1888701 7639977
3302208 7630940
4857987 7312608
3733996 4738647
3006274 9521928
6370314 7064994
3306420 5033814
2310651 5271171
1032455 6819687
7079130 9908748
3293168 3641704
1367057 7494712
4640369 8126591
3301376 9160271
5655785 6679644...

output:

8800 138304 13141 40599 14571 27757 109435 134858 38568 103483 98330 58126 52321 127161 43587 111333 131532 54910 37780 51864 72202 13323 135553 131418 99432 136123 142232 103866 130530 7413 1194 9738 51143 7337 2249 101053 66433 90345 27727 34032 75946 142242 134460 111706 88655 62588 63973 68293 1...

result:

ok answer = 300000

Test #46:

score: 0
Accepted
time: 94ms
memory: 12772kb

input:

300000 150000
11552304 25238941
57725800 74297686
59777617 68784124
34279072 42026700
59218385 84180847
89474693 95274286
95736555 96601153
35992390 95512251
71239164 91666139
97076370 97098897
40156523 62645281
32000954 57819471
60179257 88102512
5595628 31475314
55261116 84822976
71013050 92071206...

output:

139405 23251 46564 118905 82517 16742 6529 127709 51368 130718 72841 86227 79830 133240 94599 51874 3008 126588 89598 43954 112291 126970 37527 106743 100542 87938 123506 37203 58730 51708 107460 59114 23031 40862 138336 30240 133646 142930 126214 46944 68202 46939 70492 34347 81548 58896 43830 3092...

result:

ok answer = 300000

Test #47:

score: 0
Accepted
time: 97ms
memory: 12772kb

input:

300000 150000
654384400 971241348
70913001 607674248
792436692 958757039
493420264 606937015
872887558 973264081
626376272 682239078
582160167 908877630
658835446 733627713
385361776 871189995
334846500 367802854
124802907 643036263
443283183 775149618
514358696 672677144
480809185 562611368
6290012...

output:

64463 77468 34877 77682 20293 47891 84461 26397 123817 126272 67368 9147 52242 89401 2392 118893 77406 35095 97298 94249 115431 103561 72440 20965 97056 70695 34421 105279 69080 88774 138181 32826 89980 6958 29457 4644 20648 14772 26404 9619 46463 140753 56018 103556 29570 145644 110656 139877 32074...

result:

ok answer = 300000

Test #48:

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

input:

300000 259601
2 3
1 2
2 3
1 3
1 3
1 3
2 3
2 3
1 2
1 2
2 3
2 3
1 2
1 3
1 2
1 2
2 3
1 2
2 3
2 3
1 2
2 3
2 3
1 3
1 2
2 3
2 3
2 3
1 2
1 3
2 3
2 3
1 2
1 2
2 3
2 3
2 3
1 3
2 3
1 2
2 3
1 2
1 3
2 3
2 3
2 3
1 2
2 3
2 3
2 3
2 3
1 2
1 2
2 3
1 2
2 3
1 2
2 3
2 3
2 3
2 3
1 2
2 3
1 3
2 3
2 3
2 3
2 3
1 2
2 3
1 2
1 ...

output:

259601 259600 259599 259598 259597 259596 259595 259594 259593 259592 259591 259590 259589 259588 259587 259586 259585 259584 259583 259582 259581 259580 259579 259578 259577 259576 259575 259574 259573 259572 259571 259570 259569 259568 259567 259566 259565 259564 259563 259562 259561 259560 259559...

result:

ok answer = 259601

Test #49:

score: 0
Accepted
time: 50ms
memory: 12556kb

input:

300000 233601
3 5
3 4
1 3
1 4
2 3
2 5
1 2
3 5
4 5
2 4
4 5
3 4
1 2
1 5
2 4
1 4
2 3
2 3
4 5
4 5
2 5
2 3
2 3
2 5
2 3
2 5
4 5
2 4
2 4
3 4
3 5
3 4
2 4
4 5
3 4
2 4
3 4
3 4
4 5
4 5
1 5
1 3
2 4
3 5
2 4
4 5
1 3
2 5
4 5
3 5
4 5
2 3
3 5
1 5
2 3
1 5
3 5
3 5
3 5
3 5
3 4
4 5
2 5
3 4
2 5
2 3
2 3
2 3
3 5
2 3
1 3
4 ...

output:

171148 171147 173202 171146 184708 171145 227428 171144 206254 171143 206255 171142 227399 171141 171140 171139 184709 184717 206262 206233 171138 184719 184723 171137 184725 171136 206243 171135 171134 171133 171132 171131 171130 206286 171129 171128 171127 171126 206288 206292 171125 173197 171124...

result:

ok answer = 296054

Test #50:

score: 0
Accepted
time: 62ms
memory: 11148kb

input:

300000 156917
6 9
5 7
7 9
6 7
4 6
3 8
3 4
1 2
3 9
1 5
1 3
5 9
6 8
6 9
6 10
5 10
8 10
8 10
6 7
9 10
8 9
2 6
7 9
8 10
4 10
9 10
4 8
4 9
3 6
9 10
1 2
4 8
2 6
4 5
7 9
5 7
5 9
4 8
9 10
8 9
5 7
7 8
7 9
7 8
9 10
5 9
2 10
6 8
4 10
8 9
1 7
3 6
6 8
9 10
4 8
2 7
4 10
1 4
6 7
9 10
4 8
8 10
1 5
1 7
3 9
4 8
8 9
3...

output:

115895 88934 102879 74943 99166 25293 145043 156263 23230 132704 146157 137813 35193 131097 124178 140465 58277 58280 74908 54145 86917 98894 102897 58294 146119 54150 26921 23229 96376 54138 155961 35671 99045 126940 102977 83858 137790 34931 54101 86891 60773 38866 102988 38836 54110 137778 23228 ...

result:

ok answer = 290604

Test #51:

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

input:

300000 150061
40 82
23 24
73 94
66 67
66 93
17 75
27 51
54 69
84 92
39 48
14 77
9 21
45 90
44 82
41 63
92 94
63 85
11 47
73 95
86 94
17 92
35 47
45 64
35 67
93 99
65 97
38 74
56 65
23 78
3 54
27 77
79 91
70 72
88 92
17 88
19 37
87 91
99 100
11 61
26 80
73 98
91 93
11 13
89 94
43 98
90 97
70 73
9 30
...

output:

124176 141423 89303 54903 65505 42408 103169 47781 26503 108015 38945 143501 116372 118410 70897 12766 74844 111024 91765 120267 146424 111517 67952 60200 88723 68187 24957 67112 36544 96933 38984 35850 33836 111717 146637 126710 21212 93256 76823 33267 96292 14555 147850 17539 119014 69970 29864 13...

result:

ok answer = 299989

Test #52:

score: -100
Wrong Answer
time: 72ms
memory: 12808kb

input:

300000 149999
556 916
419 756
924 973
632 643
477 933
942 982
3 683
349 514
19 917
706 752
94 104
394 494
21 497
73 880
45 332
629 786
56 174
741 763
433 889
726 914
262 462
623 915
168 842
254 824
103 996
356 766
948 973
429 621
833 998
625 704
990 998
812 851
225 874
808 995
691 809
206 470
438 71...

output:

91870 17832 72415 65792 109054 133438 58239 101200 13131 19400 148357 105432 104918 19317 131509 5090 145219 14865 117249 69564 111780 74018 26043 139652 148456 13421 8151 74323 27698 38979 1404 31768 142028 112806 56610 110195 33162 108725 33934 58704 61015 70846 109024 32637 131617 42713 25217 147...

result:

wrong answer Integer -1 violates the range [0, 149999]