Liren Large Software Subsidy 9/09.iso/l/l078/1.img/QUIKSORT.BAS

BASIC Source File | 1987-04-02 | 28.8 KB | 489 lines

'┌───────────────────────────────────────────────────────────────────────────┐
'│   This  program demonstrates a non-recursive version of the popular       │
'│   Quick Sort sorting algorithm.                                           │
'│                                         │
'│    In order to run this program do the following:                 │
'│      1. Load Turbo Basic by typing TB at the DOS prompt.              │
'│      2. Load the file QUIKSORT.BAS from the Load option of the File     │
'│         pulldown menu.                             │
'│      3. Select Run from the Main menu                     │
'└───────────────────────────────────────────────────────────────────────────┘

CLS
DEFINT A-Z
%ListMax = 5000
DIM SList(%ListMax),Stack1(%ListMax)
True = 0=0
False = NOT True
StackPtr1 = 0
'
'  Build List of Numbers for the QuickSort
'
FOR I = 1 TO %ListMax
  READ SList(I)
NEXT I

PRINT "Sorting...."
'  start the timer
StartQuick# = TIMER

'  Do the Quicksort
CALL QuickSort(1,%ListMax)

'  stop the timer
StopQuick# = TIMER

PRINT "Sort Complete"
FOR I = 1 TO %ListMax
  PRINT USING "##### ";SList(I);
NEXT I
PRINT

TotalTime# = StopQuick# - StartQuick#
PRINT USING "Sort #### Integers in ##.### seconds";%ListMax;TotalTime#

END

DEF FNPartition(Left,Right)
  LOCAL Indx,Jndx,Value,Temp
  Value = SList(Right)
  Indx = Left-1
  Jndx = Right
  DO
    DO
      Indx = Indx + 1
    LOOP UNTIL SList(Indx) >= Value
    DO
      Jndx = Jndx - 1
    LOOP UNTIL SList(Jndx) <= Value
    Temp = SList(Indx)
    SList(Indx) = SList(Jndx)
    SList(Jndx) = Temp
  LOOP UNTIL Jndx <= Indx
  SList(Jndx) = SList(Indx)
  SList(Indx) = SList(Right)
  SList(Right) = Temp
  FnPartition = Indx
END DEF

DEF FNStackEmpty
  IF StackPtr1 = 0 THEN
    FNStackEmpty = True
  ELSE
    FNStackEmpty = False
  END IF
END DEF

SUB ClearStack
  SHARED StackPtr1
  StackPtr1 = 0
END SUB

SUB Push(Element)
  SHARED StackPtr1,Stack1()
  StackPtr1 = StackPtr1 + 1
  Stack1(StackPtr1) = Element
END SUB

SUB Pop(Element)
  SHARED StackPtr1,Stack1()
  Element = Stack1(StackPtr1)
  StackPtr1 = StackPtr1 - 1
END SUB

'
' QuickSort Non-Recursive Procedure
'
SUB QuickSort(Left,Right)
  LOCAL Indx,Temp1
  SHARED True,False
  CALL ClearStack
  Done = False
  DO
    IF Left <= Right THEN
      Indx = FNPartition(Left,Right)
      IF (Indx - Left) > (Right - Indx) THEN
        Call Push(Left)
        Temp1 = Indx-1
        Call Push(Temp1)
        Left = Indx + 1
      ELSE
        Temp1 = Indx+1
        Call Push(Temp1)
        Call Push(Right)
        Right = Indx - 1
      END IF
    ELSE
      IF NOT FNStackEmpty THEN
        Call Pop(Right)
        Call Pop(Left)
      ELSE
        Done = True
      END IF
    END IF
  LOOP UNTIL Done
END SUB

'
'  sample data for QuickSort of 5000 numbers
'
DATA 286,9327,9145,9701,4574,5640,8214,8347,3167,9712,5528,6872,1457
DATA 8934,7727,4404,2212,290,2890,4638,7948,4053,8406,2100,6619,4146
DATA 2115,4666,8613,4974,5893,8449,5513,7119,3459,3615,3596,6694,6560
DATA 2250,7533,5744,6301,1863,2271,3494,8817,614,3548,829,7006,2865,24
DATA 2821,2550,6146,2495,6655,4929,3135,8149,4807,6673,4733,348,5800
DATA 6530,2848,6882,7400,4817,3960,2202,9586,7624,7074,1548,7131,9135
DATA 2156,7493,4157,3750,7630,1840,5492,2241,8059,8337,2175,8667,5564
DATA 4221,958,7258,1114,992,146,980,4255,7454,6615,6016,2384,448,1366
DATA 8876,3152,1253,3430,5346,6099,8145,4502,3006,2119,8056,9127,1526
DATA 1822,2814,7784,7473,6426,7934,2714,2831,7239,4433,8835,8959,2347
DATA 6615,4601,220,1583,1328,115,3967,3393,6635,2378,6145,9670,381
DATA 9996,4193,7168,1619,2193,1484,6574,370,9469,23,2849,3679,5766
DATA 600,2914,8438,4457,2153,9289,3947,3026,4522,775,9679,3770,1338
DATA 3755,6222,372,2257,251,9855,2681,6258,1273,3750,4559,224,6611,1235
DATA 2120,9520,4616,9124,2214,9807,8095,1556,3503,1774,4907,7316,4965
DATA 3046,4332,6122,9177,3961,2850,1826,212,6441,5376,3011,8500,7684,585
DATA 3956,7504,2885,1384,1418,9533,3707,4167,5221,561,1727,2902,3117
DATA 6371,8569,6677,2869,4900,6950,1786,7055,2087,9339,1945,8536,1107
DATA 3485,2743,7066,7308,6481,8910,24,3714,1640,5502,2709,4416,4850,6600
DATA 6201,5719,9662,7604,3230,7370,2816,9736,5032,8718,4419,7822,4660
DATA 7156,9509,4966,4727,8669,209,201,25,2862,192,7713,8021,7277,5691
DATA 8729,2681,8375,9750,9666,9578,9004,8950,2632,2790,4709,4322,6876,6514
DATA 3714,674,2283,6900,7947,1037,8492,2052,4922,5465,5756,667,2828,5891
DATA 6114,2298,3691,1274,5987,4687,1929,9740,3775,6147,8142,6957,8568,3469
DATA 506,2428,8545,8305,8585,7962,169,7519,6931,5018,1763,5446,8288,135
DATA 7572,8558,8775,183,890,5485,9859,1652,7351,7861,4499,684,1992,9983
DATA 7260,3081,6155,7722,786,6002,2847,9677,3441,5566,1632,6041,5483,7083
DATA 6669,3127,3604,7132,3967,4045,6182,9203,6470,8493,4092,7122,8054,7121
DATA 4415,2973,39,8445,6895,8751,6290,8785,5478,3450,5541,8183,9790,9797
DATA 1986,7774,3884,7391,7761,6591,2107,1404,3417,8252,4433,8622,4946,517
DATA 6103,5013,8488,3161,8911,1535,6291,2170,3989,7429,26,678,8421,2702
DATA 47,9655,556,4001,1697,3805,1324,633,2246,619,1441,9923,4553,3090
DATA 6816,3638,6061,9028,7014,9683,4196,2462,4130,5825,1785,5078,1890,4607
DATA 8572,8194,7356,1225,7435,8209,60,8549,6390,1002,5895,6032,9984,3269
DATA 5659,1702,6164,1246,528,8979,7217,9785,9355,2524,5881,7280,5118,9832
DATA 210,4369,353,7806,3296,6918,3934,6013,6435,6241,4033,850,6844,2016
DATA 4600,7341,3495,5884,5219,7774,7193,6190,6671,8908,3472,6824,7059,1957
DATA 9401,5660,5829,2077,7912,527,5538,6583,5718,3209,3708,3594,3434,4428
DATA 9614,5339,8996,5278,3346,2845,7952,3088,6985,1214,6740,2175,255,7219
DATA 7537,2463,5467,3433,5771,1421,9124,5608,3895,7314,14,2523,7517,4210
DATA 6141,27,2473,1730,5348,3487,3939,5001,6944,5361,1188,2782,4226,7120
DATA 4064,4234,193,7234,9784,7300,1326,9438,1161,4167,6769,8007,9816,1775
DATA 2753,9241,530,7843,4602,901,5248,5386,1183,3792,7919,1180,9116,2235
DATA 3687,6154,6620,2626,8574,8181,9306,1809,8240,218,2788,9488,6897,9283
DATA 9436,1389,9992,4236,9134,2388,6744,2815,6363,1336,1116,918,8474,1785
DATA 2345,9587,2487,5347,8595,7669,250,6895,9842,612,4323,3330,8585,8376
DATA 9412,128,9463,7935,6705,2396,1395,8304,945,9641,8309,8610,2606,5985
DATA 7086,2127,9986,29,3776,1782,8587,1107,1711,5076,7602,1124,7593,8901
DATA 5876,3715,4160,7220,2167,4937,501,7069,7060,2205,3650,869,6377,714
DATA 7529,5497,8416,9031,7825,1099,9887,8116,3929,5100,7857,454,1489,9402
DATA 7574,8536,1709,1210,8505,4413,5957,473,3421,4523,6801,9413,7893,6522
DATA 9042,2099,28,7344,6861,4524,2789,4189,5657,8196,3752,2674,9679,2662
DATA 9640,8862,9043,4960,5468,4392,2226,6475,657,6405,2630,140,6954,6527
DATA 321,3479,5502,5586,2513,5444,2903,3309,8923,7520,8620,4705,560,2067
DATA 8561,7355,3056,3366,2188,6336,8141,9339,2990,5979,9338,4418,4683,202
DATA 485,6509,7949,5621,8164,3556,5090,4165,1658,7638,2413,4411,6487,7098
DATA 2718,3355,170,9638,2704,2850,1246,1895,2656,7409,5207,3415,8255,2617
DATA 3398,5540,6842,5845,3485,8147,2999,3507,2598,9714,767,1561,6728,8695
DATA 2375,8485,2482,6648,5793,2449,9778,6119,5972,6874,6590,8710,7109,1148
DATA 9322,1339,5783,5658,4911,1125,7300,2911,3251,1905,98,8920,1042,7810
DATA 5550,1605,635,1908,3013,5401,9990,346,2463,3825,2333,4999,9565,4180
DATA 6590,58,516,1149,2224,547,6500,8484,4539,3236,127,504,9058,2912
DATA 8650,7625,6073,9477,1362,2659,8941,3853,956,7054,2256,3145,1253,8854
DATA 8439,8049,6092,6546,3899,7960,6751,5542,8305,1756,7739,6509,3102,4719
DATA 3299,7258,7840,4581,9466,2420,5424,2131,9029,7618,9871,4388,9238,7375
DATA 2674,782,4592,8440,6356,5322,9562,2787,6328,226,8598,6987,4615,8963
DATA 3240,7179,1576,9201,8701,1345,4185,8604,4760,3130,1986,8968,8290,3909
DATA 4301,6651,7305,2325,4798,9773,8817,3014,2002,5152,5397,8744,6845,442
DATA 7746,2676,860,9449,3148,9969,1091,1090,2124,461,337,4957,8153,6616
DATA 3802,8967,7785,3487,5764,7062,1004,9894,2339,7418,4173,2542,8948,4153
DATA 420,7294,3574,7976,4787,4329,9401,3773,4013,6387,2936,5574,3262,1837
DATA 6198,1894,4675,6768,4076,6888,5061,2841,452,5321,2588,109,9162,1798
DATA 4807,6519,8425,7222,2862,8341,9795,7980,9223,8200,5259,5776,8794,9972
DATA 8555,8625,5718,2235,9324,5952,760,4508,1166,3271,6572,2990,7209,4412
DATA 720,5020,9289,1771,8774,3974,9318,7537,2361,8824,3945,1386,9462,5076
DATA 6105,2582,6855,6294,9548,6994,7000,7947,4931,1951,4247,7788,8585,4438
DATA 7679,9484,7540,597,465,8714,6900,6981,8038,3462,8168,6556,9960,2711
DATA 9614,4903,2816,273,2273,4595,3966,2954,7672,8214,8524,4797,5887,2987
DATA 4384,1594,5005,2493,2647,2406,5603,3421,3298,7310,6328,7851,8464,3076
DATA 9174,4019,8110,1002,5554,1029,5504,3636,6748,5499,2304,9585,4840,600
DATA 5610,8141,2719,444,1824,7939,4253,5319,4649,6368,8213,5709,7098,8955
DATA 2065,5587,9829,435,4190,7947,668,1726,5668,8035,2653,9544,5174,2262
DATA 451,7850,3120,3245,7486,2865,3609,3982,8626,5871,5311,6584,5764,515
DATA 4843,3570,6152,3828,8757,2175,5812,2690,2727,4643,2895,9947,9017,9981
DATA 8293,6910,5850,5130,3396,1446,4738,6028,7285,3387,4396,1545,8256,1468
DATA 2319,5733,6978,8521,7618,6391,1151,4140,1209,381,4000,6527,1950,8691
DATA 1459,7759,9820,6704,5365,9172,9733,7634,2535,6097,2076,9606,2047,3655
DATA 8574,9356,5586,7838,4573,7996,8181,8595,1324,6843,9192,4133,4380,3754
DATA 5885,8159,6683,2955,4436,4286,7450,3822,5711,4304,435,6583,5668,9562
DATA 7671,5419,2718,7150,7295,1922,6894,5122,6524,4382,8171,3474,3400,876
DATA 3783,80,3385,6624,6868,3333,9406,8582,1308,5683,6438,2735,84,4809
DATA 4223,2070,7005,1630,4218,5687,4151,6883,9366,2030,9863,493,7781,1681
DATA 4653,427,3944,7721,4832,285,3498,4103,6252,7324,254,5000,2961,5139
DATA 6468,626,8139,7722,22,7466,7159,4120,4566,3412,5103,5398,1251,747
DATA 3586,8151,3109,2465,4235,1254,5706,9894,8658,5085,147,2082,7251,4943
DATA 7018,9916,1689,2872,2385,455,8440,4610,9413,9426,3151,884,1724,2377
DATA 8240,4768,7069,7422,8557,9333,2427,5087,2435,2289,4098,3188,7983,6845
DATA 8915,7235,6981,528,5147,9321,1193,6132,4186,968,8457,1570,6633,7885
DATA 8405,7803,8852,7145,133,6597,8597,9687,6682,2303,813,3684,3675,4392
DATA 7183,6680,1939,9965,5546,7017,6468,7949,7745,7487,6577,9198,7027,6688
DATA 4565,9228,8576,6061,2757,2794,9271,3063,1259,2025,5267,3455,1269,2358
DATA 8499,8169,1284,2960,5684,2726,6058,875,5935,9664,642,611,5572,6965
DATA 4357,3385,1220,7924,2046,2749,4791,450,2443,5799,6455,6256,6001,1716
DATA 4168,2916,7032,1825,876,4240,7497,7917,2977,6964,2286,8033,6136,4194
DATA 8338,1444,7045,8590,2448,7035,2230,763,5089,1820,7484,832,111,8796
DATA 4038,3634,2650,5870,45,546,96,65,8489,3376,3456,3721,5097,8316
DATA 8968,1933,2359,405,2301,2915,8237,1477,178,5523,683,7073,6787,665
DATA 1517,266,4810,5792,5805,2885,3401,4219,5298,7100,7985,3466,7039,2835
DATA 9206,9358,735,8981,862,5098,969,8876,9178,7019,2878,3021,8274,1256
DATA 2358,4505,9142,8037,4408,5095,2000,2827,5701,2480,4356,6022,9984,1616
DATA 9637,5450,7386,5659,3705,8349,1235,4442,9126,2082,8488,970,9526,5283
DATA 2353,8900,8878,3669,8192,6489,3062,7222,6331,4941,3544,7968,7827,1670
DATA 5525,74,1820,1411,5392,6472,5543,670,4810,8744,602,3462,1330,9470
DATA 1598,8826,7807,8765,5703,3074,5533,9232,4277,2240,8357,6036,119,2708
DATA 7711,1320,6440,488,823,4697,6172,2085,6995,4015,2681,2471,9289,3126
DATA 5494,8086,1444,5880,7129,5372,2389,8055,9626,7781,3186,1446,1863,6749
DATA 3750,6825,1257,4582,9180,5014,5951,9748,8069,7747,6068,7518,7600,2594
DATA 5127,1446,2814,8605,5226,3640,9850,1961,2075,4310,5544,3275,8477,3544
DATA 8196,840,7352,794,6864,6470,7888,30,9032,3213,931,1048,8991,6612
DATA 2190,9873,1768,3755,4364,3761,9963,6829,1770,8730,3334,390,3582,127
DATA 3455,4076,4268,9164,8324,4976,2309,929,4232,6378,814,1798,4758,2113
DATA 6103,6761,9224,8207,2877,9592,5462,6077,7031,1364,4223,3971,9752,5246
DATA 5086,5879,8953,8089,6207,9640,6662,1726,2740,8448,3449,9492,1293,2493
DATA 3488,5916,251,9940,6351,48,8306,8982,4123,5400,6055,5169,4925,1981
DATA 7983,739,6459,8357,4707,5171,5650,4246,7793,8684,2986,6594,2017,2883
DATA 2647,4604,2391,5285,2024,1696,5813,6952,6712,4845,9684,4919,9580,4302
DATA 2325,3672,4997,9124,2543,2370,1829,6514,8200,7038,1287,5428,6113,9453
DATA 8216,7414,8138,6934,6931,164,776,9759,5189,1726,8152,5437,2381,5876
DATA 711,1527,556,1586,4456,1256,9354,2083,8105,8633,8458,1449,7976,2285
DATA 3636,9245,2973,9723,4989,6115,4490,6289,8490,5852,8604,5451,4409,1882
DATA 383,9716,8706,8640,2643,3850,6012,819,4039,4625,5263,5929,3780,3831
DATA 1602,8176,2854,3746,627,4090,4083,6804,3597,2905,5866,3668,4666,7132
DATA 6942,6425,3764,1316,2025,6140,1196,9421,648,6461,2570,3850,4071,7512
DATA 5143,1517,7584,6793,9165,4989,8054,6290,344,9136,9061,7535,1987,6274
DATA 8466,8818,7957,5249,5756,1279,9990,2464,9004,3092,5511,5285,3794,3466
DATA 4506,812,8954,685,6570,5480,6440,884,1716,3464,5209,6815,1027,4340
DATA 1433,8286,5764,2993,9897,8523,6018,7225,3924,3142,2483,1043,3655,984
DATA 7473,4074,5060,8501,3752,114,4499,1938,2280,235,6177,3997,2475,8458
DATA 2353,4249,1074,435,8627,4961,8188,8113,9172,6594,1661,5869,9226,9674
DATA 3291,6050,4715,2263,3057,4417,1330,4736,9896,8450,7920,6099,160,3978
DATA 1530,8558,7320,8110,3928,9554,9038,8939,1982,2992,178,4971,6708,3874
DATA 2852,9768,8352,3067,7119,9764,7329,1405,8392,5721,3392,4866,185,795
DATA 7840,5029,3256,688,6139,1525,4784,3841,783,5722,3630,2153,6739,7343
DATA 303,5180,4332,8238,2716,3291,6895,41,1330,7747,3051,4916,9769,8176
DATA 5944,1125,9517,405,4287,7616,9770,124,2554,4383,6059,349,173,7775
DATA 3715,3155,2049,2511,4794,8637,5272,4592,9532,6588,9356,1852,5942,8839
DATA 9836,1338,3631,2752,7587,5271,453,8815,8694,9784,3062,7826,2227,3154
DATA 4990,5617,5758,2769,8315,5805,966,2523,7538,3519,4169,4874,6739,5590
DATA 9143,4283,3630,5163,2051,1238,6577,1201,831,8599,3203,5845,3903,4485
DATA 1644,5118,5519,8388,8080,911,7606,9788,6610,4747,451,936,76,6284
DATA 7064,8051,2927,2010,8569,7651,9724,2123,464,7218,5366,6054,2089,1934
DATA 5639,9593,4160,1702,9187,9101,1696,5166,4488,772,2190,9950,7933,5404
DATA 1374,842,1604,1674,1409,126,1845,3341,8853,6805,2213,8404,2251,3912
DATA 6908,629,1683,5628,3287,6441,5118,8451,4519,2663,8930,3102,6029,3028
DATA 2390,6404,1776,3982,8508,4859,8978,2708,6058,4125,2399,2860,121,1122
DATA 1738,5974,997,7981,8275,9018,3839,9569,9328,1050,3838,8780,1623,4466
DATA 4301,6339,7175,8785,7490,4327,7784,7465,534,5142,6709,690,1276,115
DATA 8649,9622,1404,4511,1599,81,6688,8124,6690,6099,6693,3177,4602,6363
DATA 8782,3766,9636,8958,3794,3554,5054,2434,3185,933,5764,3622,38,3372
DATA 6963,5202,8729,5186,9813,8465,642,5415,7752,9250,5723,5064,9536,7531
DATA 2283,5397,7604,3605,9826,1517,2858,6369,2300,7952,9448,1642,1572,5460
DATA 5673,1001,3513,765,9563,4112,1495,3465,267,9,4677,6806,8810,5296
DATA 901,1561,4351,9751,6555,4711,4485,2281,8246,7174,737,2707,3616,7274
DATA 2799,7360,1155,9184,7628,8931,1358,8066,1989,3564,4053,6106,9537,652
DATA 9262,6187,6041,3309,1430,2402,8827,9982,9362,9131,9051,178,6726,2910
DATA 7883,9763,447,3786,204,3822,6846,5409,1902,7524,7879,5553,9375,7985
DATA 2291,1299,2313,2576,9053,5594,3369,1661,2925,4407,817,6224,4463,6200
DATA 2768,3364,9357,7926,4060,5110,4402,4291,9412,8540,9961,9470,8921,7673
DATA 1288,3034,4514,86,3502,4260,8434,3745,7614,1592,7375,2006,7404,6429
DATA 8326,7260,9521,2991,4753,6189,1637,8457,4189,2100,5998,119,837,2310
DATA 8225,8735,9273,1051,3702,9848,7852,856,6387,7240,2902,7901,7414,5278
DATA 7296,9280,3297,9348,9517,2655,6109,6108,1785,1283,468,7769,8346,9866
DATA 4657,7134,7540,9205,5767,2602,3697,112,1146,4867,7496,9564,1053,9520
DATA 5870,4572,9828,2283,5025,1701,5434,6081,2710,2754,9703,1691,8293,9558
DATA 4158,6158,1766,3329,8709,5730,5245,6586,3122,2500,3090,8092,3549,6492
DATA 9206,3766,9010,7412,2651,9061,5140,2765,5112,764,5055,1572,6379,8683
DATA 9688,5404,6369,208,2425,952,4837,3181,5389,833,2329,5089,7233,1889
DATA 8505,9010,4749,2657,6397,9293,3179,4260,3710,2458,2536,1415,4764,1250
DATA 9805,2795,9156,2352,9352,2449,5757,706,6388,6509,3104,5901,838,1899
DATA 9825,8634,1448,6261,1155,7663,2489,826,144,263,7883,438,4673,1631
DATA 111,7456,3841,1218,3736,8760,9830,6448,5892,7554,3857,6807,8578,4221
DATA 7270,3751,103,2917,1425,4424,5521,3141,2402,9632,8417,7995,9174,9069
DATA 8854,3351,6319,9229,4866,4642,4861,2010,7305,506,7344,4443,411,4982
DATA 5727,2550,2929,2509,3193,4770,7138,2405,3474,2938,5615,2082,3770,1278
DATA 8089,692,9874,6391,3231,7438,4585,3687,2709,1258,3001,8249,7377,1101
DATA 799,588,7915,8524,4081,252,4779,6825,1888,2781,4804,3415,4975,7940
DATA 4295,4669,6937,9742,968,4974,6286,1186,9555,4168,564,9213,8452,120
DATA 6090,7839,7222,5647,9450,9914,7321,1507,9287,513,878,9655,9523,7385
DATA 4866,3527,7586,6477,536,4521,3739,2949,420,6432,108,695,7778,2040
DATA 503,5805,5814,8574,4616,1966,6516,1279,2712,8239,1451,6782,9374,2212
DATA 9376,514,7429,3969,7998,4856,5624,8873,9716,7285,6165,9603,3720,186
DATA 693,438,9255,6583,5807,9235,7423,8500,1722,5096,1342,7157,153,2158
DATA 7029,6739,24,2513,9835,5946,2086,3698,3778,4045,6060,8735,3622,641
DATA 6364,9191,2049,888,5053,4219,6749,363,3039,1062,4809,6309,3207,4976
DATA 4189,4479,1499,9044,4691,3295,4573,6857,3220,9532,5135,3519,692,2270
DATA 8521,2954,447,4298,6639,1980,492,2721,7853,4121,4430,2970,3916,8621
DATA 8410,2940,7527,2636,3952,6471,6629,7058,8976,7897,4017,8970,1902,1881
DATA 3371,6160,6129,5238,5291,1696,4786,0,9448,9017,8042,9400,1418,509
DATA 7870,1032,5311,5034,7572,3867,5795,2386,5932,8389,5584,5139,8330,1528
DATA 7009,858,9658,631,8745,131,6390,3187,1311,8413,7647,1519,7410,2134
DATA 7601,4172,5725,2030,4052,8201,9254,9198,545,9091,1779,1818,1839,7522
DATA 8557,3008,5107,4698,9854,2806,1676,456,8367,9721,6677,885,4177,9839
DATA 6440,4660,3295,3941,5971,9813,8411,5610,1364,5168,2933,5796,4485,3151
DATA 1902,1804,9785,3193,5899,1165,5563,7449,6517,3383,4542,3057,4500,5005
DATA 1100,7634,4141,5987,4982,7258,32,7830,3867,8631,4769,6458,9598,9650
DATA 8689,5291,5457,5110,5246,6498,4291,6749,8115,893,9863,9356,8618,9438
DATA 6256,7169,4566,1835,2676,7265,4112,150,3497,9181,706,7976,5903,2467
DATA 7744,8066,9955,6397,4021,3926,8429,8567,3549,3336,6283,1576,5869,4257
DATA 2080,9524,5432,6103,6221,8558,1141,1844,3326,8142,9656,8905,8612,2327
DATA 8556,9333,607,2690,7942,2204,5042,7190,1585,3727,7278,1651,1203,3035
DATA 3095,3085,9979,4103,191,6591,3892,6788,5245,20,1958,2450,3881,3159
DATA 8994,2109,3367,625,6983,7637,407,204,3624,8922,8869,841,9189,2500
DATA 4786,7019,5257,9591,8464,8723,1423,4056,6077,8722,8586,3188,5544,1383
DATA 9906,6848,4075,9740,3005,2901,7200,36,9538,9405,1640,5440,706,6558
DATA 6858,3193,9805,3832,2640,1866,5419,286,2537,7967,1330,8526,5530,3618
DATA 1761,5276,740,9505,3032,4019,2550,9844,5221,7699,5962,8551,9931,1937
DATA 4549,8364,2761,1725,5831,7121,1555,7092,1435,7911,4049,5676,1865,2323
DATA 988,2701,8245,8507,3316,1308,5861,8279,4537,8719,6853,9958,1833,6206
DATA 1908,6194,2028,3310,3284,8472,1018,9318,4021,2533,7717,7431,672,1411
DATA 6166,9606,9405,5330,1842,2552,7826,154,809,7820,7341,8624,2780,1493
DATA 3438,1102,1687,1403,3697,5020,9851,2388,5900,4792,4362,2518,1065,6363
DATA 6731,5780,8757,3148,9445,9198,4523,2558,5491,4830,1780,4848,9452,9632
DATA 3022,8495,1275,8658,7665,8824,6286,9553,6397,9113,7579,8812,4358,5880
DATA 9335,2780,8006,2582,2187,8852,3005,8439,4217,4857,2987,1609,3694,7068
DATA 1522,8415,2119,9842,2149,2875,8691,2322,3801,3209,9788,203,1482,4592
DATA 9547,3007,4527,9827,138,9845,7294,2189,2834,9140,9633,7133,3468,266
DATA 6974,2115,8362,7581,2374,6211,9332,9831,5375,3779,8857,367,5017,8868
DATA 9011,6176,6830,9604,246,6175,6180,4255,8620,1736,2787,3214,2577,4920
DATA 3771,3607,2842,2393,5068,5740,1565,5465,3562,3120,9275,9260,4762,254
DATA 756,6458,3394,4947,3424,3581,6729,4329,4322,305,2999,6314,4296,4753
DATA 9745,721,478,249,9446,6771,638,1486,2257,6179,5527,595,8219,3562
DATA 7787,6074,3772,8378,8526,45,9915,5120,5155,1806,1870,977,6578,8161
DATA 2569,2688,4331,3481,4839,6802,755,4962,9599,67,7812,1073,9936,9158
DATA 2632,3630,3388,1485,8362,6496,7279,1261,1464,6353,4474,7593,8988,3520
DATA 9351,3790,1977,3296,6384,9591,3547,786,6142,583,2780,4681,6074,1467
DATA 7977,7964,5908,2436,5415,6008,12,369,2153,5032,1562,9040,4022,6394
DATA 5866,5107,2364,4675,2678,9041,5631,37,9842,2771,4425,7812,3136,8219
DATA 1084,804,9622,3474,7400,2253,4380,5800,6571,9950,2944,3225,7964,4469
DATA 4302,8891,5807,6957,1797,4929,5379,4503,1760,5036,2815,3495,2250,7503
DATA 7099,3989,6709,2898,5353,514,9899,3123,5007,7310,5965,1072,8952,8460
DATA 943,2598,2262,5874,4593,5016,1584,616,8874,8860,785,5516,2916,2109
DATA 8956,9562,6818,8596,9362,7023,9153,4838,431,6771,5470,1982,2378,9791
DATA 7684,2101,5563,5318,6672,559,9165,8598,2929,8646,1274,5722,2617,3233
DATA 3992,3511,8867,2628,9640,4914,667,390,6662,2907,4170,1289,6314,8322
DATA 3803,6146,3749,9630,2964,4771,9566,5089,6705,8715,450,272,1216,8050
DATA 9952,6411,7446,8909,3064,7561,8745,991,607,7004,4817,6755,2102,5909
DATA 6865,6531,8160,9691,1274,6245,6015,46,1637,6996,4283,3120,1519,8202
DATA 5548,6804,2760,8523,7855,2599,6692,1284,8723,27,8086,3626,7754,4069
DATA 4200,1095,6443,8584,3752,1879,6278,1185,3165,7438,8724,7532,9942,8720
DATA 3188,5535,5495,9688,1549,2392,2280,2393,370,9982,2588,282,4347,6544
DATA 8830,8995,7135,5125,7654,6340,8103,1765,2747,5673,6137,8889,3664,9418
DATA 4084,1873,526,1921,9910,9243,6924,3373,3198,9507,5895,9018,8041,39
DATA 6276,361,5970,6033,9327,7591,4960,9971,7921,4958,3153,4566,3177,3291
DATA 8360,4675,5866,6406,6955,6124,2438,605,8241,1935,8003,8985,2895,8906
DATA 1135,4791,6573,29,7805,509,2282,696,4332,1936,7594,9187,1650,8942
DATA 5324,4385,5772,7136,8727,6191,1772,7155,4856,6630,1137,811,2123,2080
DATA 4834,5787,698,9626,6932,3132,6822,2993,6127,4244,4628,6013,5004,6583
DATA 1561,4136,9396,9821,6000,6898,2671,6647,8175,6870,2288,4952,7962,3013
DATA 8486,610,5655,8929,7424,2571,4320,8985,3630,4493,4804,7752,9103,9617
DATA 7013,750,8911,8120,3537,6957,5622,8654,4224,6065,7416,8293,2797,5924
DATA 7228,7611,9103,8175,2758,102,3096,2516,9689,7661,9131,2583,2973,6360
DATA 1689,8911,3500,9211,6095,6948,29,5164,359,576,8695,6029,6693,4125
DATA 4958,5573,3839,8347,5311,7481,3767,8304,8626,1421,8858,3655,9451,8913
DATA 8159,4298,8115,3248,3803,6854,4989,140,1190,9936,8732,8361,9015,8696
DATA 890,2067,7762,1600,1653,9017,7708,4914,4164,1440,97,2867,7176,8729
DATA 7510,3941,8436,3713,2085,6294,3616,6702,2631,7746,8149,4044,4267,8321
DATA 1812,393,6656,5805,8385,6420,9440,7291,5263,6189,5966,2182,317,898
DATA 8891,4609,5895,8223,3778,5751,2278,8978,9246,9014,5440,5302,4811,3536
DATA 6467,7102,9955,3991,2457,5968,584,7169,1271,8272,1397,8283,4957,1682
DATA 5330,2487,9209,1796,3608,9560,8678,8128,2542,2244,516,1158,5640,1184
DATA 961,4656,2139,1950,2333,21,5540,2115,267,1831,8256,8837,3536,6337
DATA 953,9941,1311,7119,7672,3950,5185,4606,358,7031,5828,8702,8841,7357
DATA 6596,6233,4916,9805,8955,7404,1566,6498,7044,8036,959,1144,1246,6752
DATA 7292,7639,3082,8862,3088,5912,6304,1159,25,469,1496,4332,7908,9613
DATA 4052,2235,7869,5813,7872,9714,8382,168,9607,3219,5202,6471,806,920
DATA 8810,2810,7804,1538,5463,1186,1715,3623,439,8121,3326,9487,4573,1727
DATA 298,510,7685,3181,6463,3046,4976,3112,5601,6644,5001,5839,4509,8803
DATA 311,6942,2726,2971,4346,2128,8761,9022,697,7870,5144,7928,3295,6780
DATA 7168,4823,8659,3186,2654,7204,3769,6885,2583,7485,5669,5537,4949,1598
DATA 1395,8669,6655,7890,9311,8763,823,3021,5475,7391,9338,4075,1078,6865
DATA 2990,8618,9605,376,4032,6915,4782,6090,8534,3014,2898,3164,8338,3937
DATA 5611,153,4986,8679,1837,8787,451,1246,9783,8569,2019,4434,2763,176
DATA 1167,3592,4847,8125,8774,2064,4975,5682,1524,2546,598,7464,6814,1067
DATA 4463,7732,6060,2814,621,4805,8689,1526,8260,4606,1704,6667,4458,8776
DATA 2142,5104,9430,5340,2281,6503,403,2388,9930,4166,2664,7749,8655,5527
DATA 8916,116,5277,9022,515,9587,4489,6561,6673,8119,2943,3305,256,2819
DATA 7630,8981,1225,7581,5927,7456,1356,1021,7123,3769,6297,1170,7792,359
DATA 3588,9912,5845,6701,7706,2631,609,9072,5759,1011,8770,9656,9900,9504
DATA 8536,6715,5066,8399,6853,48,3131,8961,7017,8447,7073,8638,6542,8382
DATA 1242,6768,7603,5606,6322,3787,4919,3945,91,9379,8405,7940,7559,7560
DATA 455,8605,6590,9150,166,3987,7592,4604,9398,8756,8376,2678,7958,9566
DATA 7772,2893,7793,5365,4101,2265,8514,4405,7093,9268,9107,2162,4350,511
DATA 3168,6878,5932,8079,7499,1949,3187,8026,6434,6881,394,2969,6702,1030
DATA 321,4270,206,6832,7299,1769,4536,1773,3897,1521,3579,782,9789,4534
DATA 3049,3292,3920,1958,8302,1671,3552,4690,4270,256,6290,7883,9848,6692
DATA 3682,3312,1604,9820,7477,5061,4118,795,2158,6527,6839,6691,9809,9176
DATA 9759,8295,5950,6042,2786,6301,7393,5431,6122,2636,5750,2796,1536,6126
DATA 2657,1257,6825,4243,5327,3733,8350,5112,3517,2154,8962,6535,1506,1714
DATA 1175,1236,1172,657,7924,35,4774,8534,5768,7191,8519,8426,7846,4619
DATA 515,1083,6473,4195,9200,1459,7684,9889,857,614,2596,3920,7267,8432
DATA 2912,3669,7159,5155,423,8556,7476,2167,2847,8621,3116,5031,854,8992
DATA 6202,4217,3602,7000,8487,1517,2665,1125,2990,2586,6653,3517,3451,8614
DATA 1399,292,2712,2563,3044,6337,3589,7956,3869,3832,8368,693,3209,6206
DATA 5486,6834,8302,1767,4504,1862,2420,3689,2969,9345,102,5611,1250,9514
DATA 1866,4543,3951,679,3225,5305,8988,8992,5345,3219,7922,4508,7205,4273
DATA 3653,4001,1595,4474,4052,3528,9785,2608,2642,6196,2239,3126,9913,3099
DATA 5176,8379,1362,7901,5361,1918,850,8030,7945,7068,394,7949,4705,7518
DATA 9944,2479,2532,9121,3290,641,4499,4639,8634,2977,8376,5641,4990,7839
DATA 9903,8284,7935,4587,692,2189,864,4188,3087,4121,300,177,6839,722
DATA 6378,5442,4924,6974,2096,2820,8350,9650,7394,9940,2321,7446,6715,1329
DATA 8557,2021,1078,3193,1164,6667,8301,8901,5855,1827,7450,5593,4893,9164
DATA 6106,4903,2591,8438,1553,3263,8703,3856,9470,9763,9574,9164,6238,2014
DATA 9365,3174,3428,3010,6214,9936,5592,4437,678,311,4936,4415,6280,4113
DATA 8971,120,4541,4590,9735,8277,9290,9419,5680,8983,7654,4964,9823,823
DATA 7520,3000,251,7751,3844,1629,1565,729,8642,4605,8374,9534,2008,5779
DATA 4421,2781,3989,7900,3435,6549,9692,7473,306,4650,2435,9899,3680,5957
DATA 2293,1630,3562,6792,9910,8522,17,8827,7874,2153,1575,5475,4541,8276
DATA 4425,2230,7623,4171,5993,8935,7406,4071,9001,4447,1921,4417,4593,6651
DATA 8926,3146,5631,3318,2043,9717,3753,1748,875,5131,6277,7696,7482,3615
DATA 1561,6521,4016,233,3898,2047,8900,1116,1546,1095,1366,5538,3992,4159
DATA 6702,1561,7031,5193,7075,9452,6766,5981,5231,9620,6117,3048,951,4255
DATA 9928,7594,2596,4417,7284,1420,8580,6784,2104,4294,6121,6771,5628,757
DATA 7105,7246,6880,6810,3421,4569,9707,9468,6597,6148,7474,4645,9093,6264
DATA 9031,1329,7078,9355,2025,2539,7053,2495,2162,6003,1154,1277,9512,57
DATA 8474,5830,5445,2701,2271,6173,6299,4309,5366,8642,2367,6952,8614,7592
DATA 3301,5787,9772,9105,3530,513,2608,5923,3776,7327,8597,5310,7266,4387
DATA 6058,4083,1746,6205,4053,7513,861,4986,915,1327,1036,9346,9733,8512
DATA 2411,3399,5653,5175,4948,1667,2314,2133,3304,7798,7292,1483,6547,7542
DATA 8877,9860,1327,8968,9027,2611,9583,5390,9858,5577,4392,8955,3493,3744
DATA 35,5391,7626,8437,4896,2846,1650,7319,8274,326,674,3866,4699,3669
DATA 7294,5587,1861,9542,3448,2673,729,424,7198,1296,8963,6041,1799,8304
DATA 1215,9230,6871,6495,2397,6694,4053,2213,2538,7611,1943,9475,4293,5585
DATA 7709,7354,6718,1888,5179,9823,1397,471,1771,9804,9514,7712,9114,1608
DATA 977,2372,4686,8511,9157,3717,4319,4683,7377,8290,7927,3162,5704,8295
DATA 3281,4130,9176,7048,5190,180,1020,9499,9920,7808,6987,8250,7215,6846
DATA 9381,8073,4726,2045,1874,4376,2240,3546,8709,3599,5513,5439,4389,5994
DATA 2072,4139,2423,3777,3817,797,4250,101,3786,4456,1920,6830,6899,5190
DATA 626,1588,7053,8918,9684,7029,5388,8140,3058,7829,7086,5287,3013,3343
DATA 6536,7927,3002,6399,3212,7531,8374,1220,3110,6023,5997,5907,3078,6827
DATA 6389,7487,7901,9646,4458,9967,2468,674,7433,8381,3864,2455,1092,4288
DATA 757,145,7867,697,9876,3343,2942,6882,1983,5257,6899,6065,2124,3386
DATA 6058,1414,1549,8468,4056,8358,1118,891,788,3657,8543,6294,7294,4214
DATA 4323,4582,7691,1089,3690,9058,1730,6689,4430,4913,4089,5603,2924,8764
DATA 8991,2039,3233,3496,1229,9351,6592,5086,7204,9613,1147,663,2075,3706
DATA 4273,9495,1592,4892,2340,1147,9731,1352,5230,7503,5711,5632,5498,7893
DATA 6482,1500,4481,9033,3302,1146,215,3993,3459,8227,4505,6919,773,4704
DATA 8993,2737,936,1943,2558,3523,305,9062,4894,5805,9242,3976,3628,5480
DATA 3580,5115,4789,9574,316,4292,9007,6576,6138,3673,8252,9547,9859,2333
DATA 491,8737,2360,361,2070,2917,141,980,202,1154,1068,3651,376,9245
DATA 3410,3644,6041,7526,1760,6013,417,9275,5939,4483,2760,1436,1464,8188
DATA 3938,1864,2693,1741,8659,9840,2217,6599,4191,9039,2621,4208,7916,4697
DATA 9173,3869,8576,9184,4576,818,8531,2707,9333,2478,6901,8348,3859,3356
DATA 5903,3185,899,1543,5267,9675,9379,2304,2028,4060,3254,6712,5582,970
DATA 1459,5802,321,5991,7570,3204,697,373,242,1741,6070,4618,8037,1946
DATA 5168,175,4738,2973,2511,930,3720,8864,1643,8748,2498,5656,2518,9758
DATA 1035,7277,2871,608,9896,717,5937,6408,6860,3428,9343,4591,3059,8438
DATA 2532,1391,2264,5134,2552,169,9396,6181,558,3306,6858,3566,3875,1879
DATA 9780,9214,959,9832,3782,8150,9095,1883,1332,4687,7197,6849,5306,4594
DATA 8528,653,841