/
input2.txt
4800 lines (4800 loc) · 26.6 KB
/
input2.txt
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
14342
18809
30959
26458
14966
17073
6179
9469
27163
32628
24911
4074
25904
25894
17851
18257
12198
27395
27340
18061
21543
18646
32145
25555
19130
5540
25508
32680
22984
10988
20315
7660
14206
1469
30889
5054
2592
2772
24953
9690
17171
14567
11514
1489
29035
23070
77
27691
8642
21933
32446
12754
29371
237
18109
21896
20184
3299
12480
7072
139
31659
7649
2031
30902
30817
13668
25243
10934
10920
10156
23718
2864
23028
15118
10360
30640
3486
2066
9260
14022
9444
18038
29750
7462
27770
6413
32563
24397
29326
10078
27439
5777
15062
2454
80
13852
24158
25800
7972
23979
17676
783
3512
13852
3208
15779
32410
21052
2809
27473
10600
31140
31066
8774
20148
5979
24568
29538
17753
24983
12200
11320
21050
3743
19585
17751
2216
16499
29541
2141
30928
2459
27324
12058
6023
9
14637
12070
6605
7832
15514
19687
2421
7071
23481
8774
27768
4877
9436
12037
8848
14525
20311
4599
26937
21513
19423
17934
7985
27314
20940
10894
21942
19311
10864
13361
9843
10421
17769
16015
16973
21686
22599
14072
20712
4253
24856
11878
25709
7545
31339
20499
21182
5430
8500
1405
31643
15579
28943
24913
10113
6971
26138
16248
11879
29522
26143
14685
14034
4980
29167
13654
3538
16274
1375
20928
12640
30944
21375
15602
13860
7926
32027
17535
7692
10244
15185
27997
7261
17851
30537
24698
6237
8029
6021
23182
10759
27788
10195
19896
17108
4925
17593
11996
2976
31691
24654
2406
22225
2830
24979
25185
10715
18333
3527
5172
7673
18327
10444
3401
4720
32211
8357
14709
26191
10826
18012
10579
14610
30533
12820
3887
19528
1503
18454
31479
18891
12435
28038
7725
1857
3507
31317
4072
17055
3554
11571
3051
2183
29690
21284
12265
30784
8251
25614
26837
16162
4352
24751
25467
10065
9988
30998
11109
17158
6789
8792
27929
6285
25843
2156
20831
8718
17709
13560
12389
9367
15811
4152
30761
18428
26348
4894
13214
13598
9213
5671
30021
5087
10315
16280
13250
27018
22021
25520
2009
8899
19543
19112
31040
15626
27706
26618
7636
3578
11786
3989
15480
22505
545
31873
29676
24345
14169
24322
16301
12036
32607
18792
22388
2774
21958
27750
20593
24601
11576
23896
12555
32106
24915
31543
16382
10767
29246
2192
10018
1921
3078
6600
13645
24149
23223
4168
25029
31160
28568
22898
28619
3265
15936
13422
12059
32717
23756
1599
15907
14890
27489
1038
29808
1128
211
29651
7731
14939
355
5105
10069
14835
30629
29284
25519
19154
25681
27046
7298
16428
2224
4270
30297
8036
27263
27811
29562
1237
18122
31127
14626
31661
65
17898
10173
2209
20284
30248
13513
27135
22350
32542
2897
8504
12448
24220
18230
21611
5589
13916
13865
13283
876
15483
12835
12497
17863
28945
8858
4227
15137
3107
9598
14601
28779
12801
6401
17432
26899
8561
26769
10100
3189
4971
12188
11773
29813
3008
30634
17789
626
14898
12270
25215
30906
12502
20378
15534
32480
417
17113
13633
15826
1949
24180
3169
24981
27333
11957
9481
27288
810
15571
6547
2735
22394
6648
21799
18363
14675
24392
25723
2768
9141
22206
24036
24997
7380
29297
14751
20597
29769
23582
19204
24027
4085
19292
12867
17971
6416
7107
8781
8311
9712
3668
5372
19655
9149
32720
13023
23423
1382
20678
27215
19302
12159
2046
21041
8414
25174
28629
31018
29518
2236
22250
32031
6215
28046
6279
10292
13629
19807
23462
22524
15492
19997
32331
1302
16292
20468
2344
16641
14796
21192
16907
7409
22668
6138
15642
30089
19683
10531
24875
32137
29603
26613
3214
24779
12964
12071
23971
26466
7092
1073
12661
17211
23068
15955
5157
11823
10105
8049
10792
288
12699
7218
24069
18153
1128
26745
28595
30740
3990
13334
9929
14213
10110
11896
7153
2495
18805
29757
19030
3094
26537
7799
5822
24513
24885
22253
17237
14781
21897
8734
10991
28785
24861
22561
5558
21524
9804
24708
732
10930
17795
27073
15821
6566
27486
26450
2645
23827
19958
162
7658
30010
32470
10981
26749
4338
3007
28481
11184
6047
31427
4341
5617
20048
3474
30881
8736
11460
25132
23904
9550
15926
20671
32179
19704
15959
3774
20049
18100
10537
9590
31433
16738
5438
26659
931
15320
18540
31934
17627
31616
4316
8609
31499
16415
3082
44
27636
26375
18710
32339
585
25909
1233
32522
1901
18675
9714
25481
32703
27381
26383
4615
25410
16142
28042
14153
17224
6082
10956
2601
13155
15584
1629
31667
13810
4724
23395
13803
19626
5703
1085
23514
24363
24167
24060
1060
2452
13864
14405
15966
22507
29032
1874
23187
24911
21835
5997
30209
31079
28978
10206
27368
31693
15793
13284
28701
23909
31775
21789
27360
30687
20076
9358
19288
22930
1188
18193
11341
7735
1989
12826
5186
3819
5040
8020
12239
28183
14854
10025
19891
27062
21938
15653
14548
22143
4451
7880
1185
16764
7478
8952
17032
21694
12565
28756
29943
22771
781
20210
21810
18218
17177
31019
17895
28002
25775
29269
11329
19228
3174
7584
7038
14414
30270
27403
7915
18662
10537
31269
28593
20394
21956
637
31628
7605
26936
13225
6210
29196
14092
12247
23107
3434
25188
2523
15580
11733
29520
26968
12019
16925
11756
14146
17929
11568
18314
10759
13763
9855
4521
19724
16092
2464
13758
9323
31711
4388
29098
23841
2412
13154
17294
676
30915
32217
29624
614
27930
1847
14097
16508
24153
21205
2154
3386
11920
22200
10060
24019
19321
29758
25559
22460
22842
24604
5721
8608
20396
12971
11422
10827
27481
771
6349
2085
32612
24527
23292
25922
19994
29538
19221
5170
18157
17822
799
7408
243
18467
15878
11128
16439
9149
12220
12999
16071
23796
13873
18063
1082
15438
9571
21238
20269
9070
12592
8727
29394
18967
3346
22260
11036
7563
4283
14939
19981
3329
7803
9365
6607
11408
28706
20763
2140
12474
15167
24438
7219
7388
8022
752
7058
26613
24255
1515
15773
17076
7720
7157
11427
4684
31794
15580
20410
18184
26308
14880
12706
1659
8822
11696
1714
15043
7776
9044
30831
22686
9451
15081
21432
26031
17633
6327
301
27448
30247
2666
13925
3709
24887
7309
27698
7914
28010
7388
6426
3869
3105
9790
20919
17021
29910
24986
18287
19733
418
12133