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