API  0.9.6
 All Classes Files Functions Variables Macros Groups Pages
CPCharacterSet.j
Go to the documentation of this file.
1 /*
2  * CPCharacterSet.j
3  * Foundation
4  *
5  * Copyright 2008, Emanuele Vulcano
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this library; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 
22 
23 // CPCharacterSet is a class cluster. Concrete implementations
24 // follow after the main abstract class.
25 
26 var _builtInCharacterSets = {};
27 
28 @implementation CPCharacterSet : CPObject
29 {
30  BOOL _inverted;
31 }
32 
33 // Missing methods
34 /*
35 - (BOOL)isSupersetOfSet:(CPCharacterSet)theOtherSet{}
36 + (id)characterSetWithBitmapRepresentation:(CPData)data{}
37 + (id)characterSetWithContentsOfFile:(CPString)path{}
38 - (CPData)bitmapRepresentation{}
39 
40 - (void)formIntersectionWithCharacterSet:(CPCharacterSet)otherSet
41 - (void)formUnionWithCharacterSet:(CPCharacterSet)otherSet
42 - (void)removeCharactersInRange:(CPRange)aRange
43 - (void)removeCharactersInString:(CPString)aString
44 */
45 
46 - (id)init
47 {
48  self = [super init];
49 
50  if (self)
51  _inverted = NO;
52 
53  return self;
54 }
55 
56 - (void)invert
57 {
58  _inverted = !_inverted;
59 }
60 
61 - (BOOL)characterIsMember:(CPString)aCharacter
62 {
63  // IMPLEMENTED BY SUBCLASSES
64 }
65 
66 - (BOOL)hasMemberInPlane:(int)aPlane
67 {
68  // IMPLEMENTED BY SUBCLASSES
69 }
70 
71 + (id)characterSetWithCharactersInString:(CPString)aString
72 {
73  return [[_CPStringContentCharacterSet alloc] initWithString:aString];
74 }
75 
76 + (id)characterSetWithRange:(CPRange)aRange
77 {
78  return [[_CPRangeCharacterSet alloc] initWithRange:aRange];
79 }
80 
82 {
83  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
84 }
85 
87 {
88  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
89 }
90 
92 {
93  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
94 }
95 
97 {
98  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
99 }
100 
102 {
103  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
104 }
105 
107 {
108  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
109 }
110 
112 {
113  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
114 }
115 
117 {
118  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
119 }
120 
122 {
123  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
124 }
125 
127 {
128  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
129 }
130 
132 {
133  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
134 }
135 
137 {
138  return [CPCharacterSet _sharedCharacterSetWithName:_cmd];
139 }
140 
141 // private methods
142 + (id)_sharedCharacterSetWithName:(id)csname
143 {
144  var cs = _builtInCharacterSets[csname];
145  if (cs == nil)
146  {
147  var i = 0,
148  ranges = [CPArray array],
149  rangeArray = eval(csname);
150 
151  for (; i < rangeArray.length; i+= 2)
152  {
153  var loc = rangeArray[i],
154  length = rangeArray[i + 1],
155  range = CPMakeRange(loc,length);
156  [ranges addObject:range];
157  }
158  cs = [[_CPRangeCharacterSet alloc] initWithRanges:ranges];
159  _builtInCharacterSets[csname] = cs;
160  }
161 
162  return cs;
163 }
164 
165 - (void)_setInverted:flag
166 {
167  _inverted = flag;
168 }
169 
170 @end
171 
172 var CPCharacterSetInvertedKey = @"CPCharacterSetInvertedKey";
173 
175 
176 - (id)initWithCoder:(CPCoder)aCoder
177 {
178  if (self = [super init])
179  {
180  _inverted = [aCoder decodeBoolForKey:CPCharacterSetInvertedKey];
181  }
182 
183  return self;
184 }
185 
186 - (void)encodeWithCoder:(CPCoder)aCoder
187 {
188  [aCoder encodeBool:_inverted forKey:CPCharacterSetInvertedKey];
189 }
190 
191 @end
192 
193 // A character set that stores a list of ranges of
194 // acceptable characters.
195 @implementation _CPRangeCharacterSet : CPCharacterSet
196 {
197  CPArray _ranges;
198 }
199 
200 // Creates a range character set with a single range.
201 - (id)initWithRange:(CPRange)r
202 {
203  return [self initWithRanges:[CPArray arrayWithObject:r]];
204 }
205 
206 // Creates a range character set with multiple ranges.
207 - (id)initWithRanges:(CPArray)ranges
208 {
209  self = [super init];
210 
211  if (self)
212  {
213  _ranges = ranges;
214  }
215 
216  return self;
217 }
218 
219 - (id)copy
220 {
221  var set = [[_CPRangeCharacterSet alloc] initWithRanges:_ranges];
222  [set _setInverted:_inverted];
223  return set;
224 }
225 
226 - (id)invertedSet
227 {
228  var set = [[_CPRangeCharacterSet alloc] initWithRanges:_ranges];
229  [set invert];
230  return set;
231 }
232 
233 - (BOOL)characterIsMember:(CPString)aCharacter
234 {
235  c = aCharacter.charCodeAt(0);
236  var enu = [_ranges objectEnumerator],
237  range;
238 
239  while ((range = [enu nextObject]) !== nil)
240  {
241  if (CPLocationInRange(c, range))
242  return !_inverted;
243  }
244 
245  return _inverted;
246 }
247 
248 - (BOOL)hasMemberInPlane:(int)plane // TO DO : when inverted
249 {
250  // FIXME: range is undefined... don't know what's supposed to be going on here.
251  // the highest Unicode plane we reach.
252  // (There are 65536 code points in each plane.)
253  var maxPlane = FLOOR((range.start + range.length - 1) / 65536); // FIXME: should iterate _ranges
254 
255  return (plane <= maxPlane);
256 }
257 
258 - (void)addCharactersInRange:(CPRange)aRange // Needs _inverted support
259 {
260  [_ranges addObject:aRange];
261 }
262 
263 - (void)addCharactersInString:(CPString)aString // Needs _inverted support
264 {
265  var i = 0;
266 
267  for (; i < aString.length; i++)
268  {
269  var code = aString.charCodeAt(i),
270  range = CPMakeRange(code,1);
271 
272  [_ranges addObject:range];
273  }
274 }
275 
276 @end
277 
278 // A character set that scans a string's contents for
279 // acceptable characters.
280 @implementation _CPStringContentCharacterSet : CPCharacterSet
281 {
282  CPString _string;
283 }
284 
285 - (id)initWithString:(CPString)s
286 {
287  self = [super init];
288 
289  if (self)
290  {
291  _string = s;
292  }
293 
294  return self;
295 }
296 
297 - (id)copy
298 {
299  var set = [[_CPStringContentCharacterSet alloc] initWithString:_string];
300  [set _setInverted:_inverted];
301 
302  return set;
303 }
304 
305 - (id)invertedSet
306 {
307  var set = [[_CPStringContentCharacterSet alloc] initWithString:_string];
308  [set invert];
309 
310  return set;
311 }
312 
313 - (BOOL)characterIsMember:(CPString)c
314 {
315  return (_string.indexOf(c.charAt(0)) != -1) == !_inverted;
316 }
317 
318 - (CPString)description
319 {
320  return [super description] + " { string = '" + _string + "'}";
321 }
322 
323 - (BOOL)hasMemberInPlane:(int)plane
324 {
325  // JavaScript strings can only return char codes
326  // up to 0xFFFF (per the ECMA standard), so
327  // they all live in the Basic Multilingual Plane
328  // (aka plane 0).
329  // TODO if the above is wrong, this must be changed!
330 
331  return plane == 0;
332 }
333 
334 - (void)addCharactersInRange:(CPRange)aRange // Needs _inverted support
335 {
336  var i = aRange.location,
337  count = aRange.location + aRange.length;
338 
339  for (; i < count; i++)
340  {
341  var s = String.fromCharCode(i);
342 
343  if (![self characterIsMember:s])
344  _string = [_string stringByAppendingString:s];
345  }
346 }
347 
348 - (void)addCharactersInString:(CPString)aString // Needs _inverted support
349 {
350  var i = 0;
351 
352  for (; i < aString.length; i++)
353  {
354  var s = aString.charAt(i);
355 
356  if (![self characterIsMember:s])
357  _string = [_string stringByAppendingString:s];
358  }
359 }
360 
361 - (BOOL)isEqual:(CPCharacterSet)aCharacterSet
362 {
363  if (self === aCharacterSet)
364  return YES;
365 
366  if (!aCharacterSet || ![aCharacterSet isKindOfClass:[self class]])
367  return NO;
368 
369  return [self _isEqualToStringContentCharacterSet:aCharacterSet];
370 }
371 
372 - (BOOL)_isEqualToStringContentCharacterSet:(_CPStringContentCharacterSet)aCharacterSet
373 {
374  if (!aCharacterSet)
375  return NO;
376 
377  return _string == aCharacterSet._string && _inverted == aCharacterSet._inverted;
378 }
379 
380 @end
381 
382 var _CPStringContentCharacterSetStringKey = @"_CPStringContentCharacterSetStringKey";
383 
384 @implementation _CPStringContentCharacterSet (CPCoding)
385 
386 - (id)initWithCoder:(CPCoder)aCoder
387 {
388  if (self = [super initWithCoder:aCoder])
389  {
390  _string = [aCoder decodeObjectForKey:_CPStringContentCharacterSetStringKey]
391  }
392 
393  return self;
394 }
395 
396 - (void)encodeWithCoder:(CPCoder)aCoder
397 {
398  [super encodeWithCoder:aCoder];
399 
400  [aCoder encodeObject:_string forKey:_CPStringContentCharacterSetStringKey];
401 }
402 
403 @end
404 
405 _CPCharacterSetTrimAtBeginning = 1 << 1;
406 _CPCharacterSetTrimAtEnd = 1 << 2;
407 
408 @implementation CPString (CPCharacterSetAdditions)
409 
422 - (CPArray)componentsSeparatedByCharactersInSet:(CPCharacterSet)separator
423 {
424  if (!separator)
425  [CPException raise:CPInvalidArgumentException
426  reason:"componentsSeparatedByCharactersInSet: the separator can't be 'nil'"];
427 
428  var components = [CPMutableArray array],
429  componentRange = CPMakeRange(0, 0),
430  i = 0;
431 
432  for (; i < self.length; i++)
433  {
434  if ([separator characterIsMember:self.charAt(i)])
435  {
436  componentRange.length = i - componentRange.location;
437  [components addObject:[self substringWithRange:componentRange]];
438  componentRange.location += componentRange.length + 1;
439  }
440  }
441 
442  componentRange.length = self.length - componentRange.location;
443  [components addObject:[self substringWithRange:componentRange]];
444 
445  return components;
446 }
447 
448 // As per the Cocoa method.
449 - (id)stringByTrimmingCharactersInSet:(CPCharacterSet)set
450 {
451  return [self _stringByTrimmingCharactersInSet:set options:_CPCharacterSetTrimAtBeginning | _CPCharacterSetTrimAtEnd];
452 }
453 
454 // private method evilness!
455 // CPScanner's scanUpToString:... methods rely on this
456 // method being present.
457 - (id)_stringByTrimmingCharactersInSet:(CPCharacterSet)set options:(int)options
458 {
459  var str = self;
460 
461  if (options & _CPCharacterSetTrimAtBeginning)
462  {
463  var cutEdgeBeginning = 0;
464 
465  while (cutEdgeBeginning < self.length && [set characterIsMember:self.charAt(cutEdgeBeginning)])
466  cutEdgeBeginning++;
467 
468  str = str.substr(cutEdgeBeginning);
469  }
470 
471  if (options & _CPCharacterSetTrimAtEnd)
472  {
473  var cutEdgeEnd = str.length;
474 
475  while (cutEdgeEnd > 0 && [set characterIsMember:self.charAt(cutEdgeEnd)])
476  cutEdgeEnd--;
477 
478  str = str.substr(0, cutEdgeEnd + 1);
479  }
480 
481  return str;
482 }
483 
484 @end
485 
487 48,10,
488 65,26,
489 97,26,
490 170,1,
491 178,2,
492 181,1,
493 185,2,
494 188,3,
495 192,23,
496 216,31,
497 248,458,
498 710,12,
499 736,5,
500 750,1,
501 768,112,
502 890,4,
503 902,1,
504 904,3,
505 908,1,
506 910,20,
507 931,44,
508 976,38,
509 1015,139,
510 1155,4,
511 1160,140,
512 1329,38,
513 1369,1,
514 1377,39,
515 1425,45,
516 1471,1,
517 1473,2,
518 1476,2,
519 1479,1,
520 1488,27,
521 1520,3,
522 1552,6,
523 1569,26,
524 1600,31,
525 1632,10,
526 1646,102,
527 1749,8,
528 1758,11,
529 1770,19,
530 1791,1,
531 1808,59,
532 1869,33,
533 1920,50,
534 1984,54,
535 2042,1,
536 2305,57,
537 2364,18,
538 2384,5,
539 2392,12,
540 2406,10,
541 2427,5,
542 2433,3,
543 2437,8,
544 2447,2,
545 2451,22,
546 2474,7,
547 2482,1,
548 2486,4,
549 2492,9,
550 2503,2,
551 2507,4,
552 2519,1,
553 2524,2,
554 2527,5,
555 2534,12,
556 2548,6,
557 2561,3,
558 2565,6,
559 2575,2,
560 2579,22,
561 2602,7,
562 2610,2,
563 2613,2,
564 2616,2,
565 2620,1,
566 2622,5,
567 2631,2,
568 2635,3,
569 2649,4,
570 2654,1,
571 2662,15,
572 2689,3,
573 2693,9,
574 2703,3,
575 2707,22,
576 2730,7,
577 2738,2,
578 2741,5,
579 2748,10,
580 2759,3,
581 2763,3,
582 2768,1,
583 2784,4,
584 2790,10,
585 2817,3,
586 2821,8,
587 2831,2,
588 2835,22,
589 2858,7,
590 2866,2,
591 2869,5,
592 2876,8,
593 2887,2,
594 2891,3,
595 2902,2,
596 2908,2,
597 2911,3,
598 2918,10,
599 2929,1,
600 2946,2,
601 2949,6,
602 2958,3,
603 2962,4,
604 2969,2,
605 2972,1,
606 2974,2,
607 2979,2,
608 2984,3,
609 2990,12,
610 3006,5,
611 3014,3,
612 3018,4,
613 3031,1,
614 3046,13,
615 3073,3,
616 3077,8,
617 3086,3,
618 3090,23,
619 3114,10,
620 3125,5,
621 3134,7,
622 3142,3,
623 3146,4,
624 3157,2,
625 3168,2,
626 3174,10,
627 3202,2,
628 3205,8,
629 3214,3,
630 3218,23,
631 3242,10,
632 3253,5,
633 3260,9,
634 3270,3,
635 3274,4,
636 3285,2,
637 3294,1,
638 3296,4,
639 3302,10,
640 3330,2,
641 3333,8,
642 3342,3,
643 3346,23,
644 3370,16,
645 3390,6,
646 3398,3,
647 3402,4,
648 3415,1,
649 3424,2,
650 3430,10,
651 3458,2,
652 3461,18,
653 3482,24,
654 3507,9,
655 3517,1,
656 3520,7,
657 3530,1,
658 3535,6,
659 3542,1,
660 3544,8,
661 3570,2,
662 3585,58,
663 3648,15,
664 3664,10,
665 3713,2,
666 3716,1,
667 3719,2,
668 3722,1,
669 3725,1,
670 3732,4,
671 3737,7,
672 3745,3,
673 3749,1,
674 3751,1,
675 3754,2,
676 3757,13,
677 3771,3,
678 3776,5,
679 3782,1,
680 3784,6,
681 3792,10,
682 3804,2,
683 3840,1,
684 3864,2,
685 3872,20,
686 3893,1,
687 3895,1,
688 3897,1,
689 3902,10,
690 3913,34,
691 3953,20,
692 3974,6,
693 3984,8,
694 3993,36,
695 4038,1,
696 4096,34,
697 4131,5,
698 4137,2,
699 4140,7,
700 4150,4,
701 4160,10,
702 4176,10,
703 4256,38,
704 4304,43,
705 4348,1,
706 4352,90,
707 4447,68,
708 4520,82,
709 4608,73,
710 4682,4,
711 4688,7,
712 4696,1,
713 4698,4,
714 4704,41,
715 4746,4,
716 4752,33,
717 4786,4,
718 4792,7,
719 4800,1,
720 4802,4,
721 4808,15,
722 4824,57,
723 4882,4,
724 4888,67,
725 4959,1,
726 4969,20,
727 4992,16,
728 5024,85,
729 5121,620,
730 5743,8,
731 5761,26,
732 5792,75,
733 5870,3,
734 5888,13,
735 5902,7,
736 5920,21,
737 5952,20,
738 5984,13,
739 5998,3,
740 6002,2,
741 6016,52,
742 6070,30,
743 6103,1,
744 6108,2,
745 6112,10,
746 6128,10,
747 6155,3,
748 6160,10,
749 6176,88,
750 6272,42,
751 6400,29,
752 6432,12,
753 6448,12,
754 6470,40,
755 6512,5,
756 6528,42,
757 6576,26,
758 6608,10,
759 6656,28,
760 6912,76,
761 6992,10,
762 7019,9,
763 7424,203,
764 7678,158,
765 7840,90,
766 7936,22,
767 7960,6,
768 7968,38,
769 8008,6,
770 8016,8,
771 8025,1,
772 8027,1,
773 8029,1,
774 8031,31,
775 8064,53,
776 8118,7,
777 8126,1,
778 8130,3,
779 8134,7,
780 8144,4,
781 8150,6,
782 8160,13,
783 8178,3,
784 8182,7,
785 8304,2,
786 8308,6,
787 8319,11,
788 8336,5,
789 8400,32,
790 8450,1,
791 8455,1,
792 8458,10,
793 8469,1,
794 8473,5,
795 8484,1,
796 8486,1,
797 8488,1,
798 8490,4,
799 8495,11,
800 8508,4,
801 8517,5,
802 8526,1,
803 8531,50,
804 9312,60,
805 9450,22,
806 10102,30,
807 11264,47,
808 11312,47,
809 11360,13,
810 11380,4,
811 11392,101,
812 11517,1,
813 11520,38,
814 11568,54,
815 11631,1,
816 11648,23,
817 11680,7,
818 11688,7,
819 11696,7,
820 11704,7,
821 11712,7,
822 11720,7,
823 11728,7,
824 11736,7,
825 12293,3,
826 12321,15,
827 12337,5,
828 12344,5,
829 12353,86,
830 12441,2,
831 12445,3,
832 12449,90,
833 12540,4,
834 12549,40,
835 12593,94,
836 12690,4,
837 12704,24,
838 12784,16,
839 12832,10,
840 12881,15,
841 12928,10,
842 12977,15,
843 13312,6582,
844 19968,20924,
845 40960,1165,
846 42775,4,
847 43008,40,
848 43072,52,
849 44032,11172,
850 63744,302,
851 64048,59,
852 64112,106,
853 64256,7,
854 64275,5,
855 64285,12,
856 64298,13,
857 64312,5,
858 64318,1,
859 64320,2,
860 64323,2,
861 64326,108,
862 64467,363,
863 64848,64,
864 64914,54,
865 65008,12,
866 65024,16,
867 65056,4,
868 65136,5,
869 65142,135,
870 65296,10,
871 65313,26,
872 65345,26,
873 65382,89,
874 65474,6,
875 65482,6,
876 65490,6
877 ];
878 
880 0,32,
881 127,33,
882 173,1,
883 1536,4,
884 1757,1,
885 1807,1,
886 6068,2,
887 8203,5,
888 8234,5,
889 8288,4,
890 8298,6,
891 65279,1
892 ];
893 
895 48,10,
896 1632,10,
897 1776,10,
898 1984,10,
899 2406,10,
900 2534,10,
901 2662,10,
902 2790,10,
903 2918,10,
904 3046,10,
905 3174,10,
906 3302,10,
907 3430,10,
908 3664,10,
909 3792,10,
910 3872,10,
911 4160,10,
912 6112,10,
913 6160,10,
914 6470,10,
915 6608,10,
916 6992,10
917 ];
918 
920 192,6,
921 199,9,
922 209,6,
923 217,5,
924 224,6,
925 231,9,
926 241,6,
927 249,5,
928 255,17,
929 274,20,
930 296,9,
931 308,4,
932 313,6,
933 323,6,
934 332,6,
935 340,18,
936 360,23,
937 416,2,
938 431,2,
939 461,16,
940 478,6,
941 486,11,
942 500,2,
943 504,36,
944 542,2,
945 550,14,
946 832,2,
947 835,2,
948 884,1,
949 894,1,
950 901,6,
951 908,1,
952 910,3,
953 938,7,
954 970,5,
955 979,2,
956 1024,2,
957 1027,1,
958 1031,1,
959 1036,3,
960 1049,1,
961 1081,1,
962 1104,2,
963 1107,1,
964 1111,1,
965 1116,3,
966 1142,2,
967 1217,2,
968 1232,4,
969 1238,2,
970 1242,6,
971 1250,6,
972 1258,12,
973 1272,2,
974 1570,5,
975 1728,1,
976 1730,1,
977 1747,1,
978 2345,1,
979 2353,1,
980 2356,1,
981 2392,8,
982 2507,2,
983 2524,2,
984 2527,1,
985 2611,1,
986 2614,1,
987 2649,3,
988 2654,1,
989 2888,1,
990 2891,2,
991 2908,2,
992 2964,1,
993 3018,3,
994 3144,1,
995 3264,1,
996 3271,2,
997 3274,2,
998 3402,3,
999 3546,1,
1000 3548,3,
1001 3907,1,
1002 3917,1,
1003 3922,1,
1004 3927,1,
1005 3932,1,
1006 3945,1,
1007 3955,1,
1008 3957,2,
1009 3960,1,
1010 3969,1,
1011 3987,1,
1012 3997,1,
1013 4002,1,
1014 4007,1,
1015 4012,1,
1016 4025,1,
1017 4134,1,
1018 6918,1,
1019 6920,1,
1020 6922,1,
1021 6924,1,
1022 6926,1,
1023 6930,1,
1024 6971,1,
1025 6973,1,
1026 6976,2,
1027 6979,1,
1028 7680,154,
1029 7835,1,
1030 7840,90,
1031 7936,22,
1032 7960,6,
1033 7968,38,
1034 8008,6,
1035 8016,8,
1036 8025,1,
1037 8027,1,
1038 8029,1,
1039 8031,31,
1040 8064,53,
1041 8118,7,
1042 8126,1,
1043 8129,4,
1044 8134,14,
1045 8150,6,
1046 8157,19,
1047 8178,3,
1048 8182,8,
1049 8192,2,
1050 8486,1,
1051 8490,2,
1052 8602,2,
1053 8622,1,
1054 8653,3,
1055 8708,1,
1056 8713,1,
1057 8716,1,
1058 8740,1,
1059 8742,1,
1060 8769,1,
1061 8772,1,
1062 8775,1,
1063 8777,1,
1064 8800,1,
1065 8802,1,
1066 8813,5,
1067 8820,2,
1068 8824,2,
1069 8832,2,
1070 8836,2,
1071 8840,2,
1072 8876,4,
1073 8928,4,
1074 8938,4,
1075 9001,2,
1076 10972,1,
1077 12364,1,
1078 12366,1,
1079 12368,1,
1080 12370,1,
1081 12372,1,
1082 12374,1,
1083 12376,1,
1084 12378,1,
1085 12380,1,
1086 12382,1,
1087 12384,1,
1088 12386,1,
1089 12389,1,
1090 12391,1,
1091 12393,1,
1092 12400,2,
1093 12403,2,
1094 12406,2,
1095 12409,2,
1096 12412,2,
1097 12436,1,
1098 12446,1,
1099 12460,1,
1100 12462,1,
1101 12464,1,
1102 12466,1,
1103 12468,1,
1104 12470,1,
1105 12472,1,
1106 12474,1,
1107 12476,1,
1108 12478,1,
1109 12480,1,
1110 12482,1,
1111 12485,1,
1112 12487,1,
1113 12489,1,
1114 12496,2,
1115 12499,2,
1116 12502,2,
1117 12505,2,
1118 12508,2,
1119 12532,1,
1120 12535,4,
1121 12542,1,
1122 44032,11172,
1123 63744,270,
1124 64016,1,
1125 64018,1,
1126 64021,10,
1127 64032,1,
1128 64034,1,
1129 64037,2,
1130 64042,4,
1131 64048,59,
1132 64112,106,
1133 64285,1,
1134 64287,1,
1135 64298,13,
1136 64312,5,
1137 64318,1,
1138 64320,2,
1139 64323,2
1140 ];
1141 
1143 880,4,
1144 886,4,
1145 895,5,
1146 907,1,
1147 909,1,
1148 930,1,
1149 975,1,
1150 1159,1,
1151 1300,29,
1152 1367,2,
1153 1376,1,
1154 1416,1,
1155 1419,6,
1156 1480,8,
1157 1515,5,
1158 1525,11,
1159 1540,7,
1160 1558,5,
1161 1564,2,
1162 1568,1,
1163 1595,5,
1164 1631,1,
1165 1806,1,
1166 1867,2,
1167 1902,18,
1168 1970,14,
1169 2043,262,
1170 2362,2,
1171 2382,2,
1172 2389,3,
1173 2417,10,
1174 2432,1,
1175 2436,1,
1176 2445,2,
1177 2449,2,
1178 2473,1,
1179 2481,1,
1180 2483,3,
1181 2490,2,
1182 2501,2,
1183 2505,2,
1184 2511,8,
1185 2520,4,
1186 2526,1,
1187 2532,2,
1188 2555,6,
1189 2564,1,
1190 2571,4,
1191 2577,2,
1192 2601,1,
1193 2609,1,
1194 2612,1,
1195 2615,1,
1196 2618,2,
1197 2621,1,
1198 2627,4,
1199 2633,2,
1200 2638,11,
1201 2653,1,
1202 2655,7,
1203 2677,12,
1204 2692,1,
1205 2702,1,
1206 2706,1,
1207 2729,1,
1208 2737,1,
1209 2740,1,
1210 2746,2,
1211 2758,1,
1212 2762,1,
1213 2766,2,
1214 2769,15,
1215 2788,2,
1216 2800,1,
1217 2802,15,
1218 2820,1,
1219 2829,2,
1220 2833,2,
1221 2857,1,
1222 2865,1,
1223 2868,1,
1224 2874,2,
1225 2884,3,
1226 2889,2,
1227 2894,8,
1228 2904,4,
1229 2910,1,
1230 2914,4,
1231 2930,16,
1232 2948,1,
1233 2955,3,
1234 2961,1,
1235 2966,3,
1236 2971,1,
1237 2973,1,
1238 2976,3,
1239 2981,3,
1240 2987,3,
1241 3002,4,
1242 3011,3,
1243 3017,1,
1244 3022,9,
1245 3032,14,
1246 3067,6,
1247 3076,1,
1248 3085,1,
1249 3089,1,
1250 3113,1,
1251 3124,1,
1252 3130,4,
1253 3141,1,
1254 3145,1,
1255 3150,7,
1256 3159,9,
1257 3170,4,
1258 3184,18,
1259 3204,1,
1260 3213,1,
1261 3217,1,
1262 3241,1,
1263 3252,1,
1264 3258,2,
1265 3269,1,
1266 3273,1,
1267 3278,7,
1268 3287,7,
1269 3295,1,
1270 3300,2,
1271 3312,1,
1272 3315,15,
1273 3332,1,
1274 3341,1,
1275 3345,1,
1276 3369,1,
1277 3386,4,
1278 3396,2,
1279 3401,1,
1280 3406,9,
1281 3416,8,
1282 3426,4,
1283 3440,18,
1284 3460,1,
1285 3479,3,
1286 3506,1,
1287 3516,1,
1288 3518,2,
1289 3527,3,
1290 3531,4,
1291 3541,1,
1292 3543,1,
1293 3552,18,
1294 3573,12,
1295 3643,4,
1296 3676,37,
1297 3715,1,
1298 3717,2,
1299 3721,1,
1300 3723,2,
1301 3726,6,
1302 3736,1,
1303 3744,1,
1304 3748,1,
1305 3750,1,
1306 3752,2,
1307 3756,1,
1308 3770,1,
1309 3774,2,
1310 3781,1,
1311 3783,1,
1312 3790,2,
1313 3802,2,
1314 3806,34,
1315 3912,1,
1316 3947,6,
1317 3980,4,
1318 3992,1,
1319 4029,1,
1320 4045,2,
1321 4050,46,
1322 4130,1,
1323 4136,1,
1324 4139,1,
1325 4147,3,
1326 4154,6,
1327 4186,70,
1328 4294,10,
1329 4349,3,
1330 4442,5,
1331 4515,5,
1332 4602,6,
1333 4681,1,
1334 4686,2,
1335 4695,1,
1336 4697,1,
1337 4702,2,
1338 4745,1,
1339 4750,2,
1340 4785,1,
1341 4790,2,
1342 4799,1,
1343 4801,1,
1344 4806,2,
1345 4823,1,
1346 4881,1,
1347 4886,2,
1348 4955,4,
1349 4989,3,
1350 5018,6,
1351 5109,12,
1352 5751,9,
1353 5789,3,
1354 5873,15,
1355 5901,1,
1356 5909,11,
1357 5943,9,
1358 5972,12,
1359 5997,1,
1360 6001,1,
1361 6004,12,
1362 6110,2,
1363 6122,6,
1364 6138,6,
1365 6159,1,
1366 6170,6,
1367 6264,8,
1368 6314,86,
1369 6429,3,
1370 6444,4,
1371 6460,4,
1372 6465,3,
1373 6510,2,
1374 6517,11,
1375 6570,6,
1376 6602,6,
1377 6618,4,
1378 6684,2,
1379 6688,224,
1380 6988,4,
1381 7037,387,
1382 7627,51,
1383 7836,4,
1384 7930,6,
1385 7958,2,
1386 7966,2,
1387 8006,2,
1388 8014,2,
1389 8024,1,
1390 8026,1,
1391 8028,1,
1392 8030,1,
1393 8062,2,
1394 8117,1,
1395 8133,1,
1396 8148,2,
1397 8156,1,
1398 8176,2,
1399 8181,1,
1400 8191,1,
1401 8292,6,
1402 8306,2,
1403 8335,1,
1404 8341,11,
1405 8374,26,
1406 8432,16,
1407 8527,4,
1408 8581,11,
1409 9192,24,
1410 9255,25,
1411 9291,21,
1412 9885,3,
1413 9907,78,
1414 9989,1,
1415 9994,2,
1416 10024,1,
1417 10060,1,
1418 10062,1,
1419 10067,3,
1420 10071,1,
1421 10079,2,
1422 10133,3,
1423 10160,1,
1424 10175,1,
1425 10187,5,
1426 10220,4,
1427 11035,5,
1428 11044,220,
1429 11311,1,
1430 11359,1,
1431 11373,7,
1432 11384,8,
1433 11499,14,
1434 11558,10,
1435 11622,9,
1436 11632,16,
1437 11671,9,
1438 11687,1,
1439 11695,1,
1440 11703,1,
1441 11711,1,
1442 11719,1,
1443 11727,1,
1444 11735,1,
1445 11743,33,
1446 11800,4,
1447 11806,98,
1448 11930,1,
1449 12020,12,
1450 12246,26,
1451 12284,4,
1452 12352,1,
1453 12439,2,
1454 12544,5,
1455 12589,4,
1456 12687,1,
1457 12728,8,
1458 12752,32,
1459 12831,1,
1460 12868,12,
1461 13055,1,
1462 19894,10,
1463 40892,68,
1464 42125,3,
1465 42183,569,
1466 42779,5,
1467 42786,222,
1468 43052,20,
1469 43128,904,
1470 55204,92,
1471 64046,2,
1472 64107,5,
1473 64218,38,
1474 64263,12,
1475 64280,5,
1476 64311,1,
1477 64317,1,
1478 64319,1,
1479 64322,1,
1480 64325,1,
1481 64434,33,
1482 64832,16,
1483 64912,2,
1484 64968,40,
1485 65022,2,
1486 65050,6,
1487 65060,12,
1488 65107,1,
1489 65127,1,
1490 65132,4,
1491 65141,1,
1492 65277,2,
1493 65280,1,
1494 65471,3,
1495 65480,2,
1496 65488,2,
1497 65496,2,
1498 65501,3,
1499 65511,1,
1500 65519,10
1501 ];
1502 
1504 65,26,
1505 97,26,
1506 170,1,
1507 181,1,
1508 186,1,
1509 192,23,
1510 216,31,
1511 248,458,
1512 710,12,
1513 736,5,
1514 750,1,
1515 768,112,
1516 890,4,
1517 902,1,
1518 904,3,
1519 908,1,
1520 910,20,
1521 931,44,
1522 976,38,
1523 1015,139,
1524 1155,4,
1525 1160,140,
1526 1329,38,
1527 1369,1,
1528 1377,39,
1529 1425,45,
1530 1471,1,
1531 1473,2,
1532 1476,2,
1533 1479,1,
1534 1488,27,
1535 1520,3,
1536 1552,6,
1537 1569,26,
1538 1600,31,
1539 1646,102,
1540 1749,8,
1541 1758,11,
1542 1770,6,
1543 1786,3,
1544 1791,1,
1545 1808,59,
1546 1869,33,
1547 1920,50,
1548 1994,44,
1549 2042,1,
1550 2305,57,
1551 2364,18,
1552 2384,5,
1553 2392,12,
1554 2427,5,
1555 2433,3,
1556 2437,8,
1557 2447,2,
1558 2451,22,
1559 2474,7,
1560 2482,1,
1561 2486,4,
1562 2492,9,
1563 2503,2,
1564 2507,4,
1565 2519,1,
1566 2524,2,
1567 2527,5,
1568 2544,2,
1569 2561,3,
1570 2565,6,
1571 2575,2,
1572 2579,22,
1573 2602,7,
1574 2610,2,
1575 2613,2,
1576 2616,2,
1577 2620,1,
1578 2622,5,
1579 2631,2,
1580 2635,3,
1581 2649,4,
1582 2654,1,
1583 2672,5,
1584 2689,3,
1585 2693,9,
1586 2703,3,
1587 2707,22,
1588 2730,7,
1589 2738,2,
1590 2741,5,
1591 2748,10,
1592 2759,3,
1593 2763,3,
1594 2768,1,
1595 2784,4,
1596 2817,3,
1597 2821,8,
1598 2831,2,
1599 2835,22,
1600 2858,7,
1601 2866,2,
1602 2869,5,
1603 2876,8,
1604 2887,2,
1605 2891,3,
1606 2902,2,
1607 2908,2,
1608 2911,3,
1609 2929,1,
1610 2946,2,
1611 2949,6,
1612 2958,3,
1613 2962,4,
1614 2969,2,
1615 2972,1,
1616 2974,2,
1617 2979,2,
1618 2984,3,
1619 2990,12,
1620 3006,5,
1621 3014,3,
1622 3018,4,
1623 3031,1,
1624 3073,3,
1625 3077,8,
1626 3086,3,
1627 3090,23,
1628 3114,10,
1629 3125,5,
1630 3134,7,
1631 3142,3,
1632 3146,4,
1633 3157,2,
1634 3168,2,
1635 3202,2,
1636 3205,8,
1637 3214,3,
1638 3218,23,
1639 3242,10,
1640 3253,5,
1641 3260,9,
1642 3270,3,
1643 3274,4,
1644 3285,2,
1645 3294,1,
1646 3296,4,
1647 3330,2,
1648 3333,8,
1649 3342,3,
1650 3346,23,
1651 3370,16,
1652 3390,6,
1653 3398,3,
1654 3402,4,
1655 3415,1,
1656 3424,2,
1657 3458,2,
1658 3461,18,
1659 3482,24,
1660 3507,9,
1661 3517,1,
1662 3520,7,
1663 3530,1,
1664 3535,6,
1665 3542,1,
1666 3544,8,
1667 3570,2,
1668 3585,58,
1669 3648,15,
1670 3713,2,
1671 3716,1,
1672 3719,2,
1673 3722,1,
1674 3725,1,
1675 3732,4,
1676 3737,7,
1677 3745,3,
1678 3749,1,
1679 3751,1,
1680 3754,2,
1681 3757,13,
1682 3771,3,
1683 3776,5,
1684 3782,1,
1685 3784,6,
1686 3804,2,
1687 3840,1,
1688 3864,2,
1689 3893,1,
1690 3895,1,
1691 3897,1,
1692 3902,10,
1693 3913,34,
1694 3953,20,
1695 3974,6,
1696 3984,8,
1697 3993,36,
1698 4038,1,
1699 4096,34,
1700 4131,5,
1701 4137,2,
1702 4140,7,
1703 4150,4,
1704 4176,10,
1705 4256,38,
1706 4304,43,
1707 4348,1,
1708 4352,90,
1709 4447,68,
1710 4520,82,
1711 4608,73,
1712 4682,4,
1713 4688,7,
1714 4696,1,
1715 4698,4,
1716 4704,41,
1717 4746,4,
1718 4752,33,
1719 4786,4,
1720 4792,7,
1721 4800,1,
1722 4802,4,
1723 4808,15,
1724 4824,57,
1725 4882,4,
1726 4888,67,
1727 4959,1,
1728 4992,16,
1729 5024,85,
1730 5121,620,
1731 5743,8,
1732 5761,26,
1733 5792,75,
1734 5888,13,
1735 5902,7,
1736 5920,21,
1737 5952,20,
1738 5984,13,
1739 5998,3,
1740 6002,2,
1741 6016,52,
1742 6070,30,
1743 6103,1,
1744 6108,2,
1745 6155,3,
1746 6176,88,
1747 6272,42,
1748 6400,29,
1749 6432,12,
1750 6448,12,
1751 6480,30,
1752 6512,5,
1753 6528,42,
1754 6576,26,
1755 6656,28,
1756 6912,76,
1757 7019,9,
1758 7424,203,
1759 7678,158,
1760 7840,90,
1761 7936,22,
1762 7960,6,
1763 7968,38,
1764 8008,6,
1765 8016,8,
1766 8025,1,
1767 8027,1,
1768 8029,1,
1769 8031,31,
1770 8064,53,
1771 8118,7,
1772 8126,1,
1773 8130,3,
1774 8134,7,
1775 8144,4,
1776 8150,6,
1777 8160,13,
1778 8178,3,
1779 8182,7,
1780 8305,1,
1781 8319,1,
1782 8336,5,
1783 8400,32,
1784 8450,1,
1785 8455,1,
1786 8458,10,
1787 8469,1,
1788 8473,5,
1789 8484,1,
1790 8486,1,
1791 8488,1,
1792 8490,4,
1793 8495,11,
1794 8508,4,
1795 8517,5,
1796 8526,1,
1797 8579,2,
1798 11264,47,
1799 11312,47,
1800 11360,13,
1801 11380,4,
1802 11392,101,
1803 11520,38,
1804 11568,54,
1805 11631,1,
1806 11648,23,
1807 11680,7,
1808 11688,7,
1809 11696,7,
1810 11704,7,
1811 11712,7,
1812 11720,7,
1813 11728,7,
1814 11736,7,
1815 12293,2,
1816 12330,6,
1817 12337,5,
1818 12347,2,
1819 12353,86,
1820 12441,2,
1821 12445,3,
1822 12449,90,
1823 12540,4,
1824 12549,40,
1825 12593,94,
1826 12704,24,
1827 12784,16,
1828 13312,6582,
1829 19968,20924,
1830 40960,1165,
1831 42775,4,
1832 43008,40,
1833 43072,52,
1834 44032,11172,
1835 63744,302,
1836 64048,59,
1837 64112,106,
1838 64256,7,
1839 64275,5,
1840 64285,12,
1841 64298,13,
1842 64312,5,
1843 64318,1,
1844 64320,2,
1845 64323,2,
1846 64326,108,
1847 64467,363,
1848 64848,64,
1849 64914,54,
1850 65008,12,
1851 65024,16,
1852 65056,4,
1853 65136,5,
1854 65142,135,
1855 65313,26,
1856 65345,26,
1857 65382,89,
1858 65474,6,
1859 65482,6,
1860 65490,6
1861 ];
1862 
1864 97,26,
1865 170,1,
1866 181,1,
1867 186,1,
1868 223,24,
1869 248,8,
1870 257,1,
1871 259,1,
1872 261,1,
1873 263,1,
1874 265,1,
1875 267,1,
1876 269,1,
1877 271,1,
1878 273,1,
1879 275,1,
1880 277,1,
1881 279,1,
1882 281,1,
1883 283,1,
1884 285,1,
1885 287,1,
1886 289,1,
1887 291,1,
1888 293,1,
1889 295,1,
1890 297,1,
1891 299,1,
1892 301,1,
1893 303,1,
1894 305,1,
1895 307,1,
1896 309,1,
1897 311,2,
1898 314,1,
1899 316,1,
1900 318,1,
1901 320,1,
1902 322,1,
1903 324,1,
1904 326,1,
1905 328,2,
1906 331,1,
1907 333,1,
1908 335,1,
1909 337,1,
1910 339,1,
1911 341,1,
1912 343,1,
1913 345,1,
1914 347,1,
1915 349,1,
1916 351,1,
1917 353,1,
1918 355,1,
1919 357,1,
1920 359,1,
1921 361,1,
1922 363,1,
1923 365,1,
1924 367,1,
1925 369,1,
1926 371,1,
1927 373,1,
1928 375,1,
1929 378,1,
1930 380,1,
1931 382,3,
1932 387,1,
1933 389,1,
1934 392,1,
1935 396,2,
1936 402,1,
1937 405,1,
1938 409,3,
1939 414,1,
1940 417,1,
1941 419,1,
1942 421,1,
1943 424,1,
1944 426,2,
1945 429,1,
1946 432,1,
1947 436,1,
1948 438,1,
1949 441,2,
1950 445,3,
1951 454,1,
1952 457,1,
1953 460,1,
1954 462,1,
1955 464,1,
1956 466,1,
1957 468,1,
1958 470,1,
1959 472,1,
1960 474,1,
1961 476,2,
1962 479,1,
1963 481,1,
1964 483,1,
1965 485,1,
1966 487,1,
1967 489,1,
1968 491,1,
1969 493,1,
1970 495,2,
1971 499,1,
1972 501,1,
1973 505,1,
1974 507,1,
1975 509,1,
1976 511,1,
1977 513,1,
1978 515,1,
1979 517,1,
1980 519,1,
1981 521,1,
1982 523,1,
1983 525,1,
1984 527,1,
1985 529,1,
1986 531,1,
1987 533,1,
1988 535,1,
1989 537,1,
1990 539,1,
1991 541,1,
1992 543,1,
1993 545,1,
1994 547,1,
1995 549,1,
1996 551,1,
1997 553,1,
1998 555,1,
1999 557,1,
2000 559,1,
2001 561,1,
2002 563,7,
2003 572,1,
2004 575,2,
2005 578,1,
2006 583,1,
2007 585,1,
2008 587,1,
2009 589,1,
2010 591,69,
2011 661,27,
2012 891,3,
2013 912,1,
2014 940,35,
2015 976,2,
2016 981,3,
2017 985,1,
2018 987,1,
2019 989,1,
2020 991,1,
2021 993,1,
2022 995,1,
2023 997,1,
2024 999,1,
2025 1001,1,
2026 1003,1,
2027 1005,1,
2028 1007,5,
2029 1013,1,
2030 1016,1,
2031 1019,2,
2032 1072,48,
2033 1121,1,
2034 1123,1,
2035 1125,1,
2036 1127,1,
2037 1129,1,
2038 1131,1,
2039 1133,1,
2040 1135,1,
2041 1137,1,
2042 1139,1,
2043 1141,1,
2044 1143,1,
2045 1145,1,
2046 1147,1,
2047 1149,1,
2048 1151,1,
2049 1153,1,
2050 1163,1,
2051 1165,1,
2052 1167,1,
2053 1169,1,
2054 1171,1,
2055 1173,1,
2056 1175,1,
2057 1177,1,
2058 1179,1,
2059 1181,1,
2060 1183,1,
2061 1185,1,
2062 1187,1,
2063 1189,1,
2064 1191,1,
2065 1193,1,
2066 1195,1,
2067 1197,1,
2068 1199,1,
2069 1201,1,
2070 1203,1,
2071 1205,1,
2072 1207,1,
2073 1209,1,
2074 1211,1,
2075 1213,1,
2076 1215,1,
2077 1218,1,
2078 1220,1,
2079 1222,1,
2080 1224,1,
2081 1226,1,
2082 1228,1,
2083 1230,2,
2084 1233,1,
2085 1235,1,
2086 1237,1,
2087 1239,1,
2088 1241,1,
2089 1243,1,
2090 1245,1,
2091 1247,1,
2092 1249,1,
2093 1251,1,
2094 1253,1,
2095 1255,1,
2096 1257,1,
2097 1259,1,
2098 1261,1,
2099 1263,1,
2100 1265,1,
2101 1267,1,
2102 1269,1,
2103 1271,1,
2104 1273,1,
2105 1275,1,
2106 1277,1,
2107 1279,1,
2108 1281,1,
2109 1283,1,
2110 1285,1,
2111 1287,1,
2112 1289,1,
2113 1291,1,
2114 1293,1,
2115 1295,1,
2116 1297,1,
2117 1299,1,
2118 1377,39,
2119 7424,44,
2120 7522,22,
2121 7545,34,
2122 7681,1,
2123 7683,1,
2124 7685,1,
2125 7687,1,
2126 7689,1,
2127 7691,1,
2128 7693,1,
2129 7695,1,
2130 7697,1,
2131 7699,1,
2132 7701,1,
2133 7703,1,
2134 7705,1,
2135 7707,1,
2136 7709,1,
2137 7711,1,
2138 7713,1,
2139 7715,1,
2140 7717,1,
2141 7719,1,
2142 7721,1,
2143 7723,1,
2144 7725,1,
2145 7727,1,
2146 7729,1,
2147 7731,1,
2148 7733,1,
2149 7735,1,
2150 7737,1,
2151 7739,1,
2152 7741,1,
2153 7743,1,
2154 7745,1,
2155 7747,1,
2156 7749,1,
2157 7751,1,
2158 7753,1,
2159 7755,1,
2160 7757,1,
2161 7759,1,
2162 7761,1,
2163 7763,1,
2164 7765,1,
2165 7767,1,
2166 7769,1,
2167 7771,1,
2168 7773,1,
2169 7775,1,
2170 7777,1,
2171 7779,1,
2172 7781,1,
2173 7783,1,
2174 7785,1,
2175 7787,1,
2176 7789,1,
2177 7791,1,
2178 7793,1,
2179 7795,1,
2180 7797,1,
2181 7799,1,
2182 7801,1,
2183 7803,1,
2184 7805,1,
2185 7807,1,
2186 7809,1,
2187 7811,1,
2188 7813,1,
2189 7815,1,
2190 7817,1,
2191 7819,1,
2192 7821,1,
2193 7823,1,
2194 7825,1,
2195 7827,1,
2196 7829,7,
2197 7841,1,
2198 7843,1,
2199 7845,1,
2200 7847,1,
2201 7849,1,
2202 7851,1,
2203 7853,1,
2204 7855,1,
2205 7857,1,
2206 7859,1,
2207 7861,1,
2208 7863,1,
2209 7865,1,
2210 7867,1,
2211 7869,1,
2212 7871,1,
2213 7873,1,
2214 7875,1,
2215 7877,1,
2216 7879,1,
2217 7881,1,
2218 7883,1,
2219 7885,1,
2220 7887,1,
2221 7889,1,
2222 7891,1,
2223 7893,1,
2224 7895,1,
2225 7897,1,
2226 7899,1,
2227 7901,1,
2228 7903,1,
2229 7905,1,
2230 7907,1,
2231 7909,1,
2232 7911,1,
2233 7913,1,
2234 7915,1,
2235 7917,1,
2236 7919,1,
2237 7921,1,
2238 7923,1,
2239 7925,1,
2240 7927,1,
2241 7929,1,
2242 7936,8,
2243 7952,6,
2244 7968,8,
2245 7984,8,
2246 8000,6,
2247 8016,8,
2248 8032,8,
2249 8048,14,
2250 8064,8,
2251 8080,8,
2252 8096,8,
2253 8112,5,
2254 8118,2,
2255 8126,1,
2256 8130,3,
2257 8134,2,
2258 8144,4,
2259 8150,2,
2260 8160,8,
2261 8178,3,
2262 8182,2,
2263 8305,1,
2264 8319,1,
2265 8458,1,
2266 8462,2,
2267 8467,1,
2268 8495,1,
2269 8500,1,
2270 8505,1,
2271 8508,2,
2272 8518,4,
2273 8526,1,
2274 8580,1,
2275 11312,47,
2276 11361,1,
2277 11365,2,
2278 11368,1,
2279 11370,1,
2280 11372,1,
2281 11380,1,
2282 11382,2,
2283 11393,1,
2284 11395,1,
2285 11397,1,
2286 11399,1,
2287 11401,1,
2288 11403,1,
2289 11405,1,
2290 11407,1,
2291 11409,1,
2292 11411,1,
2293 11413,1,
2294 11415,1,
2295 11417,1,
2296 11419,1,
2297 11421,1,
2298 11423,1,
2299 11425,1,
2300 11427,1,
2301 11429,1,
2302 11431,1,
2303 11433,1,
2304 11435,1,
2305 11437,1,
2306 11439,1,
2307 11441,1,
2308 11443,1,
2309 11445,1,
2310 11447,1,
2311 11449,1,
2312 11451,1,
2313 11453,1,
2314 11455,1,
2315 11457,1,
2316 11459,1,
2317 11461,1,
2318 11463,1,
2319 11465,1,
2320 11467,1,
2321 11469,1,
2322 11471,1,
2323 11473,1,
2324 11475,1,
2325 11477,1,
2326 11479,1,
2327 11481,1,
2328 11483,1,
2329 11485,1,
2330 11487,1,
2331 11489,1,
2332 11491,2,
2333 11520,38,
2334 64256,7,
2335 64275,5
2336 ];
2337 
2339 768,112,
2340 1155,4,
2341 1160,2,
2342 1425,45,
2343 1471,1,
2344 1473,2,
2345 1476,2,
2346 1479,1,
2347 1552,6,
2348 1611,20,
2349 1648,1,
2350 1750,7,
2351 1758,7,
2352 1767,2,
2353 1770,4,
2354 1809,1,
2355 1840,27,
2356 1958,11,
2357 2027,9,
2358 2305,3,
2359 2364,1,
2360 2366,16,
2361 2385,4,
2362 2402,2,
2363 2433,3,
2364 2492,1,
2365 2494,7,
2366 2503,2,
2367 2507,3,
2368 2519,1,
2369 2530,2,
2370 2561,3,
2371 2620,1,
2372 2622,5,
2373 2631,2,
2374 2635,3,
2375 2672,2,
2376 2689,3,
2377 2748,1,
2378 2750,8,
2379 2759,3,
2380 2763,3,
2381 2786,2,
2382 2817,3,
2383 2876,1,
2384 2878,6,
2385 2887,2,
2386 2891,3,
2387 2902,2,
2388 2946,1,
2389 3006,5,
2390 3014,3,
2391 3018,4,
2392 3031,1,
2393 3073,3,
2394 3134,7,
2395 3142,3,
2396 3146,4,
2397 3157,2,
2398 3202,2,
2399 3260,1,
2400 3262,7,
2401 3270,3,
2402 3274,4,
2403 3285,2,
2404 3298,2,
2405 3330,2,
2406 3390,6,
2407 3398,3,
2408 3402,4,
2409 3415,1,
2410 3458,2,
2411 3530,1,
2412 3535,6,
2413 3542,1,
2414 3544,8,
2415 3570,2,
2416 3633,1,
2417 3636,7,
2418 3655,8,
2419 3761,1,
2420 3764,6,
2421 3771,2,
2422 3784,6,
2423 3864,2,
2424 3893,1,
2425 3895,1,
2426 3897,1,
2427 3902,2,
2428 3953,20,
2429 3974,2,
2430 3984,8,
2431 3993,36,
2432 4038,1,
2433 4140,7,
2434 4150,4,
2435 4182,4,
2436 4959,1,
2437 5906,3,
2438 5938,3,
2439 5970,2,
2440 6002,2,
2441 6070,30,
2442 6109,1,
2443 6155,3,
2444 6313,1,
2445 6432,12,
2446 6448,12,
2447 6576,17,
2448 6600,2,
2449 6679,5,
2450 6912,5,
2451 6964,17,
2452 7019,9,
2453 7616,11,
2454 7678,2,
2455 8400,32,
2456 12330,6,
2457 12441,2,
2458 43010,1,
2459 43014,1,
2460 43019,1,
2461 43043,5,
2462 64286,1,
2463 65024,16
2464 ];
2465 
2467 33,3,
2468 37,6,
2469 44,4,
2470 58,2,
2471 63,2,
2472 91,3,
2473 95,1,
2474 123,1,
2475 125,1,
2476 161,1,
2477 171,1,
2478 183,1,
2479 187,1,
2480 191,1,
2481 894,1,
2482 903,1,
2483 1370,6,
2484 1417,2,
2485 1470,1,
2486 1472,1,
2487 1475,1,
2488 1478,1,
2489 1523,2,
2490 1548,2,
2491 1563,1,
2492 1566,2,
2493 1642,4,
2494 1748,1,
2495 1792,14,
2496 2039,3,
2497 2404,2,
2498 2416,1,
2499 3572,1,
2500 3663,1,
2501 3674,2,
2502 3844,15,
2503 3898,4,
2504 3973,1,
2505 4048,2,
2506 4170,6,
2507 4347,1,
2508 4961,8,
2509 5741,2,
2510 5787,2,
2511 5867,3,
2512 5941,2,
2513 6100,3,
2514 6104,3,
2515 6144,11,
2516 6468,2,
2517 6622,2,
2518 6686,2,
2519 7002,7,
2520 8208,24,
2521 8240,20,
2522 8261,13,
2523 8275,12,
2524 8317,2,
2525 8333,2,
2526 9001,2,
2527 10088,14,
2528 10181,2,
2529 10214,6,
2530 10627,22,
2531 10712,4,
2532 10748,2,
2533 11513,4,
2534 11518,2,
2535 11776,24,
2536 11804,2,
2537 12289,3,
2538 12296,10,
2539 12308,12,
2540 12336,1,
2541 12349,1,
2542 12448,1,
2543 12539,1,
2544 43124,4,
2545 64830,2,
2546 65040,10,
2547 65072,35,
2548 65108,14,
2549 65123,1,
2550 65128,1,
2551 65130,2,
2552 65281,3,
2553 65285,6,
2554 65292,4,
2555 65306,2,
2556 65311,2,
2557 65339,3,
2558 65343,1,
2559 65371,1,
2560 65373,1
2561 ];
2562 
2564 65,26,
2565 192,23,
2566 216,7,
2567 256,1,
2568 258,1,
2569 260,1,
2570 262,1,
2571 264,1,
2572 266,1,
2573 268,1,
2574 270,1,
2575 272,1,
2576 274,1,
2577 276,1,
2578 278,1,
2579 280,1,
2580 282,1,
2581 284,1,
2582 286,1,
2583 288,1,
2584 290,1,
2585 292,1,
2586 294,1,
2587 296,1,
2588 298,1,
2589 300,1,
2590 302,1,
2591 304,1,
2592 306,1,
2593 308,1,
2594 310,1,
2595 313,1,
2596 315,1,
2597 317,1,
2598 319,1,
2599 321,1,
2600 323,1,
2601 325,1,
2602 327,1,
2603 330,1,
2604 332,1,
2605 334,1,
2606 336,1,
2607 338,1,
2608 340,1,
2609 342,1,
2610 344,1,
2611 346,1,
2612 348,1,
2613 350,1,
2614 352,1,
2615 354,1,
2616 356,1,
2617 358,1,
2618 360,1,
2619 362,1,
2620 364,1,
2621 366,1,
2622 368,1,
2623 370,1,
2624 372,1,
2625 374,1,
2626 376,2,
2627 379,1,
2628 381,1,
2629 385,2,
2630 388,1,
2631 390,2,
2632 393,3,
2633 398,4,
2634 403,2,
2635 406,3,
2636 412,2,
2637 415,2,
2638 418,1,
2639 420,1,
2640 422,2,
2641 425,1,
2642 428,1,
2643 430,2,
2644 433,3,
2645 437,1,
2646 439,2,
2647 444,1,
2648 452,2,
2649 455,2,
2650 458,2,
2651 461,1,
2652 463,1,
2653 465,1,
2654 467,1,
2655 469,1,
2656 471,1,
2657 473,1,
2658 475,1,
2659 478,1,
2660 480,1,
2661 482,1,
2662 484,1,
2663 486,1,
2664 488,1,
2665 490,1,
2666 492,1,
2667 494,1,
2668 497,2,
2669 500,1,
2670 502,3,
2671 506,1,
2672 508,1,
2673 510,1,
2674 512,1,
2675 514,1,
2676 516,1,
2677 518,1,
2678 520,1,
2679 522,1,
2680 524,1,
2681 526,1,
2682 528,1,
2683 530,1,
2684 532,1,
2685 534,1,
2686 536,1,
2687 538,1,
2688 540,1,
2689 542,1,
2690 544,1,
2691 546,1,
2692 548,1,
2693 550,1,
2694 552,1,
2695 554,1,
2696 556,1,
2697 558,1,
2698 560,1,
2699 562,1,
2700 570,2,
2701 573,2,
2702 577,1,
2703 579,4,
2704 584,1,
2705 586,1,
2706 588,1,
2707 590,1,
2708 902,1,
2709 904,3,
2710 908,1,
2711 910,2,
2712 913,17,
2713 931,9,
2714 978,3,
2715 984,1,
2716 986,1,
2717 988,1,
2718 990,1,
2719 992,1,
2720 994,1,
2721 996,1,
2722 998,1,
2723 1000,1,
2724 1002,1,
2725 1004,1,
2726 1006,1,
2727 1012,1,
2728 1015,1,
2729 1017,2,
2730 1021,51,
2731 1120,1,
2732 1122,1,
2733 1124,1,
2734 1126,1,
2735 1128,1,
2736 1130,1,
2737 1132,1,
2738 1134,1,
2739 1136,1,
2740 1138,1,
2741 1140,1,
2742 1142,1,
2743 1144,1,
2744 1146,1,
2745 1148,1,
2746 1150,1,
2747 1152,1,
2748 1162,1,
2749 1164,1,
2750 1166,1,
2751 1168,1,
2752 1170,1,
2753 1172,1,
2754 1174,1,
2755 1176,1,
2756 1178,1,
2757 1180,1,
2758 1182,1,
2759 1184,1,
2760 1186,1,
2761 1188,1,
2762 1190,1,
2763 1192,1,
2764 1194,1,
2765 1196,1,
2766 1198,1,
2767 1200,1,
2768 1202,1,
2769 1204,1,
2770 1206,1,
2771 1208,1,
2772 1210,1,
2773 1212,1,
2774 1214,1,
2775 1216,2,
2776 1219,1,
2777 1221,1,
2778 1223,1,
2779 1225,1,
2780 1227,1,
2781 1229,1,
2782 1232,1,
2783 1234,1,
2784 1236,1,
2785 1238,1,
2786 1240,1,
2787 1242,1,
2788 1244,1,
2789 1246,1,
2790 1248,1,
2791 1250,1,
2792 1252,1,
2793 1254,1,
2794 1256,1,
2795 1258,1,
2796 1260,1,
2797 1262,1,
2798 1264,1,
2799 1266,1,
2800 1268,1,
2801 1270,1,
2802 1272,1,
2803 1274,1,
2804 1276,1,
2805 1278,1,
2806 1280,1,
2807 1282,1,
2808 1284,1,
2809 1286,1,
2810 1288,1,
2811 1290,1,
2812 1292,1,
2813 1294,1,
2814 1296,1,
2815 1298,1,
2816 1329,38,
2817 4256,38,
2818 7680,1,
2819 7682,1,
2820 7684,1,
2821 7686,1,
2822 7688,1,
2823 7690,1,
2824 7692,1,
2825 7694,1,
2826 7696,1,
2827 7698,1,
2828 7700,1,
2829 7702,1,
2830 7704,1,
2831 7706,1,
2832 7708,1,
2833 7710,1,
2834 7712,1,
2835 7714,1,
2836 7716,1,
2837 7718,1,
2838 7720,1,
2839 7722,1,
2840 7724,1,
2841 7726,1,
2842 7728,1,
2843 7730,1,
2844 7732,1,
2845 7734,1,
2846 7736,1,
2847 7738,1,
2848 7740,1,
2849 7742,1,
2850 7744,1,
2851 7746,1,
2852 7748,1,
2853 7750,1,
2854 7752,1,
2855 7754,1,
2856 7756,1,
2857 7758,1,
2858 7760,1,
2859 7762,1,
2860 7764,1,
2861 7766,1,
2862 7768,1,
2863 7770,1,
2864 7772,1,
2865 7774,1,
2866 7776,1,
2867 7778,1,
2868 7780,1,
2869 7782,1,
2870 7784,1,
2871 7786,1,
2872 7788,1,
2873 7790,1,
2874 7792,1,
2875 7794,1,
2876 7796,1,
2877 7798,1,
2878 7800,1,
2879 7802,1,
2880 7804,1,
2881 7806,1,
2882 7808,1,
2883 7810,1,
2884 7812,1,
2885 7814,1,
2886 7816,1,
2887 7818,1,
2888 7820,1,
2889 7822,1,
2890 7824,1,
2891 7826,1,
2892 7828,1,
2893 7840,1,
2894 7842,1,
2895 7844,1,
2896 7846,1,
2897 7848,1,
2898 7850,1,
2899 7852,1,
2900 7854,1,
2901 7856,1,
2902 7858,1,
2903 7860,1,
2904 7862,1,
2905 7864,1,
2906 7866,1,
2907 7868,1,
2908 7870,1,
2909 7872,1,
2910 7874,1,
2911 7876,1,
2912 7878,1,
2913 7880,1,
2914 7882,1,
2915 7884,1,
2916 7886,1,
2917 7888,1,
2918 7890,1,
2919 7892,1,
2920 7894,1,
2921 7896,1,
2922 7898,1,
2923 7900,1,
2924 7902,1,
2925 7904,1,
2926 7906,1,
2927 7908,1,
2928 7910,1,
2929 7912,1,
2930 7914,1,
2931 7916,1,
2932 7918,1,
2933 7920,1,
2934 7922,1,
2935 7924,1,
2936 7926,1,
2937 7928,1,
2938 7944,8,
2939 7960,6,
2940 7976,8,
2941 7992,8,
2942 8008,6,
2943 8025,1,
2944 8027,1,
2945 8029,1,
2946 8031,1,
2947 8040,8,
2948 8072,8,
2949 8088,8,
2950 8104,8,
2951 8120,5,
2952 8136,5,
2953 8152,4,
2954 8168,5,
2955 8184,5,
2956 8450,1,
2957 8455,1,
2958 8459,3,
2959 8464,3,
2960 8469,1,
2961 8473,5,
2962 8484,1,
2963 8486,1,
2964 8488,1,
2965 8490,4,
2966 8496,4,
2967 8510,2,
2968 8517,1,
2969 8579,1,
2970 11264,47,
2971 11360,1,
2972 11362,3,
2973 11367,1,
2974 11369,1,
2975 11371,1,
2976 11381,1,
2977 11392,1,
2978 11394,1,
2979 11396,1,
2980 11398,1,
2981 11400,1,
2982 11402,1,
2983 11404,1,
2984 11406,1,
2985 11408,1,
2986 11410,1,
2987 11412,1,
2988 11414,1,
2989 11416,1,
2990 11418,1,
2991 11420,1,
2992 11422,1,
2993 11424,1,
2994 11426,1,
2995 11428,1,
2996 11430,1,
2997 11432,1,
2998 11434,1,
2999 11436,1,
3000 11438,1,
3001 11440,1,
3002 11442,1,
3003 11444,1,
3004 11446,1,
3005 11448,1,
3006 11450,1,
3007 11452,1,
3008 11454,1,
3009 11456,1,
3010 11458,1,
3011 11460,1,
3012 11462,1,
3013 11464,1,
3014 11466,1,
3015 11468,1,
3016 11470,1,
3017 11472,1,
3018 11474,1,
3019 11476,1,
3020 11478,1,
3021 11480,1,
3022 11482,1,
3023 11484,1,
3024 11486,1,
3025 11488,1,
3026 11490,1
3027 ];
3028 
3030 9,5,
3031 32,1,
3032 133,1,
3033 160,1,
3034 5760,1,
3035 8192,12,
3036 8232,2,
3037 8239,1,
3038 8287,1
3039 ];
3040 
3042 9,1,
3043 32,1,
3044 160,1,
3045 5760,1,
3046 8192,12,
3047 8239,1,
3048 8287,1
3049 ];