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