Binary Search Method

[Pete]

Well you need to run my long string INSTR() test then, because it is fast. That's why seeding was made part of the keyword. Without seeding, I agree, INSTR is too slow, as in your example. With seeding, I can't see any reason to jump to a more complicated way of constructing data to parse it. Too many collisions with hash tables and more and more difficulty trying to figure out ways around that. Words over 9-characters and Steve's indexing method has to be adjusted to read and interpret more than one number representing ascii character. That's not hard, but takes a bit more processing time to achieve.

Anyway, let's just look at that simple INSTR() method, without seeding, for a one time place lookup with 50 loops and that long-ascii string I made up for the seeding example.

Code: QB64: [Select]

1. CLS
2. WIDTH 80, 55
3. _SCREENMOVE 0, 0
4.  
5. _CONTROLCHR OFF
6. s1$ = "4bill3cat3dog7dogfood4pete5steve4bill3cat3dog7dogfood4pete5steve4bill3cat3dog7dogfood4pete5steve0"
7. 'convert format...
8. FOR i = 1 TO LEN(s1$)
9.     index = VAL(MID$(s1$, i, 1))
10.     x$ = MID$(s1$, i + 1, index)
11.     i = i + index
12.     news$ = news$ + CHR$(index) + x$
13. NEXT
14.  
15. FOR i = 1 TO 15 ' Concatenate to a string size of 3178497
16.     news$ = news$ + news$
17. NEXT
18.  
19. s1$ = news$ + CHR$(1) + "*": news$ = ""
20.  
21. news$ = ",bill,cat,dog,dogfood,pete,steve,bill,cat,dog,dogfood,pete,steve,bill,cat,dog,dogfood,pete,steve,"
22. FOR i = 1 TO 15
23.     news$ = news$ + news$
24. NEXT
25. s2$ = news$ + "*,": news$ = ""
26.  
27. word$ = "*": x = 1
28. LOCATE , x: PRINT "INDEX Search"
29. t# = TIMER
30. FOR j = 1 TO 50
31.     FOR i = 1 TO LEN(s1$)
32.         index = ASC(s1$, i) ' Good for words 9 letters or less.
33.         x$ = MID$(s1$, i + 1, index)
34.         IF x$ = word$ THEN EXIT FOR
35.         i = i + index
36.     NEXT
37.     LOCATE , x: PRINT j, i
38. NEXT
39. PRINT USING "###.### seconds lookup"; TIMER - t#
40.  
41. word$ = ",*,": x = 40
42. LOCATE 1, x: PRINT "INSTR() Search"
43. t# = TIMER
44. FOR i = 1 TO 50
45.     place = INSTR(s2$, word$)
46.     LOCATE , x: PRINT i, place
47. NEXT
48. LOCATE , x: PRINT USING "###.### seconds lookup"; TIMER - t#
49.  
50. END
51.  

INSTR() won that footrace, which is why I'm finding it hard to understand how it failed so miserably in your use of it. I mean it appears here that INSTR(), however it reads the string, reads it faster than skipping by an index and looking for a word match. Now if Steve's function was applied to it, maybe it would be different, but this is why I was asking Steve if the FOR/NEXT index example I came up with would be a fair comparison.

Pete
 

[SMcNeill]

Well it did. Though both methods were flawed in my test, I think what the results point to is still valid ie INSTR is great for short strings but when the strings get to a certain length the Binary Search method will come into it's own as the hash method would with truly large amounts of data.

Pete, I suspect you haven't run INSTR search on nearly half a million word string, with 50,000 lookups in a row.

PS the time was not really that bad except when comparing to Binary Search Method.

All 3 methods are valid tools for a programmer to use. 

INSTR is the quickest and simplest to implement, and like a Bubblesort, is more than sufficient for many applications.  Its ease of implementation makes it a desirable work horse.


Binary Search works great for organized lists of data, or indexed data.  In many cases, it’s easier to use than a Hash Table, and fast enough to run in almost all applications.  The memory requirements are lower and it works perfectly fine with external files — all things to make it a desirable process to learn to implement.

To see the usefulness of indexes with Binary Search, think of of database with 3 fields — Name, Age, Phone.  Fill it with 10,000,000 records...  Now, who’s the youngest person on the list?  Oldest?  Who is listed 1000th alphabetically?

If you maintain indexes of the data, that information is instantly available, even if the data itself is unsorted. 

The DataRecord:
Joe, 86, 555-1234
Pete, 62, 555-2345
Mark, 16, 555-9786

Name Index: 1, 3, 2
Age Index: 3, 2, 1
Phone Index: 1, 2, 3

So youngest is DataRecord(Age(1)).
Oldest is DataRecord(Ubound(Age))
DataRecord(Name(1000)) tells us who is listed 1000th alphabetically.

And for a look up, we just binary search the proper index...  Instead of IF search$ = DataRecord(RecordToCheck), we’d make that condition IF search$ = DataRecord(IndexDesired(RecordToCheck)), in our binary search routine.

Indexing and Binary Search make for a powerful organizational toolset.


Hash Tables are, of course, the fastest method for looking things up (provided there’s not a ton of collisions to process.). Pete’s old spell check routine is actually a form of a hash table; he just didn’t know it.  He was hashing by the first and then second letters of his word, similar to:

Hash = 100* (ASC(word,1) - 64) + _CEIL((ASC(word,2) -64) / 13)

A word starting with AA would hash to 100 * 1 + _CEIL(1 / 13) = 101
A word starting with AM would hash to 100 * 1 + _CEIL(13 / 13) = 101
A word starting with AN would hash to 100.* 1 + _CEIL(14 / 13) = 102

Letters from Aa-Am in one list, An to Az in the next...

Pete was using a form of a hash table; he just wasn’t using a very efficient one.  (Which is why I said a simple binary search would have probably been better in his case.)

A good hash table has almost instant look ups, but it also requires more memory.  It can require finding the best formula for data distribution and lookup, but it’s still an invaluable tool for programming.

All have their merits and drawbacks.  You just need to choose which suits your current needs the most.

[Pete]

So we are finally in agreement that my way is the best way! :D :D :D

Actually I did realize my old form of alphabetizing with folders was a type of hash process, but I always considered it a bastardized one. What I wanted was a hash method without collisions, but after a brief look at permutations, I punted on that idea.  Numbers way too big for words with over 20 characters.

QBasic ran interpreted, which slows things down. QuickBASIC was faster and you could use integers and include/exclude libraries to speed things up more but I don't think I ever got a WP in QB that could outdo Windows Word for speed of spell checking. I assumed those developers came up with a hash table loaded into memory, but I could be wrong. Whatever they used, it was damn fast.

Pete   

[SMcNeill]

I have number of data bases which are just numbers. At present when searching I convert them to strings. I gather neither Hashing or Binary offer a way to search without the conversion step?

Sorry Dimster; in all the brouhaha, I somehow missed your post earlier.  There’s no reason at all to convert them.  Just search them as they are.  (I’ll post a demo soon for you.)

[SMcNeill]

Using the SET Library I just posted here ( https://www.qb64.org/forum/index.php?topic=1015.0 ), we see a quick demo of using a binary search method on numbers, without needing to convert them to strings:

Code: QB64: [Select]

1. '$INCLUDE:'SET.BI'
2.  
3. DIM NumberArray(0 TO 100) AS LONG
4. DIM m AS _MEM: m = _MEM(NumberArray())
5.  
6. RANDOMIZE TIMER
7.  
8. FOR i = 0 TO 100
9.     NumberArray(i) = i 'toss a set of sorted numbers into the array
10.     'For ease of reference, the numbers are going to start out being the exact same as the array index.
11. NEXT
12. PRINT "Values = Index"
13. PRINT "The number 12 is in the "; BinaryMemSearch(12, m); " spot."
14. PRINT "The number 37 is in the "; BinaryMemSearch(37, m); " spot."
15.  
16. 'And now to multiply those values by 100 so we can see we're not just parroting the index:
17.  
18. FOR i = 0 TO 100
19.     NumberArray(i) = i * 100 'toss a set of sorted numbers into the array
20.     'For ease of reference, the numbers are going to start out being the exact same as the array index.
21. NEXT
22. PRINT
23. PRINT "Values = Index * 100"
24. PRINT "The number 1200 is in the "; BinaryMemSearch(1200, m); " spot."
25. PRINT "The number 3700 is in the "; BinaryMemSearch(3700, m); " spot."
26. PRINT
27. PRINT "PRESS <ANY KEY> TO CONTINUE"
28.  
29.  
30. DO
31.     SLEEP
32.     CLS
33.     'And now to randomize some numbers
34.     DO
35.         WeHave50Somewhere = 0
36.         FOR i = 1 TO 20
37.             r = INT(RND * 100)
38.             NumberArray(i) = r
39.             IF r = 50 THEN WeHave50Somewhere = -1
40.         NEXT
41.     LOOP UNTIL WeHave50Somewhere
42.  
43.     MemSortSome m, 1, 20 'sort those 20 numbers so we can search them
44.     PRINT "Index", "Number"
45.     FOR i = 1 TO 20
46.         PRINT "      "; i, NumberArray(i)
47.     NEXT
48.     index = BinaryMemSearchSome(50, m, 1, 20) 'find 50 amongst the records from 1 to 20
49.     LOCATE index + 1, 1: PRINT "HERE=>"
50.     LOCATE 23, 1
51.     PRINT "PRESS <ANY KEY> TO SEARCH A NEW DATASET, OR <ESC> TO QUIT>"
52. LOOP UNTIL _KEYHIT = 27
53.  
54. '$INCLUDE:'SET.BM'

Now this makes use of a _MEM routine which I wrote to do the binary searching for us, but that's just so I can have one routine work properly with all data types, and utilize the speed of the _MEM commands.

If you look into the SET.BM file, you can see the actual subs there, and in this case what we're doing is basically:

Code: QB64: [Select]

1.         CASE 4 'LONG
2.             DO
3.                 gap = (max + min) \ 2: IF oldgap = gap THEN gap = gap + 1
4.                 IF search > _MEMGET(m, m.OFFSET + gap * m.ELEMENTSIZE, LONG) THEN
5.                     min = gap
6.                 ELSEIF search < _MEMGET(m, m.OFFSET + gap * m.ELEMENTSIZE, LONG) THEN
7.                     max = gap
8.                 ELSE
9.                     BinaryMemSearchSome = gap
10.                     EXIT FUNCTION
11.                 END IF
12.                 oldgap = gap: IF max - min <= 1 THEN BinaryMemSearchSome = -gap: found = -1 'it's not in the list
13.             LOOP UNTIL found

It's just a simple binary compare of the array, comparing our search value vs the actual value.  There's no actual reason to need to convert it to a string, at all. (In fact, we're not actually converting it here.  We're just referencing it via the _MEM offsets.)

[RonB]

The absolute fastest TLU is a "direct" lookup - one where the argument IS the entry number (or index) of the entry, itself. For example, if you needed to validate the 5-digit U.S. zip code for 360 million address records, you could first construct a table (ZipCodeTable) in which there is an array entry for every possible zip code, whether valid or not. That's 100000 entries (numbered from zero to 99999). The entry for each VALID zip code will contain the number '1' (for valid). The entry for each INVALID zip code will contain the number '0' (for invalid). This TLU table requires 100000 entries (which, I believe, means that QB64 will generate code to maintain an array index table containing pointers for each of those 100000 entries). Processing is simple (assuming that you have already verified that the RecordZipCode was 5 numeric digits):
     zipcode& = VAL(RecordZipCode)
     IF ZipCodeTable(zipcode&) = '1' THEN process as valid ELSE process as invalid END IF.

Alternatively, you could create a single string of 100000 bytes, with each corresponding byte set to either 1 or 0. This TLU "table" (really a byte-string) requires 100000 bytes (no QB64 generated array index table). Processing is simple:
     zipcode& = VAL(RecordZipCode)
     IF MID$(ZipCodeTable,zipcode&,1) = '1' THEN process as valid ELSE process as invalid END IF.

I'm not sure whether QB64 would support a bitstring of 100000 bits; and while the "table" would take only 12500 bytes, it may take a lot longer to obtain the result.

Always trade offs. Bottom line: pick the TLU method that works best based on THE ACTUAL (or expected) DATA, depending on your requirements - array size, speed, simplicity, reliability, data placement (file, memory, web), etc. One size does NOT fit all.

[codeguy]

Another super useful data structure is a binary tree, in this example, implemented as an array. It includes searching, traversal and even presents output in sorted order. Two caveats: for sorted input or monotonically repeating datasets, the performance is terrible for reasons I haven't patience to discuss.

Code: [Select]

'treesortI64.bas
OPTION _EXPLICIT
TYPE minmaxrec
    min AS _INTEGER64
    max AS _INTEGER64
END TYPE
'**************************************
'* anyone claiming you need c/c++ to implement trees is telling you CRAP
'* This is a bit more complex than the standard non-copying version, but it is still
'* respectably fast. General complexity for TreeSort() is O(NLogN), EXCEPT when
'* presented with elements already sorted. One way to avoid this is to KnuthShuffle
'* the input first. Skipped in this implementation, but there is no reason you
'* can't do it prior to TreeSort(). Code modified/added from my repository. This
'* version allows multiple same-value nodes
'* Modified/added 26 March 2018.
'* Further modifed for _INTEGER64 sized indexes 20 May 2020
'**************************************
SUB TreeSortUsingBST (CGSortLibArr() AS DOUBLE, start AS _INTEGER64, finish AS _INTEGER64, order AS INTEGER)
    DIM TSAmmrec AS minmaxrec
    'GetMinMaxArray CGSortLibArr(), start, finish, TSAmmrec
    'if  CGSortLibArr(TSAmmrec.max) = CGSortLibArr(TSAmmrec.min) then exit sub
    'IF delta# = 0 THEN 'already sorted because they're all equal
    '    EXIT SUB
    'END IF
    DIM NilValue: NilValue = LBOUND(CGSortLibArr) - 1
    DIM x AS _INTEGER64
    DIM pointer AS _INTEGER64
    DIM free: free = 2
    TYPE TreeNode
        value AS DOUBLE
        left AS _INTEGER64
        right AS _INTEGER64
    END TYPE
    DIM tree(start + 1 TO finish + 1) AS TreeNode
    FOR x = start + 1 TO finish + 1
        tree(x).value = 0
        tree(x).left = NilValue
        tree(x).right = NilValue
    NEXT
    tree(1).value = CGSortLibArr(1 - 1)
    IF order = 1 THEN
        FOR x = 2 TO finish
            pointer = 1
            DO
                IF CGSortLibArr(x - 1) < tree(pointer).value THEN
                    IF tree(pointer).left = NilValue THEN
                        tree(pointer).left = free
                        tree(free).value = CGSortLibArr(x - 1)
                        free = free + 1
                        EXIT DO
                    ELSE
                        pointer = tree(pointer).left
                    END IF
                ELSE
                    IF tree(pointer).right = NilValue THEN
                        tree(pointer).right = free
                        tree(free).value = CGSortLibArr(x - 1)
                        free = free + 1
                        EXIT DO
                    ELSE
                        pointer = tree(pointer).right
                    END IF
                END IF
            LOOP
        NEXT x
    ELSE
        FOR x = 2 TO finish
            pointer = 1
            DO
                IF CGSortLibArr(x - 1) > tree(pointer).value THEN
                    IF tree(pointer).left = NilValue THEN
                        tree(pointer).left = free
                        tree(free).value = CGSortLibArr(x - 1)
                        free = free + 1
                        EXIT DO
                    ELSE
                        pointer = tree(pointer).left
                    END IF
                ELSE
                    IF tree(pointer).right = NilValue THEN
                        tree(pointer).right = free
                        tree(free).value = CGSortLibArr(x - 1)
                        free = free + 1
                        EXIT DO
                    ELSE
                        pointer = tree(pointer).right
                    END IF
                END IF
            LOOP
        NEXT x
    END IF
    DIM depth AS _INTEGER64
    depth = start + 1
    Traverse_tree CGSortLibArr(), start + 1, depth, tree(), NilValue
    ERASE tree
END SUB

SUB Traverse_tree (CGSortLibArr() AS DOUBLE, NextPtr&, depth&, tree() AS TreeNode, NilValue&)
    IF tree(NextPtr&).left <> NilValue& THEN
        Traverse_tree CGSortLibArr(), tree(NextPtr&).left, depth&, tree(), NilValue&
    END IF
    CGSortLibArr(depth& - 1) = tree(NextPtr&).value
    depth& = depth& + 1
    IF tree(NextPtr&).right <> NilValue& THEN Traverse_tree CGSortLibArr(), tree(NextPtr&).right, depth&, tree(), NilValue&
END SUB


[codeguy]

One caveat: BINARY search as it's coded fails on descending lists, SO a minor change is necessary. Presented is code that works successfully for ascending and descending order.

Code: [Select]

'BinarySearchTestI64
OPTION _EXPLICIT
CONST OrderDescending = -1
CONST OrderAscending = 1
CONST OrderMonotonic = 0

DIM LowerBoundTestArry AS _UNSIGNED _INTEGER64
DIM UpperBoundTestArry AS _UNSIGNED _INTEGER64: UpperBoundTestArry = 0
DIM MainI AS _UNSIGNED _INTEGER64: MainI = LowerBoundTestArry
DIM MainWhere AS _UNSIGNED _INTEGER64: MainWhere = LowerBoundTestArry
DIM MaiTestStart AS SINGLE
DIM MainTestEnd AS SINGLE
DIM mainOrderchoice AS INTEGER: mainOrderchoice = OrderDescending
DIM MainRepPercentage AS DOUBLE: MainRepPercentage = 0
DO
    UpperBoundTestArry = UpperBoundTestArry + 1
    REDIM CgSortLbAr(LowerBoundTestArry TO UpperBoundTestArry) AS DOUBLE
    FillArray CgSortLbAr(), LowerBoundTestArry, UpperBoundTestArry, mainOrderchoice, MainRepPercentage
    MaiTestStart = TIMER(.001)
    FOR MainI = LowerBoundTestArry TO UpperBoundTestArry
        cgBinarysearch CgSortLbAr(), LowerBoundTestArry, UpperBoundTestArry, CgSortLbAr(MainI), MainWhere
        IF CgSortLbAr(MainI) = CgSortLbAr(MainWhere) THEN
        ELSE
            STOP
        END IF
    NEXT
    MainTestEnd = TIMER(.001)
    PRINT UpperBoundTestArry - LowerBoundTestArry; MainTestEnd - MaiTestStart
    UpperBoundTestArry = UpperBoundTestArry * 2
LOOP UNTIL UpperBoundTestArry > 67108863
PRINT UpperBoundTestArry

SUB FillArray (CgSortLibArr() AS DOUBLE, start AS _UNSIGNED _INTEGER64, finish AS _UNSIGNED _INTEGER64, OrderChoice AS INTEGER, Repetitions AS DOUBLE)
    DIM FillArray_RepeatStart AS _UNSIGNED _INTEGER64
    IF OrderChoice = OrderMonotonic THEN
        FOR FillArray_RepeatStart = start TO finish
            CgSortLibArr(FillArray_RepeatStart) = 0
        NEXT
    ELSE
        IF Repetitions > 0 THEN
            IF Repetitions < 100 THEN
                FillArray_RepeatStart = finish - INT((Repetitions / 100) * (finish - start))
            ELSE
                FillArray_RepeatStart = finish
            END IF

            DIM FillArray_u AS _UNSIGNED _INTEGER64: FillArray_u = start
            DO
                IF FillArray_u > finish - 1 THEN
                    EXIT DO
                ELSE
                    IF FillArray_u > FillArray_RepeatStart THEN
                        CgSortLibArr(FillArray_u) = CgSortLibArr(FillArray_RepeatStart)
                    END IF
                END IF
                FillArray_u = FillArray_u + 1
            LOOP
        ELSE
            SELECT CASE OrderChoice
                CASE OrderDescending
                    FOR FillArray_RepeatStart = start TO finish
                        CgSortLibArr(FillArray_RepeatStart) = (finish - FillArray_RepeatStart) / (finish - start + 1)
                    NEXT
                CASE OrderAscending
                    FOR FillArray_RepeatStart = start TO finish
                        CgSortLibArr(FillArray_RepeatStart) = (FillArray_RepeatStart) / (finish - start + 1)
                    NEXT

                CASE ELSE
                    FOR FillArray_RepeatStart = start TO finish
                        CgSortLibArr(FillArray_RepeatStart) = 0
                    NEXT
            END SELECT
        END IF
    END IF
END SUB

SUB cgBinarysearch (CgSortLibArr() AS DOUBLE, start AS _UNSIGNED _INTEGER64, finish AS _UNSIGNED _INTEGER64, what AS DOUBLE, where AS _UNSIGNED _INTEGER64)
    DIM BinarySearch_low AS _INTEGER64
    DIM BinarySearch_high AS _INTEGER64
    SELECT CASE CgSortLibArr(start)
        CASE IS <= CgSortLibArr(finish)
            BinarySearch_low = start
            BinarySearch_high = finish
            DO
                where = BinarySearch_low + (BinarySearch_high - BinarySearch_low) \ 2
                IF CgSortLibArr(where) < what THEN
                    BinarySearch_low = where + 1
                ELSEIF CgSortLibArr(where) > what THEN
                    BinarySearch_high = where - 1
                ELSE
                    EXIT SUB
                END IF
            LOOP WHILE BinarySearch_low < BinarySearch_high
            where = BinarySearch_low
        CASE ELSE
            BinarySearch_low = finish
            BinarySearch_high = start
            DO
                where = BinarySearch_high + (BinarySearch_low - BinarySearch_high) \ 2
                IF CgSortLibArr(where) > what THEN
                    BinarySearch_high = where + 1
                ELSEIF CgSortLibArr(where) < what THEN
                    BinarySearch_low = where - 1
                ELSE
                    EXIT SUB
                END IF
            LOOP WHILE BinarySearch_low > BinarySearch_high
            where = BinarySearch_high
    END SELECT
END SUB


[Dav]

As always that some nice coding, @codeguy. 

By the way....I just remembered something.  Yes, this code it's off topic, but so what.  Have a good one!

- Dav

Code: QB64: [Select]

1. DIM SHARED HBC&, HBCM$
2.  
3. :::::::::::::::::
4. :::: HBCDATA::::: 'Make HBC variable data
5. :::::::::::::::::
6.  
7. SCREEN _NEWIMAGE(600, 600, 32): CLS , _RGB(255, 255, 255)
8.  
9. FOR y = _HEIGHT TO 0 STEP -1
10.     _PUTIMAGE (0, y)-(_WIDTH, y + _HEIGHT), HBC&: _DISPLAY
11.     IF y = _HEIGHT THEN PLAY HBCM$
12.     _LIMIT 60
13. NEXT: _DELAY 3
14. FOR c = 0 TO -300 STEP -1
15.     _PUTIMAGE (x - c, y - c)-(_WIDTH + c, _HEIGHT + c), HBC&: _DISPLAY
16.     _LIMIT 120
17. NEXT
18.  
19. :::::::::::::::::
20. :::: SYSTEM::::::
21. :::::::::::::::::
22.  
23.  
24. SUB HBCDATA
25.     v& = _NEWIMAGE(246, 264, 32)
26.     DIM m AS _MEM: m = _MEMIMAGE(v&)
27.     A$ = A$ + "haIkM^6cfUMFGoU_#81nVVa3QH`h7j78#DX29D]MB`VXQ?IRT0Y=6>h<Ej87"
28.     A$ = A$ + "JSU4JRUQDBKZdF5]cdQ8PU48E>Zb1[1JXSYUFjdQJ[Ha#DB78N8`7D3D>HWf"
29.     A$ = A$ + "ifWOkgWO?_oOG_[mN_fggkk3?gg[[T[LOL_g[mJOmojdjJ]FKfdY>eY>eY>e"
30.     A$ = A$ + "Y>MGjWhWHcV7nQg\iaOlSM;YCWJdWhCL\K1CC_[geV=OOOOKflkmkM\K9kGj"
31.     A$ = A$ + "iN^Um\PokM^cmhWnYgO]]>EWhI6mkb]B8;S<mcl<kWfeSmHgEVh[i[Y]o;o_"
32.     A$ = A$ + "39n2<]b]]d6_]Bo2o2gkn\EK_87eae7NRWEO3O3Kfl#?dmgo3cgm4?ad7?hW"
33.     A$ = A$ + "lH1O_fDfVVR#FKYbM[1mjNMgkjbk?GY\o5oZKQ:aeMJo#HCN:\L=N:\MYOFL"
34.     A$ = A$ + "^GC:?oOaOaCoOiggWjG6S#6g[;f^?GYln\EL=?7lHnRnRf_]_;E2<mDHIjgi"
35.     A$ = A$ + "i5LnoVkiQhYi`MK3UjkWc7gSUoNYlnYNN0f5:_?a^#;dfHS_C;ShIA9Fn[h["
36.     A$ = A$ + "h^fH;S7U?gZoCLlk[L6]4O[cfkQ<njd?QcI:eegJL>Y<gBR=2mSmHaKSBm]l"
37.     A$ = A$ + "<JZlLaHCTHoS5Q=jF\1Wi^j#S_f5kAXoQk;lUjDWf6oQBI^iRASn2`nYnSFm"
38.     A$ = A$ + ";H:bl1_[man\jDCOCZkLZlkTHjS]_U43`HHEjW1?WoWmYoNVgOdeTS7kf83R"
39.     A$ = A$ + ">EdGV]kCI\MINDJeOXF_ohlUnmT<bSKKK^\?NK>GeNFAKM=l94M4kjiI>ORh"
40.     A$ = A$ + "loene^>mYeXUN?#oY]S?o?okZ_Wf=g7S93\_`e8SD;g4I^`Ke?cBmV[]\2dJ"
41.     A$ = A$ + "8_DNnFJn_07gR?DUHJ`#ia>ecC>FdcR<ANo>FO<L=oD]=`chd_R<>`BNZWg>"
42.     A$ = A$ + "N[CY;ckiMM\ACOR\=am3bVlKUfmVc_9>7LL]T3LegEVK=\oU?C=_MIKM>Vn5"
43.     A$ = A$ + "bIoLnR`cCJc;MLf;adLn]_2m=;agdDNcaA<UMVkLL8UGB:ScI>mVjgK63eD7"
44.     A$ = A$ + "CJ;4k:#InMV2oTiKga09U5d?ZD6[VOEe^o:]aacllIeHjgJ9W#I]0\[fQZQ["
45.     A$ = A$ + ";m_8ITkhoEC_O[jRQZU3^YlkZ5Vk5N>ZlMJ?Y\_T[efjcKihc[o;ic5iiRG9"
46.     A$ = A$ + "moPcYoodVoDTeWcQBN9YDFUfNZo]V=QJjN[A9N:mG9_?6c^AYnFJSiaAKbnh"
47.     A$ = A$ + "ijGbW1PkCM3L=ba_<aAceV6c6BNmfeaT=kW;S=L:^VoQ9>J^ag:o_fW^D<=m"
48.     A$ = A$ + "edg>Vm\lJTb1SioL[ScL=K9UG_F`Td>BIo<nVF6W`BK772iUTBK_K3?FLOic"
49.     A$ = A$ + "VD_Hf_GkIN]W[l<e_[DV=aeYmJd_GZc?SGUcCY=0O>FnlZd?QYbgL:;\[iEY"
50.     A$ = A$ + "VLMFCnNnieblBFN?\TaO:o_8gUfMhl>V<JfNWkN?m7CiPba[OYSCCjc<?7Bi"
51.     A$ = A$ + "TBoEV2GG:3Vf^BKhSIO]4COXTGBZFLAe\K3VPnFh\]D[oN<IX\?Y6^VW;edE"
52.     A$ = A$ + "keSO[lN?egai_F^gU=f:n]BkIIKC<D]lc=U]SlL\[elAYLH;a2FV3dal5I>o"
53.     A$ = A$ + "?CmO9nKZl4U]GjOWSBI4?WY?18;Ta3<W?ZUiMYdG`bnVa`eLLUjFbkiDNX\="
54.     A$ = A$ + "E;nQ3UlB9UGoF7OTJamUDR3cnTBOibS=]9Rn^JhbbfGZOWncba#Q_[FL4e^?"
55.     A$ = A$ + "cl4ai=U];O>?6Unn\[eWHYOS]Z;O\W=im#[W3>6kGZY;L\fK;a9F6SJjC#jc"
56.     A$ = A$ + "K;bmiaFcnHVKPYZ9UJiT=k3[5S^4?OlLO<TG:_OWCoE=:kK:K?S=7B\_?aIl"
57.     A$ = A$ + "NT7Z5CdDm_BiaUiiTc[][BoAZEkdYOCelM?ON?Fn4:mmJG7cRd>iBNfTm_f7"
58.     A$ = A$ + "\4kN#:GVbW]T[m\?K>bW;jGOicobfB]n07cTBIUbh4B<MZoaWASMNBMIY=TB"
59.     A$ = A$ + "oEAV:kcBKD7:iUTbkaFlMB:K?Un7VjQe6CR;`FiHadW?Cc__DGM]a]]4?;Uh"
60.     A$ = A$ + "JeSKmAPlgHi5To[b796[Do2g?UnQ\6SGAih`e2EF3G:[dZ]D^G:eeWmKCAic"
61.     A$ = A$ + "dFR5>aen<Xfe9OnUhe<W;C9[Tb9UgOd>iIKNNZECeYmN^?[iC_H8n]SQlBBK"
62.     A$ = A$ + "C=NGnL_4GGVCi4C[oEeb?BImDTG3]E`cbJj4ZQW[eNhlDjcF9ccbBONcn9O6"
63.     A$ = A$ + "Dj[Nb[Q?EUgWcAUmYLO:=7^>eCFjWPhQiXU>7Ylo>E>?P:7oaBo_hhZEo>YO"
64.     A$ = A$ + "a`YOJSUKOj3:7o]BOh]=FcgOo]SQlBBieIKWOVUhjDN<ko:m_bLhbmDiccDO"
65.     A$ = A$ + "XnADkIaDhIYbl=>V>nYV74eR[Z\MTn__6nDE:o>5EJ3X<oFUiP;o]<W4R]:k"
66.     A$ = A$ + "KJQVBVXTZiC`DSiiHmk^N<D63#INC;Um:m[9WgjieSnUdojBmKLNhJEnm73i"
67.     A$ = A$ + "UTBInFaeUm9U?3[M?]dJK\VmUbhbKE7G9f`h0:[CRiXJnm3SNkLLAF[lJVjL"
68.     A$ = A$ + "]>IbLDhH3CL?Unn<EN1Wb^W7Gnm]>VZ;1GGJKH>olAn9em#OCjCN=O<bW?e8"
69.     A$ = A$ + "[m^JnWEJ3IKZGd3]lBBie[eJU]<^_J?3Y?7\SaR\DZfLhM:kkCA]Jc[5bh0#"
70.     A$ = A$ + "N0lTb3Y^^eZf2lI_aXD[^::ia`dii[faImm:UoF[jmbcmLhjBK3kjlDY\N9D"
71.     A$ = A$ + "gef^>?Y?0kjJggQDN9YD7N[?ofWSiVdJ]nhDj3gnRfVnaUBeTMCl<b=cY_Sf"
72.     A$ = A$ + "VeF^b\c=VO]BV7UFNN]dLWg2YNO`9Wj[E2kKi5e;]DmJFWhk;J]`e;M<Eg6:"
73.     A$ = A$ + "SMMOYWC2iE`19^L]G7SP#^HOR=X?3kY[ilQjf2M8UG>eXiZkUFY<^[m5^nH]"
74.     A$ = A$ + "fkeYKWdU\lbJQ[?4[ECInl>emo[C7OjBFNIKbWG=JK67_U#Uca\>eYYX;MiU"
75.     A$ = A$ + "U<V9CA[UMoaXFGWRjDWP^dUGLLJgeeO_LnQ]?FWXcJ`iBcWZ>]LZ;_\Ndn<g"
76.     A$ = A$ + "^Kkh9dY;CZ;_dY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>"
77.     A$ = A$ + "eY>eYePHNif[]`>eYc7:W[mkSjH_CMZC7NjBN^f_=dnNmLYCMJ=X4G_?F7k>"
78.     A$ = A$ + "WXLocJ\eJd>eYC1:WWhkce=^c1:G3PGkm9S>eYeTBLmUfjhgBYeJ]dYCMJOC"
79.     A$ = A$ + "7Re2ic5J]F;MjDWFKRLnhj6mBg[;UL_3lBJNjG^O4eY>U4h1`#;Mo522l4if"
80.     A$ = A$ + "2ldBGCg;g7]JM?h]T:gkeQGbmRg3^>T?eNCF;Tk=Bef3RGC:G?h_dFk]kdh4"
81.     A$ = A$ + "b^Uk_e;aFGini6L[[;oLMZ]OMTkKg]4_hHk3M]^nFBkXfN3l^\_KD^7Z^[4j"
82.     A$ = A$ + "M[=^0ih6L9^^oeYjD9VN9hQaf7e0[>Wm^L_aR[GJS>aecEC:iNi3_26=UeWS"
83.     A$ = A$ + "b[[km?C53PkgkC=NB;9>2_nCmobkWYf[Fg7kc9Mjf7Ub;h3gBFK8cmjH>Flg"
84.     A$ = A$ + "\V]GgOehJ1ckCo^iHdgM[KdlgW;?#imPj04K>WnYL][^fNWI]H0be5gaJKiN"
85.     A$ = A$ + "8gDf#KM_BKZe=oef_P>MkVbl]hNlL^o1>5^6<L=L9DiN?oLLY?oIKXUah:]i"
86.     A$ = A$ + "3Uf_Wb7nbm\_lnMZH0bSI\fFj3dH]Qb[oHnlW?WZYWZEo2jdU1UfMBOMA>L<"
87.     A$ = A$ + "O<K9Fl<?>V;=c55LNle^>UkcbCAYmFmkgSOZL816>]1Vif:]QFR9[]G5?EKJ"
88.     A$ = A$ + ":KjUgWSU_aLoD[V]oN\eMBZdFM;DRIVbFD:kG:CG6;LYm^Ja[?5UnPCLZ9VN"
89.     A$ = A$ + "<KYUkieUkc2Ik_ln;aHeRk_fnfK=LMimiDke3c]gE=WO1MjbQBicFbiKYm=m"
90.     A$ = A$ + "9\6f9?gUbQC=G>:7K[Fl3?S]DldB`delg8_fU]a<WJUgKYN_<_OUhjJj^6;g"
91.     A$ = A$ + "PIObHnOXo?milFWBIgiT76K\XZIO0IKaoeR5dO[dFM6_^k3kniabaK]ld1VI"
92.     A$ = A$ + "<ZfhKGREbL1FkNLZLDUhelnAoS=?jUjQ6c7llLHL6MZCCA]>W::cGN6KL]S;"
93.     A$ = A$ + "omBm5IL[I\P9N#LiDaabi]<N0aBe8`CUi^_\M0V_fhme2^6<IN>]FHBL;7Gn"
94.     A$ = A$ + "id>LY>2>OeJ;;]NOjdU7UbWe\7R=jDfBlfHj3:U][5_HJ3VSU[AN<UfJConi"
95.     A$ = A$ + "oUGKo^dnG9nWfDI=c0f?K7L=bOWgWWcY6[HRO9cmHim#ZC<?ofOGZCR[EiiK"
96.     A$ = A$ + ">O`AG9m;mH[k4D:K[\6bE8ODJ;<]3VbMlohocgUHSaR_]VLnDfJ;c[LfNE>^"
97.     A$ = A$ + "lo0>5ilbL1ThYaJ7LO#kN:OIbn]B^F=[R_5X;XFMY>eh1JMm<VO3#UiXKOG_"
98.     A$ = A$ + "ZMjdWZUgfJf8:c=4f0Wjh#FM\LFEkHa^nDSC>fd5G`[PCJ97je`[im^Sm6WC"
99.     A$ = A$ + "`?Y?^YN]JDY?bcM?<6EKl5bfKZ3]fi?SEI\oCW^lXJihF\iDiB[lh\NbJA^B"
100.     A$ = A$ + "OSQGCi`Bo<hmdVfVHBCKVSAdf1G]6c;LlS`L5V]gbj]YTD_#joBWjTTbXmi]"
101.     A$ = A$ + "km?^n7cjgZej#]CMjBWdokY\aVhYSY=`UDWnMZCGbTaSR_[SiON6kla2?]=e"
102.     A$ = A$ + "2HWjdU<I<h>O<C\KF78]>?Eg7DV_nMInOgY>MY#SU3jBnH^6:UiT\?OZkDWJ"
103.     A$ = A$ + "S:73YF67j35UeTGg7l>eYUC>VK>oAgfa5K]KCmego>eYc?Z_G3fY>eY>eY>e"
104.     A$ = A$ + "Y>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY;1jWk"
105.     A$ = A$ + "gioiNiLnDoZOd=_egc_lVOfO]oSKn0oAo9EoOoWNQ7TGS[iCldO`mbmEWjdY"
106.     A$ = A$ + ">QL?HPGo?noV1l`JBLNoFnnoG\i[k=nF6H>oO\?cWm^lEHg7Pmg2N9g7Ln1;"
107.     A$ = A$ + "k[L?][hJ>nmAOCWjD[TbP_jWl7L#>\5IJnON<NL[IK1\=_Wc=HLNOE<mE<fc"
108.     A$ = A$ + "ijcoUSM<kkeXgaCo\373hI>>eG1_]]o_gO^OU1mAo=Oe_^]nldY>][4bNR9D"
109.     A$ = A$ + "6O:BIO]aaaPob[19^F\=HJaZ?Pmj[n\oo47]4LMJGUS36L9OgBYDGW]k>eYS"
110.     A$ = A$ + "11ND\<bh:W?5>EoEcooLf[GROklo4Wb[3fZ[h3NJKUf3h9S7_eH]cf_nT_=n"
111.     A$ = A$ + "?kaUjjjfZk4bD8CXoWK3QlD[nA;9FSS1l`?`kogLBiJaBROdGii\akeYelBa"
112.     A$ = A$ + "o3Lm=aFG9VJmmfcW_GKk;Y?#oEffno<^LeE<GOBW>o9aeKS\UfI<O^;ihe_A"
113.     A$ = A$ + "RcdH=iea>NKWZ70l=nL>U<\n4X_^l:GSJWKaHHWn[n[oENS=Knn4OWaD[^\]"
114.     A$ = A$ + "9nJ_^j;ofVW0kgEGG7Gg98a;R?GB>I1gX\]HSFU?iH=N#HR]L:BM7N]4;=EK"
115.     A$ = A$ + "=m;eS_fa`e6Ll;o[me>PYUo;lGiU?lmI^c0oX>9ea#kW?g:^F<Xj7hJ\]i:`"
116.     A$ = A$ + "k9miZ5OHjdi?9N<aV]:GXn0ckSHWUNm=OEH;5<6nTKkA<XHdUV;LUe=OBL^;"
117.     A$ = A$ + "9nN`FPUO9o=nj^Qo[mboK=lMPgBL=ggHSefRhbF`eL^lJUjBhm`Z_H9mON?2"
118.     A$ = A$ + "gS]^C#ILW;9FKT?mh`?Eae;aN_fMeWG]kYo_e8aD]:oJ^]WB70oNJW>]Gc[d"
119.     A$ = A$ + ">o_lI^KmWTnRKkFMK=eNN7o#3WG>^GmCmOH#?fKjWoI7dg`m>ofSm?n]=iiX"
120.     A$ = A$ + "L<ihmL?dYcG:mG]eoOVCFhil7<cQUHjL\XKiJWiNFo`e>]nVGkl#kSO[ELM6"
121.     A$ = A$ + "ojH];J3RQUaFm3mWiQ6No_a_ec]iiNn=3HKagL^6`VGkoM[i;3<;G;`dLo2V"
122.     A$ = A$ + "FL=]En=`ncM?Qo4YMNJ;Mo_?OY<o_]P_BlL[eaH>fAJOGK]]4S87_H9>>U[Q"
123.     A$ = A$ + "aGL[i[\]TnBX=mY^N_kgg7m6oLCOL;9`\PQo2OAO93hTGa[h^<_W_kANTGgV"
124.     A$ = A$ + "OW?i_m0^FFmH>Nc;a_iGm[ikJhlnHoSng=P]UY?Pk9n]oYoho[WmL#k3M4`R"
125.     A$ = A$ + "[mn\S_?=Y<^bUBVOD]KG;o_e^N8;\4iQL<GW;^^oh:SY;bQP[eNEjCZbX9V5"
126.     A$ = A$ + "IMTUAV6\6o^ao2f\T`V7fdNd7iOiVGc[iIflBOYo37n_PgCRSmUl`?lV_R_h"
127.     A$ = A$ + "oRKnNonn2_QOTGi;I`N=WW?eOhO`Vo_Oj=3l_oWjNS56]Oc]F;n?Pn1JkL<o"
128.     A$ = A$ + "3NCo`?0^VfkGnGf;Kccn\S7c0m9LOoml]n:flOmGj9gl9Ooo[6hOnOagk06W"
129.     A$ = A$ + "kUilS_C7NZ\^QGjaVS[3fo0[dJmIVi5O9f^clHEN<PY_7oI^1SWnS:^>]KQ<"
130.     A$ = A$ + "NZW1L=O7_nclCmC_i7k9oA6\[bg1fdc;G3`QOg?nS?PAnQO\ok3<hKn_8oW]"
131.     A$ = A$ + "]?n7kS_iUmGo;MP;aeoUocnWOhooWLU_gbL^EWTn2X]N`]CAlkfVC<]jdhL2"
132.     A$ = A$ + "V]VN:YghgcS?X3jWm]o]?PW1K3CkTkI`ecI__C7NBLM>?OFB\bnocHNWcGa<"
133.     A$ = A$ + "g;YoLFO6CML83InMAVTS?9adOf[2olColOj1\1OVSCoA5G[]K\U96F2L<WO\"
134.     A$ = A$ + "ObkmcPC0_`iV[1<H_gfKh=_i;m?gOk=O;OcOX1Lmgf;nKM0WSlOZWimo1n03"
135.     A$ = A$ + "hTGi;m_jmQ[1WkiVf<fYiEn<HW1MBG[?cHcW2?2a_KlkUjbXOh?eOjGdTaFc"
136.     A$ = A$ + "aCKRfjkiMomO3^FKflKdW`mDW>]8mQ^\N5WS<N?[AQ\VS7;7D#V7Z4;[\gPM"
137.     A$ = A$ + "U:aT:aaQL4n6Sl8_Z=akIoLcVGhJLmWmi_V_jmlO0GS=_BoA1G3FAL=H:`Y_"
138.     A$ = A$ + "hoBOUKNk_UWJ`N=_2>5kGPSOQ[_>`lInM`eJ_6o`iho#_o?l0n4m0loXM0^^"
139.     A$ = A$ + "dN=O6KfXoP[777ffimd^M\]X]VaQ?5aaS>1^WCL=nEQo4LNBo9:9^fdF;m17"
140.     A$ = A$ + "6L>]iibiFW>lD>6C>N:]F7dV?e\VV5G?E^BiH:7O7`Z6k8HE9m55B\3bYJkP"
141.     A$ = A$ + "?S=7>6Tae>=d0fnJL=H:\YPL<h]BKGUhJS;5L9hK^>l:GK`MlkH;3L3aV2fP"
142.     A$ = A$ + "OWc=f[O[_nOZ1<^h?lG5KKXGPHX_cM^cV?W[h?_?g_PkSigTiclO^ceo?>G>"
143.     A$ = A$ + ">gLN0?aeVk;`Od6hmdVX]AKDMId6nUN_o^3?KlNVf:W7noSAd^CO`C6\>hjY"
144.     A$ = A$ + "R=_C7N:7CbQa=Y0G?gLd97khL>7iL9N<kePg5;W<O7bI6_7Hd<>C`VJoh]mZ"
145.     A$ = A$ + "N]gHcP?[];`d_`ef]e7IH>Nc3=f^n9O_og6``bR[ilP>2`PR_0G0nVf6j#\="
146.     A$ = A$ + "b[`lKlmb?d3mE=lJRGmk5GBKhKj[oeOce36m2Z31V_So3\7GN^]MUG;N?O7j"
147.     A$ = A$ + "OX=b[L?`aR^6^?1Kcm<W;mk_6agciH0knSnMn0fZYOWSO^H1jdQU<oCUnA;^"
148.     A$ = A$ + "^<o`UTnCWe2M]a;Zfeead1i>]IS?X8[X_QJkE6l:f6dOEU_8f_KT?OQ?m0ka"
149.     A$ = A$ + "PodHW7I?>WgLM_B>7LLR7eN9_go3h>`EP3CF\IR;1c8C>jlmRC1GEbh;<\hG"
150.     A$ = A$ + "In>o??eolO]=oTo0oF3_jaHKH8^U[^fN=`n:<];m?Pk5H_?imN_Co1m;Hc^4"
151.     A$ = A$ + "OKl2dGGj3>fZ97OL=kdY7UcOP4Gg:n<[gJcoUeM<o6f5#Vaa\1VaS5IA`#JW"
152.     A$ = A$ + "6I7H`\>F?R==oDPGAf3L<o?Te4GcaJ^\07[_a63>G7a^l:be8cSN5aXRa0k0"
153.     A$ = A$ + ">:I`D9^B\NF3XjO\aCPm#h4CEJ7GO\Co_e7LIaU96eoShd1Kc5n1X>7e]`[f"
154.     A$ = A$ + "f;]mc[dGP^0bO0ncSn1^>oX_Y_^k3CCo>miPiki;kdT\6\be#SL=iY5:WGcV"
155.     A$ = A$ + "7<Uicl<MglBoI6`fPi#VY<gA`jOWhdK`eK^[]G\E`o1<=<HJ^>h3[HHUo5Ca"
156.     A$ = A$ + "_?T_<bgVf0_bGl4c2WbnN?06]llUfnd_LI[;[TcL4Jo[ea:mMI<1bFo7eZgd"
157.     A$ = A$ + "\^#\nC]MV]_dn<];^_Zic0aJCn0BMAZSQWO9^VH]aF=OOW>=9W[#Yl6b9l:b"
158.     A$ = A$ + "E:[FFK5e8m_6I86S7TI#FRhm`nYa93^6KhP=;[=3c;<O?HO`aX;`h[1[Sl4b"
159.     A$ = A$ + "KPW5S[=W1K`Q_YH_6fhEa6FJW]<FHa1gP5^>>1>Fj?ll1^cikI[<joFja\]\"
160.     A$ = A$ + "i7alWkmLN_2>6l\HmdW4n>cWPmeX35KelnNLeWnTc]HU3\^7\^VdGI`DP97S"
161.     A$ = A$ + "\^?#6baj1i3T=070fTLCkHbbi5mnUhJSc6\Xa6CnbdF<7CVoHd3TfQBK]jGL"
162.     A$ = A$ + "Y?`Uaf?DcW4WL\69=5feh>bicm]16MBlL2mK9>gljYO=RciIPe]>mk6c3??j"
163.     A$ = A$ + "d];2ILNnR]#lkBkS6cKj?=<H?`08KPnOadbHG0<3o?aeFOFLN[Q[ikY=PM1]"
164.     A$ = A$ + "IX?_jWKnZfFDnDoB=VCWSS>g<g5kPL=e^>mE[5V;WC:7B\>fciJCoTi58cO_"
165.     A$ = A$ + "i0Tkk<goXKX7Om]32oUeFVSA\eO0j]1?J<_FSVlNlIVWe4[F=L=W_QaQji_g"
166.     A$ = A$ + "HFah0S=0`aUnPWn5KNYe6Si?:c1VhG77Wm9>XLMGI]H^?hNbL?N8afdWIoF="
167.     A$ = A$ + "L>?kikAo]aGYO?MKgWf4nk2fYF^BLL=6d?OmH9I^W=^GdUWeKU<aJ3^VHZ5G"
168.     A$ = A$ + "ch?aiRSY<G`ZG9abJ3AL\fPAFk#:oWlJ7_lfj?Qh?jWX?YeSSj8]UoWeV^mm"
169.     A$ = A$ + "6c3nPI^jVZVejdaU\V3=GciHFnd_[_SKZK9`bP[cJS46OV73GklI`JY6MlI]"
170.     A$ = A$ + "OPm07kf<?dILa6_O[bS]RU^]5SL9kL8M9n_ClB`;Y_TnNea2kHZiL#IZjF[C"
171.     A$ = A$ + "7GRlT0>[\NPim>7T6NnMM]OhLI26oZ[i;>O6OWig1KK<c>VYXgGK>I<blMYl"
172.     A$ = A$ + "dJR5d6Ti7l#Q]MNK\6W;ce]SEfQDGRiH`LOPNgNMROjBh;^imL\J<2K]>VbJ"
173.     A$ = A$ + "cfH\;m5WJU6k2jOM>NDF?DUa9O8T;=oGLmfflDEj7nLnUkJC2lJdn=6hSAlh"
174.     A$ = A$ + "9nVW]D7khcEW>M9`KPO=_II=1Km8<TKkX6?]F`6R?o:K]hk=\jd1oJlbI^[e"
175.     A$ = A$ + "7^MAfBiKdOLXTWM]FcJ8I^a5CfaAKK^VHKfi7c=eMfei\^UhZM<<]F5F[hIh"
176.     A$ = A$ + "iWi#K^iGFW>N4fS1ojhLUnRK]NRMM\ACncQI>5b[hC]ib6Kg4oUe]\jf=NJn"
177.     A$ = A$ + "_[QLUaR_VSidL<G[bjIANX>FFAojM>YDVgZ\FaM\mV;?R6oaBcafLm5d7Tc3"
178.     A$ = A$ + "_>MjAijdSnRk[j;>a:ClDilJbiPXe[\cinb_O]aOHgIKUAe?fFoo^V>06Sh="
179.     A$ = A$ + "biXQeSYeQ9SkkHW7lmge:\Yd1THJJ[D[8okO7o?^Q]neM\WPiH<fKieDOFY>"
180.     A$ = A$ + "Daemh[?m9dm2n]LNgJ]1klN2<;fW#nFL\eX\HI[3ce4;?6nFi>`FYOielmeH"
181.     A$ = A$ + "D;aElmRi07?\n8NmHjX=J`dPUB<6c_IaJdOHNS5_U[U`il6;c_\SA\[]Jj30"
182.     A$ = A$ + "j<hlVG_a`fI^7UKaFnB`fUhJ^OjSSmY?Q^G`_>GN`N=HJW_EH?7o[M^;WbP>"
183.     A$ = A$ + "77g5iVDg#;iIbea8TQ7Z3V:nV?gh3kj>HYoeikE?F9V^6[mk1oE:WkDG_n6V"
184.     A$ = A$ + "eS]ck2c]VmWlKcM]B\=GCeAXojlM[9f>IWk[ma`ndW#g;H:b;^[=MV[6bm5H"
185.     A$ = A$ + "0aBnmFWe[U\bBbWVno:FAl2OOFSJUcYSQa3ojjUF\Ta_jlfDo\oWm6oe7eVI"
186.     A$ = A$ + ";h>>nL>EGnOhgCOiiEWcXY?1?c?`WhVk?R7bO_L>UVLRggEKeUOWS]A?WIWn"
187.     A$ = A$ + "4?SL<XP1SiLRbib\iaaWePeGKK1ehLM=#Fkd^64Tf_d>Xa2khUG>_7d6jfRM"
188.     A$ = A$ + "G:[OkCIoE<I^f:`m1iT<WGFiL6_6^^D?gfJg^Dg]nFem1odW0CSMPBkcI\Ke"
189.     A$ = A$ + "lcFoaFbhcZLAJ7]VMJWWail;fH7mmR9;I\32Wh9HamiJY#=<V7Obk:VFKcSM"
190.     A$ = A$ + "^<FI_7=7M>6Q>N2`>O;mH73G3ce<Si6mK;Ml^bW?n<Y_6WMJCF;Y^VHQ=JNf"
191.     A$ = A$ + "WSQC]WcI]NfZ\QbF8_R\U[Unil2FKaILcY_fYm\BKebCIC\lc:kW[Y8VOK7O"
192.     A$ = A$ + "8SoeeHUBOZ[I76OWikClZigScAILiN_JnbEo7hjbl\K<4Io#=>e;AO]GWblk"
193.     A$ = A$ + "Uc?milKgeMVnLandUL=T7i7RYfeEG`[CU7<[CRFS]N8oY>70_6?3C]Yik;Sc"
194.     A$ = A$ + "T_CIbYTM[Q[5oZ=jTCkf83[o0>NL^F:H>ZYmkJIRn_DR;EGCYoc^^nJn[Lo`"
195.     A$ = A$ + ";?NJ?ZK[\>Gbf#bNNXmd:^>agFCPiJVBiW[Q_EGCOl]>]9NnPMJSSN]Z7\BF"
196.     A$ = A$ + "kE^OgPLEb96gG[9CF3S?6^>c9\n3H=ZUiNVkeiZK<Ze<HnOL\L>ljhhKE6W#"
197.     A$ = A$ + "6oRS[6_BoKI<m^?QDKL][E[ZXSY<WQ]R[YFO]oEMZIo=_WkYJem3OGOMCidV"
198.     A$ = A$ + "Lm;aeZ[i\A_;\Sk3fZ;ad9f^LNQUL;hJn<G3a^jGI^GQ`gYMiUDOWP_H]QSS"
199.     A$ = A$ + "GL=j>dfFiJiX[]D9fdj5OHM?>JgP?Mo1\UfRko7h3#jO#ILeVc<NU?COC9NN"
200.     A$ = A$ + "<>?Ng[bL]<]CW^4aEK=nJMN^?`d`J;;mo>acY=Sa`c]P[efYkmc[im#=keP["
201.     A$ = A$ + "M?W=][?eiaHB0CbjX8g363oBdchlQ[L]:cH2bJO9[9EmI:k[Coc;mQ2OMBOK"
202.     A$ = A$ + "jhjCKRjkfmG2\W>WLTe=eB`26?Fj3NY?gig;kl2;m9O^LnJ\i^Oc]?d?=4gb"
203.     A$ = A$ + "eSOVi`NYenQf\M\W4g]=S3E^nVhHOkhRagQ^=laPe5U\>N<FjT;eaV\a_H\g"
204.     A$ = A$ + "h;NO^GOJBj7^[3?R3[9oHNbBKjImKV[MfiWci]#:W8N>c=;b>9VfOSGaoaBk"
205.     A$ = A$ + "ARUeFTc[QmilGLH=#oZfTeNVfJGJ]ihNiiJ=O<\MIlfjGO=M5>?#:Wo:>^Ji"
206.     A$ = A$ + "cWJHMWKm]\GQeYS3iJZPSKE[fS5;Ua]UeZUf0DfXdWKUkljiHPinBYhjLmj`"
207.     A$ = A$ + "JTdaS=[]T3aJS4nPSl\nPkhTebH3]_I[UMc7WS]fBdG<d?G\o4DjWUl`H2n`"
208.     A$ = A$ + "?lP?OMjdSbm]AdofbcOe1X_K]bYLQfccc[n7R?gXW`HTMn=Ue#M>W9hHI?UK"
209.     A$ = A$ + "W`5G?NaC]N5`eZL\WW3G_[[E:]jkQeZReJcfP[QceHJm7ScKVo37k>gg3kdY"
210.     A$ = A$ + "7ac5gkkbW]>V^injDbJKH9HJm]3\K]jGcH5cHUeoF`DJk>ac[9kNT`Ho^[O4"
211.     A$ = A$ + "iloPg?ehh_;[ghj_L;HCjC4GG6Om^dWH=2Uc;EG[IkaGOJCT;8eobcb<NGcG"
212.     A$ = A$ + "RSEB^WF=fHFEj7^\edARG;idN\e`BioYEKcTk\biGh^Rk]6_XFB<fjQn^mdJ"
213.     A$ = A$ + "UF[f[5oiLnd?_[[?:>_c]6cDGO?WhWn4[m_>??\nAMM[L:K_6W\[O7V3[bjb"
214.     A$ = A$ + "8iUPaFSe\We4GkjSFFKY8S_fSWff`6[RnGE>Gdgen#GcKH]ciSn;ld7KAf>e"
215.     A$ = A$ + "8YlPb4>g0V2GOcjCH<oQM^:WkiL[9fjDPMmGH^eiGd3<\n<\3[_I;QM=SP[i"
216.     A$ = A$ + "J6W2??IMdQe=7G;ZaF#g?lCObeekbLL3feji^4OG63l]IFO\GceiCmQMODG^"
217.     A$ = A$ + "7Bfe7;`e?kCm=O3kNK:[17oOn=kc][CARH\cLL3Ffa^bh\cJkfaJjHRYcj5M"
218.     A$ = A$ + "H?dkZhYgfjAI\e7YMUGZ>2[1eCUm]0m1o=mZOig7VN<nomoiW^Sa?A8ZQO\Y"
219.     A$ = A$ + "D>Nc>6cihHVoFihDeiMWM?;n#_?l9G^6:`HNQ]JFK\J1G;g]QOl97kc<NJ]5"
220.     A$ = A$ + "J\fV7V<OIMLmi5G;?8X_WHdF2V^S_?n4inPLMUe?8\HIO>K>Peglif3;Fcem"
221.     A$ = A$ + "\MQM_h2fiKUilBON7SY?`eL]ab5hm]VkOMndLMA#>W;gilYn#^Wgg2GFoo^^"
222.     A$ = A$ + "XD6GM7OOjCD7PTGT\N`\^AbLmhhjTS3mDhF[IYmYLXSSMRE]NYL>Zi[K;OCm"
223.     A$ = A$ + "D^3WSL?3Efem?GWVE_1n>ijjP_VL;k_8[9>gfN[aGgBlgMj`#8;I\eg<WX^2"
224.     A$ = A$ + "[GnL>GWa>dig5kNFcIJ;ea[5LgM^cM6HaPlm4G8h7^G43A=Sam;[=<^n`DRM"
225.     A$ = A$ + "PI]N[TYVK[mNnoNnTijThFJ3`^G:`J#HZcaiEgMVPck]L<5;mWH=gK04KcJD"
226.     A$ = A$ + "kofo9oMG5\=SCFgfmnWLO]?]?=6^m#__iTeoARQE6G<;h8`CR99GPg6Hd?<\"
227.     A$ = A$ + "_aOEk6M<\?Xam1jNL_=Cm3b3kMPaJ0m3<G=:l?XLmUHY?3\NDF;L]L7KOH8T"
228.     A$ = A$ + "c`_L]a];haUH??a_h;Phfdn4]7>W8c3FhHS713:VSfVfDa71\53SMJJ_7bf5"
229.     A$ = A$ + "jdL_AKX]5[Sjin:N^W7<5N?ae[9V>]MgY33iNEmfPYKIm<DLO^7i8WkcGHkJ"
230.     A$ = A$ + "]\mZOcK[>1>>G7e1k:>ff:g?Sio\kC:7KMAL?THNJkY]NSk?g3VheQeMjm4^"
231.     A$ = A$ + "^kGnQShi^c9k]a_]Y\9kndC^?NYocK[\ZagZmCTG=VFSWe_3idUP]iLVfSC6"
232.     A$ = A$ + "KbL]I>#`nW;WkYR?Vf1oWS=nN\n#_GegN[E>`lkCL=<e]F?WJkGbmcWU>?=Z"
233.     A$ = A$ + "QUMO2AOZg6\E:oMSoUAlUYOjlKLna^d^h_>GWY`XJ7FLmknmmA7hF>>HJWW:"
234.     A$ = A$ + "aD<Fo\ScU?k8gI;]nDji;odQ<?J`UhdF`ig\n8M]?N^oQdZ?e6kJY\FJcm]m"
235.     A$ = A$ + "6Nck5<Q[Oj]P=e?L`fPYMM=T_[eS?ai7KllDm9^g;bnb8aQPmkm56_S]gOTn"
236.     A$ = A$ + "RWeUbDeQBY]iURUQca?2KQ7jL>AkM9HA^OAVG<]f\Y_H9W7dSL8bQ_c]7S1b"
237.     A$ = A$ + "eX\UXSTLN`i1\=W7NUafN]ahmlY]O8l]LZak:i4?c[UfJ[aPIih#VZlk>THI"
238.     A$ = A$ + "TCGRmiJHKZO4GOQ1GSLO[7oQ>NKcMVi0<73MmmXec5WSBlMg^mY=AmUJL[CQ"
239.     A$ = A$ + "W=GZP=Vbn:fS#>PL=Ym2]gM8U[CiKJ;96cm?Db_gB`fX7cmiWi`dV_I^6Lo_"
240.     A$ = A$ + "]iI`LLI>1iLjhMcc1dG16]Uc?o7noVc2jGhn8ei>5ceaL[_fhk>fNM9NNYnl"
241.     A$ = A$ + "a\?KMQ<6N6\<bI>nY8_\Donf7lHa#3^lIOV=3<fM=?k<n^K[=MRM1mIF3XNn"
242.     A$ = A$ + "QM\UWZ_`JJ[\][meKf3C:bSXifPG5kgBL=I^9]VmJ=fOeMca\FhKbCNO<`FG"
243.     A$ = A$ + "RWA8KhHIVi7M:kcXkGmg>OP>56oFia`XUh^JlmUCn[aUX_B\Seee#]MoNnUW"
244.     A$ = A$ + "lLiNWG=OaAoGjS\eC^hF>o4[4W7OegCKTO?7;Je5`WGR>E^GiH5OgZOj<GAh"
245.     A$ = A$ + "H8OKk:n^S]GGbakba0>c7F=mlJKfS1iYSA=M:fSf3jHb_O<<=O?fXW3G_f<h"
246.     A$ = A$ + "j<W2dOUfSM<8bJ8QG76?_Wl7ln>G4O?_jn9RhOnN`kVg\]A7;nHiNYlBRORo"
247.     A$ = A$ + ";i#OGWCHmJGIm8O^Te<N9>U?[ML]=_]eHb^bJGBfh4BI\YRAn#SYeGLjg\=B"
248.     A$ = A$ + "OWfV;o_h?Q[ciRi7kljJZ6e;3WCadL]f5OW#gXi3_EocY]RMkM]nbki8Og9F"
249.     A$ = A$ + "GaAFGO^;U5dnLj[mJJKfak2k]IMTUi:biRUejX]3W;5Y_5cE;H<gW>6hJKkY"
250.     A$ = A$ + "^#n>^?1GFcNL[<m1iL]Tn\ejITkC<]T?OlM2Kf[aHQalh^CK7UHJT_:S7caG"
251.     A$ = A$ + "N<KhK;ci1IP\F6eGQBL8cYaL^=knl8eD3W;S?efFF?Yel1WkaS1^6oT97TUn"
252.     A$ = A$ + "hhLfZUHn;Iao3kAfGkcbn8o6]Fon[9^6^C;WHmSE<K=Ma3k_K[PoLUhITS=n"
253.     A$ = A$ + "Ml=5I1`Y`jW?_J]MULY<]fXX]2>GKRdNIOY56kc7KKe9^^FOY]K[AFnLRcMM"
254.     A$ = A$ + "<^LMOajXEMK[ELAYnM^6]D?`lkh3>n]_VcOk>e>aLddhY[5k4h?[CYe#FAOi"
255.     A$ = A$ + "M>4BNT;]?QL?hlF\K1NeH3dn=jY\nCijI]ShnH=g;7;<=<hbYlWUnLS1A<>g"
256.     A$ = A$ + "SnIcSVc?D\;VcaeJnK]DM^n\bi^Vc]=7gbi`dkSiiIOL]KS`gKc]bH?[`6Jj"
257.     A$ = A$ + "Kk^8[hHfhndeHhF`PPGW3OHnV\Ng0?[_RVONn?R[e>iadF=<igZeJdCoX0kb"
258.     A$ = A$ + "L`h]mZN]3mU\oKlok3oA6HN?h9n=nO;Y^cclIXN3gOWhga7PiZG5[a5`cI]T"
259.     A$ = A$ + "_f[93`mlS??1>`l`>fc<NN][hjLLLZIONKI\?klVTJUCfi5]kagJ[NH]Sh:m"
260.     A$ = A$ + "9kjeemRk]mhaGJcggDmKLO16i_oGeOWQn#aaSa<V_P]JilF>G\]F01OgZOIP"
261.     A$ = A$ + "eilXo2ZkI]abMoaG6Q?[8g<E<cjoUhJW30lm]j[Wnb3_FHJJk3i#n:LZi>3V"
262.     A$ = A$ + "gceAL=fk`>][Y3[ahEknGi^P[WCOZmeXgRniWkmMGkb`ij_6HI]McW1GGjO_"
263.     A$ = A$ + "e7>G?[YgL<=hj<ecbLL:Ll^03kiQg_?W[GMKf;SLO`^eLQihHjhKUhkLm6[F"
264.     A$ = A$ + "^deOO]=HL^^F8ImAR<I9fKH<L_jk]6[=6cL<f7b]mcNgi2MI^dmJ>TC]E#WB"
265.     A$ = A$ + "=L=]AgK;K5GGK\4Cfjn2o[ClTedEnIdOik;?WIlj>Ge7[>bMl9Ln^kLl8SY7"
266.     A$ = A$ + "6kbPUYfCf7nKg]I_m4?oKaO`B\]_gea0T5bLlDcWmdVQidBM1`^OLkholL?o"
267.     A$ = A$ + "VKVoS>nGJSciR]W?[5;[_Zbad2IBloO=`d`^^OFnm^_Eg2^fJl6kWSEK^>>4"
268.     A$ = A$ + "JC4<TaF3KmSBOQeemHj9hoALG`T[DH>NaafoG^N8Z>4`akSiVif`meIUa9di"
269.     A$ = A$ + "mcnfof7diZNndV[[CAJ?N9nM_=\[;?V3?mU06iFl3]<NBm=Uh?YmK>n:adHS"
270.     A$ = A$ + "O=[GD\E?6^NZj1[T9ONV_ZJm7>>5P[#FNZH[Y?0\gHm]foZ_dVcjD_Qb1RQ?"
271.     A$ = A$ + "fhgi`fMjn9ZOWWnMmM\iYonOE3n#ac#cUIZ[fWcn\>GgKAn0>GWLc_ce;QB>"
272.     A$ = A$ + "S=4l:fP\V3EFCK?R_[QWii:nWBkbleXo7RWQiLWcARiH\[gR_d\^[Gj;^kG]"
273.     A$ = A$ + ";bWn[`JXgY<GE>o#L>V`mfDhJWc5fgVihfi`ARSClkYRMhUbmh\_7AOacnSn"
274.     A$ = A$ + "M^i3lD?fVOagagh`[`Pcan=?OiETClI>fd5OK<M9GZg_d6#nnd^P<hI^6L]D"
275.     A$ = A$ + "n3M7POYm2;N6IF\=iiTS5l]j<hk5GSllBcC7H9fW4J96keHlbbldSOgijhVc"
276.     A$ = A$ + "k;`VL?WS]E9kHLEnl8kW>Tifj#`mj;mN4nO36n3n>ok]iGmYn6_Qico:?aSM"
277.     A$ = A$ + "O<hMd10ca<Po_f6_<b9RoG2caaaS^5h1o7^Ra62bPV3HadHO6IKUM=gMY\]h"
278.     A$ = A$ + "j]5C[mjF7;<gW=f5L=fUcJ=9e=bnRXkIaTC^Y6[;n]dg:jSAgli4>^Kc^>A^"
279.     A$ = A$ + "64O:^nINb7Mccl4?j3PYCVo;l7nYNdQnB>^?bCm83<OWonH<o7hlHhL`[XWP"
280.     A$ = A$ + "fSa3P<YnXkHhH^P7\=Omg?V=;]e_]aCS_e\O4fZ]f]=OLDK:^F[`m\H#Soem"
281.     A$ = A$ + "`HgORAG3OoHf\A?XiXnHSe>TL?oIgeF]HJaelJR[1[i[gP7ObGe0N\\?=]gg"
282.     A$ = A$ + "2;^fS?an8CKM:I^`<G#Ho2<kLeU1Hn]e>mfb4CmfHcfllS^:RkahP4C[]jL_"
283.     A$ = A$ + "7gJh\6ffn\mMMQLZaGjSiEV[\4GGj;NJO]4G_c<WW:<?O`N=bT`ho=HDS37i"
284.     A$ = A$ + "mi`dj;:HR3EMRR?1KKmcah:1V6mIl<1VgkLPAlLR[1[SN[a\Ikh2L^kkMgVm"
285.     A$ = A$ + "M9R19mo>]EG3O_:HhFaeGKo6iJcKVSm6HlF`cbH;SaoNYSgdfbXoHKm37L]H"
286.     A$ = A$ + "#N^`[PcMO9>gGb;afSi?^i4oB3GOYVo<]EWa:?6Vn#R[CO2Df6\\Sa6f\K5C"
287.     A$ = A$ + "W[oh3c_[7j[JWZecFHGCcfVS5m>R1]>2`FLjkMb^?UC\oL_E;^T;Ao`Q_4m5"
288.     A$ = A$ + "7KeTW9`dPUNVgiS>9Vn#S[YMXO4Inc#V7k?]R[A>Wa3RjXJY[a8;en\k5gkb"
289.     A$ = A$ + "LHAke>VRlN>Oe`dUhKbW6aJGVOl;alV9OYUGLm1_6^N_QOGPOh9^Ffak2IDl"
290.     A$ = A$ + "eX5L=fZZ]nP]f<hh]5;CmSjakJSRHJRYN<KeUhJnOh_>gcFg>>>GkjJ5h]En"
291.     A$ = A$ + "B;6Kc1^h86G;]CN`aeS`X[aanRgCk4<=HkC=LmBe1Tka6>_c1Oc[gDk8GiG="
292.     A$ = A$ + "nG?7V^<FK>>Rk`H[9nlS=njHaGBnRGJ[FL]HKOOb7M<nCN?L=fOV[^XcL6M\"
293.     A$ = A$ + "ae<Vd>_cL=oemjNWk:^^6I=UiJBNihJe2KMVR>1cgha6OM<i;5Oa7bGfeemA"
294.     A$ = A$ + "RY_13?bh>MDafGg686KbMF[Sa5aG36J9e2n^J;Va^fm90]733>Vj;Qf2[c3^"
295.     A$ = A$ + "^<1>Do`Mo_ciVUcGeUP]=7JL=?4kW]WjlU2^6KMDSVSJKn46GKMZdBmXTi=b"
296.     A$ = A$ + "ed<RgL=`_>?XBk`ROM]>emeJ`_\fBmIo\KflYOn?m`[lIWWI^NmSMMW;7R[i"
297.     A$ = A$ + "jP=lY6W[a6g;J;FG^7K\eaT_46_;m17kegDK95f\?UaeHWfLW]TajRSaiAL["
298.     A$ = A$ + "e3:<fFCl[cSZ43kLo6lhP]hOmoG3hfohGhc\i?ic\I073o2_`mN?o_Qieae["
299.     A$ = A$ + "UPD;;NnciZ6HK6G?\oJmSf2K]SOZ?_:khjeQ\F`]na^1Go>W1GOTS_F\]SY;"
300.     A$ = A$ + "i2ZeLWE6_]S5D=OXa7HWS7iNGW[mW^VAPOdPMQoDoQo1KnmoDgeF<_2F6Vg3"
301.     A$ = A$ + "66B<=o7>6``XG0KePYilR=iaZ7DSeN9i?K`Wnmdj4h]9nB8gIL?>FMQF>?<>"
302.     A$ = A$ + "ih[`eXCbaa^eLWU<7Skm[9V>WoD6S;OWa23f=]m>7ko5l<<4_biamO4`fPYM"
303.     A$ = A$ + "MAgmPSZi9H;\IcoM=f?\>7hcIBKeFW9RQ_eP[_R]NYGJmYDRA0KG^^ViJFP["
304.     A$ = A$ + "]KRU5?R]f1ljc?3oI_O<]<O7[eJI^b0GS>4J?CE7M^f]^DKf3[KaGhi37nL>"
305.     A$ = A$ + "gIH[VlU9^VkgK[hJW;8L?];HK`DD;J9nfmW0\Yc_9VD<nL\DRWQAgPeZ^nOk"
306.     A$ = A$ + "n38i#KZe71HccmBb=>gSGRe#J7GOk2GS_hL?\dakJZa0[fhKK^ZMml5<YhCX"
307.     A$ = A$ + "4o>7QMNHGKfdoKgo20[gBkUeRUUj;>aUkl3kHS]jhjm3ajK2H2_G[QY?eaed"
308.     A$ = A$ + "^Y=B^P\V;fVlWEjOK=obaF]k;F>>IVW<ag]#^6RjJJ\[aiHgfm99cmmD]EV_"
309.     A$ = A$ + ":]Vo<[[DG3c^dc;ni:^fe_<`e9>if8^6Vk3WgV;I\\[a^>W3f6LCinY9fE]f"
310.     A$ = A$ + "`LMF2\=LYOgI\eHSVa^fc=HIn\k[\^FQK\ecQ[aN=Hjal5gifU[AB3aILV]f"
311.     A$ = A$ + "U]]liJMRW[O23eJm]LL][U:4kh#MZ\Pi^iDf^]>aH>JMO[IB?kM7;:7o;n?^"
312.     A$ = A$ + "7BRMMbI^[IXlnL]CWGM_o4okM_ePf^[=KC]n3biRH[ca=O<OaikY]iNfea6?"
313.     A$ = A$ + "MZ`W[SQ]hjL^ND>GW_=Q[9o0XSbjDaacIGaf`POMMhUHO9_eD?HD_9`>_=\6"
314.     A$ = A$ + "?5[1KMSZ]Mg?N1CWegY[3Q_i_b_Y1lJ]iGYfX1ccaP]J`]eRafib5]k>Nnb1"
315.     A$ = A$ + "Gkj=j]ML]<e?S[mJJgF\m^4_mmUG][gohL=8JHOlkJ\m7lInSfl;mNoM_1cn"
316.     A$ = A$ + "FO?ob3hM\cc[?aCo17d50Wn?c[FSWdNObGnSNOf\C\]ie3M0l:HGe=TnRgmi"
317.     A$ = A$ + "n27GOUm]L>LM[5GK=b5[[RiNDR[MY[1f6faVbiC9nBC>\P1GW<HLgW>MmF#L"
318.     A$ = A$ + "XHj4G3fEl[f\M]#gl2bmSjF4WkN4>f]MnJO\a>Wbli:^Vj\jL3GW<gGTG#G?"
319.     A$ = A$ + "2dngJP[a69W?`?I<^PEM>A:cW;m=GOX[Q[aN=hJ]ICk?mm0IB7C?g;SL_7cm"
320.     A$ = A$ + "WS>Vnb4GWceSBLM=\mA7g^0Oa[ECkL?H]V^6aMkNB9H#HN_hjBlZHFablO6F"
321.     A$ = A$ + "Ko[H_6LYWC?_lO1GGFCgiNZS[A[mJo^S[MOiYfljhf:^N0KclEiJnnF;C_bf"
322.     A$ = A$ + "M6gmfjK>ikFOT;aee`dgPI_67_4L=G3e3E3_jgiNZba6[LKR?Wae3[aAElQm"
323.     A$ = A$ + "f<^>ili8OFMIY]kUR_Mm:?aej;nDhjBkeY_kVCld7P<oIMoZkhjFXdNmU2^>"
324.     A$ = A$ + "IdWQm=G3UF2nfm]>no96L:o`M_0cj9SSgm`bbmUdJhj^oeMLM;dU2^>_7Bob"
325.     A$ = A$ + "im^gPjn1HVK=\9GKOg5F\FRodGlBLM^f3ijZ6\eBFJkgiSAiiem8_nhE]^li"
326.     A$ = A$ + "HmVUhjL]DhB1GkmX[YK^?PjniG]a>fjlbHN;aOj;>_Z_g3e3jEfgM=<J#WaE"
327.     A$ = A$ + "OVmOXdf?OOiiCffcUNmL_fliHmQWaGO^Ug\4?Gnm^>5K^d4[G^gNkh8EF?Z>"
328.     A$ = A$ + "G>cH[CL]SeTnEknX3mgPUa70[=DaiedA<V_h7K\`i4gaegn`e]bUf`cmbkdg"
329.     A$ = A$ + "LafOK_h_e9aQ>Vb^gKka2V6NHOmmJkgj3N=O_[I_^fHMei]W?7Y>^NLLMnNR"
330.     A$ = A$ + "9>m9Wj<Y5\HRcioZ=JaeHg>?gcMNjaH_^lijjKFR[?WS_NYhjB<>nTcJ#Pa9"
331.     A$ = A$ + "KMRDc?lY\eVc=;\KckmgVkLXOhh7#?6k>^N::aee63k>^nN[QaFSiDSI>O;J"
332.     A$ = A$ + "1CG3KSMjL?k^UcUhjaZk\>_LnL<Gh#CQ[_EFOhk2?2VVnUL]J`lQ]DLMR]Mm"
333.     A$ = A$ + "B8W_F;1GO9__J]VliH>cPL]BYfHHOYQ[cj>eeG2g;Aim67lHe>B[Lj?mBRA_"
334.     A$ = A$ + "lhjeNf^cW[4[9GP[5K?5VnL7G?6kJiXSi5HjQmYf[l7OK`eRAUGbaUSQF_fc"
335.     A$ = A$ + "f=Viahi<I]HdaeeIU387dJ_DKVK;^NKIaeZKYS[gNnL=fJ9g_[OPlQoDgbFW"
336.     A$ = A$ + "QgcHKae3c1[]8_I[1S?kR]kc_jMS?GS]FRjN_JmQgae3\nQWf[g5O`g5Ogcl"
337.     A$ = A$ + "fakkSSmfaW[S_EBgP[3O>EV^S[_KOBIle;9OG[5chV[mJ[o]N=U^MlihLhZT"
338.     A$ = A$ + "L_ij6<m5Jn`W2G3WhjaVcEKS=hJOGb^_4il<i>gi>g`>?#jaI_<nLg7L87[["
339.     A$ = A$ + "KfoNjhjZhJgCodNmf4OM9Nei>BF7i9^]EVcEgWlfh;1O`QjhjUS[7K^L=6>>"
340.     A$ = A$ + "]g^]HgihnN]EKlUP?hBVCl>^NNLM>?]ZQ]7cWi31gg_]VW_4l1GbH\ciTL7G"
341.     A$ = A$ + "O?L]i3?m3?S_>mWn#SUkf]KW_T\E3ij=\i5_S[7gN]fY?5``SamJA[>O9I[F"
342.     A$ = A$ + "jnl5_S[O0\=hJ`;7K<K;LOmBj1i;UlUEBj;N?njjl]9LMgOl7T_4]E3INakh"
343.     A$ = A$ + "j7TiNgm1XS=NMYnSO\aCW2lUZ]J8`eLokJ0D7GO?<=aWLKbF]L_6b_\]E;Y="
344.     A$ = A$ + "knlijN<[1aP=>fHdM1KO9k?ninlfZEbiRM7GO?L=SYea6O^;lU\ohGjfZUbi"
345.     A$ = A$ + "]I7Go8g<nF7K\i^JcnBdOl;]a[N::[A5Ggc^Tae<NA7KLiJ`\7PM\aIM<maU"
346.     A$ = A$ + "`VmU<^6i2_o_]k3^lUdlenB>ogCAFoI\>LVHkS=Nk#QYY^A9^JWKV7K<iJaG"
347.     A$ = A$ + ":aIgcEfh4jl\fB;]GO>6g=g7>WfhEGKQ?fHaefVmiNLfM<mdTaIWhJjgdodc"
348.     A$ = A$ + "EL]HKZ_jc5O`_D\IgSY^=Rn9`fPSe>fU0^>GgS>fh`^=kfHFgPkSYEkD>O#:"
349.     A$ = A$ + "cSfi>^nHS1gG<nQL\aQM<maU`OLWoVl:eIjiX=KeII\eWSnPWf\?WV_GM<mf"
350.     A$ = A$ + "AJc6<]LI][L\aU[9fVH[gWeRR[g:<W[8NGHdSL8[oUcQh\a>M??IK?IMSO9P"
351.     A$ = A$ + "[iNKOj3^[aP\7MB^;Bn#V[^Kke=NggkeQLM6oL6GclHSa]NO=nFLN1?;knMX"
352.     A$ = A$ + "<HK`J72\m]mlWe]C_N4HKU7MM#k\R_jNJOHcdeC#RKGfaC3>gWENVWhA?HiR"
353.     A$ = A$ + "ofX_hMkd[?E>7]ceh`S>VL5HdGinecJRO0W>hgmEn2H=l1^FM9UlQbOlKKi5"
354.     A$ = A$ + "_SYgOD6[][o2CEWYicUS=^M>N][MDme5<=mGY]j1LM5<m#\0Gi?^kgfkCL=i"
355.     A$ = A$ + "]kHSEKUaNB7C_O9afF?J`eZSlJ?O>fHgi\G_VaFci2L<j;biA3lHfZQYMP^P"
356.     A$ = A$ + "mMna_]Tk\NMTMh8bK1n59f^4G?fcXS=fM:6\dJio[H6kK\Oinbch8hJno[IK"
357.     A$ = A$ + "I>o9>fhfah^Og77bJ87KB:on<_c7MbWE7K\kDlJ>^e6CMZ_k1^o[PYYoSo?m"
358.     A$ = A$ + "[7RiMbY8^^?^d7ObJ8gl1=gc\S=fM:N]FKD8^E7gPL>ReaeccmhX?M8]KKLT"
359.     A$ = A$ + "?0F>UMgShBc75]1`7SiWkn4GK=JVcG6?oMLmdfXO^gg7iH;:gY22kfV;]dGl"
360.     A$ = A$ + "FaDk:[=AaecMMmoW_O=FgA9VHlW_LOAjD5GCkeJI5mA7SlXemindV:WcfE]I"
361.     A$ = A$ + "^W`dbe6o8o=a<b4k0H#heJol`m6;]G_DL]i=k#Q[7Sa_5[OMjKFkmk;lg6iU"
362.     A$ = A$ + "^?gg>8NFiJE\eMjQ6K?V=#WC78WR]9\EQ\[kWN[1N8[[\beJVUP[9nl31^Vm"
363.     A$ = A$ + "#`Ga[hEN3GfWhn2<O7gKk:nFlLW^mAX36obca1;[SUE7GGP;hJI]c0n0o[Mn"
364.     A$ = A$ + "BiLYRgoBNh7NHMj4ii7iANM3b^k26QSGKek2^VoonHL^nbobNIKnZojOUgLo"
365.     A$ = A$ + "2oZO=OGKNSO??nmaOg?nS?lm`lO:al;a6>b08;d];On#R]ci2FJ3M]`e^GkX"
366.     A$ = A$ + "n3`4JCFL\HIT91WS\[<bb_]g`KN#>6iFiURK#?a#MXDP[GZOhL<kJ>ln2OAO"
367.     A$ = A$ + "93]7`SLOimYhfU`9VWn>j3Yo1LNilhVWgHC^SU?_Yd_lB\m3hGn2mG7M3`RY"
368.     A$ = A$ + "MNBQLWfVAn3IKT?1k:GJSZDVggSmlFaBlOcal[dgTF`eL<>_^FJ\1hC=]1\a"
369.     A$ = A$ + ">7>MKaenIjCY_5odYofJ8igiCnKO\5ijd1Tn=n]N^=o<oDodeafcHoZ<FI]A"
370.     A$ = A$ + "Ocgm4?j=hITcPaF5fY43G:OFCFM:6iH\1>5^RoC^^[DjCj3<_F79fJd;djL0"
371.     A$ = A$ + "?]7_4LjB]I?6FW[_mgM<mU9acMlA;]Og2>^T5G?T_i[SWfmaFTadn\nGGJ7N"
372.     A$ = A$ + "<kcCa6c9f4W2SU[YYK3^VOK^eQ9d_\=him5S?2ONO^O13__CG^TcgCagSRYO"
373.     A$ = A$ + "bkRS5;8^f??\N:Nei`HAQAN7LHV?Xil[\5LMR]afdHhJ`[SQ][]^?F3GCnX6"
374.     A$ = A$ + ";nNeIMZ`fg#O2mooloR_gS]hEW>bThK[E=Ui7Zcl[l]FLM]abJH<N_jHB<=f"
375.     A$ = A$ + "\[5SlDhj]Qe6E=<WeVCj;NVO_T]Vj;GgDZUc<\A[^ZS=F^Fo9adS_Bd6kDWP"
376.     A$ = A$ + "8gJJofl>E^72Un_:V0iO7[E`dUnL?W=VM5KGjC>O?jZbk7Im]8gOa;acbUaF"
377.     A$ = A$ + "G;G1WB\]9dmPn^NLfMZTZ=fg?`j0fEfY=?ITcH\C>FN^K1K_]bcUaKciZfmS"
378.     A$ = A$ + "HmBVkcJLR[1W\=]eF^gG:fM\hBXo7M?6g?i8]CMJ<BkN^NMVHJ778mmcLTE3"
379.     A$ = A$ + "OWbVC=6GK3SoWR1G;O#IL3d?labAfBm]H^O_5\\OORSYoWLVmiLEKUG[YK[C"
380.     A$ = A$ + "MJ:BKLH;7lYSOJ93VPJ[2I?[Y<H[eZ]QiHiLhiTcOihN]VaFnno0OPKZ1>a>"
381.     A$ = A$ + "N_Ue8gHhmUhGReFFbIMVI>a\MHK1Vn1n?_mgbC]iIOfnhGgYMWnhO\?n#nGa"
382.     A$ = A$ + "nf?fCnS<8KUn6:N6OUCIbJLZG8e9`k;UW]F^Bl5GgmA^PiNTk?^ghj`e]Fk1"
383.     A$ = A$ + "VkCJ_bN?hmQ<o?I`[Nl9GJ7fHWY_UnJJCXkYkcMW>64f?ZaPGn#_o?l`[8K2"
384.     A$ = A$ + "GnknKlilg?f4]5dQlFO7o#3HMeM=66ELJ9k_EjOSeO:jBhjhmM73gY>MhYDO"
385.     A$ = A$ + "5fB;InNHlG6VokYR^Z>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY>eY"
386.     A$ = A$ + ">eY>eY>eY>=?moga%%L2": btemp$ = ""
387.     HBCM$ = "MBO2L4G8G8AG>C<B2G8G8AG>DC2<G8G8>GEC<BA2>P8F8F8ECDC2"
388.     FOR i& = 1 TO LEN(A$) STEP 4: B$ = MID$(A$, i&, 4)
389.         IF INSTR(1, B$, "%") THEN
390.             FOR C% = 1 TO LEN(B$): F$ = MID$(B$, C%, 1)
391.                 IF F$ <> "%" THEN C$ = C$ + F$
392.             NEXT: B$ = C$: END IF: FOR j = 1 TO LEN(B$)
393.             IF MID$(B$, j, 1) = "#" THEN
394.         MID$(B$, j) = "@": END IF: NEXT
395.         FOR t% = LEN(B$) TO 1 STEP -1
396.             B& = B& * 64 + ASC(MID$(B$, t%)) - 48
397.             NEXT: X$ = "": FOR t% = 1 TO LEN(B$) - 1
398.             X$ = X$ + CHR$(B& AND 255): B& = B& \ 256
399.     NEXT: btemp$ = btemp$ + X$: NEXT
400.     btemp$ = _INFLATE$(btemp$)
401.     _MEMPUT m, m.OFFSET, btemp$: _MEMFREE m
402.     HBC& = _COPYIMAGE(v&): _FREEIMAGE v&
403. END SUB
404.  
405.  

[bplus]

Wow Dav, you can remember that? :)

[Sanmayce]

Interesting topic, it's nice seeing fellow members sharing their views.

A decade ago, this very problem (finding a word among MANY words) caught my attention, as a result, I wrote Leprechaun - the x-gram ripper. It is simply the fastest (on Internet, at least) tool for ripping x-gram lists (wordlists in particular).

According to my experience, Binary-Search is not the answer, nor lookup table hashing (per se).

Indeed "a billion words" as @STxAxTIC said, makes the game brutal, in such scenarios the really good solutions scream, so far, my biggest rip was up to 600+ million distinct words when ripping the ten years span corpus of reddit JSON comments being 300+ billion words strong:

 

The answer is simply using the fastest 32bit (the hash output, not the instruction set) hasher combined with B-trees as a collision handler for each slot.
By the way, hate to see B-trees misnamed, the real name is Bayer-trees, not that crappy lore stating Broad/Boeing and so on.

When collisions grow then searching/dealing with them FAST, can be done nicely (but hard to code, it took me several months) with B-trees, MOSTLY because when you tailor your physical RAM memory footprint to be small, that is, the in-memory hash table(s) to be, say, with only 1<<20 slots then Dr. Bayer comes solving the DEGENERATION of Binary-Trees, or the nasty Linked Lists used in many Hash schemes.

My point, with Hash+Bayertrees duo, there is no limit of number of keys, nor DEGRADATION, on top of that, the duo can be tweaked/tailored according to your memory needs.

Oh, as for speed, on my laptop with i5-7200U, ripping rate (i.e. how many words are recognized/found per second) was around 12,000,000 lookups-per-second till the end of the file - STEADILY, when ripping the English Wikipedia XML dump ~70GB in size.

[Sanmayce]

What I wanted was a hash method without collisions, but after a brief look at permutations, I punted on that idea.  Numbers way too big for words with over 20 characters.

"PUNTED", hah-hah, didn't know that word, don't leave your donkey behind in the mud Pete, as the Bulgarian proverb says. FAST Hashing without collisions is possible.
My Gumbotron (source code in my Masakari thread) is a 128bit hash (using either 128bit or 256bit instructions) suitable for such tasks, it has only one weakness - the range 1..15 of key lengths, therefore it has to be prefixed with some bytes, up to 4, anyway 20bytes or 160bit is kinda the standard. For keys with lengths 16 or bigger, for what it has been designed, it screams.

Didn't have enough time to make the complete benchmark, yet some results, all the 466544 lines have been hashed (with Gumbotron_YMM) in 8 miliseconds:

 

 

Code: QB64: [Select]

1. C:\qb64>dir
2.  
3. 12/11/2021  08:42         5,329,510 466544 Word List.txt
4. 12/12/2021  03:26        18,661,760 Gumbotron_466544 Word List.txt
5.  
6. C:\qb64>"QuickSortExternal_4+GB.distinct.txt"
7.  
8. C:\qb64>type "Gumbotron_466544 Word List.txt"|more
9. 0x01-66D12A342B6CCE8B-76DD8BBCDC717EA2
10. 0x04-4DEB4F7BD2C7B41A-EFA92545B3FDB9AF
11. 0x02-156418E71C1387D0-C56894090FE9BCBB
12. 0x08-47210BB6197940FF-77FDA06EA6D5CE3E
13. 0x04-59B0EE4F929901C0-8166DE482670F770
14. 0x08-EB52ABD995A0EE6E-495DC42CCA812D52
15. 0x08-D1ED8F252634F052-A7564B142920ADEB
16. 0x08-590505A51FC4A007-1742348B51C5C667
17. 0x08-23748F08CBDDA10A-B90F700EDB31A73B
18. ...
19.  
20. C:\qb64>"Sandokan_QuickSortExternal_Deduplicated_4+GB_64bit_Intel.exe" "Gumbotron_466544 Word List.txt" /fast /ascend 300
21. Sandokan_QuickSortExternal_4+GB r.3+, written by Kaze, using Bill Durango's Quicksort source.
22. Size of input file: 18,661,760
23. Counting lines ...
24. Lines encountered: 466,544
25. Longest line (including CR if present): 39
26. Allocated memory for pointers-to-lines in MB: 3
27. Assigning pointers ...
28. sizeof(int), sizeof(void*): 4, 8
29. Trying to allocate memory for the file itself in MB: 17 ... OK! Get on with fast internal accesses.
30. Uploading ...
31. Sorting 466,544 Pointers ...
32. Quicksort (Insertionsort for small blocks) commenced ...
33. / RightEnd: 000,000,353,900; NumberOfSplittings: 0,000,053,177; Done: 100% ...
34. NumberOfComparisons: 10,162,539
35. The time to sort 466,544 items via Quicksort+Insertionsort was 938 clocks.
36. Performance: 10,822,725 Comparisons_128B_long-Per-Second i.e 21,645,450 RandomReads_128B_long-Per-Second.
37. Dumping the sorted data (Regime=2)...
38. | Done 100% ...
39. Dumped 466,544 lines.
40. OK! Incoming and resultant file's sizes match.
41. Dumping the sorted data [deduplicated] ...
42. Dumped 466,544 distinct lines.
43. Dump time: 181 clocks.
44. Total time: 1,227 clocks.
45. Performance: 15,184 bytes/clock.
46. Done successfully.
47.  
48. C:\qb64>dir
49.  
50. 12/12/2021  03:27                 0 QuickSortExternal_4+GB.distinct.txt
51. 12/12/2021  03:27        18,661,760 QuickSortExternal_4+GB.txt
52.  
53. C:\qb64>
54.  

My old console tool Sandokan (something like 'sort') sorts the hashed lines of '466544 Word List.txt' and reports/dumps the duplicates in another file, just for visual purpose.
In fact, the hash is 16+1 bytes long, so whether the 466544 hashes are in external RAM or internal RAM changes nothing, Binary Search applied on fixed length keys (prefixed by the length of the key/hash) will be fast enough, considering the avoidance of using B-trees for maximum speed.
Those 400,000+ keys are not a serious benchmark, though, since binary logarithm of 466544 is 19 - it cannot stress properly the search, moreover the first run is not indicative since the keys are not cached yet, also 17*466544 < 8MB will be cached well or not depending on L3 cache of the CPU, more older CPUs are up to 4MB LLC, whereas latest Intel and AMD have 30MB, so it has to be considered if such a benchmark is to be ... modern enough.

[Sanmayce]

Having an English wordlist containing 15+ million distinct words, taken from 40 million titles, is worth benchmarking.

"As of October 2019, Google celebrated 15 years of Google Books and provided the number of scanned books as more than 40 million titles."
Source: https://en.wikipedia.org/wiki/Google_Books

The attached (ugh, the archive exceeded 20MB)  wordlist is ripped from "Google_Books_Ngram_Viewer_Exports_2020-02-17_eng-1-ngrams" corpus.
It is a must-have PLAYGROUND when comes to Binary-Search etudes.

How to make it, yourself:

Step #1: Download from http://storage.googleapis.com/books/ngrams/books/20200217/eng/eng-1-ngrams_exports.html 1-gram corpora;
Step #2: Decompress *.gz and "copy *24 Google_Books_Ngram_Viewer_Exports_2020-02-17_eng-1-ngrams.txt /b" them into one file;
Step #3: Trim all the "years" statistics i.e. crop only the first field (up to the first TAB character);
Step #4: Rip (make a wordlist) the trimmed file;
Step #5: Sort (for better compression) the ripped file;
Step #6: The resultant "Google_Books_Ngram_Viewer_Exports_2020-02-17_eng-1-ngrams.wordlist.txt" houses 15,074,900 distinct words with length 1..31 characters.

The whole package (including "Google_Books_Ngram_Viewer_Exports_2020-02-17_eng-1-ngrams.wordlist.txt"):
www.sanmayce.com/Google_Books_Ngram_Viewer_datasets_v3_WORDLIST.7z (32.0 MB)

 

Maybe, a somewhat decent Binary-Search benchmark would be to "spell-check" the KJV Bible (~4MB text) using Google's wordlist, it amounts to Binary-Searching 793,877 words into 15,074,900 wordlist ...

[Sanmayce]

Finally, we have a decent benchmark utilizing the Binary-Search in a speedy manner, it is a good start for all kind of experiments since it is creating as a result the .HTM counterpart (with all unfamiliar words in BOLD, all OED distinct words are used as a spell-check wordlist) of our .TXT file.

 

It throws all the words of KJV Bible at OED 2nd edition, which is 700,000+ words against the 1,000,000+ OED words:

 

The 64bit binary and the QB64 source code are attached, also the OED wordlist.

Spell-checking KJV Bible under 2 seconds, can we do better?