Checking an Alibi 测试数据集

发表于 | Edited on | 分类于 | 次阅读

题目来源

http://bailian.openjudge.cn/practice/2394/

解题思路

  • 这道题目就是计算从源点1到其他顶点之间的最短距离，使用Dijkstra算法即可实现，然后判断每头牛所在的点，判断其和源点1之间的距离是否不超过M。
  • 代码运行了很多遍之后发现老是出错，最后发现测试数据集中会出现重复的边，比如2 3 1，表示2号顶点到3号顶点距离为1，但是还会出现2 3 100，表示2号顶点到3号顶点最短距离是100，我的输入中构造图的时候就会更新为2号到3号的距离为100，但是实际计算按照1来计算，因此，读取P条边的时候，采用如下代码读取每条边的距离，结果一直无法通过。
1
2
3
scanf("%d%d%d",&x, &y, &w);
graph[x][y] = w;
graph[y][x] = w;

最后知道了错误后改用如下读取方式，最终AC了。

1
2
3
scanf("%d%d%d",&x, &y, &w);
graph[x][y] = min(graph[x][y],w);
graph[y][x] = min(graph[y][x], w);
  • 这算是一个经验教训吧，以后读取图的边的时候，不要随时更新，读取两个顶点的距离时，保存最小值就好。

算法实现

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

// 表示边的结构体
struct Edge {
	int from, to, distance;
	Edge(int f, int t, int d) :from(f), to(t), distance(d) {};
	bool operator <(const Edge& e)const { return this->distance > e.distance; };
};

// 计算从source出发，到图中每个顶点的最短距离
void dijkstra(const vector<vector<int>>& graph, const int source, vector<int>& distance) {
	vector<int> visit(graph.size(), 0);
	priority_queue<Edge> myQueue;
	visit[0] = 1;
	visit[source] = 1;
	for (int i = 1; i < graph.size(); ++i)
		if(visit[i]==0)
			myQueue.emplace(source, i, distance[i]);
	
	while (!myQueue.empty()) {
		Edge e = myQueue.top();
		myQueue.pop();
		if (visit[e.to] == 1)
			continue;
		visit[e.to] = 1;
		distance[e.to] = e.distance;
		for (int j = 1; j < graph.size(); ++j) {
			if (visit[j] == 0 && distance[e.to] + graph[e.to][j] < distance[j]){
				myQueue.emplace(e.to, j, distance[e.to] + graph[e.to][j]);
			}
		}
	}
}


int main() {
	int F, P, C, M;
	while (scanf("%d%d%d%d", &F, &P, &C, &M) != EOF) {
		vector<vector<int>> graph(F + 1, vector<int>(F + 1, static_cast<int>(1e9)));
		for (int i = 0; i < graph.size(); ++i)
			graph[i][i] = 0;
		for (int i = 0; i < P; ++i) {
			int x, y, w;
			scanf("%d%d%d",&x, &y, &w);
			graph[x][y] = min(graph[x][y],w);
			graph[y][x] = min(graph[y][x], w);
		}
		vector<int> cows(C, 0);
		for (int j = 0; j < C; ++j)
			scanf("%d",&cows[j]);
		vector<int> distance(graph[1]);
		dijkstra(graph, 1,distance);
		int ans = 0;
		for (int i = 0; i < cows.size(); ++i)
			if (distance[cows[i]] <= M)
				++ans;
		printf("%d\n",ans);
		for (int i = 0; i < cows.size(); ++i)
			if (distance[cows[i]] <= M)
				printf("%d\n",i+1);
	}
	return 0;
}

测试数据集

  • test case 1—input
1
2
3
4
5
6
7
8
9
10
11
12
7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7
  • test case 1—output
1
2
3
4
5
4
1
2
3
4
  • test case 2—input
1
2
3
1 1 1 1
1 1 1
1
  • test case 2—output
1
2
1
1
  • test case 3—input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
11 10 10 20
2 1 11
3 1 12
4 1 13
5 1 14
6 1 15
7 1 16
8 1 18
9 1 19
10 1 20
11 1 10
2
3
4
5
6
7
8
9
10
11
  • test case 3—output
1
2
3
4
5
6
7
8
9
10
11
10
1
2
3
4
5
6
7
8
9
10
  • test case 4—input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
3 2 10 4
1 2 3
3 1 10
2
2
2
2
3
3
3
2
2
2

  • test case 4—output
1
2
3
4
5
6
7
8
9
7
1
2
3
4
8
9
10

  • test case 5—input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
11 22 12 69999
1 2 69998
2 3 100
2 3 1
2 3 100
2 4 100
2 4 1
2 4 100
2 5 100
2 5 1
2 5 100
2 6 100
2 6 1
2 6 100
2 7 100
2 7 1
2 7 100
2 8 1
2 8 100
2 9 100
2 9 1
2 10 1
2 11 2
1
2
3
4
11
5
6
7
8
9
9
10
  • test case 5—output
1
2
3
4
5
6
7
8
9
10
11
12
11
1
2
3
4
6
7
8
9
10
11
12
  • test case 6—input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
5 5 10 100
1 2 50
2 3 50
3 4 50
4 5 50
2 5 10
1
2
3
4
5
5
4
3
2
1
  • test case 6—output
1
2
3
4
5
6
7
8
9
8
1
2
3
5
6
8
9
10
  • test case 7—input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
10 10 11 70000
1 2 10000
2 3 10000
3 4 10000
4 5 10000
5 6 10000
6 7 10000
7 8 10000
8 9 10000
9 5 10000
5 7 10000
6
5
4
7
7
8
9
3
2
1
10
  • test case 7—output
1
2
3
4
5
6
7
8
9
10
11
10
1
2
3
4
5
6
7
8
9
10
  • test case 8—input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
50 100 50 1000
43 10 336
19 34 625
11 36 300
36 24 4
4 39 546
43 36 973
37 39 967
37 31 531
8 18 843
5 9 86
28 48 115
32 28 81
18 37 699
40 27 695
11 50 185
45 47 610
28 38 167
39 44 848
23 4 311
33 2 712
7 8 150
15 3 100
30 23 329
13 23 730
29 3 927
48 46 329
13 5 994
19 41 465
2 25 825
34 12 923
6 31 569
13 16 550
46 36 995
17 35 647
18 47 154
29 19 335
27 46 432
15 12 704
16 30 232
22 47 18
50 15 362
35 36 620
8 24 506
21 36 570
21 36 503
47 12 409
38 33 452
7 40 272
42 18 552
29 26 500
27 13 398
44 9 766
46 32 993
37 12 699
5 2 671
50 5 865
11 22 278
11 7 689
21 35 253
15 14 823
18 14 90
46 11 512
10 16 17
33 16 743
9 43 181
43 7 43
47 22 194
45 7 606
1 6 637
18 25 661
12 21 37
16 1 440
23 6 188
13 2 251
39 29 519
36 43 183
32 35 477
32 30 54
14 23 85
15 46 176
20 49 330
30 46 70
24 44 538
9 1 217
30 23 16
36 39 141
5 4 825
41 30 31
45 16 762
34 21 37
31 17 1
21 18 563
29 21 341
10 39 55
16 34 803
24 39 24
25 38 240
45 16 484
40 41 901
9 45 232
15
31
22
38
35
40
34
12
45
33
37
41
21
18
18
30
42
24
26
31
41
29
21
41
31
23
9
15
44
33
43
16
29
16
33
43
12
21
27
9
12
21
32
33
5
49
23
3
43
35

  • test case 8—output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
24
1
4
6
9
12
14
15
16
18
21
24
26
27
28
29
31
32
34
36
40
43
45
47
49
  • test case 9—input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
500 100 100 70000
244 51 1
285 491 1
497 30 1
196 105 1
430 202 1
397 155 1
39 236 1
257 19 1
395 122 1
75 91 1
364 55 1
77 451 1
44 322 1
374 430 1
83 200 1
207 70 1
100 488 1
434 430 1
315 383 1
270 146 1
157 238 1
147 241 1
406 114 1
460 273 1
361 344 1
290 76 1
485 343 1
257 346 1
424 439 1
72 396 1
240 135 1
187 127 1
297 297 1
242 376 1
145 214 1
422 342 1
449 428 1
173 53 1
219 151 1
113 177 1
323 468 1
23 96 1
207 401 1
179 403 1
322 94 1
131 331 1
185 328 1
143 183 1
429 193 1
350 2 1
332 297 1
61 327 1
483 317 1
365 247 1
117 237 1
118 108 1
373 203 1
156 54 1
488 212 1
338 490 1
117 475 1
402 217 1
316 94 1
247 364 1
34 18 1
476 333 1
210 368 1
398 9 1
106 275 1
15 47 1
71 201 1
122 170 1
27 109 1
236 454 1
222 137 1
259 244 1
89 328 1
52 28 1
441 183 1
307 328 1
2 194 1
153 495 1
69 78 1
252 293 1
379 158 1
370 279 1
426 376 1
295 234 1
230 329 1
191 482 1
406 201 1
10 351 1
311 280 1
460 10 1
331 450 1
204 498 1
227 247 1
166 64 1
179 476 1
22 296 1
185
218
34
78
277
87
371
336
21
342
118
423
229
132
441
66
355
447
50
227
45
96
210
284
100
245
388
32
126
213
157
459
6
334
342
102
279
300
445
1
400
293
37
318
181
154
108
425
423
346
63
273
308
74
62
498
440
205
498
305
133
472
176
415
365
25
115
420
120
353
85
294
123
279
1
493
395
43
148
37
313
358
345
280
459
34
420
236
409
254
209
102
456
42
270
473
462
285
167
105

  • test case 9—output
1
2
3
2
40
75
  • test case 10—input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
50 1000 100 69999
15 13 70000
42 48 70000
48 47 70000
25 50 70000
34 31 70000
28 16 70000
26 28 70000
6 48 70000
14 46 70000
26 38 70000
27 2 70000
5 40 70000
43 35 70000
29 12 70000
37 14 70000
10 10 70000
40 37 70000
13 7 70000
27 22 70000
42 15 70000
20 44 42351
7 38 70000
47 20 70000
36 22 70000
48 40 70000
20 8 70000
23 48 70000
10 23 70000
35 6 70000
25 2 70000
29 30 70000
1 34 25649
4 45 70000
8 30 70000
24 3 25772
41 2 70000
43 49 70000
29 47 70000
1 26 46450
32 17 70000
25 12 70000
2 43 70000
41 37 57658
15 45 70000
4 50 70000
16 33 70000
27 19 70000
12 2 70000
32 18 70000
2 22 70000
28 37 70000
43 24 70000
1 14 34964
21 9 70000
44 34 70000
18 11 70000
47 50 70000
27 1 70000
11 43 70000
4 25 70000
50 7 70000
30 36 70000
45 15 70000
50 48 70000
2 17 70000
37 33 70000
37 28 70000
10 34 70000
21 5 70000
14 12 70000
30 36 70000
3 18 70000
25 42 9223
29 11 70000
18 40 70000
30 18 70000
22 34 70000
42 5 70000
1 9 70000
50 23 70000
44 18 70000
4 36 70000
9 36 70000
32 47 70000
13 44 70000
45 14 70000
12 39 70000
14 41 70000
23 43 70000
41 35 66210
21 31 69450
11 1 70000
15 41 70000
8 20 70000
23 16 70000
13 13 70000
47 25 70000
27 11 70000
10 24 70000
15 11 70000
32 12 58003
5 37 70000
40 33 70000
41 38 70000
47 37 70000
21 48 70000
44 12 70000
20 31 70000
8 27 70000
2 49 70000
38 33 70000
6 27 70000
33 11 70000
16 32 70000
44 36 70000
34 37 70000
49 10 70000
44 10 70000
23 9 70000
12 19 70000
5 37 70000
41 47 70000
17 28 70000
30 17 70000
29 19 70000
39 26 70000
46 47 70000
35 34 70000
7 17 70000
50 36 70000
32 3 70000
21 40 70000
41 41 70000
29 35 70000
46 31 70000
43 24 70000
19 27 70000
15 24 70000
12 2 70000
23 1 70000
3 48 70000
22 5 70000
41 44 70000
41 13 70000
8 13 70000
22 10 70000
3 23 70000
9 45 70000
47 4 70000
37 23 70000
35 27 70000
44 44 70000
17 34 70000
5 34 70000
25 2 70000
33 15 70000
23 31 70000
20 24 39168
7 3 70000
26 31 70000
2 40 70000
44 48 70000
43 28 70000
46 29 70000
7 15 70000
8 43 70000
38 42 31588
13 49 70000
9 33 70000
1 29 70000
11 22 70000
43 29 70000
47 33 70000
28 45 70000
8 8 70000
16 16 70000
12 34 70000
10 17 70000
27 24 70000
10 20 70000
12 2 70000
14 48 70000
45 35 70000
23 14 70000
35 12 70000
49 45 70000
11 3 70000
24 33 70000
17 33 70000
12 23 70000
29 24 70000
6 24 70000
9 29 70000
47 35 70000
20 41 70000
37 6 70000
7 40 70000
48 10 70000
24 31 70000
2 34 70000
27 23 70000
32 12 70000
46 43 70000
23 7 70000
40 9 70000
7 10 70000
39 9 5401
14 46 70000
20 45 70000
18 23 70000
38 36 70000
39 5 70000
50 6 70000
2 39 70000
41 43 49787
40 34 70000
46 25 18391
7 33 70000
1 13 70000
7 24 70000
2 42 70000
27 14 70000
10 33 70000
7 28 70000
24 5 70000
44 38 70000
30 41 70000
9 10 70000
48 49 70000
24 5 70000
3 4 70000
1 5 70000
7 12 50231
48 25 70000
36 32 70000
46 27 70000
18 10 70000
13 38 70000
25 28 70000
10 17 70000
40 1 70000
23 40 70000
5 48 70000
38 47 70000
32 29 70000
3 6 70000
17 40 70000
39 38 70000
27 7 70000
43 10 70000
32 19 70000
21 9 70000
29 25 70000
32 3 70000
46 47 70000
39 43 70000
22 19 70000
50 31 70000
29 50 70000
32 32 70000
48 33 70000
24 24 70000
43 49 70000
40 10 70000
43 3 70000
34 2 70000
34 19 70000
4 46 70000
16 33 70000
21 5 70000
33 12 70000
36 13 70000
39 43 70000
20 26 70000
49 34 70000
43 36 70000
15 12 70000
40 49 70000
36 2 70000
42 21 12130
4 41 70000
38 20 70000
10 16 70000
34 39 70000
17 13 70000
47 34 70000
29 7 70000
16 9 70000
17 49 70000
18 33 70000
40 26 70000
36 30 70000
23 22 70000
25 22 70000
48 48 70000
39 21 70000
3 36 70000
30 43 70000
38 10 56654
6 6 70000
45 40 70000
11 16 70000
23 22 70000
47 48 70000
14 44 70000
43 25 8359
8 43 70000
13 19 70000
50 25 70000
17 10 70000
8 11 70000
8 31 70000
41 23 70000
29 7 70000
41 28 20261
11 33 70000
16 41 70000
16 7 70000
17 27 70000
40 50 70000
12 42 70000
31 42 70000
22 13 70000
14 47 70000
31 16 70000
43 44 70000
19 48 70000
16 44 70000
3 7 70000
33 40 70000
17 30 70000
46 16 70000
11 48 70000
9 4 32110
2 20 70000
34 17 24471
38 39 70000
22 7 70000
31 46 70000
17 37 70000
46 8 51655
33 50 70000
17 17 70000
43 15 70000
17 49 70000
14 7 70000
16 7 70000
27 24 70000
1 17 70000
13 37 70000
30 23 70000
46 36 70000
12 23 70000
2 47 70000
13 44 70000
38 6 70000
23 16 70000
5 29 70000
10 8 70000
43 16 70000
5 14 64476
3 47 70000
24 8 70000
16 33 70000
46 13 70000
11 29 70000
24 34 70000
32 36 70000
8 48 70000
33 34 70000
38 42 70000
5 39 70000
15 44 70000
24 45 70000
14 11 70000
45 34 55601
16 40 70000
50 29 70000
32 8 70000
16 44 70000
10 29 70000
19 8 70000
27 50 70000
12 35 70000
19 30 70000
31 17 70000
20 25 70000
32 46 70000
6 41 70000
44 8 70000
29 45 70000
16 9 70000
25 14 70000
5 47 70000
33 41 70000
23 9 70000
30 1 70000
13 43 70000
14 15 70000
31 26 70000
10 29 70000
38 28 70000
10 13 70000
39 25 70000
32 13 70000
46 16 70000
2 44 70000
40 27 70000
17 47 70000
34 12 70000
3 31 70000
12 1 11365
14 17 70000
50 14 70000
45 24 70000
21 32 70000
43 29 70000
12 18 70000
32 28 70000
45 42 70000
8 13 70000
26 37 70000
30 14 70000
16 22 70000
16 8 70000
6 17 70000
11 9 70000
7 30 70000
23 9 70000
13 44 70000
45 14 70000
30 33 70000
36 34 70000
14 16 70000
40 40 70000
2 3 70000
14 45 70000
43 19 70000
44 8 70000
13 46 70000
45 40 70000
15 25 70000
13 47 70000
21 3 70000
38 39 70000
38 48 70000
32 3 70000
43 33 70000
46 1 70000
35 4 70000
27 7 70000
43 24 70000
6 17 70000
41 17 70000
49 34 70000
42 25 67081
12 37 70000
12 29 70000
1 6 70000
8 30 70000
44 15 70000
32 50 70000
39 14 70000
43 40 22715
30 40 70000
20 26 70000
22 28 70000
13 37 70000
26 42 70000
3 22 70000
15 3 70000
31 37 70000
20 24 70000
39 41 70000
11 44 70000
45 27 70000
8 50 70000
21 32 70000
36 2 70000
13 47 70000
47 6 70000
7 40 70000
6 26 70000
47 18 70000
11 28 70000
31 43 70000
40 48 70000
23 50 70000
43 5 18256
8 13 70000
12 34 70000
31 45 70000
6 37 70000
5 15 70000
17 18 70000
47 27 70000
21 22 70000
13 12 70000
42 24 70000
31 2 70000
2 49 70000
48 47 70000
15 26 70000
3 46 70000
16 45 70000
39 50 70000
43 45 70000
24 22 70000
49 28 70000
37 35 70000
34 14 70000
43 44 70000
13 26 70000
8 41 70000
20 18 70000
40 39 70000
10 26 70000
26 1 70000
48 28 70000
15 29 56279
16 19 70000
36 47 70000
5 7 20142
27 33 70000
44 14 70000
31 12 70000
24 49 70000
37 11 70000
41 19 70000
38 26 70000
10 4 70000
8 35 70000
36 47 70000
18 36 70000
38 47 68543
39 20 70000
20 22 70000
36 47 70000
31 2 70000
40 26 70000
11 13 70000
25 40 70000
26 21 31323
14 41 70000
17 29 70000
12 2 70000
20 46 70000
13 10 70000
15 9 70000
21 40 70000
24 12 58373
20 23 70000
17 48 70000
27 8 70000
36 15 70000
50 45 70000
11 46 70000
7 11 23623
11 14 70000
19 35 50735
33 36 70000
27 24 70000
1 8 70000
32 38 70000
4 47 70000
29 47 70000
3 48 70000
39 29 70000
5 14 70000
3 18 70000
35 21 70000
41 2 70000
48 35 70000
31 48 70000
12 7 70000
8 23 70000
20 12 70000
50 45 70000
6 44 70000
44 27 70000
24 6 70000
15 40 70000
49 48 70000
39 14 70000
20 2 70000
24 8 70000
4 8 70000
42 10 70000
5 11 70000
14 19 70000
29 11 70000
9 40 70000
40 29 70000
20 15 70000
26 37 70000
18 29 70000
34 3 70000
38 16 70000
27 6 70000
39 39 70000
44 18 36647
34 39 70000
13 46 70000
11 40 70000
20 16 70000
18 31 70000
36 6 70000
25 26 70000
27 22 70000
40 45 70000
43 21 70000
8 9 31897
32 43 70000
35 3 70000
28 4 70000
4 20 70000
28 32 70000
7 31 70000
48 27 70000
44 15 70000
19 38 70000
32 16 70000
37 14 70000
20 40 70000
37 40 70000
42 46 70000
20 45 70000
44 49 70000
27 27 70000
21 48 70000
22 37 70000
34 1 70000
44 3 70000
21 29 70000
17 39 70000
31 38 70000
1 7 70000
35 15 70000
18 14 70000
34 24 70000
20 45 70000
5 31 70000
32 36 70000
13 33 70000
15 41 70000
22 49 70000
3 42 70000
30 33 70000
21 49 32764
2 13 70000
1 16 70000
33 3 70000
20 7 70000
17 9 70000
26 2 70000
13 23 70000
38 7 70000
7 32 70000
6 49 70000
31 9 7007
18 21 70000
8 28 70000
34 35 70000
3 47 70000
22 18 70000
46 15 70000
34 12 70000
22 37 70000
11 47 70000
37 23 70000
42 30 70000
10 17 70000
10 33 59253
50 22 70000
48 36 70000
33 10 70000
50 33 70000
5 27 70000
40 12 70000
17 30 70000
25 11 70000
6 20 70000
44 30 70000
32 20 70000
5 2 70000
1 27 70000
47 6 70000
24 6 70000
4 24 52172
20 13 70000
23 36 70000
12 1 70000
34 14 70000
42 8 70000
49 20 39251
18 42 70000
45 42 70000
20 49 70000
12 48 70000
31 40 70000
48 5 70000
19 41 70000
39 6 70000
3 18 70000
14 45 70000
41 27 70000
20 19 70000
3 2 70000
18 10 70000
35 29 70000
25 2 43307
3 5 70000
42 36 70000
38 17 70000
18 13 70000
1 21 70000
35 50 70000
4 33 70000
12 9 70000
12 18 70000
21 34 61567
17 17 70000
44 31 70000
12 43 70000
48 16 70000
34 19 70000
47 30 70000
3 3 70000
17 7 70000
49 45 70000
34 43 70000
5 36 70000
4 1 70000
43 47 70000
32 33 70000
4 4 70000
6 23 70000
42 34 70000
49 11 70000
20 14 70000
42 30 70000
12 30 70000
38 15 70000
23 24 70000
16 21 70000
3 41 70000
33 34 70000
50 32 70000
39 3 70000
24 29 70000
1 8 14922
34 41 70000
32 10 70000
46 49 70000
40 13 70000
47 42 70000
28 20 70000
47 49 70000
21 30 70000
25 22 52878
33 14 70000
36 6 61445
27 23 70000
50 7 70000
25 6 70000
35 9 70000
14 32 70000
26 8 70000
45 37 70000
39 15 70000
3 11 70000
2 41 70000
50 11 70000
11 23 70000
40 1 42369
26 48 70000
40 2 70000
35 5 70000
40 41 70000
28 22 36519
6 12 70000
33 29 70000
33 31 70000
37 20 70000
35 25 70000
32 27 70000
42 1 70000
49 36 37672
34 35 70000
23 9 70000
42 3 70000
33 50 70000
20 20 40293
13 28 70000
13 27 70000
36 39 70000
49 17 70000
25 1 70000
42 36 70000
43 27 70000
19 13 70000
36 16 70000
50 7 70000
48 35 70000
36 33 70000
13 26 70000
35 7 70000
37 35 70000
2 9 70000
8 17 70000
42 15 70000
45 21 70000
42 42 70000
50 22 70000
50 23 70000
29 36 70000
36 16 70000
42 47 70000
7 27 56677
4 13 70000
3 5 70000
41 1 70000
42 15 70000
38 42 70000
1 13 70000
15 47 70000
3 32 70000
30 19 25996
3 23 70000
2 37 70000
20 20 70000
47 21 70000
20 30 70000
39 21 70000
29 6 70000
20 28 70000
35 33 70000
29 44 70000
43 44 70000
35 9 70000
37 15 70000
20 25 6496
24 4 70000
6 10 70000
14 27 70000
28 8 70000
18 24 70000
13 2 70000
23 22 70000
30 5 70000
14 33 70000
12 49 70000
44 8 70000
22 38 70000
44 18 68081
33 7 70000
2 20 70000
30 5 70000
32 32 70000
28 32 70000
17 31 70000
16 16 70000
41 28 58544
1 26 70000
36 48 70000
1 42 70000
48 36 70000
11 26 70000
49 47 70000
27 48 447
1 18 70000
23 2 70000
1 32 11950
44 23 70000
22 49 46018
35 2 70000
12 21 4682
15 17 70000
31 23 70000
10 10 70000
41 32 70000
34 40 70000
32 4 70000
21 28 70000
7 5 70000
6 8 70000
4 10 70000
5 27 70000
21 46 70000
36 14 70000
30 9 70000
17 45 53013
43 44 70000
48 49 70000
19 44 70000
19 7 70000
28 11 70000
10 33 70000
27 15 70000
44 2 70000
43 2 70000
9 8 70000
24 24 70000
12 18 70000
9 46 70000
8 41 70000
9 37 70000
19 41 47051
46 34 70000
21 5 70000
36 6 70000
36 15 70000
34 1 70000
47 26 70000
6 33 70000
21 34 70000
22 1 70000
33 35 41278
6 47 70000
40 21 70000
40 41 70000
21 37 70000
41 15 70000
33 43 70000
7 44 70000
19 33 70000
35 12 70000
40 35 70000
11 23 70000
47 41 70000
13 36 29655
6 18 70000
33 7 70000
32 45 70000
42 10 70000
1 25 16284
48 10 70000
35 40 56206
22 7 70000
24 50 70000
10 22 70000
18 39 70000
17 27 70000
21 13 70000
47 18 70000
44 3 70000
18 9 21396
20 15 70000
12 20 70000
41 50 70000
18 13 70000
13 36 70000
14 11 70000
39 20 70000
25 38 70000
48 4 70000
2 25 70000
24 12 70000
16 1 70000
29 44 70000
35 5 70000
22 19 70000
39 25 70000
7 47 18704
47 34 70000
41 34 70000
1 48 70000
20 3 70000
43 10 70000
20 43 70000
2 27 70000
46 41 70000
33 47 70000
47 43 70000
48 24 70000
31 4 70000
38 1 70000
37 44 70000
24 42 70000
27 31 70000
17 35 69703
27 41 70000
46 30 70000
36 32 70000
39 43 70000
44 41 70000
8 37 70000
7 18 70000
17 42 70000
1 42 70000
32 15 70000
23 10 70000
10 19 70000
38 28 70000
14 10 70000
32 17 70000
32 12 70000
30 32 70000
39 31 70000
19 37 70000
7
50
35
9
23
8
28
17
50
33
26
20
1
5
26
50
50
12
42
6
47
30
3
48
50
46
47
32
10
17
1
23
48
20
16
18
3
14
49
13
25
22
7
38
34
22
36
15
46
32
26
19
3
39
18
4
29
43
50
44
13
48
28
26
30
15
27
3
20
48
19
17
33
36
31
36
11
21
3
17
47
14
7
43
32
50
41
29
1
14
21
22
31
14
9
16
46
14
37
20

  • test case 10—output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
52
1
4
6
8
11
12
13
14
15
18
19
26
28
30
31
34
36
38
39
41
42
43
44
45
46
49
50
51
54
55
58
60
64
69
72
75
78
80
82
83
84
85
89
90
91
92
93
94
95
97
98
100
  • test case 11—input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
500 499 100 70000
1 2 141
2 3 141
3 4 141
4 5 141
5 6 141
6 7 141
7 8 141
8 9 141
9 10 141
10 11 141
11 12 141
12 13 141
13 14 141
14 15 141
15 16 141
16 17 141
17 18 141
18 19 141
19 20 141
20 21 141
21 22 141
22 23 141
23 24 141
24 25 141
25 26 141
26 27 141
27 28 141
28 29 141
29 30 141
30 31 141
31 32 141
32 33 141
33 34 141
34 35 141
35 36 141
36 37 141
37 38 141
38 39 141
39 40 141
40 41 141
41 42 141
42 43 141
43 44 141
44 45 141
45 46 141
46 47 141
47 48 141
48 49 141
49 50 141
50 51 141
51 52 141
52 53 141
53 54 141
54 55 141
55 56 141
56 57 141
57 58 141
58 59 141
59 60 141
60 61 141
61 62 141
62 63 141
63 64 141
64 65 141
65 66 141
66 67 141
67 68 141
68 69 141
69 70 141
70 71 141
71 72 141
72 73 141
73 74 141
74 75 141
75 76 141
76 77 141
77 78 141
78 79 141
79 80 141
80 81 141
81 82 141
82 83 141
83 84 141
84 85 141
85 86 141
86 87 141
87 88 141
88 89 141
89 90 141
90 91 141
91 92 141
92 93 141
93 94 141
94 95 141
95 96 141
96 97 141
97 98 141
98 99 141
99 100 141
100 101 141
101 102 141
102 103 141
103 104 141
104 105 141
105 106 141
106 107 141
107 108 141
108 109 141
109 110 141
110 111 141
111 112 141
112 113 141
113 114 141
114 115 141
115 116 141
116 117 141
117 118 141
118 119 141
119 120 141
120 121 141
121 122 141
122 123 141
123 124 141
124 125 141
125 126 141
126 127 141
127 128 141
128 129 141
129 130 141
130 131 141
131 132 141
132 133 141
133 134 141
134 135 141
135 136 141
136 137 141
137 138 141
138 139 141
139 140 141
140 141 141
141 142 141
142 143 141
143 144 141
144 145 141
145 146 141
146 147 141
147 148 141
148 149 141
149 150 141
150 151 141
151 152 141
152 153 141
153 154 141
154 155 141
155 156 141
156 157 141
157 158 141
158 159 141
159 160 141
160 161 141
161 162 141
162 163 141
163 164 141
164 165 141
165 166 141
166 167 141
167 168 141
168 169 141
169 170 141
170 171 141
171 172 141
172 173 141
173 174 141
174 175 141
175 176 141
176 177 141
177 178 141
178 179 141
179 180 141
180 181 141
181 182 141
182 183 141
183 184 141
184 185 141
185 186 141
186 187 141
187 188 141
188 189 141
189 190 141
190 191 141
191 192 141
192 193 141
193 194 141
194 195 141
195 196 141
196 197 141
197 198 141
198 199 141
199 200 141
200 201 141
201 202 141
202 203 141
203 204 141
204 205 141
205 206 141
206 207 141
207 208 141
208 209 141
209 210 141
210 211 141
211 212 141
212 213 141
213 214 141
214 215 141
215 216 141
216 217 141
217 218 141
218 219 141
219 220 141
220 221 141
221 222 141
222 223 141
223 224 141
224 225 141
225 226 141
226 227 141
227 228 141
228 229 141
229 230 141
230 231 141
231 232 141
232 233 141
233 234 141
234 235 141
235 236 141
236 237 141
237 238 141
238 239 141
239 240 141
240 241 141
241 242 141
242 243 141
243 244 141
244 245 141
245 246 141
246 247 141
247 248 141
248 249 141
249 250 141
250 251 141
251 252 141
252 253 141
253 254 141
254 255 141
255 256 141
256 257 141
257 258 141
258 259 141
259 260 141
260 261 141
261 262 141
262 263 141
263 264 141
264 265 141
265 266 141
266 267 141
267 268 141
268 269 141
269 270 141
270 271 141
271 272 141
272 273 141
273 274 141
274 275 141
275 276 141
276 277 141
277 278 141
278 279 141
279 280 141
280 281 141
281 282 141
282 283 141
283 284 141
284 285 141
285 286 141
286 287 141
287 288 141
288 289 141
289 290 141
290 291 141
291 292 141
292 293 141
293 294 141
294 295 141
295 296 141
296 297 141
297 298 141
298 299 141
299 300 141
300 301 141
301 302 141
302 303 141
303 304 141
304 305 141
305 306 141
306 307 141
307 308 141
308 309 141
309 310 141
310 311 141
311 312 141
312 313 141
313 314 141
314 315 141
315 316 141
316 317 141
317 318 141
318 319 141
319 320 141
320 321 141
321 322 141
322 323 141
323 324 141
324 325 141
325 326 141
326 327 141
327 328 141
328 329 141
329 330 141
330 331 141
331 332 141
332 333 141
333 334 141
334 335 141
335 336 141
336 337 141
337 338 141
338 339 141
339 340 141
340 341 141
341 342 141
342 343 141
343 344 141
344 345 141
345 346 141
346 347 141
347 348 141
348 349 141
349 350 141
350 351 141
351 352 141
352 353 141
353 354 141
354 355 141
355 356 141
356 357 141
357 358 141
358 359 141
359 360 141
360 361 141
361 362 141
362 363 141
363 364 141
364 365 141
365 366 141
366 367 141
367 368 141
368 369 141
369 370 141
370 371 141
371 372 141
372 373 141
373 374 141
374 375 141
375 376 141
376 377 141
377 378 141
378 379 141
379 380 141
380 381 141
381 382 141
382 383 141
383 384 141
384 385 141
385 386 141
386 387 141
387 388 141
388 389 141
389 390 141
390 391 141
391 392 141
392 393 141
393 394 141
394 395 141
395 396 141
396 397 141
397 398 141
398 399 141
399 400 141
400 401 141
401 402 141
402 403 141
403 404 141
404 405 141
405 406 141
406 407 141
407 408 141
408 409 141
409 410 141
410 411 141
411 412 141
412 413 141
413 414 141
414 415 141
415 416 141
416 417 141
417 418 141
418 419 141
419 420 141
420 421 141
421 422 141
422 423 141
423 424 141
424 425 141
425 426 141
426 427 141
427 428 141
428 429 141
429 430 141
430 431 141
431 432 141
432 433 141
433 434 141
434 435 141
435 436 141
436 437 141
437 438 141
438 439 141
439 440 141
440 441 141
441 442 141
442 443 141
443 444 141
444 445 141
445 446 141
446 447 141
447 448 141
448 449 141
449 450 141
450 451 141
451 452 141
452 453 141
453 454 141
454 455 141
455 456 141
456 457 141
457 458 141
458 459 141
459 460 141
460 461 141
461 462 141
462 463 141
463 464 141
464 465 141
465 466 141
466 467 141
467 468 141
468 469 141
469 470 141
470 471 141
471 472 141
472 473 141
473 474 141
474 475 141
475 476 141
476 477 141
477 478 141
478 479 141
479 480 141
480 481 141
481 482 141
482 483 141
483 484 141
484 485 141
485 486 141
486 487 141
487 488 141
488 489 141
489 490 141
490 491 141
491 492 141
492 493 141
493 494 141
494 495 141
495 496 141
496 497 141
497 498 141
498 499 141
499 500 141
5
10
15
20
25
30
35
40
45
50
55
60
65
70
75
80
85
90
95
100
105
110
115
120
125
130
135
140
145
150
155
160
165
170
175
180
185
190
195
200
205
210
215
220
225
230
235
240
245
250
255
260
265
270
275
280
285
290
295
300
305
310
315
320
325
330
335
340
345
350
355
360
365
370
375
380
385
390
395
400
405
410
415
420
425
430
435
440
445
450
455
460
465
470
475
480
485
490
495
500

  • test case 11—output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

  • test case 12—input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
500 499 100 70000
1 2 141
2 3 141
3 4 141
4 5 141
5 6 141
6 7 141
7 8 141
8 9 141
9 10 141
10 11 141
11 12 141
12 13 141
13 14 141
14 15 141
15 16 141
16 17 141
17 18 141
18 19 141
19 20 141
20 21 141
21 22 141
22 23 141
23 24 141
24 25 141
25 26 141
26 27 141
27 28 141
28 29 141
29 30 141
30 31 141
31 32 141
32 33 141
33 34 141
34 35 141
35 36 141
36 37 141
37 38 141
38 39 141
39 40 141
40 41 141
41 42 141
42 43 141
43 44 141
44 45 141
45 46 141
46 47 141
47 48 141
48 49 141
49 50 141
50 51 141
51 52 141
52 53 141
53 54 141
54 55 141
55 56 141
56 57 141
57 58 141
58 59 141
59 60 141
60 61 141
61 62 141
62 63 141
63 64 141
64 65 141
65 66 141
66 67 141
67 68 141
68 69 141
69 70 141
70 71 141
71 72 141
72 73 141
73 74 141
74 75 141
75 76 141
76 77 141
77 78 141
78 79 141
79 80 141
80 81 141
81 82 141
82 83 141
83 84 141
84 85 141
85 86 141
86 87 141
87 88 141
88 89 141
89 90 141
90 91 141
91 92 141
92 93 141
93 94 141
94 95 141
95 96 141
96 97 141
97 98 141
98 99 141
99 100 141
100 101 141
101 102 141
102 103 141
103 104 141
104 105 141
105 106 141
106 107 141
107 108 141
108 109 141
109 110 141
110 111 141
111 112 141
112 113 141
113 114 141
114 115 141
115 116 141
116 117 141
117 118 141
118 119 141
119 120 141
120 121 141
121 122 141
122 123 141
123 124 141
124 125 141
125 126 141
126 127 141
127 128 141
128 129 141
129 130 141
130 131 141
131 132 141
132 133 141
133 134 141
134 135 141
135 136 141
136 137 141
137 138 141
138 139 141
139 140 141
140 141 141
141 142 141
142 143 141
143 144 141
144 145 141
145 146 141
146 147 141
147 148 141
148 149 141
149 150 141
150 151 141
151 152 141
152 153 141
153 154 141
154 155 141
155 156 141
156 157 141
157 158 141
158 159 141
159 160 141
160 161 141
161 162 141
162 163 141
163 164 141
164 165 141
165 166 141
166 167 141
167 168 141
168 169 141
169 170 141
170 171 141
171 172 141
172 173 141
173 174 141
174 175 141
175 176 141
176 177 141
177 178 141
178 179 141
179 180 141
180 181 141
181 182 141
182 183 141
183 184 141
184 185 141
185 186 141
186 187 141
187 188 141
188 189 141
189 190 141
190 191 141
191 192 141
192 193 141
193 194 141
194 195 141
195 196 141
196 197 141
197 198 141
198 199 141
199 200 141
200 201 141
201 202 141
202 203 141
203 204 141
204 205 141
205 206 141
206 207 141
207 208 141
208 209 141
209 210 141
210 211 141
211 212 141
212 213 141
213 214 141
214 215 141
215 216 141
216 217 141
217 218 141
218 219 141
219 220 141
220 221 141
221 222 141
222 223 141
223 224 141
224 225 141
225 226 141
226 227 141
227 228 141
228 229 141
229 230 141
230 231 141
231 232 141
232 233 141
233 234 141
234 235 141
235 236 141
236 237 141
237 238 141
238 239 141
239 240 141
240 241 141
241 242 141
242 243 141
243 244 141
244 245 141
245 246 141
246 247 141
247 248 141
248 249 141
249 250 141
250 251 141
251 252 141
252 253 141
253 254 141
254 255 141
255 256 141
256 257 141
257 258 141
258 259 141
259 260 141
260 261 141
261 262 141
262 263 141
263 264 141
264 265 141
265 266 141
266 267 141
267 268 141
268 269 141
269 270 141
270 271 141
271 272 141
272 273 141
273 274 141
274 275 141
275 276 141
276 277 141
277 278 141
278 279 141
279 280 141
280 281 141
281 282 141
282 283 141
283 284 141
284 285 141
285 286 141
286 287 141
287 288 141
288 289 141
289 290 141
290 291 141
291 292 141
292 293 141
293 294 141
294 295 141
295 296 141
296 297 141
297 298 141
298 299 141
299 300 141
300 301 141
301 302 141
302 303 141
303 304 141
304 305 141
305 306 141
306 307 141
307 308 141
308 309 141
309 310 141
310 311 141
311 312 141
312 313 141
313 314 141
314 315 141
315 316 141
316 317 141
317 318 141
318 319 141
319 320 141
320 321 141
321 322 141
322 323 141
323 324 141
324 325 141
325 326 141
326 327 141
327 328 141
328 329 141
329 330 141
330 331 141
331 332 141
332 333 141
333 334 141
334 335 141
335 336 141
336 337 141
337 338 141
338 339 141
339 340 141
340 341 141
341 342 141
342 343 141
343 344 141
344 345 141
345 346 141
346 347 141
347 348 141
348 349 141
349 350 141
350 351 141
351 352 141
352 353 141
353 354 141
354 355 141
355 356 141
356 357 141
357 358 141
358 359 141
359 360 141
360 361 141
361 362 141
362 363 141
363 364 141
364 365 141
365 366 141
366 367 141
367 368 141
368 369 141
369 370 141
370 371 141
371 372 141
372 373 141
373 374 141
374 375 141
375 376 141
376 377 141
377 378 141
378 379 141
379 380 141
380 381 141
381 382 141
382 383 141
383 384 141
384 385 141
385 386 141
386 387 141
387 388 141
388 389 141
389 390 141
390 391 141
391 392 141
392 393 141
393 394 141
394 395 141
395 396 141
396 397 141
397 398 141
398 399 141
399 400 141
400 401 141
401 402 141
402 403 141
403 404 141
404 405 141
405 406 141
406 407 141
407 408 141
408 409 141
409 410 141
410 411 141
411 412 141
412 413 141
413 414 141
414 415 141
415 416 141
416 417 141
417 418 141
418 419 141
419 420 141
420 421 141
421 422 141
422 423 141
423 424 141
424 425 141
425 426 141
426 427 141
427 428 141
428 429 141
429 430 141
430 431 141
431 432 141
432 433 141
433 434 141
434 435 141
435 436 141
436 437 141
437 438 141
438 439 141
439 440 141
440 441 141
441 442 141
442 443 141
443 444 141
444 445 141
445 446 141
446 447 141
447 448 141
448 449 141
449 450 141
450 451 141
451 452 141
452 453 141
453 454 141
454 455 141
455 456 141
456 457 141
457 458 141
458 459 141
459 460 141
460 461 141
461 462 141
462 463 141
463 464 141
464 465 141
465 466 141
466 467 141
467 468 141
468 469 141
469 470 141
470 471 141
471 472 141
472 473 141
473 474 141
474 475 141
475 476 141
476 477 141
477 478 141
478 479 141
479 480 141
480 481 141
481 482 141
482 483 141
483 484 141
484 485 141
485 486 141
486 487 141
487 488 141
488 489 141
489 490 141
490 491 141
491 492 141
492 493 141
493 494 141
494 495 141
495 496 141
496 497 141
497 498 141
498 499 141
499 500 141
5
10
15
20
25
30
35
40
45
50
55
60
65
70
75
80
85
90
95
100
105
110
115
120
125
130
135
140
145
150
155
160
165
170
175
180
185
190
195
200
205
210
215
220
225
230
235
240
245
250
255
260
265
270
275
280
285
290
295
300
305
310
315
320
325
330
335
340
345
350
355
360
365
370
375
380
385
390
395
400
405
410
415
420
425
430
435
440
445
450
455
460
465
470
475
480
485
490
495
500

  • test case 12—output
1
2
1
100