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