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