1000
696754 401634722 0 1000000000
615218 784557231 0 1000000000
444417 784728369 0 1000000000
88316 302772165 0 1000000000
574010 754567282 0 1000000000
638639 830808159 0 1000000000
427988 243969809 0 1000000000
245794 199048032 0 1000000000
392635 25756018 0 1000000000
578398 838835565 0 1000000000
88160 235804715 0 1000000000
689140 271933033 0 1000000000
827411 281255871 0 1000000000
308650 450831063 0 1000000000
563862 669894196 0 1000000000
290442 251968253 0 1000000000
604535 830714131 0 1000000000
364157 830392429 0 1000000000
488445 192934351 0 1000000000
460233 100460474 0 1000000000
28031 959010050 0 1000000000
660044 942570333 0 1000000000
99429 748457717 0 1000000000
820203 774699930 0 1000000000
968283 898357202 0 1000000000
125994 76037110 0 1000000000
598623 372838548 0 1000000000
745237 805066826 0 1000000000
682281 996435703 0 1000000000
905422 859150025 0 1000000000
528899 492555536 0 1000000000
406355 107321311 0 1000000000
481565 711636084 0 1000000000
833206 558355333 0 1000000000
140888 359534836 0 1000000000
562441 671949512 0 1000000000
880041 250246243 0 1000000000
103188 457701014 0 1000000000
427250 351072786 0 1000000000
223642 786101254 0 1000000000
757826 417233943 0 1000000000
670068 553333786 0 1000000000
909987 527216390 0 1000000000
301192 450381025 0 1000000000
700228 518114893 0 1000000000
993139 507067572 0 1000000000
813792 457222175 0 1000000000
532999 963514567 0 1000000000
304641 758023617 0 1000000000
237796 199997175 0 1000000000
71913 736204658 0 1000000000
183558 995891110 0 1000000000
592953 699959450 0 1000000000
909447 305544373 0 1000000000
478600 348746152 0 1000000000
436629 534181634 0 1000000000
855166 747008444 0 1000000000
210313 761275423 0 1000000000
91078 165035187 0 1000000000
321891 152914099 0 1000000000
601909 653103214 0 1000000000
945172 471197650 0 1000000000
522734 248380627 0 1000000000
456416 939412569 0 1000000000
147943 17494145 0 1000000000
283204 761158706 0 1000000000
692240 185430059 0 1000000000
474746 439490253 0 1000000000
239962 336408643 0 1000000000
824473 224089003 0 1000000000
58041 740206766 0 1000000000
514964 667487393 0 1000000000
774443 300280384 0 1000000000
630287 293026544 0 1000000000
87786 907676742 0 1000000000
885650 573274020 0 1000000000
663962 951725294 0 1000000000
280999 18141044 0 1000000000
517131 534533185 0 1000000000
832842 388599605 0 1000000000
999627 988547442 0 1000000000
184746 301389735 0 1000000000
33006 738201295 0 1000000000
185750 708172837 0 1000000000
553213 137489921 0 1000000000
421926 497482120 0 1000000000
395640 543063429 0 1000000000
66449 490384807 0 1000000000
443092 290692313 0 1000000000
976927 626465023 0 1000000000
799504 99940495 0 1000000000
275670 336018526 0 1000000000
74016 827489962 0 1000000000
552760 790034900 0 1000000000
534127 104018494 0 1000000000
963346 805910511 0 1000000000
199536 660115260 0 1000000000
148234 679482228 0 1000000000
592343 164881360 0 1000000000
585937 969106519 0 1000000000
176681 307983631 0 1000000000
168444 449341906 0 1000000000
351481 186148689 0 1000000000
432123 972401507 0 1000000000
267659 37012605 0 1000000000
895879 671804930 0 1000000000
552800 921100304 0 1000000000
66517 985260836 0 1000000000
839320 984536960 0 1000000000
236169 516773328 0 1000000000
392698 940580339 0 1000000000
586616 324776827 0 1000000000
382379 984698068 0 1000000000
927305 590501475 0 1000000000
586374 825003993 0 1000000000
722724 104340707 0 1000000000
940866 124583583 0 1000000000
232540 546533338 0 1000000000
775689 69999432 0 1000000000
3379 421932439 0 1000000000
910598 876091029 0 1000000000
590037 732444375 0 1000000000
183106 492370651 0 1000000000
854072 102974406 0 1000000000
774820 13754699 0 1000000000
549192 959746993 0 1000000000
588996 262112857 0 1000000000
860147 185078363 0 1000000000
249075 751731069 0 1000000000
259891 463614970 0 1000000000
580467 558547922 0 1000000000
781090 668025322 0 1000000000
276866 970523060 0 1000000000
877240 969758836 0 1000000000
262268 937024872 0 1000000000
518363 565879236 0 1000000000
526563 497708859 0 1000000000
644521 433845726 0 1000000000
774077 115031054 0 1000000000
887911 223556625 0 1000000000
736908 855675416 0 1000000000
277726 820874304 0 1000000000
666647 204176678 0 1000000000
545366 415069137 0 1000000000
557245 813302014 0 1000000000
907749 47901998 0 1000000000
486490 80301228 0 1000000000
182855 174357460 0 1000000000
416434 845658239 0 1000000000
891358 53265571 0 1000000000
336063 116612404 0 1000000000
539377 20976555 0 1000000000
393141 368063479 0 1000000000
1736 646164959 0 1000000000
689138 480891296 0 1000000000
193220 834829712 0 1000000000
365633 415517211 0 1000000000
614220 124680728 0 1000000000
950742 154282577 0 1000000000
749634 331459028 0 1000000000
556241 484883557 0 1000000000
514043 753211599 0 1000000000
436685 167084573 0 1000000000
646354 593727912 0 1000000000
548547 898371857 0 1000000000
399526 652938701 0 1000000000
590648 124953809 0 1000000000
145121 227687480 0 1000000000
873143 201317362 0 1000000000
322157 708982937 0 1000000000
97263 773182716 0 1000000000
625197 266321012 0 1000000000
187595 39178090 0 1000000000
953845 64799735 0 1000000000
596444 386317936 0 1000000000
652640 904034416 0 1000000000
221537 14812454 0 1000000000
405810 250274014 0 1000000000
642730 526278403 0 1000000000
550733 122638283 0 1000000000
921110 869027048 0 1000000000
808910 378246320 0 1000000000
477259 218696477 0 1000000000
267866 272515668 0 1000000000
905072 286358114 0 1000000000
704354 146186038 0 1000000000
34980 274594925 0 1000000000
261900 898240965 0 1000000000
341258 830431431 0 1000000000
227464 346042812 0 1000000000
45298 529292736 0 1000000000
611568 727990052 0 1000000000
273163 382197510 0 1000000000
369296 230350287 0 1000000000
270418 655230422 0 1000000000
290278 775308873 0 1000000000
295595 416559286 0 1000000000
512327 541627489 0 1000000000
517051 320461414 0 1000000000
53828 116642950 0 1000000000
438522 64213152 0 1000000000
429500 607335762 0 1000000000
445262 696149475 0 1000000000
725387 280234817 0 1000000000
326526 386255621 0 1000000000
935521 399018145 0 1000000000
643745 845743319 0 1000000000
638719 771960579 0 1000000000
85647 812625752 0 1000000000
910987 751954886 0 1000000000
420787 912098863 0 1000000000
927392 730091387 0 1000000000
129428 862066175 0 1000000000
476421 295308734 0 1000000000
993177 214220259 0 1000000000
374615 975820732 0 1000000000
301459 355191523 0 1000000000
577126 50965886 0 1000000000
143678 829479546 0 1000000000
379242 314487163 0 1000000000
473180 542055206 0 1000000000
537205 44500332 0 1000000000
836856 408195394 0 1000000000
221054 561340582 0 1000000000
75250 55674184 0 1000000000
889768 190827614 0 1000000000
502284 744261609 0 1000000000
707517 420787119 0 1000000000
618719 448951731 0 1000000000
70127 627390329 0 1000000000
633829 541436666 0 1000000000
242015 730394972 0 1000000000
323532 115086761 0 1000000000
735216 239189897 0 1000000000
273801 804986062 0 1000000000
198035 22176305 0 1000000000
379377 518332599 0 1000000000
800299 838370017 0 1000000000
559094 489029563 0 1000000000
92623 868392175 0 1000000000
890143 900777963 0 1000000000
954463 573531150 0 1000000000
342987 222463714 0 1000000000
812588 722440546 0 1000000000
541217 709172660 0 1000000000
970056 757155150 0 1000000000
826618 53028540 0 1000000000
168942 802669003 0 1000000000
487568 21945142 0 1000000000
847914 639303682 0 1000000000
118884 945625787 0 1000000000
59064 583157389 0 1000000000
708794 260709317 0 1000000000
640862 330630287 0 1000000000
464243 114988871 0 1000000000
756322 224122845 0 1000000000
839577 809662814 0 1000000000
835738 718031327 0 1000000000
430796 768647713 0 1000000000
933403 936677129 0 1000000000
865562 91674556 0 1000000000
76473 86596471 0 1000000000
805581 327751583 0 1000000000
218332 761452971 0 1000000000
97563 28923253 0 1000000000
594289 10926323 0 1000000000
965095 755641526 0 1000000000
400107 520496848 0 1000000000
275151 711902807 0 1000000000
25929 613553632 0 1000000000
359352 114002669 0 1000000000
224683 635593695 0 1000000000
817429 66841420 0 1000000000
808009 203473430 0 1000000000
742504 974822686 0 1000000000
221948 388296234 0 1000000000
45475 499646646 0 1000000000
512297 884972878 0 1000000000
498185 991882052 0 1000000000
706112 772255036 0 1000000000
469056 347881991 0 1000000000
798997 379952178 0 1000000000
520418 402402959 0 1000000000
43402 357397692 0 1000000000
294316 500495250 0 1000000000
588420 862576536 0 1000000000
566965 553377920 0 1000000000
569924 683492747 0 1000000000
348116 670275787 0 1000000000
418212 31963062 0 1000000000
805204 317346846 0 1000000000
26719 303573266 0 1000000000
7925 118260020 0 1000000000
319424 845078242 0 1000000000
57354 519460003 0 1000000000
215564 110557131 0 1000000000
185920 990876283 0 1000000000
588762 88412279 0 1000000000
512712 154373804 0 1000000000
337635 386544617 0 1000000000
283733 68325392 0 1000000000
169248 505980878 0 1000000000
157338 362583259 0 1000000000
987313 560907927 0 1000000000
116775 180081157 0 1000000000
275044 73633255 0 1000000000
480048 59222103 0 1000000000
746174 807866888 0 1000000000
195905 68160018 0 1000000000
285130 729415293 0 1000000000
476900 165970094 0 1000000000
104762 769687392 0 1000000000
275615 949625758 0 1000000000
418667 948195361 0 1000000000
88329 260992914 0 1000000000
476921 433488848 0 1000000000
456322 728331534 0 1000000000
103441 168918060 0 1000000000
258277 330167218 0 1000000000
478034 99783271 0 1000000000
165095 623368539 0 1000000000
675165 245016591 0 1000000000
514781 869840221 0 1000000000
863669 312651947 0 1000000000
388983 101724481 0 1000000000
717839 25921370 0 1000000000
738492 330260101 0 1000000000
468952 184253336 0 1000000000
895117 211006715 0 1000000000
623682 983274859 0 1000000000
155191 763165714 0 1000000000
52948 244142084 0 1000000000
898188 520046994 0 1000000000
295255 892655459 0 1000000000
932162 404325192 0 1000000000
75106 448695177 0 1000000000
249037 276325530 0 1000000000
914396 117800853 0 1000000000
312219 453675001 0 1000000000
637061 945054024 0 1000000000
291071 47580493 0 1000000000
933336 217455832 0 1000000000
152425 647884356 0 1000000000
631449 427356309 0 1000000000
514630 103205273 0 1000000000
655257 681746498 0 1000000000
404828 718997643 0 1000000000
175690 884156001 0 1000000000
880153 680340263 0 1000000000
521670 18956605 0 1000000000
215646 565415983 0 1000000000
529188 141943077 0 1000000000
30983 997421873 0 1000000000
620268 55248168 0 1000000000
63631 862945787 0 1000000000
307201 13736546 0 1000000000
422621 701173985 0 1000000000
186913 528554444 0 1000000000
296108 646154240 0 1000000000
581806 200885987 0 1000000000
343562 10928884 0 1000000000
378099 82238713 0 1000000000
575673 708837486 0 1000000000
803418 79347712 0 1000000000
868147 736378774 0 1000000000
288930 898385699 0 1000000000
551766 535330830 0 1000000000
441115 175028344 0 1000000000
334507 815008275 0 1000000000
246358 812049537 0 1000000000
657616 379117457 0 1000000000
481779 345879570 0 1000000000
856455 124068311 0 1000000000
460764 529871421 0 1000000000
649186 920110935 0 1000000000
578003 406607610 0 1000000000
12723 86554604 0 1000000000
367428 238299502 0 1000000000
297338 386157807 0 1000000000
754173 789592305 0 1000000000
569221 749994257 0 1000000000
74729 897993579 0 1000000000
515176 167770052 0 1000000000
939952 832749244 0 1000000000
388238 491409736 0 1000000000
968303 406477964 0 1000000000
10696 138066017 0 1000000000
359724 11999426 0 1000000000
934020 596965751 0 1000000000
421039 803546382 0 1000000000
309171 820484026 0 1000000000
828199 898080523 0 1000000000
548113 871424337 0 1000000000
545566 419660298 0 1000000000
136516 42165005 0 1000000000
148706 526276740 0 1000000000
798780 368256409 0 1000000000
29484 599241488 0 1000000000
138704 614766618 0 1000000000
504343 613961218 0 1000000000
357387 851605799 0 1000000000
588312 272897225 0 1000000000
853805 902070603 0 1000000000
340841 122651808 0 1000000000
572133 369616771 0 1000000000
113000 64323340 0 1000000000
183538 80038110 0 1000000000
232197 820801050 0 1000000000
284573 62015660 0 1000000000
909298 341089689 0 1000000000
988881 475401783 0 1000000000
806427 966057204 0 1000000000
611909 535968619 0 1000000000
835238 706901845 0 1000000000
389806 813410193 0 1000000000
883380 219766100 0 1000000000
203908 275548553 0 1000000000
274474 686805500 0 1000000000
750619 707231774 0 1000000000
950605 642558315 0 1000000000
573491 331189127 0 1000000000
345073 691510906 0 1000000000
677602 155285701 0 1000000000
846975 161759673 0 1000000000
613343 606547115 0 1000000000
87001 429980642 0 1000000000
931514 539750781 0 1000000000
430863 97485534 0 1000000000
823659 256970920 0 1000000000
105308 83457976 0 1000000000
637294 819088392 0 1000000000
516733 773548311 0 1000000000
445057 146744544 0 1000000000
533935 31255099 0 1000000000
538104 268804218 0 1000000000
99043 721918925 0 1000000000
467889 956043826 0 1000000000
50103 383195835 0 1000000000
267311 130277340 0 1000000000
655189 321728810 0 1000000000
122930 184151428 0 1000000000
89256 543228405 0 1000000000
638827 490543594 0 1000000000
222144 777272972 0 1000000000
73252 199647073 0 1000000000
87413 202903333 0 1000000000
85684 733561126 0 1000000000
732692 568723304 0 1000000000
374549 664455889 0 1000000000
986143 370335674 0 1000000000
826653 545898876 0 1000000000
536762 660311006 0 1000000000
615953 93329628 0 1000000000
884164 48754113 0 1000000000
325894 265222900 0 1000000000
540463 305545748 0 1000000000
116942 961705735 0 1000000000
631195 4390558 0 1000000000
608112 604655524 0 1000000000
190657 444589020 0 1000000000
486100 404191466 0 1000000000
730541 210713810 0 1000000000
431449 137070155 0 1000000000
403690 635451289 0 1000000000
69560 968198723 0 1000000000
286816 88320685 0 1000000000
583819 355255034 0 1000000000
272049 586011549 0 1000000000
123034 899939863 0 1000000000
860141 72191398 0 1000000000
479725 278225633 0 1000000000
432092 640554321 0 1000000000
372618 886414775 0 1000000000
982325 361523752 0 1000000000
991539 849885028 0 1000000000
646365 186295674 0 1000000000
102279 972496605 0 1000000000
789011 498461936 0 1000000000
710513 918861538 0 1000000000
81714 203837984 0 1000000000
547735 307579364 0 1000000000
188615 245141715 0 1000000000
726538 779447292 0 1000000000
305490 798968132 0 1000000000
918597 772409570 0 1000000000
843105 671849978 0 1000000000
603152 167021339 0 1000000000
280597 216668537 0 1000000000
731257 611748217 0 1000000000
773993 284037098 0 1000000000
954186 827243912 0 1000000000
334010 164592657 0 1000000000
534347 670953580 0 1000000000
483401 91610155 0 1000000000
683697 195337068 0 1000000000
830729 36017642 0 1000000000
957075 476451392 0 1000000000
263396 758846601 0 1000000000
211902 432189331 0 1000000000
922406 427039761 0 1000000000
584661 604067976 0 1000000000
618807 960043407 0 1000000000
950202 310448854 0 1000000000
271779 181931850 0 1000000000
712873 458074035 0 1000000000
560643 658163753 0 1000000000
904875 858005481 0 1000000000
819258 911527318 0 1000000000
641030 474204531 0 1000000000
689672 244019155 0 1000000000
339454 411689780 0 1000000000
172915 817831207 0 1000000000
264584 936877919 0 1000000000
188214 260249335 0 1000000000
797794 166365919 0 1000000000
295818 946722910 0 1000000000
434372 688288196 0 1000000000
382147 429876498 0 1000000000
600438 722834428 0 1000000000
334662 282307349 0 1000000000
505698 737302424 0 1000000000
8785 120409029 0 1000000000
815124 270932841 0 1000000000
437434 825416241 0 1000000000
754286 629801272 0 1000000000
733758 596079000 0 1000000000
291802 314409833 0 1000000000
422230 157095130 0 1000000000
784601 166306081 0 1000000000
862533 231327160 0 1000000000
4176 164889420 0 1000000000
27764 693401636 0 1000000000
911489 735504343 0 1000000000
487434 947690655 0 1000000000
174073 286262276 0 1000000000
285132 200813190 0 1000000000
30001 375158591 0 1000000000
963096 915656754 0 1000000000
677751 502028759 0 1000000000
382354 497248040 0 1000000000
441580 535183460 0 1000000000
420982 917577458 0 1000000000
999073 966228402 0 1000000000
170340 781902750 0 1000000000
76075 584800100 0 1000000000
247540 907102667 0 1000000000
932100 378588886 0 1000000000
805539 948961143 0 1000000000
942767 227057559 0 1000000000
311549 577137657 0 1000000000
241241 674105122 0 1000000000
803723 100369847 0 1000000000
765358 190746917 0 1000000000
54296 653077724 0 1000000000
18817 616561667 0 1000000000
91625 805236777 0 1000000000
86845 416537057 0 1000000000
257986 237061515 0 1000000000
17643 7823684 0 1000000000
725308 19630513 0 1000000000
848141 22418038 0 1000000000
900801 54864490 0 1000000000
699460 852158363 0 1000000000
81321 529025509 0 1000000000
426636 644180048 0 1000000000
707432 866610008 0 1000000000
511052 806275680 0 1000000000
59497 723411076 0 1000000000
298322 616913691 0 1000000000
883858 303769968 0 1000000000
661604 885335775 0 1000000000
436947 153177652 0 1000000000
980828 784770806 0 1000000000
450150 877596648 0 1000000000
405578 375045764 0 1000000000
659215 290272678 0 1000000000
426362 28819559 0 1000000000
776051 219790897 0 1000000000
764429 808092337 0 1000000000
103303 134417703 0 1000000000
535653 731273428 0 1000000000
101654 640438288 0 1000000000
628998 572747909 0 1000000000
35724 135191181 0 1000000000
781310 54503668 0 1000000000
436532 992317606 0 1000000000
755907 935112487 0 1000000000
524580 855142542 0 1000000000
554053 770991285 0 1000000000
546381 374478296 0 1000000000
79270 364401804 0 1000000000
132264 884608501 0 1000000000
668231 551937524 0 1000000000
973172 800898678 0 1000000000
873625 169851204 0 1000000000
940713 124486292 0 1000000000
835067 51095440 0 1000000000
388058 57084315 0 1000000000
847451 901640835 0 1000000000
990788 729442359 0 1000000000
387647 693149443 0 1000000000
21442 181339722 0 1000000000
69446 98827891 0 1000000000
870804 675051044 0 1000000000
386442 968061115 0 1000000000
280300 724034783 0 1000000000
678073 93518470 0 1000000000
387492 80033308 0 1000000000
145904 318652167 0 1000000000
872044 906338612 0 1000000000
717186 675977305 0 1000000000
879813 542328242 0 1000000000
275834 987344656 0 1000000000
552864 278698265 0 1000000000
122248 59003462 0 1000000000
154361 499926258 0 1000000000
967934 112076340 0 1000000000
27212 648381651 0 1000000000
811693 712962699 0 1000000000
833184 667129045 0 1000000000
649493 338307132 0 1000000000
559335 96999195 0 1000000000
35209 35742630 0 1000000000
848853 199940114 0 1000000000
350926 514474297 0 1000000000
58881 967614529 0 1000000000
659333 753238227 0 1000000000
255107 839549432 0 1000000000
8314 713759661 0 1000000000
894424 890623588 0 1000000000
72351 701564997 0 1000000000
438511 913410087 0 1000000000
908575 255160526 0 1000000000
668642 385016345 0 1000000000
337900 526606131 0 1000000000
524103 554150148 0 1000000000
299638 949349215 0 1000000000
959066 610587440 0 1000000000
900314 528037852 0 1000000000
448102 278386354 0 1000000000
719996 503007695 0 1000000000
354529 942006811 0 1000000000
686340 965744655 0 1000000000
967308 310224539 0 1000000000
290943 461524049 0 1000000000
980458 996316044 0 1000000000
983694 331785252 0 1000000000
441525 779125664 0 1000000000
629197 56669968 0 1000000000
290631 377154110 0 1000000000
351125 804170022 0 1000000000
923642 325873958 0 1000000000
669891 744279238 0 1000000000
857725 909000926 0 1000000000
546433 528711475 0 1000000000
376856 500221196 0 1000000000
553556 585431230 0 1000000000
614228 724304674 0 1000000000
544310 793778230 0 1000000000
209517 344305256 0 1000000000
114310 978277221 0 1000000000
586024 237779589 0 1000000000
788687 999512351 0 1000000000
933738 610816756 0 1000000000
973468 195363586 0 1000000000
868408 224513354 0 1000000000
324471 523175301 0 1000000000
453216 633356093 0 1000000000
191970 997346444 0 1000000000
391282 197566278 0 1000000000
781625 83938802 0 1000000000
63730 692314986 0 1000000000
883669 363050320 0 1000000000
810163 651805940 0 1000000000
59594 986383862 0 1000000000
69445 531050857 0 1000000000
21744 312222552 0 1000000000
534000 706907314 0 1000000000
954580 556128904 0 1000000000
450118 963261062 0 1000000000
539660 436053132 0 1000000000
381804 655472579 0 1000000000
528560 370907492 0 1000000000
825755 118637108 0 1000000000
141811 732790395 0 1000000000
940290 82518162 0 1000000000
75916 794785604 0 1000000000
824137 407159486 0 1000000000
375417 505861094 0 1000000000
181 279311680 0 1000000000
540031 215511370 0 1000000000
514995 762551157 0 1000000000
141271 141735160 0 1000000000
351579 902002593 0 1000000000
480328 742266560 0 1000000000
159544 861288333 0 1000000000
793743 30897300 0 1000000000
601221 691761422 0 1000000000
501046 106185517 0 1000000000
961477 643619717 0 1000000000
259908 275672226 0 1000000000
834004 476524621 0 1000000000
759874 225216088 0 1000000000
767960 383447044 0 1000000000
570889 35134932 0 1000000000
315190 416678790 0 1000000000
564215 952385244 0 1000000000
504538 944619473 0 1000000000
715867 425321300 0 1000000000
584614 763774638 0 1000000000
217503 181451796 0 1000000000
304438 900612772 0 1000000000
214564 550361971 0 1000000000
741550 252364201 0 1000000000
877825 794586306 0 1000000000
830994 753367720 0 1000000000
520074 600112705 0 1000000000
854487 705954800 0 1000000000
882707 99882851 0 1000000000
116373 969782759 0 1000000000
606201 142692144 0 1000000000
31689 626884082 0 1000000000
177036 906549909 0 1000000000
621789 717802174 0 1000000000
507618 926965864 0 1000000000
596075 429205177 0 1000000000
166504 72531192 0 1000000000
300869 518470568 0 1000000000
546107 324053571 0 1000000000
712164 42530339 0 1000000000
459557 287665559 0 1000000000
276333 446799256 0 1000000000
277361 97126132 0 1000000000
125266 565877099 0 1000000000
408900 938141459 0 1000000000
685666 377756557 0 1000000000
942574 422813024 0 1000000000
35261 631973393 0 1000000000
547425 179119112 0 1000000000
94329 817803619 0 1000000000
315369 703703191 0 1000000000
631394 216229896 0 1000000000
671923 7613714 0 1000000000
355594 20138024 0 1000000000
61056 152122435 0 1000000000
871396 543795735 0 1000000000
578336 251038432 0 1000000000
297888 996714377 0 1000000000
921962 45409537 0 1000000000
739366 146221161 0 1000000000
863255 580067368 0 1000000000
544079 200140903 0 1000000000
311363 828969495 0 1000000000
796644 118403150 0 1000000000
677067 277318332 0 1000000000
744504 710570435 0 1000000000
317662 528259625 0 1000000000
15879 64600726 0 1000000000
947061 788176447 0 1000000000
809564 872547503 0 1000000000
141523 374002483 0 1000000000
673597 451991427 0 1000000000
306070 543116072 0 1000000000
342311 867599726 0 1000000000
365595 464327131 0 1000000000
452011 606490345 0 1000000000
526780 174111927 0 1000000000
474038 409123606 0 1000000000
734028 715436598 0 1000000000
807353 156947189 0 1000000000
101895 254071234 0 1000000000
900667 154017176 0 1000000000
842152 685690852 0 1000000000
409782 878395372 0 1000000000
163721 156969238 0 1000000000
255002 312899687 0 1000000000
315162 643860935 0 1000000000
413000 384694265 0 1000000000
329740 302253773 0 1000000000
227482 945012757 0 1000000000
907244 1827269 0 1000000000
255430 171706455 0 1000000000
64759 23391166 0 1000000000
82349 242348156 0 1000000000
173170 20544378 0 1000000000
753570 593189150 0 1000000000
656769 142901960 0 1000000000
524855 37023413 0 1000000000
705787 221170486 0 1000000000
170219 219939273 0 1000000000
781039 510507932 0 1000000000
100809 688683699 0 1000000000
797413 379120115 0 1000000000
755760 869646980 0 1000000000
100768 159917612 0 1000000000
951542 306315279 0 1000000000
453880 21461483 0 1000000000
481887 171333537 0 1000000000
414500 19399567 0 1000000000
859481 479453584 0 1000000000
205450 90147200 0 1000000000
92954 219865884 0 1000000000
294011 62472066 0 1000000000
7276 204943337 0 1000000000
882622 657774371 0 1000000000
881377 462311639 0 1000000000
852909 923858516 0 1000000000
259725 852492242 0 1000000000
769573 12741937 0 1000000000
248585 552978585 0 1000000000
241848 452146207 0 1000000000
253392 18039276 0 1000000000
906723 391554123 0 1000000000
598361 280450946 0 1000000000
326959 894475396 0 1000000000
464757 712546055 0 1000000000
281001 185453488 0 1000000000
711018 793097713 0 1000000000
422998 190448459 0 1000000000
794052 545945369 0 1000000000
289633 135561619 0 1000000000
704212 858157918 0 1000000000
740037 714860309 0 1000000000
364007 477391661 0 1000000000
19762 709686909 0 1000000000
524650 145095213 0 1000000000
346658 121522536 0 1000000000
618406 610464691 0 1000000000
769432 604807831 0 1000000000
327603 645959469 0 1000000000
297249 291202100 0 1000000000
601771 832847218 0 1000000000
960275 783448573 0 1000000000
327096 830290331 0 1000000000
683248 249314097 0 1000000000
674432 205514763 0 1000000000
32658 728572077 0 1000000000
688060 887448715 0 1000000000
727715 139239255 0 1000000000
508682 198316668 0 1000000000
168649 491130925 0 1000000000
504896 35416535 0 1000000000
751475 57590364 0 1000000000
814145 790840248 0 1000000000
993519 112234924 0 1000000000
578302 705225187 0 1000000000
182030 763226343 0 1000000000
222021 26333844 0 1000000000
53864 84166396 0 1000000000
384881 76487242 0 1000000000
275225 277442247 0 1000000000
574455 292681777 0 1000000000
516011 611040204 0 1000000000
850345 700247296 0 1000000000
43396 935227122 0 1000000000
350233 431793832 0 1000000000
840516 347317607 0 1000000000
218875 949940064 0 1000000000
896863 582762724 0 1000000000
711913 520930183 0 1000000000
159575 488972148 0 1000000000
375488 383426941 0 1000000000
500940 452500409 0 1000000000
249639 451550579 0 1000000000
649077 975900015 0 1000000000
430073 547447069 0 1000000000
65181 806327746 0 1000000000
32810 206106223 0 1000000000
927753 580730884 0 1000000000
698093 499170864 0 1000000000
33364 308645724 0 1000000000
33847 674259754 0 1000000000
595403 491705719 0 1000000000
358117 175486263 0 1000000000
197628 62488594 0 1000000000
982952 245156801 0 1000000000
568046 263658873 0 1000000000
410057 504849233 0 1000000000
169029 41226956 0 1000000000
272833 681421804 0 1000000000
920522 516232207 0 1000000000
648344 996827184 0 1000000000
377565 626127896 0 1000000000
943726 270922808 0 1000000000
116064 779462423 0 1000000000
262467 513800667 0 1000000000
416508 923041657 0 1000000000
963873 373794443 0 1000000000
177443 605331528 0 1000000000
461688 178092997 0 1000000000
722437 685621924 0 1000000000
804009 748667367 0 1000000000
63664 963118687 0 1000000000
933564 68547360 0 1000000000
944649 457386446 0 1000000000
39859 604853972 0 1000000000
857359 757474231 0 1000000000
797015 158098232 0 1000000000
95102 753874951 0 1000000000
804548 415830342 0 1000000000
468374 940548524 0 1000000000
357684 410179567 0 1000000000
364426 65104287 0 1000000000
131870 502908573 0 1000000000
58186 586968457 0 1000000000
255374 862305926 0 1000000000
139232 25227492 0 1000000000
357406 293170095 0 1000000000
114570 527484346 0 1000000000
270982 767861304 0 1000000000
239734 709968284 0 1000000000
24148 187015236 0 1000000000
154456 400451081 0 1000000000
497141 817919975 0 1000000000
341917 73027780 0 1000000000
317355 727791859 0 1000000000
982311 664933659 0 1000000000
459674 749903963 0 1000000000
928876 515366440 0 1000000000
881623 276928824 0 1000000000
32515 399277020 0 1000000000
684395 989194313 0 1000000000
345788 549405694 0 1000000000
719495 320489146 0 1000000000
253043 324888505 0 1000000000
184652 757834645 0 1000000000
988828 137675303 0 1000000000
781211 982780929 0 1000000000
975644 978541944 0 1000000000
434082 469779742 0 1000000000
417370 758683497 0 1000000000
373899 31239419 0 1000000000
761647 370514040 0 1000000000
729910 269759025 0 1000000000
206766 654091288 0 1000000000
664858 108388001 0 1000000000
45637 491929005 0 1000000000
267730 95178814 0 1000000000
721188 399880659 0 1000000000
390879 866896715 0 1000000000
782315 925414623 0 1000000000
668321 157909570 0 1000000000
21634 451283432 0 1000000000
322858 682333004 0 1000000000
575340 45956336 0 1000000000
229348 86619433 0 1000000000
305614 683303595 0 1000000000
500482 4714564 0 1000000000
488987 174916025 0 1000000000
945912 642279130 0 1000000000
320744 193502853 0 1000000000
778787 858840720 0 1000000000
780646 580061332 0 1000000000
201696 191135588 0 1000000000
404112 650001456 0 1000000000
484695 901546467 0 1000000000
180995 4543172 0 1000000000
144597 828052982 0 1000000000
952031 257505666 0 1000000000
363171 258907224 0 1000000000
864968 789244644 0 1000000000
416422 430045641 0 1000000000
129202 241578396 0 1000000000
171406 463894208 0 1000000000
377278 21165762 0 1000000000
703301 317136674 0 1000000000
124837 668079538 0 1000000000
588600 753477468 0 1000000000
349761 279464826 0 1000000000
600883 916353745 0 1000000000
177598 782149531 0 1000000000
993124 129825873 0 1000000000
873582 527176674 0 1000000000
198026 826114561 0 1000000000
954461 168361452 0 1000000000
108192 369993577 0 1000000000
397660 124366860 0 1000000000
1374 534467826 0 1000000000
719887 512295880 0 1000000000
171216 617983636 0 1000000000
583146 448279961 0 1000000000
827988 959307780 0 1000000000
814275 934431289 0 1000000000
823331 484947640 0 1000000000
933188 505092027 0 1000000000
763622 20047952 0 1000000000
129099 660323402 0 1000000000
203995 896038689 0 1000000000
163962 256231372 0 1000000000
746489 919988870 0 1000000000
764805 467658770 0 1000000000
898680 564688904 0 1000000000
187193 647346382 0 1000000000
177837 200035398 0 1000000000
188091 196390144 0 1000000000
834632 336263283 0 1000000000
783817 33927658 0 1000000000
579902 554037782 0 1000000000
21839 614012504 0 1000000000
191197 632300439 0 1000000000