tommyod/efficient-apriori

An efficient Python implementation of the Apriori algorithm.

efficient-apriori's Issues

GPL-3.0 license classifier?

Hi — I noticed the license of this project is inconsistently identified as both MIT and GPLv3 in your setup.py file. Since your LICENSE file clearly contains the MIT license text, I would assume that to be the actual license, but can you please clarify that?

Why not add Rule Power Factor (RPF) as one more property to Rule?

According to this https://en.wikipedia.org/wiki/Association_rule_learning#Useful_Concepts it would be very reasonable to add RPF as method to Rule instance. Moreover it is not computationally hard and provides good insights on algorithm results.

I would be glad to contribute with PR.

Using iterator or generator to provide transactions

I use a generator to pass the transactions.
This works just fine if it actually returns any items.
However, if the generator or iterator is "empty", the application will crash:

File "...\.venv\lib\site-packages\efficient_apriori\itemsets.py", line 36, in __init__
    self._transactions = i + 1
UnboundLocalError: local variable 'i' referenced before assignment

A check for empty transactions is already done here but it does not work with generators or iterators:

Efficient-Apriori/efficient_apriori/itemsets.py

Line 274 in 96e8917

if not transactions:

My suggestion:
Initialize i in TransactionManager.__init__ as follows

    def __init__(self, transactions: typing.Iterable[typing.Iterable[typing.Hashable]]):

        # A lookup that returns indices of transactions for each item
        self._indices_by_item = collections.defaultdict(set)

        # Populate
        i = -1 # NEW
        for i, transaction in enumerate(transactions):
            for item in transaction:
                self._indices_by_item[item].add(i)

        # Total number of transactions
        self._transactions = i + 1

and add (or move the) check after instantiating the class like this:

def itemsets_from_transactions(...
    ...
    # Store in transaction manager
    manager = TransactionManager(transactions)

    # NEW: moved check below manager init and replaced the check by using no. of transactions
    if len(manager) < 1:
        return dict(), 0  # large_itemsets, num_transactions
    ...

I understand that the expected input is a list, set or tuple but wrt. duck-typing and the (hopefully) little effort required to fix, maybe one can add it ;)

Thanks for considering and thanks as well for providing the library. 👍

weighted Association rule mining

Hello Tommy,

I am a newbie who just started writing code. I downloaded your code and made some small changes to implement weighted ARM for manufacturing data, I wonder if you are interested and can give me some suggestions to optimize the code?

Best regards
Yuqiang

data generator sample not working

Any help about using the data generator as mentioned in the examples?

Here is what I am trying

`from efficient_apriori import apriori

def data_generator(filename):
"""
Data generator, needs to return a generator to be called several times.
"""
def data_gen():
with open(filename) as file:
for line in file:
yield tuple(k.strip() for k in line.split(','))

return data_gen

transactions = data_generator('data.csv')

itemsets, rules = apriori(transactions, min_support=0.2, min_confidence=1)

rules_rhs = filter(lambda rule: len(rule.lhs) == 2 and len(rule.rhs) == 1, rules)
for rule in sorted(rules_rhs, key=lambda rule: rule.lift):
print(rule) # Prints the rule and its confidence, support, lift, ...
`

And the csv file is downloaded from

https://drive.google.com/file/d/1y5DYn0dGoSbC22xowBq2d4po6h1JxcTQ/view?usp=sharing

Seeing #30, tuning confidence and min support for max itemsets?

Hi!

Thanks for an amazing job on this. I was trying to test it carrying out an analysis with, maybe a quite high number of transactions, 1000, and they with several items:

[(1868,  2355,  2849,  1373,  1431,  2545,  2147,  981,  1043,  3516,  2666,  3127,  3583,  594,  425,  1284,  1335,  2220,  2113,  3034,  3250,  3502,  3256,  2831,  2702), (788, 2503, 33, 2324, 1830, 1454, 3277), (2133, 3216, 1612, 501), (2118, 2545), (2413,), (2617, 1910, 886, 3064, 2517, 556, 2653, 171), (1404, 876, 1794, 1592), (3539, 1875, 2118, 2849, 2545), (2831, 1327), (1207,), (3407, 2568, 2091, 321, 1873, 2831, 1543), (876, 835, 799, 2940, 1736, 360, 2081), (2163, 48, 1910), (981, 1497, 1300, 3034, 694, 227, 2355, 2666, 34, 3164, 2922), (2723, 2691, 3228, 2503, 939, 1094), (280,  902,  730,  2075,  3053,  181,  399,  578,  983,  1384,  1328,  1837,  3589,  1743,  2500,  32,  151,  2044,  1468,  3443,  1472,  2450,  1297,  3084,  3550,  167,  1423), (44, 2268, 254, 1754, 2783), (115, 1300, 1245, 1576, 1346, 935, 3236), (115, 1300, 1245, 1576, 1346, 935, 3236), (3251,), (352, 2423, 682, 1462, 3181, 3196, 3378, 3103, 1336), (243, 1043), (243, 1043), (243,), (243,), (243,), (243, 981, 3116), (981, 3116, 545, 1029, 2217, 3268, 2287, 3440, 359, 935), (981, 3116, 545, 1029, 2217, 3268, 2287, 3440, 359, 935), (981, 3116, 545, 1029, 2217, 3268, 2287, 3440, 359, 935), (732, 3200, 1441, 2493), (1164, 1517, 317, 1829, 2254, 1319, 3200, 1707, 3233, 449), (1357, 1910, 1139, 2673, 1750, 542), (1873, 1536, 321), (1975, 2783, 3086, 3017), (1163,  157,  694,  458,  2985,  50,  2848,  1656,  1947,  1685,  2247,  53,  2017,  1006,  1423,  2348,  1938,  2123), (2756, 3379), (1127, 1489, 768, 2503), (2231, 3325, 853, 2338), (1472, 902, 1536, 3131), (575,  1677,  2840,  2131,  1010,  2304,  2464,  3387,  930,  3466,  3149,  357,  3427,  2377,  274,  867,  76,  3369,  1474), (1054, 2268, 2783, 1522, 55), (609,  1313,  2593,  1028,  2940,  3268,  3455,  3274,  180,  1974,  2479,  931,  404,  815,  694,  1583,  1241,  3378,  2633,  714,  2404), (28, 991, 2338), (3539, 1478, 2849, 2545, 2146), (224,  968,  785,  1032,  2305,  672,  470,  2203,  2480,  2666,  2557,  1450,  1327,  3418,  252,  1168,  593,  3181,  949,  599,  3501,  2880,  545,  2817,  2818,  3196,  3149,  2292,  274,  2249,  1594,  2831,  3387,  3045), (3489, 1390, 2268), (1161,  1435,  1095,  184,  2981,  145,  1030,  3357,  1889,  1249,  2503,  2487,  714,  3501,  954), (1362,  1967,  286,  1493,  3456,  794,  3401,  233,  2022,  924,  1667,  1889,  1831,  938,  2213,  877,  2098,  2798,  419,  92,  3532,  2622,  1064,  1071,  2984,  1130,  1911,  2884,  3502), (3539, 1388, 1893, 506), (2794, 2421, 2635, 1808, 2619, 2731, 2651, 398), (2967, 3345, 3368, 430, 1938), (1547, 269, 1809, 3515, 2905, 1682, 1073, 488, 2716), (3389,  1761,  2849,  2016,  1040,  2418,  2901,  2147,  2084,  930,  3237,  1679,  699,  3184,  489,  3443,  1472,  331,  1189,  1586,  1910,  110,  2293,  556,  3154,  3502), (321, 2920, 1074, 3407), (2655, 876, 1363, 3146, 1982, 1928), (2085, 2396, 3252, 1794, 496, 3388), (1977, 1292), (3583, 2152, 2342, 2958, 2355, 2849, 2516, 2669, 597), (835,), (1070, 1385), (1449, 2756, 1578), (2268, 3207, 2346, 2541, 1538), (2232, 3392, 3292, 512, 1955, 2005, 554, 527, 2336), (1818, 1043, 2841, 1790, 3265, 2088, 3507, 259, 822, 2664, 2377, 525, 2623), (2131, 859, 3086, 1910, 3254, 867, 937, 648, 606), (1164, 3292, 442, 1337, 1637, 706), (2340,  3586,  759,  3118,  519,  1010,  2203,  1033,  930,  1910,  3251,  2275,  1147,  3490,  1750), (2993,  2,  1028,  1427,  287,  3214,  3330,  292,  3567,  475,  1500,  3040,  404,  2372,  932,  1897,  876,  2098,  945,  1000,  2875,  3371,  1533,  3036,  1480,  1023,  1707,  2832), (1028, 583, 2629, 1292, 1974), (1582, 311, 3024, 3597, 2733, 831), (3390,  2593,  1028,  1364,  3209,  2136,  2306,  121,  2849,  3106,  737,  1217,  2210,  629,  999,  2804,  1519,  835,  2511,  2345,  3378,  1701,  1309,  714), (849, 1057, 710, 1520, 1175, 13, 2017, 936, 127), (1873, 1536, 1052), (1910, 3269, 2503, 2827, 648, 767), (1982, 714), (280, 1366, 1365, 81, 1324, 1616, 2893, 1089, 1062, 833), (1442, 1478, 1370, 1524, 1636), (1727, 1508, 1647, 14, 466, 60), (2938, 2976, 227, 2355, 2971, 552, 1783, 152, 2964, 180, 2836), (2038, 869, 856), (271, 2783, 1647, 12, 2672), (1694, 1262), (1095, 2352, 2022, 1889, 94, 1004, 3075, 2503, 2364, 3244, 768), (3185,), (2593,  1028,  2068,  2940,  1316,  1812,  467,  1974,  1439,  3229,  404,  2607,  3126,  2791,  2382,  1456,  1679,  1577,  535,  1631,  3082,  838,  1407,  440,  3150,  3039,  714,  1708,  3501), (3501, 315, 2461, 2831, 404, 98, 2503, 2899, 2406, 2671, 717, 1848, 1974), (417, 329, 188, 945, 3378, 50, 33, 3464, 1090, 1794, 3501, 2902, 471), (941, 1741, 2550, 2085, 944, 698, 430, 251), (1851, 600, 1102, 873, 828, 2325, 1974), (562, 1794, 3501, 3378), (738, 294, 694, 2817, 3427, 2647), (2413, 714), (2421,  2424,  771,  2940,  2874,  3229,  2337,  2309,  1829,  1685,  348,  516,  871,  262), (1914, 2557, 3268), (835, 2811, 2131, 2970, 1970, 1155, 3459, 1077, 1040, 3273, 2081), (221, 321), (2691, 2503), (1873, 2630, 2474, 3407), (1707, 287, 812), (543,  2937,  1974,  835,  1301,  928,  287,  841,  347,  524,  360,  2046,  1707,  1236,  2081,  2475), (1904, 610, 1679, 2306, 2829, 3348, 2126), (3080, 2185), (2634, 3200, 1932, 1610), (1292, 3405, 524), (3257, 1405, 876, 3205, 1083, 3292, 818, 962, 168, 3598), (1983, 2503, 1426), (2038, 2094, 1300, 66, 34, 54, 1648, 1292, 869, 468), (1164, 3568, 816, 2783, 1889, 2503, 554, 2770, 433, 1609), (404, 1982), (2203, 1298, 2630, 3407), (1028,  454,  2413,  514,  622,  1879,  1666,  1100,  2322,  3011,  1509,  1790,  2800,  3358,  1334,  206,  2232,  1304,  1014,  3252,  380,  3501), (1212, 2256, 1348, 3175, 1135, 57), (741, 1284, 356, 1686, 3551, 2293), (1300, 2659, 2743, 2404, 856, 2922), (189, 2839), (209,  1095,  1457,  1789,  670,  2258,  1128,  2709,  2241,  3304,  2503,  2827,  3537,  305,  2034,  1422), (2495, 2142), (714,), (2950, 714, 1974, 1028), (2859, 1300, 1060, 2619, 856, 2635, 2651, 2922), (509,  1600,  2131,  1969,  3561,  2771,  925,  930,  745,  357,  3348,  1113,  1790,  32,  887,  2623,  3541,  3035,  548,  2822,  3151,  3149), (1977, 321), (835, 2997), (1746, 3316), (714, 2010, 1982), (876, 1224, 2413), (2147, 486, 3378), (2399, 1164, 892, 1900), (780,  1486,  1031,  2843,  346,  2851,  3272,  1553,  2772,  2650,  2419,  1663,  470,  2265,  739,  1985,  478,  1327,  1159,  990,  27,  1511,  1161,  3473,  3350,  2099,  2569,  1172,  2445,  2107,  156,  2114,  504,  2003,  3201,  2249,  2250,  2831,  1312,  3259), (1685, 361), (2783, 2296, 491, 3127, 2672), (567, 2503, 1974, 714), (2297, 2666, 425), (2302,), (2814, 2270, 1100, 1889, 1449, 3580, 3309, 1974), (280, 1879, 902, 3583, 874, 3293, 3443, 2855, 752, 1236), (3562,), (1977, 648, 1910, 1415, 2162, 3222, 606), (1974, 755), (1740, 1440, 2319, 3086, 3222, 3104, 763, 2714, 2730, 529, 719, 2703), (2849, 2545, 2342, 1838), (2423, 3196), (2423, 3196), (311, 404, 1982, 627, 714, 873), (2268, 503, 1945, 121, 3063, 1900, 87), (876, 1962, 270, 1303, 2940, 696, 1518, 3550, 360, 714, 1144, 1292, 1239, 27), (2592,  2305,  1207,  3331,  3341,  1451,  1450,  3526,  1940,  1164,  1172,  1337,  3028,  2228,  3080,  1474,  2178,  3196,  2586,  2122,  3501,  3259), (1910, 1750, 542), (1695, 3292, 1281, 4, 1588, 148, 289, 2853, 527), (3550, 2061), (1053, 1559, 2085, 1839, 1910, 1285, 2413, 1994, 3245), (1804, 1164, 1099, 287, 2003, 350, 3595, 1707, 2670, 3028), (2413,), (426, 2522), (1694, 876, 3371, 1533, 287, 3574, 1174, 2260, 1707, 1775, 1330), (2413,), (1200,  1028,  1964,  2352,  3048,  1827,  443,  1969,  2824,  2608,  1450,  244,  248,  27), (3444,  2879,  44,  3300,  929,  3086,  1890,  1349,  672,  2503,  3065,  3382,  392,  937,  529,  648,  3156,  650), (3444,  2879,  3300,  2692,  317,  1910,  672,  1349,  390,  2503,  3382,  3065,  2545,  648,  650), (2147,  981,  1544,  2831,  3196,  594,  3378,  425,  2849,  3452,  3150,  1844,  1335,  3039,  2046,  2545,  3502), (2860, 3225), (1938, 2670, 714, 1982), (1498,  1300,  2882,  2831,  1501,  1334,  2985,  3105,  2157,  2695,  856,  3378,  34,  2404,  13,  430,  1775,  1786,  2922), (1206, 1728), (3246,), (3407, 2815, 695, 1428, 317, 1502, 2945, 321, 1400), (1746, 2998, 3316), (280,  902,  2131,  2396,  1889,  2500,  1945,  1286,  2849,  2309,  32,  2663,  3550,  2293,  1040,  3053), (2876,), (922, 1165, 1520, 13, 3179), (3299, 1941, 2565, 2396, 331, 2693, 2787, 1286, 58, 2888), (981,  1362,  3162,  2433,  157,  2917,  1300,  1245,  2001,  190,  425,  1284,  2170,  1656,  2545,  1849), (2227, 304), (1404, 2423, 3196), (958, 1889, 123, 2255), (2593, 1679, 1977, 2534, 3229, 2216, 2883, 3126, 446, 1039, 360, 1292), (280,  902,  287,  1375,  3053,  399,  3118,  1978,  1889,  1733,  1827,  3470,  1785,  3239,  2500,  32,  3028,  953,  2924,  1479,  3149,  2292,  3550,  1707,  3443), (2408, 2388, 1945, 3216, 3365), (2127, 287, 3610, 1707, 1292), (2413, 524, 3329, 1839), (714, 1446), (1449,), (499, 2203, 1977, 1857, 2040, 321), (29,  3021,  1301,  81,  2614,  1365,  1225,  3425,  1995,  1616,  2503,  1784,  1659,  1776,  3556), (451, 2774, 224, 1975, 2849, 2289, 351, 2610, 27), (1762, 1367, 421, 803, 3211, 1910, 2503, 2666, 1750, 1903), (1677,  2387,  93,  3212,  1916,  2292,  2072,  3365,  274,  2377,  1040,  2751,  1959,  3054,  1975), (2940, 3563), (780, 1839), (1889,), (2940, 2651, 714), (142,), (1161,  835,  184,  1547,  269,  3168,  2860,  366,  3572,  202,  2537,  369,  864,  2503,  1469,  2294,  3202,  557), (2413,), (2940, 45, 2010), (556, 3064, 1910), (1612, 2256, 2657, 3196, 2618, 121, 1657, 448, 470), (1292, 2081, 2385), (3292, 458, 2569, 404, 3378, 524, 409), (2413, 2886), (1907, 2447, 3235), (1798, 579, 3378, 915, 3501), (1043, 3341, 2849, 2545, 2451), (835, 3589, 3394, 1618, 2356, 243, 2922), (1028, 1790, 404, 1982, 3197, 1292), (919, 45, 926, 2657, 2940, 1115, 21, 404, 1969, 2140, 3363, 2220, 714), (280,  902,  3433,  1753,  2215,  2801,  1333,  388,  1747,  382,  2896,  2171,  1472,  181,  3582), (3292, 1114, 2940, 189, 332, 94, 947, 1049, 714), (244, 1200, 1001, 1839), (184, 1203, 2028, 2503, 3002, 88), (1460, 3048, 317, 3452, 3184), (1690, 2921), (325, 813, 1461, 597, 470), (1940, 1043, 1168, 2203, 2371, 972, 2631, 2943, 1658, 2611), (1201, 3395, 31, 3211, 1910, 1580, 1038, 2503, 3549, 2448, 1866, 1750, 1094), (3317, 1839, 1977, 2221, 3309, 1878), (2477, 2303, 287, 1358, 2985, 2973, 3509, 1832, 2383, 3276), (1964,), (2413,), (2233, 275, 1801, 789, 1277, 2503, 1253, 2008), (2413,), (714,), (2656,  102,  903,  3475,  519,  3569,  3423,  1033,  2765,  1969,  228,  1429,  2503,  1910,  3412,  3597,  917,  1750), (2165,  876,  636,  1498,  835,  1164,  287,  1933,  2861,  1337,  2196,  1707,  2769,  3273,  2081,  434), (3539, 2118, 2849, 2545, 1875), (281, 1974, 3501, 1028, 627, 714, 384, 3564, 872, 873, 40), (3196, 2540, 2819, 1256), (287, 404, 2373, 2960, 1633, 1707, 558), (1858, 3229, 1589, 1701, 1631, 506, 2522, 3348, 2264), (3200, 1481, 1610), (3292, 474, 527, 2624, 992), (1154,), (2770,), (2413,), (280, 2939), (321,), (714,), (430, 1158, 2839), (3258, 2591), (390,  1777,  622,  2085,  2430,  1831,  1742,  143,  1173,  3533,  153,  891,  770,  3192,  1068,  1070,  50,  2247,  3552,  2348,  338), (3539, 455, 1991, 712, 1893, 1133), (714,), (280, 1839, 1395, 134, 1392, 1994, 100), (3539, 1652, 1670, 3009, 207, 1875, 1794, 3501), (18, 1677, 2534, 2708, 3181, 3378, 2644, 1292, 3140), (835, 472), (1930, 2503, 1554), (1742, 3192, 655, 458, 404, 1982, 2355, 1447, 3378, 1704, 714, 3501, 2010), (905, 1452, 3392, 913), (2413,), (1164, 1028, 404, 1397, 714, 1972, 3131, 892, 482), (400, 812, 1292, 360), (116, 3099, 556, 1564, 762, 1910, 2959, 897, 75, 2448, 1596, 2653), (1461, 1292, 2633), (1512, 2686, 2872, 1790, 404, 975, 1423), (1910, 1750, 542), (2413,), (3539, 1875, 2118, 2849, 2545), (667,  1028,  2533,  1603,  1763,  725,  1257,  2849,  3460,  2314,  2545,  1776,  573,  2082,  2147,  1043,  680,  3517,  355,  3343,  2031,  1161,  588,  2039,  3589,  1790,  3359,  317,  2501,  699,  1628,  890,  832,  2754,  268,  3034,  2342,  1908,  2119,  218,  3253,  1311,  2937,  3502), (3539, 1875, 2118, 2849, 2545), (1119, 1790, 1910, 700, 1736, 3399, 631, 112, 622), (1993, 2040, 672), (2149, 2054, 2088, 2220, 1235, 1180), (1754, 2268), (3539, 1875, 2118, 2849, 2545), (1075, 1302), (2350,  509,  2134,  2940,  2411,  2849,  390,  1375,  2141,  1607,  1436,  2023,  19,  800,  681,  2603,  1045,  524,  2378,  412,  635,  1677,  996,  3419,  2037,  589,  2612,  3583,  3529,  487,  694,  317,  3184,  3297,  2751,  651,  2979,  546,  3248,  2756,  2986,  3039,  1136,  3443,  3155,  112), (2413,), (79, 1123, 1889, 2849, 554, 2899, 1472), (2131,  1028,  2940,  287,  2946,  1143,  856,  1498,  3579,  2962,  2795,  2922,  1637,  498,  435,  1300,  106,  840,  1707,  717,  847,  1805), (430, 2413, 1761, 3105), (2685,), (447, 3222, 2280), (183, 1938, 2338), (280, 902, 3501, 3378, 2987, 1794, 1472, 181), (2268, 1975, 853, 1912, 493, 1595, 168, 2338), (1480, 1685, 1049, 1632), (3392, 2556, 913, 1452, 3348), (3311,  1530,  2396,  814,  2651,  2302,  2466,  1945,  2849,  1156,  585,  3163,  1472,  3112), (184, 1440, 3378, 1794, 3501), (2409,  456,  1257,  2940,  2889,  1766,  68,  2849,  2261,  1726,  2545,  3006,  1043,  1611,  2317,  984,  858,  401,  3122,  1891,  1272,  3343,  2666,  195,  198,  870,  2491,  1507,  3589,  2739,  317,  882,  95,  3364,  3078,  1470,  1634,  1472,  1692,  1404,  957,  2688,  2513,  554,  1352,  1957,  776,  1597,  2888), (1879, 3317, 404, 1155, 524), (1427, 3341, 124), (2012,  66,  3268,  2849,  2198,  3324,  2546,  1497,  2366,  798,  3116,  2904,  931,  3471,  1160,  250,  2105,  1003,  34,  702,  497,  3540,  771,  3251,  3440,  1914,  383,  843,  2989,  554), (2529, 1345, 2068, 2958, 3049, 2454, 3265, 1193, 645, 470), (2063,  3069,  1678,  877,  924,  1100,  214,  1001,  1413,  380,  1449,  3010,  1956,  3112), (100, 3611, 2880), (2849,), (835, 924, 3056, 1130, 505, 360, 2081, 3491), (714,), (1790, 2503, 2472), (1691, 2503), (3313,  2593,  64,  1028,  2131,  2357,  1969,  3052,  390,  855,  1722,  2644,  1376,  978,  78,  573,  979,  518,  1211,  3404,  1267,  738,  1780,  2086,  583,  3573,  404,  301,  3174,  1934,  2665,  138,  1450,  1986,  2793,  753,  2562,  2864,  27,  1162,  1679,  2677,  694,  3358,  594,  2877,  1523,  2109,  1749,  3139,  2393,  435,  2175,  107,  1301,  1587,  1699,  3196,  2398,  3150,  3037,  2402,  3039,  714,  2249,  1025), (183, 2338), (1161, 1301, 788, 1985, 1830, 3277), (2940, 714), (3407, 1230, 1428, 321, 1873), (1707, 876, 287), (2453, 3151, 2937), (1185, 1058, 2306, 3378, 135, 3411, 197, 2732, 2525), (704, 2522, 3298, 3348), (2817, 1918), (1340, 3132, 1401, 1889), (386,  2995,  906,  1811,  2465,  3217,  912,  1205,  914,  2316,  1097,  1979,  2088,  1675,  3285,  3287,  2561,  89,  309,  3583,  1286,  368,  2223,  703,  1008,  2452,  3602,  2396,  1999,  1347,  3381,  1255,  3388), (2849,), (280,  902,  2408,  3317,  3208,  3319,  1258,  671,  1658,  2187,  2897,  2652,  399,  2149,  2956,  2906,  2088,  744,  2160,  3522,  807,  633,  2612,  531,  1790,  1944,  1462,  3025,  1235,  1525,  3372,  1800,  3196,  2631,  3378,  2986,  3381,  1757,  1598,  3157), (2483, 3530, 3196, 3510), (1851, 1852, 3021, 2189, 2301, 801, 817, 2664, 3286, 2276, 2899), (280, 902, 399, 2612, 2428, 1944, 3196, 23, 3378, 1235, 3039, 807), (2937, 1889, 2183, 554), (2147,  576,  2064,  1716,  1852,  3588,  1477,  1245,  487,  317,  1828,  3152,  122,  2519,  2933,  1711,  2937,  3260), (899, 2952), (1982,), (874, 3255, 2666, 2457, 321, 2522, 3348), (675, 3021, 1889), (2651,), (956,  836,  598,  1442,  1461,  2756,  1086,  821,  121,  2143,  1900,  597,  1423,  1975), (1920,), (876, 2209, 1224, 2455), (1343, 1071), (1292,), (28, 1260, 1629, 991, 2338), (1176,), (1982,), (561, 141, 691, 354, 3195, 1671, 933, 1687, 24, 3039, 2624, 1749, 1527, 3107), (2941, 1410, 1893, 1133, 1221, 1472), (3501, 845, 2940, 2088, 476, 1982, 404, 714, 607, 1638), (876, 2413, 1224), (2849, 425), (280, 3379, 2893, 1062, 2460, 1080, 833), (1778, 694, 512, 2603, 1720, 390, 2229, 3502), (2413,), (1537, 2783, 1022), (2775, 1461, 2643, 1144, 720), (2268, 2783, 1889, 2470, 806, 2458, 3017), (2277, 2123), (585, 2896), (1033, 3086, 2332, 1910, 6, 1793, 1706, 3190, 3156, 1750), (2849, 2545), (1441, 2493), (2268, 1794, 2783, 3378, 2346, 33, 491, 3127, 2672, 3501, 1223, 574), (1582, 1440, 968, 881, 380, 515, 2559, 75, 2673, 2937, 2475), (0,  3143,  2968,  1301,  3086,  67,  863,  2910,  2899,  765,  75,  718,  2673,  1750,  3261), (3539, 1875, 2118, 2849, 2545), (2720, 2268, 2269, 1282, 3495, 2783, 321, 322, 2732, 1975), (714,), (1437, 2166, 708, 637, 1396, 2861, 1984, 153, 348, 2045, 3308, 597, 26, 1929), (223, 2056, 1101, 2849, 2259, 2609, 2899, 2520, 2545, 2749, 2937, 2451), (3590, 2254, 86, 2313, 829, 1292, 1472, 100), (982, 1101, 2849, 2545, 2451), (2010,), (2850, 196, 470), (714,), (1164, 3166, 2131, 773, 3595, 1337, 350, 3526), (2775, 1461, 2643, 1144, 720), (714,), (2060, 3348, 807), (1245, 1370, 1442), (1052,  1280,  1833,  923,  3586,  1298,  223,  1794,  2203,  2554,  1536,  1388,  10,  2043,  1705,  506,  2831,  2773,  2653), (63, 720, 1910, 2007, 1649, 556, 3138, 447), (2129, 226, 1310, 1794, 3501, 1938, 1567), (2397, 1281, 470), (280,  902,  2131,  1369,  66,  2355,  2358,  2849,  2309,  3103,  1969,  977,  1660,  1818,  399,  2724,  3057,  20,  2729,  1453,  3525,  1622,  2612,  1677,  1944,  1231,  317,  3531,  425,  2222,  373,  3028,  1472,  3246,  2342,  3196,  1191,  2822,  3440,  3306,  3501,  778), (1750, 2027, 1910, 1091), (1164,), (2352,), (3405, 1889, 2028, 1144, 1958, 1292), (3539, 2118, 2849, 2545, 1875), (3539, 2118, 2849, 2545, 1875), (3311,  2849,  2259,  3460,  2076,  2545,  1875,  1815,  861,  193,  416,  2969,  1165,  1899,  2220,  2223,  263,  3539,  330,  1301,  2118,  1026,  1079), (955, 29, 863, 1089, 1784), (714, 1982), (2849, 2545, 140), (1942, 287, 2537, 2891, 886, 163, 1143, 3535, 1707, 952, 2976), (1461, 422, 1292, 1472), (3312, 2414, 3192), (1370, 1442), (1292, 1144), (1674, 1029), (920,  1919,  1100,  1477,  1014,  863,  1724,  522,  2503,  1274,  1814,  2019,  1509,  2589), (2413, 48), (1207,), (2704,  1028,  2940,  2889,  121,  7,  2309,  2074,  3003,  1432,  518,  858,  2782,  238,  3518,  240,  404,  1891,  1448,  23,  2607,  3126,  1982,  85,  199,  2484,  138,  1734,  2382,  1515,  1679,  1572,  2216,  535,  1117,  2224,  3243,  1529,  3542,  602,  3378,  2883,  1194,  2243,  3442,  714,  1708,  506,  3554,  3501), (1028, 2117, 2940, 714, 1974), (2522, 3481), (2100, 3268, 2538, 1216, 3457, 2667, 568, 35, 2922), (714,), (1952, 760), (1851, 1977, 513, 359, 274, 2092, 1528), (3307, 524, 2352), (1982,), (1164, 1337), (714,), (2137, 404, 714, 3511, 1794), (876, 1164, 3293, 3061, 1337, 769, 894), (1028, 2067, 816, 2481, 2629, 2583, 404, 1376, 1554), (280,  902,  2307,  3452,  3003,  573,  2654,  399,  2603,  2958,  1827,  2482,  2607,  807,  2963,  2382,  2612,  1944,  2499,  317,  1177,  1631,  1406,  107,  2582,  3378,  2243,  3039,  2937,  113), (1170, 3292), (651, 1436, 2776, 1164, 2235, 3317, 2940, 840, 3282, 1579, 746, 559), (783,), (1069, 1756, 2413, 628, 1794, 3501), (1668, 1398, 3328, 3503, 918), (344, 1975), (2850, 3162, 470), (2423, 1941, 2816, 1383, 1999, 3196, 2254), (2970, 1040, 707), (2780, 425, 699, 2849, 2666, 2545, 3502), (740, 1248), (811, 437, 1028, 1573, 422, 2137, 404, 2028, 1430, 714, 3511, 1541, 1621), (922, 1520, 13), (2870, 623, 2925, 1171, 1781, 1001, 1770, 321, 165, 465, 3080), (3134, 3407), (3534,), (711, 1794, 1723), (1982, 714), (1183, 1028, 583, 476, 3378, 1969, 2665, 3501, 1650, 1974), (2883, 1292), (556, 1910), (2469, 1748, 2085, 2486), (280, 2767, 860, 3026), (2429, 1033, 1910, 1353, 1750), (1498, 590, 377, 287, 2985, 1707, 479), (737, 1281, 1461, 2802, 360, 1292, 2254), (2147, 1736, 2377), (2783, 44, 2268, 3017), (1873, 1901, 3407, 82), (468, 1982), (3539, 1875, 2118, 2849, 2545), (2201, 2088, 1889, 3378, 2849, 3187, 2768, 3428, 687, 3039), (3539, 1875, 2118, 2849, 2545), (3539, 1875, 2118, 2849, 2545), (3539, 1875, 2118, 2849, 2545), (981, 577, 1144, 243, 1292, 2922), (876, 803, 567, 2503, 714), (645, 274), (1227, 2099, 2907, 1492, 2629, 2569, 2539, 3563, 2171), (1028,), (585, 142), (3144, 2131, 1889, 1933, 2309, 347, 1707, 1454, 573), (3027, 3310), (1440, 1696, 511, 1323, 48, 2503, 3411, 410, 2863, 234, 2526), (157, 1300, 1656), (1245, 1300, 1284), (1300, 2206, 3231, 2666, 74, 1278, 3162, 1197, 2922, 1805), (62, 2503, 2442), (2736, 3080, 2185), (2413, 3365), (1955, 3458), (2630, 3407), (223,  2940,  3450,  69,  607,  674,  1146,  1779,  2427,  1101,  404,  1982,  3172,  2034,  3131,  2492,  2737,  694,  3592,  101,  210,  2690,  1015,  2927,  714,  2295,  3501,  111), (3539, 1875, 2118, 2849, 2545), (930,), (470,), (1458, 3181, 3196, 1945, 516), (223,  2476,  1404,  1164,  510,  2066,  1838,  3315,  3468,  3264,  587,  706,  2746,  446,  524,  1337,  1505,  1794,  2507,  2913), (1404, 1256, 926, 1790, 3378, 2540, 3501, 2507), (1300, 2284, 2343, 2355, 856, 2777), (28, 2012), (2736, 3080, 2185, 2880), (694, 527, 317, 3105), (1561, 1400, 2871), (585, 1164, 1337), (280, 63, 1807, 1570, 726, 2972, 2767, 604), (1974, 714), (1838, 1099, 2725, 1790, 1492), (3431, 28, 3332, 3560, 991, 2338), (2503,), (3473,  3085,  1790,  3178,  2088,  191,  3378,  2586,  1351,  2298,  1290,  3417,  3501,  2254), (1354, 2560, 1987, 3373), (2165, 3370, 79, 256, 595, 3217, 1144, 2313, 1292), (1919,  901,  223,  2593,  1963,  2940,  2136,  3452,  3559,  3218,  2359,  393,  1726,  3279,  803,  404,  3174,  2488,  3524,  1831,  1326,  1162,  2329,  3136,  147,  2220,  370,  2878,  3487,  1406,  1301,  3085,  1587,  1131,  1193,  1913,  1646,  714,  1420,  3309,  2062), (3100, 2734), (3539, 2118, 2849, 2545, 1875), (26,), (2849, 2545, 1569), (2849, 1699, 1883, 1376), (3137,), (3137,), (1300, 2135, 727, 2666, 856, 2922), (3539, 2118, 2849, 2545, 1875), (2965,  835,  234,  284,  1682,  2997,  2354,  3005,  2342,  2928,  643,  2541,  3200,  2911,  2487,  1423,  1794,  1066,  3156,  1750), (63,  2843,  853,  1260,  2899,  1975,  470,  738,  402,  721,  1325,  3021,  3071,  2441,  490,  323,  2338,  545,  3604,  3196,  713,  604,  3260), (3378,), (1642, 404, 1982, 1969, 714), (2633, 360, 1292, 2111, 3330), (1315,  563,  2068,  1764,  2889,  2136,  3102,  121,  2467,  1037,  1921,  614,  2415,  1145,  229,  3400,  230,  1874,  2854,  2261,  3110,  2420,  518,  1882,  2268,  2478,  236,  2786,  3171,  3126,  988,  1110,  3015,  2212,  2327,  1679,  2678,  1574,  147,  535,  884,  97,  3185,  888,  950,  1120,  837,  3193,  2627,  2236,  2632,  1702,  3039,  2405,  1865,  3041,  2296), (325, 1195, 2019), (3086, 898), (3539, 2118, 2849, 2545, 1875), (1011, 902, 921, 280), (1108, 317, 2937, 1974), (63, 1807, 848, 851, 2438, 823, 2007, 447, 307, 1975), (3315, 404, 1982, 3378, 3183, 3501, 777), (3599, 1530, 2849, 3002, 2259, 2749, 2545, 2230, 2146, 3111), (458, 476, 404, 3378, 220, 3501), (3539, 2118, 2849, 2545, 1875), (2849,), (2268, 2783, 3478, 557, 259, 1921, 2106, 2865, 2672, 1917, 1997, 3017), (1227, 2506, 1274), (3378,), (714,), (3076, 3232, 734, 714), (1201,  3264,  1364,  1549,  2192,  3159,  121,  2849,  1604,  973,  2259,  125,  1875,  2545,  2770,  78,  1432,  2719,  1435,  3113,  185,  1269,  2203,  2784,  742,  2662,  2789,  2609,  1784,  410,  2563,  416,  1834,  886,  2047,  2446,  1295,  2451,  2056,  1301,  1953,  2180,  1539,  1020,  168,  221), (2081, 360), (2503,), (1624,  1989,  3589,  1760,  512,  458,  2849,  1017,  3002,  2006,  1078,  2545,  2935,  3132), (1130,), (1873, 1305, 1623), (1164,), (3378,), (2849, 2545, 2700), (1494,), (2551, 3602, 1012, 2374, 1862, 1155, 38, 1794, 264), (3444, 556, 299, 410), (699, 2666, 2780, 3502), (3539, 1875, 2118, 2849, 2545), (3539, 1875, 2118, 2849, 2545), (3539, 2118, 2849, 2545, 1875), (714, 2629, 1028), (956, 545, 842, 2849, 1194), (3501, 1982), (317, 1108, 2937, 1974), (3314,  3317,  2846,  2849,  2416,  794,  3512,  1975,  2201,  241,  993,  1937,  1162,  1677,  875,  878,  3353,  3588,  1394,  2683,  1996,  1590,  2243,  333,  1423), (3539, 1875, 2118, 2849, 2545), (360, 554, 2081), (3539, 1875, 2118, 2849, 2545), (3539, 1875, 2118, 2849, 2545), (585, 2150, 142), (1250, 722), (2003,), (596, 321, 1400, 396, 140), (317, 1108, 2937, 1974), (3058, 1548, 3259), (30, 2191), (3317,  1368,  2849,  911,  614,  2415,  11,  1874,  2473,  618,  1040,  2900,  620,  1882,  1380,  2478,  985,  1977,  520,  2605,  685,  2790,  2488,  2036,  1510,  1835,  1988,  3352,  1790,  694,  318,  151,  950,  321,  1951,  3433,  2880,  2926,  1412,  1702,  1536,  2990,  1915,  560,  1959), (3080, 2185), (2054, 330, 2849, 714, 607, 3131), (2118, 2545), (3539, 1875, 2118, 2849, 2545), (3539, 902, 1840, 725, 2847, 3506, 1234, 2849, 1893, 1118, 1472), (420, 3581, 2713, 404), (186, 800, 3086, 1016, 1046, 897, 3429, 3581, 573), (3581,), (2343, 3581), (3021,  2054,  2531,  2201,  1009,  456,  1070,  5,  2758,  150,  2665,  3160,  3307,  2674,  3189,  2899,  3581,  2394), (874, 3581, 3034), (3581,), (2499, 2833, 865, 3581), (2707,  8,  3160,  1376,  1149,  3406,  2954,  2726,  1386,  687,  2033,  27,  1162,  2494,  694,  2747,  2054,  274,  2518,  282,  2531,  3451,  3452,  1433,  1434,  295,  301,  2789,  2558,  1450,  993,  994,  1677,  2096,  3021,  312,  998,  317,  2569,  537,  538,  1686,  3487,  2572,  2110,  326,  3034,  2818,  1700,  1919,  1488,  573,  797,  3284,  2615,  372,  1749,  3306,  1545,  1759,  387,  1765,  390,  2899,  3114,  624,  3119,  403,  871,  3581,  2675,  1113,  3356,  2437,  423,  1791,  3369,  893,  435,  1998,  2240,  2243,  3612,  1594,  2937), (874,  1124,  2812,  1245,  694,  3396,  2818,  2707,  457,  824,  1192,  2218,  3581,  2110,  1210), (1228,  940,  1475,  3021,  2099,  2054,  435,  1976,  1641,  5,  2833,  444,  150,  2899,  3160,  675,  3581,  27), (3, 3061, 3378, 26, 714, 324, 1794, 3501, 857), (3581,), (2625, 2531, 2345, 50, 3140, 2899, 3581, 3095, 27), (1166, 2574, 3434, 2904, 2068, 2741, 1131, 2467, 2665, 2727, 3090, 464, 3581), (2630, 3407), (157, 1718, 1245, 2181, 594, 425, 1656, 2030, 1849), (1889, 2022), (1404,), (3137,), (2985, 2017), (1993, 2040, 2756), (207, 1830), (3539, 1875, 2118, 2849, 2545), (1108, 317, 2937, 1974), (648, 1910, 3104, 3222, 606), (3445,  2528,  2131,  2535,  3003,  1927,  1975,  1438,  2366,  1818,  1045,  187,  2203,  3469,  3341,  682,  1387,  358,  359,  3236,  3291,  532,  2101,  1990,  3072,  32,  1002,  425,  3296,  1949,  2574,  1301,  2245,  3442,  843,  3310,  1867,  2937,  1918), (63,  3315,  851,  121,  3453,  1975,  404,  2321,  2959,  3064,  407,  2738,  1055,  1945,  2441,  597,  3138,  1182,  3433,  2693,  1916,  2696,  896,  333,  3611,  274,  2007,  1649,  448,  447), (2217, 1854, 613), (835,), (1806,  2940,  458,  1374,  3163,  467,  1378,  1821,  2033,  1162,  29,  1841,  1838,  694,  695,  1177,  1631,  265,  2050,  1406,  1186,  46,  2983,  51,  52,  714,  2528,  1869,  724,  2068,  2533,  2542,  515,  2544,  2081,  984,  747,  522,  2324,  2792,  3022,  314,  1461,  533,  2577,  1477,  3498,  1021,  3039,  1709,  3501,  779,  113,  1487,  340,  2593,  2355,  2849,  2143,  2858,  1930,  133,  2862,  2380,  2165,  2613,  2872,  1946,  1523,  1292,  1295,  1076,  2884,  844,  607,  1082,  612,  2642,  1969,  2894,  1554,  621,  2201,  2426,  404,  1982,  3126,  3128,  2913,  3587,  435,  1587,  656,  2937), (3581,), (1449, 1395, 3450, 924), (1707, 1859, 287, 2373), (3581,), (2096,  2054,  2812,  456,  1204,  3581,  2512,  5,  1719,  883,  2833,  3303,  150,  2379,  1749,  232,  2110), (3002,), (3021, 2129), (2940, 2872, 649), (3032,  709,  858,  3265,  3340,  317,  404,  3378,  240,  2742,  3215,  551,  2194,  3039,  714,  3220,  384,  395,  1295), (1095, 1299, 2503, 2032, 1094), (2998,), (3292,), (554, 2081), (2820,), (3391,  3558,  456,  1084,  2996,  458,  469,  2899,  2151,  2369,  1442,  803,  190,  865,  584,  2379,  2431,  2164,  3021,  2918,  1991,  948,  425,  3297,  1470,  3140,  2054,  1854,  839,  2756,  3149,  3039), (1642, 1891, 1982, 714, 1974), (1403, 981, 3570, 2940, 1566, 404, 3252, 1923, 1024, 714, 1876, 335), (2413, 3002, 2403, 3317), (2144,  1095,  2065,  184,  19,  1300,  669,  2940,  1827,  1369,  1889,  2597,  3075,  2400,  2503,  3003,  3323,  687,  3080,  2702), (3447, 1885, 2581, 2849, 2749, 2545), (1885, 2581, 3051, 2849, 2852, 2545), (3181, 3196, 470, 3268), (28, 2012), (902,  3392,  1601,  1370,  2355,  1263,  350,  2475,  1974,  2201,  3120,  1669,  1889,  1164,  3293,  2103,  2616,  317,  1337,  3028,  769,  2510,  3550,  554,  664,  1916,  2937), (1403,  2497,  2882,  803,  291,  3471,  1284,  2606,  2355,  2404,  856,  243,  2124,  250), (2132,  2355,  856,  291,  15,  2777,  1043,  683,  803,  404,  2606,  3471,  243,  250,  2497,  1060,  1284,  1579,  2051,  1403,  1241,  3494,  2882,  2514,  2404,  2124), (2413,), (317, 1108, 2937, 1974), (1982, 714), (1081, 1012, 2849, 597, 2899), (264, 38, 3602), (714,), (115,  545,  1300,  1245,  1029,  1576,  1346,  2217,  3268,  2287,  3440,  359,  935,  3236), (609,  2593,  64,  1653,  2532,  2999,  458,  121,  3213,  2945,  1318,  2541,  973,  855,  1971,  178,  1208,  3055,  1731,  1819,  580,  1562,  2481,  3229,  3342,  404,  3518,  1152,  1107,  1108,  3288,  138,  3584,  2937,  3588,  2329,  1056,  692,  2439,  317,  96,  825,  2220,  1631,  3082,  1295,  2339,  1796,  835,  1185,  1072,  3036,  3378,  1589,  1701,  2988,  2459,  506,  3501,  2254), (464, 1641, 3581), (322, 916, 3017), (91, 1034, 2240, 2355, 2661, 822, 3284, 1591, 2849, 701, 1846, 1787, 1805), (1425,  2013,  1,  459,  2355,  2543,  3565,  1209,  981,  1886,  3579,  2666,  245,  754,  364,  874,  2329,  2331,  3241,  694,  1116,  886,  1688,  1007,  1530,  266,  1013,  2342,  1860,  216,  2004,  3152,  843,  2249), (119,  2640,  2463,  2069,  66,  1259,  2355,  2849,  390,  2309,  2644,  1320,  3565,  981,  1044,  186,  581,  130,  404,  3284,  3579,  2666,  3523,  3413,  687,  2489,  866,  139,  586,  3583,  1113,  694,  424,  886,  1521,  2220,  1686,  427,  1471,  2051,  3374,  772,  2000,  3086,  109,  1591,  1307,  3039,  1355,  2524), (2842,  2131,  1035,  3210,  2890,  3003,  1877,  2144,  2547,  470,  1975,  2908,  2663,  3126,  2378,  1327,  3013,  2095,  1226,  1622,  1677,  2434,  3043,  2328,  2283,  1232,  317,  540,  491,  3427,  1797,  545,  3196,  3150,  2248,  3039,  2831,  336,  2059,  3502), (2842,  2131,  2843,  2192,  1035,  2996,  3210,  2890,  854,  3003,  1877,  573,  470,  738,  803,  2908,  132,  3414,  477,  632,  1327,  3013,  1622,  2434,  2328,  1841,  1232,  487,  2283,  32,  1177,  1797,  545,  1858,  3196,  2756,  2243,  2831,  3043,  508), (1028,  1969,  16,  1776,  1266,  2480,  404,  1982,  627,  2789,  413,  1161,  3350,  2329,  145,  892,  2809,  1301,  2342,  48,  2057,  714,  716,  607,  2636), (2268, 1281, 2783, 1921, 2865, 2672), (3050,  1493,  1921,  125,  1662,  129,  2268,  1322,  2783,  522,  1831,  2865,  2672,  3528,  3020,  1281,  258,  1400,  2052,  2055,  2880,  1188,  2251), (1921,  2312,  2417,  3108,  2953,  2268,  1825,  2783,  3283,  480,  2865,  2672,  1165,  1281,  2919,  2680,  3073,  1115,  1689,  1404,  654,  3606,  114), (2268, 1281, 2783, 1921, 2865, 2672), (2268, 1992, 1384, 2642, 259, 1414, 2108, 2684, 555), (1043, 3268), (2721,  3021,  943,  1442,  1461,  2181,  803,  2756,  1370,  948,  3343,  190,  2666,  3140,  597,  2545,  1636,  3502), (3293, 131, 287, 1503, 1464, 3609, 2697, 3203), (1161, 879, 1300, 1040, 296, 2308, 2158, 3137, 2666, 3176, 3597, 2648, 27), (1568, 2883, 3176, 3137, 2831, 3029, 2590), (2534,  787,  3397,  3270,  1873,  3407,  2554,  1886,  1979,  2377,  410,  2211,  1109,  25,  1939,  1624,  1839,  2333,  701,  321,  1993,  2052,  2579,  2002,  3605,  2929,  1018,  3383,  3203), (3176, 3137), (677, 757, 2497, 2086, 2131, 927, 460, 3547, 701, 867, 1895), (63, 1187, 2638, 211, 2503, 33, 3202, 1112), (2386,  3096,  327,  1301,  1744,  1461,  1889,  109,  231,  1658,  554,  34,  1831,  2198,  597,  179,  2735,  2649), (2704,  3448,  784,  926,  1550,  3265,  2940,  458,  1968,  1142,  391,  1721,  616,  570,  1926,  607,  1496,  572,  2080,  733,  795,  1974,  1556,  919,  2781,  3279,  2553,  3226,  1563,  238,  239,  1151,  2555,  742,  1891,  1272,  3124,  404,  1105,  197,  1221,  1936,  3234,  2867,  3018,  3420,  1572,  1790,  1115,  1463,  640,  1708,  3363,  3594,  2220,  1121,  1238,  1476,  601,  1185,  1752,  3372,  45,  3600,  2580,  2239,  3378,  2241,  2244,  2762,  384,  714,  2459,  1758,  665,  3501,  3262,  2187), (1870,), (170,  2639,  2410,  2138,  2940,  2302,  2139,  1317,  1495,  616,  1606,  1208,  2080,  3223,  2200,  3463,  2422,  1879,  1822,  1977,  1732,  404,  2726,  1048,  523,  1155,  988,  2490,  869,  3350,  3351,  1838,  1233,  3181,  534,  2804,  700,  3538,  156,  1342,  1185,  2880,  1242,  546,  1012,  2581,  2821,  2239,  3378,  3437,  3498,  714,  384,  3553,  1712,  3502), (360, 835, 554, 2081), (1096, 545, 238, 3145, 317, 404, 1447, 3014, 56, 2937, 338), (1028,), (1028, 694, 3074, 404, 2078, 3186, 1388, 714, 2276, 607, 3068), (714,), (1649, 63, 2007, 2914), (1099, 3496, 2121, 1736, 1337, 3028, 1293), (1515, 1679, 3357, 2910, 1523, 2505, 3188, 1240), (2700, 1885, 2658, 2849, 2545, 2451), (63, 211, 192, 2537, 2503, 319, 3344, 163, 3277), (280,  902,  3583,  399,  1424,  2500,  32,  3126,  2400,  3550,  1375,  34,  481,  3053,  3554,  1472,  1896), (3583,  2326,  902,  280,  2980,  3319,  2658,  458,  2500,  32,  2156,  2400,  1472,  2763,  1375,  3550,  3053,  2573,  2021), (1677, 2367, 853, 1467, 493, 2338), (2724, 2890, 2333, 2849, 274), (1910, 204, 1784, 1738, 447, 648), (451, 1028, 3378, 1646, 714, 2750, 2899, 607, 892), (280,  902,  2612,  2053,  1136,  1960,  1300,  1944,  317,  3378,  1284,  2849,  3453,  390,  2404,  807,  2922), (176, 1459), (2796,  3067,  3117,  1027,  995,  1301,  986,  805,  2804,  3198,  2503,  1803,  2007,  1523,  371,  1925,  2866,  608,  483), (3280, 1965, 2860, 1301, 1127, 2503, 1776), (3473, 376, 1027, 3292, 175, 1790, 1744, 1605, 2599, 2830, 1506), (381, 2271, 3196), (381, 2271, 3196), (2278, 404, 714), (2352, 476, 513, 3379, 381, 1495, 988, 2895, 2590), (3137,), (2849, 287, 2753), (3200, 215), (2201, 2566, 3514, 3091, 2698), (2752,  1977,  3229,  862,  513,  2207,  3531,  1891,  3150,  2377,  2323,  431,  2279,  2474), (1870,), (1731,  1940,  452,  1790,  1444,  2958,  404,  742,  2355,  2254,  1019,  1657,  2899,  1020,  714,  2963,  337,  2507,  2754,  3157), (3581, 2812, 2353), (2495, 1013, 215, 2909, 1829, 1275, 3200, 619), (1028,  3505,  2940,  3219,  1553,  3162,  2771,  2899,  3338,  404,  1218,  748,  2161,  1391,  3178,  1331,  2620,  596,  432,  2807,  3031,  1404,  2173,  2117,  1350,  714), (922, 2257, 3170, 2909, 1520, 3453, 1685, 1049, 13), (780, 1790, 191, 3196, 662), (3204, 3002, 1795), (280,  1366,  2940,  2715,  516,  1973,  1975,  399,  2908,  404,  1324,  1565,  2159,  2485,  1935,  1831,  3588,  3476,  761,  3075,  36,  1063,  833,  2451,  159,  3196,  554,  2937), (280, 955, 3222, 1324, 1565, 2159, 2715, 1482, 1935, 554, 1973, 833), (1095, 1545, 2396, 3452, 2503, 3199, 794, 3156), (85, 649, 1520), (3375, 3589, 984, 971, 3517, 2641, 121, 2108, 699, 85, 489, 3460, 2749), (264, 2581, 1657, 895), (756, 2087, 2041, 287, 841, 2007, 1707), (3492,  3601,  3293,  1126,  849,  1171,  321,  656,  2920,  2089,  3182,  1074,  1275,  153,  3271,  750,  2831), (3504,  3046,  451,  849,  3271,  2089,  1275,  750,  1171,  2920,  153,  321,  500,  835,  3492,  3601,  656,  3607,  1308,  2831,  1484), (2630, 3407), (1300, 2284, 2343, 2358, 856), (3539, 1875, 2118, 3453, 2849, 425, 2545), (3539, 1875, 2118, 2849, 2545), (3539, 1875, 2118, 2849, 2446, 2545), (1884,  2940,  2088,  3341,  1105,  3378,  404,  3219,  3498,  391,  616,  714,  2145,  3463), (2466,  2849,  2598,  2541,  2015,  2545,  1776,  16,  1043,  1931,  1381,  2955,  581,  2271,  355,  3007,  3285,  1784,  2378,  3418,  811,  29,  3350,  1679,  2566,  814,  258,  886,  1121,  1693,  2236,  1301,  2396,  2823,  1129,  2120,  2346,  3608,  3438,  1255,  716,  605,  3502), (2563, 1717, 1614, 2184, 3499, 699, 2849, 2545, 796, 3502), (1974, 3252, 1049, 2937, 2636, 1975), (1880,  3208,  2783,  3321,  1333,  1036,  1626,  322,  1921,  2042,  3364,  1289,  1647,  1138,  2717,  1120,  2865,  3017), (723,  458,  2596,  926,  404,  476,  987,  1985,  1745,  255,  2742,  1295,  3142,  1694,  2576,  1303,  2454,  3378,  714,  1708,  2937), (2529, 2849, 2545, 3465, 1664), (1837, 2131, 1010, 2817, 673, 1710, 664, 1918), (3539, 967, 1234, 2849, 1893, 1221, 2545, 2349, 1296), (981, 1300, 1245, 3339, 2217, 2287, 2922, 1975), (280,  509,  2267,  2131,  1839,  1977,  1888,  658,  3531,  3184,  1194,  489,  3027,  1021,  1400,  3554,  100), (1520,), (201,  981,  1640,  1546,  1199,  1842,  404,  3480,  826,  2985,  2347,  2058,  749,  1049,  347,  1206,  2123,  1938,  2496), (518,  1796,  942,  1028,  2705,  240,  404,  3378,  1792,  1317,  2988,  3008,  988,  714,  1505,  1432,  1295), (2127, 1742, 1514, 3169, 2651, 1887, 1746, 1520, 964, 1466, 153, 607, 3131), (2127,  2794,  2421,  1514,  1742,  1808,  3169,  1887,  3131,  1746,  1520,  2619,  964,  1466,  153,  607,  2635,  2651,  2731), (2651, 94, 947, 1114), (1165, 1323, 502, 70, 2601, 1737, 244, 306), (609,  1081,  3501,  1028,  3335,  2940,  317,  404,  3576,  1465,  2899,  714,  3461,  1291,  37,  530,  607,  250), (1122, 600, 3392, 1164, 63, 2352, 684, 790, 2644, 1337, 2523, 873, 40), (1716, 2435, 2352, 404, 3440, 2349), (2413,), (280,  902,  1124,  1268,  3501,  119,  159,  1243,  2996,  1032,  66,  2849,  1472,  181,  308), (3583,  2612,  103,  435,  902,  280,  2940,  3302,  2757,  2500,  32,  1173,  1132,  3550,  2378,  1264,  3053,  3443), (1028,  2940,  1316,  1767,  458,  1087,  7,  2467,  1318,  2414,  3398,  1092,  2899,  2080,  1093,  1974,  2777,  2773,  3167,  3408,  802,  1047,  404,  1891,  627,  2607,  1388,  406,  1217,  2161,  2274,  1505,  2382,  753,  2564,  1051,  873,  90,  311,  877,  2916,  253,  365,  367,  317,  2285,  700,  3482,  3186,  1177,  2109,  1404,  600,  838,  3543,  3378,  2243,  1416,  3384,  898,  714,  169,  2834), (835, 1300, 1029, 3577, 2287, 277, 2922), (1784,), (2012,  2764,  66,  1144,  1872,  1206,  2144,  2081,  2775,  2266,  625,  2268,  747,  524,  360,  481,  3012,  2385,  3583,  1461,  698,  543,  835,  3432,  1012,  2633,  3440,  1914,  663,  1423,  3557), (2012,  2764,  1144,  1872,  1206,  2144,  2081,  2775,  2266,  625,  2268,  747,  524,  481,  3012,  2385,  3583,  1461,  698,  543,  835,  3432,  1012,  2633,  3440,  1914,  663,  2831,  3557), (2012,  2643,  1144,  1206,  2144,  2081,  2775,  2266,  625,  2268,  582,  747,  524,  360,  481,  3012,  3583,  1461,  698,  543,  3432,  2174,  1012,  2633,  3440,  1914,  1137,  663,  3557), (2012,  117,  1144,  1206,  2144,  2081,  1975,  2775,  2266,  625,  2268,  747,  524,  360,  481,  3012,  3583,  1461,  698,  543,  3432,  1012,  2633,  3440,  1914,  3557,  663,  338), (3539, 1478, 2849, 2545, 2146), (1150, 2660, 3007, 2849, 699, 2413, 2666, 2077, 2545, 3502, 2451), (280,  902,  2128,  2357,  1969,  2943,  910,  390,  2644,  462,  3003,  915,  573,  470,  3466,  626,  399,  3467,  2658,  2088,  2908,  23,  3126,  359,  687,  1450,  1451,  3525,  633,  3583,  2612,  1677,  3354,  819,  2681,  317,  3184,  2805,  1235,  3428,  3486,  1339,  3028,  2507,  326,  651,  2237,  3435,  3378,  2822,  2759,  550,  3150,  2009,  2292,  3039,  274,  2250,  3309,  2937,  61), (2188, 184, 1461, 2756, 2503, 3002, 2932, 597, 2899, 1975), (1200, 2352, 49, 3441, 3039, 244, 1975), (1140,  1200,  1313,  1362,  2190,  2352,  2302,  2535,  458,  3452,  1920,  792,  71,  3560,  1922,  1923,  856,  2018,  1321,  1607,  17,  1975,  2366,  1043,  2778,  3006,  237,  2479,  2603,  1613,  241,  1447,  2934,  194,  2728,  244,  3471,  2610,  3235,  1226,  250,  3236,  2096,  2434,  2873,  252,  91,  487,  316,  3358,  2105,  885,  428,  2288,  3079,  39,  892,  331,  2694,  378,  1306,  2515,  1914,  843,  2989,  2250,  2831,  3443,  965,  2125), (1200,  2423,  2054,  2352,  1550,  1301,  3196,  2849,  2974,  1736,  2261,  244,  1749,  2675), (981, 1163, 2268, 341, 91, 1478, 3196, 2390, 1524, 2899, 2835), (3407,  1428,  131,  1526,  3148,  149,  1645,  3385,  321,  1873,  2933,  2831,  2325,  1975), (2774, 224, 1975, 2192, 2996, 2849, 2289, 351, 2610, 27), (1963,  2536,  3454,  1813,  464,  2080,  3277,  1672,  522,  1893,  2161,  3234,  529,  2498,  1679,  2742,  3539,  104,  1798,  2628,  2691,  1013,  2241,  2587,  1359), (2495,  1546,  3034,  849,  2116,  1271,  213,  2831,  287,  3281,  1861,  1703,  2728,  1871,  2542,  2771,  676), (1790, 3265, 3378, 1782, 3508, 1630, 2459, 3501, 3030), (2165, 2084, 3590, 2203, 2849, 2545), (280,  902,  435,  2676,  1944,  1103,  807,  3378,  2412,  3525,  2449,  2293,  3053,  1794,  3501), (2495, 639, 1829, 1275, 3200, 1049, 619), (3585, 3433, 2268, 330, 331, 2783, 1333, 48, 259, 463, 1647, 3127, 491, 796), (3589, 1033, 3086, 1910, 3190, 1750), (1314,  3393,  1764,  516,  1823,  2478,  2783,  2088,  2787,  302,  2672,  3017,  2097,  1338,  2226,  1997,  1753,  272,  3196,  2588,  2760,  1702,  2296,  846), (1165, 813, 2268, 2783, 1826, 742, 3305, 2666, 2672, 1997, 2754, 3017), (3539, 2783, 2146, 1647, 1997, 3017), (966,  2640,  1768,  2534,  343,  2355,  3452,  2849,  390,  1373,  2542,  349,  2198,  1927,  2545,  981,  2366,  2425,  3118,  2203,  3469,  1827,  190,  2155,  2666,  1894,  3289,  2868,  3421,  257,  594,  2104,  822,  425,  1287,  3185,  1335,  34,  1339,  3082,  3433,  3544,  331,  2579,  3603,  3436,  3145,  2242,  217,  2181,  2515,  3089,  2404,  2250,  666), (2503, 1154, 2007, 3336), (1127, 2537, 3062, 2503, 1619), (849,  3394,  3271,  1873,  182,  3407,  298,  1275,  1052,  1833,  1171,  153,  321,  770,  3492,  3601,  656,  1536,  166,  2831,  3203), (1534, 545, 3196, 3268, 1336, 2948, 1975), (3475, 3265, 2958, 1910, 597), (1985, 2271, 3201, 476), (1584, 1977, 2389, 2849, 162, 1657, 3613), (555,  850,  1810,  3000,  121,  1776,  78,  1041,  1443,  2368,  3059,  3518,  1980,  132,  1106,  413,  751,  1161,  877,  2329,  1900,  2750,  3029,  2508,  1301,  1013,  3196,  3036,  1536,  3092,  1713,  2252,  2837), (375, 2268, 969, 2783, 3410, 3269, 1593, 2296, 2049), (375,  42,  3334,  2880,  271,  634,  2783,  803,  3410,  3269,  1983,  358,  205,  12,  2049,  1751), (2115, 2268, 3060, 2682, 288, 1075, 136, 304, 830, 1816), (173,  2131,  1028,  342,  3048,  1603,  1032,  2892,  1317,  462,  2768,  571,  915,  797,  1780,  237,  2480,  2208,  1153,  3066,  199,  411,  1739,  1677,  2872,  3422,  1463,  2502,  2046,  652,  3191,  212,  1012,  839,  3036,  3378,  2398,  1193,  2883,  714,  1916,  2461,  2937), (1442, 1790, 3004, 1492, 3196, 1642, 1658, 2293, 2507, 3096), (3583, 2189, 2088, 1536, 1040, 1975), (3583, 2189, 2088, 1536, 1040), (1678,  668,  1028,  970,  800,  3086,  404,  1910,  660,  72,  2825,  714,  276,  648,  606,  2281,  3333,  265), (619, 1301), (3205, 1363, 2831, 287, 1466, 1707, 2771, 607), (1820,  2700,  1885,  1115,  2849,  1288,  3219,  2899,  2545,  2749,  689,  963,  1794,  1661,  3556), (1820, 2700, 2131, 1885, 3452, 2849, 3219, 1050, 2545, 2899, 1661, 2637), (2340, 3586, 1881, 1999, 3075, 304, 2831), (1795, 2282, 2137, 2745, 1873), (2903, 2436, 2029, 797, 3366, 648, 2035), (2102, 2503, 2527, 3493), (509,  176,  73,  2195,  1873,  1660,  3402,  1975,  1214,  3341,  3286,  2730,  1623,  3023,  2744,  2225,  321,  1901,  1400,  1008,  2815,  603,  1863,  900,  2186,  1483), (1363, 1746, 348, 607, 2831, 3131), (435,  2054,  3501,  1028,  1790,  2940,  3180,  1411,  3479,  404,  348,  714,  3131,  622), (2966, 311, 1680, 2940, 2594, 404, 1982, 1306, 1318, 522, 290, 140), (3048,  2306,  2849,  1148,  181,  1435,  3337,  2428,  3126,  3289,  1455,  1677,  1742,  1679,  487,  317,  640,  822,  3184,  3537,  2339,  1642,  2243,  1864,  1252,  384,  3443,  3501,  2937), (280, 902, 2612, 2138, 1858, 3358, 3365, 2623, 1794), (781,  1201,  1364,  1028,  1550,  2940,  1602,  1085,  1969,  125,  794,  2199,  2899,  2475,  1974,  736,  2201,  3517,  1889,  404,  1891,  1982,  686,  405,  522,  2090,  1111,  1454,  2797,  317,  31,  705,  1902,  1850,  1301,  2584,  547,  1642,  2517,  714,  1704,  1599,  607,  2937,  1714), (2994,  2131,  850,  852,  456,  1491,  2137,  5,  390,  2712,  3565,  3327,  232,  2475,  470,  1929,  981,  1041,  2369,  2957,  1045,  2028,  3575,  2833,  3578,  2663,  2666,  584,  3289,  2730,  2380,  1222,  3527,  2675,  3042,  1677,  418,  1162,  813,  2329,  317,  1898,  1397,  2805,  3484,  1523,  951,  1749,  1475,  1950,  2054,  107,  1301,  3545,  1070,  1860,  3544,  2756,  3196,  2346,  2243,  553,  2824,  2826,  3199,  2403,  3087,  3443,  2937,  2061), (1012, 3265, 2849, 85, 1155, 2262, 714, 2010), (1162, 2755, 2131, 2615, 2758, 1061, 714, 1470, 2899), (3432,  2687,  1181,  2814,  2301,  1585,  2707,  2756,  974,  2377,  2380,  2898,  507,  3369,  2869,  1423), (225,  1141,  456,  2940,  1372,  1814,  1147,  3164,  2022,  470,  677,  2475,  1824,  1382,  2270,  1827,  3173,  2272,  687,  2489,  478,  694,  1843,  3427,  34,  1178,  2509,  265,  1403,  3432,  707,  3194,  2758,  1646,  3443,  1867,  965,  1423,  2992,  283,  1202,  2310,  66,  3452,  1656,  729,  2768,  976,  2077,  1433,  517,  2777,  1434,  981,  2552,  1213,  2317,  984,  2788,  526,  1454,  754,  3238,  3021,  2328,  314,  997,  1683,  95,  2334,  537,  1686,  766,  2575,  328,  545,  3034,  1245,  2345,  109,  3251,  2822,  2838,  1918,  339,  2844,  1028,  564,  120,  3267,  3265,  2355,  125,  794,  126,  573,  2857,  1497,  576,  1268,  3278,  1270,  3066,  3521,  145,  146,  1058,  2617,  1284,  2621,  1749,  2172,  2626,  836,  1534,  2880,  2180,  379,  1757,  2401,  1540,  2404,  3093,  168,  3097,  1545,  2640,  3319,  3320,  1969,  390,  2645,  1774,  1320,  3565,  1974,  186,  187,  404,  1982,  1106,  2668,  3579,  3580,  2666,  3346,  869,  3347,  3132,  1329,  200,  3583,  1571,  2679,  1573,  422,  2443,  1581,  2444,  1344,  1124,  435,  3147,  3378,  1591,  3386,  1136,  2250,  2252,  222), (1514, 2985, 2373, 1947, 2017), (2413, 26), (280, 902, 399, 638, 404, 1982, 1591, 847, 1914, 243, 3525, 2922, 3068), (1940,  1487,  2915,  2408,  1855,  835,  2025,  2154,  3608,  2633,  2309,  2321,  360,  394,  2081,  114,  2754), (2548,  1677,  599,  509,  1993,  2192,  694,  2040,  3360,  2711,  822,  1235,  359,  1524,  3039,  2887,  3486,  2365,  2590,  3466), (325, 1529, 3181, 3196, 470), (1028,  970,  1551,  2940,  3210,  1490,  9,  177,  1974,  404,  1982,  3125,  85,  414,  3130,  3131,  2492,  1788,  694,  1232,  2219,  494,  1636,  2290,  1639,  267,  435,  2578,  3034,  3086,  1910,  3378,  897,  714,  3501,  1715), (3452,  1656,  2849,  1927,  2545,  467,  1975,  981,  1213,  2780,  2201,  3469,  1889,  1445,  2666,  2702,  754,  1895,  1162,  638,  1167,  3588,  2217,  1898,  425,  699,  2570,  2446,  1406,  2342,  657,  3088,  2885,  3443,  168,  3502), (1043, 1885, 317, 2849, 2545), (3264, 1334, 896, 1829, 3200, 2831), (1442, 2756, 1370, 1813, 2666, 1582, 598, 1975), (2498,  45,  436,  2410,  453,  3085,  546,  3519,  242,  3279,  2139,  959,  1858,  3378,  682,  697,  731,  1155,  2361), (714,), (2970, 1040, 714), (280,  902,  399,  181,  3118,  1837,  2940,  2344,  1655,  3452,  1375,  1147,  1472,  2299), (3269,), (1200,  63,  3206,  1761,  2352,  458,  790,  2073,  2767,  1560,  2205,  1449,  1155,  3010,  3127,  244,  3129,  142,  3587,  1790,  94,  642,  492,  647,  3430,  155,  1531,  2688,  435,  1477,  549,  1643,  2633,  2822,  2402,  2293,  1485), (1704, 470), (451,  2064,  876,  1363,  2940,  1673,  404,  219,  3548,  2335,  714,  2950,  26,  1198,  1974), (714,), (3492,  3601,  2048,  1966,  849,  750,  1171,  656,  2089,  1286,  1275,  628,  3271,  153,  321,  350,  2831), (1244, 1672, 2849, 2666, 2600, 2545, 2808, 1378), (473, 3224, 63, 2130, 1790, 1955, 415, 2338), (575, 1010, 930, 2849, 3149, 867, 2377, 274, 1220, 76, 3369, 1474), (1790, 922, 1520, 13), (1440, 3409, 1245, 3546, 1284, 2442, 2761, 552, 2503, 3077, 1134, 1975), (1558,  79,  651,  2410,  3571,  422,  2940,  2802,  1889,  1827,  3378,  32,  1012,  1360,  83,  1155,  524,  2141,  573,  3238), (611,  2706,  2309,  2262,  2362,  1971,  2899,  573,  1558,  2368,  1155,  137,  524,  423,  2216,  2112,  1125,  1951,  43,  1012,  2345,  3378,  1418,  555), (2917, 2001, 190, 1656, 1292, 26), (2413, 26), (1437, 2166, 708, 637, 1396, 2861, 1984, 153, 348, 2045, 3308, 597, 26, 1929), (2633, 1144, 360, 1292, 2111), (2293, 2813, 583, 2111, 3378, 3002, 1704, 1450, 810), (3583, 3501, 1499, 2203, 2604, 48, 2849, 1472, 633), (1498, 1301, 2026, 287, 1933, 2373, 2944, 3576, 273, 1707, 397, 3464, 2383), (2203, 1074, 221, 321), (3446,  2592,  2300,  3392,  1491,  2466,  68,  11,  2141,  618,  2545,  351,  2147,  1436,  984,  1614,  1273,  2609,  363,  591,  2567,  2389,  764,  2806,  950,  1690,  3028,  1532,  3376,  3302,  1542), (1910, 2503, 163, 2162, 556), (45, 1790, 3378, 714, 3310, 3501, 2061), (1028, 404, 1982, 2927, 219, 3038, 714, 2991), (1854, 1300, 1029, 1461, 271, 648, 1910, 597, 3222, 606, 719), (105,  2395,  1028,  3163,  2940,  2284,  3479,  1982,  1969,  3439,  536,  2517,  2313,  750,  1794,  385,  2937), (280,  902,  981,  2213,  942,  3317,  960,  442,  2348,  50,  3075,  1947,  2247,  2404,  410,  3290,  2831,  2899,  1948), (80, 1098, 1952, 3211, 160, 1910, 2440, 2666, 2079, 556, 77, 1472), (3237, 404, 1982), (326, 310, 2370, 3230, 2849, 152, 408, 2273, 1136, 2007, 1664), (693, 804, 1334, 1829, 1319, 3200, 3094), (835, 693, 1334, 1829, 3200, 3094), (1697, 82, 3407, 321, 1901, 1873, 2186, 2325), (1625,  835,  813,  65,  1681,  2086,  3034,  3357,  743,  1579,  2456,  2292,  1523,  1784,  541,  1814,  1729,  2385), (981, 638, 2849, 1389, 2545, 3502, 2451), (63, 917, 1260, 2338), (880, 44, 2268, 630), (3098, 2330, 1370, 3536), (3474,  2189,  682,  2970,  803,  566,  3507,  1536,  357,  2222,  3365,  1040,  3203,  3348), (981, 2640, 2000, 66, 216, 2849, 1591, 85, 2666, 866, 3275, 2051), (1839, 1586, 658, 2849, 1285, 244, 3245), (3583, 3237, 280, 902, 146, 2603, 1769, 1969, 2170, 1472), (1536, 835, 803, 948), (2809, 1028, 3317, 1627, 627, 2523, 873, 40), (1764,  11,  1874,  1823,  2478,  2268,  2783,  1826,  685,  3127,  2672,  820,  2748,  491,  374,  1997,  41,  2052,  2055,  1408,  2581,  441,  3305,  557), (876, 708, 2238, 803, 1396, 3242, 1984, 153, 3308, 597, 26, 1929), (835,  3449,  3317,  1395,  505,  2309,  1449,  3253,  3459,  360,  714,  2360,  3273,  3081,  2081), (874,  2922,  1300,  2202,  1245,  2181,  190,  1656,  827,  1845,  1849,  3162,  2964,  3263,  1975), (280,  902,  1361,  3392,  3109,  181,  3120,  2724,  1889,  1451,  1332,  1940,  485,  1164,  1790,  3426,  1337,  1400,  1472,  45,  3035,  1800,  3249,  3310), (2147, 981, 594, 425, 2849, 1335, 2666, 2545, 3502), (1944,), (609, 3513, 1028, 3085, 2216, 404, 23, 1982, 1969, 1704, 714, 1708, 1291), (1873, 1536, 321), (2268, 2977), (280,  1404,  1940,  902,  452,  2176,  1790,  3378,  3219,  1472,  1657,  1179,  2404,  450,  165,  3310,  3501,  2507,  181), (2970, 1040, 3378, 1982), (2849, 2545, 2220), (280,  902,  174,  1772,  3003,  1206,  16,  181,  234,  399,  743,  2666,  3583,  2499,  3186,  1472,  3033,  1905,  3492,  1125,  3545,  2342,  1251,  1707,  3443), (509, 1977, 2304, 2849, 3185, 3365), (2253, 644, 2007, 2214), (3023, 2995, 1614, 2088, 3196, 2581, 1286, 2849, 3217, 3039, 808, 1255, 2561), (2413, 3222), (922, 2740, 1520, 13, 3040, 59), (451, 694, 1982, 714, 3131), (1124, 1999, 2581, 1246, 2464, 2849, 3460, 2381, 2749, 3349), (2165, 106, 2581, 3229, 458, 321), (2193, 2581, 2849, 3460, 1725, 2545), (3135,  1164,  2387,  1516,  2061,  317,  2182,  2804,  1464,  2571,  1337,  1608,  3402,  3310,  1651,  2083), (280,  902,  981,  181,  2978,  3119,  2579,  663,  3301,  2668,  2538,  1707,  34,  2912,  2936,  2831,  1715), (899, 2214, 2952), (2366, 1853, 2425, 1300, 1977, 2342, 3196, 2489, 243, 1635, 2922, 1434), (3432, 404, 1982, 714, 481, 2899, 3133, 778), (3350, 876, 1962, 270, 1518, 909, 3550, 360, 1157, 1292, 1239), (1685,), (1292,  2081,  1461,  3229,  1395,  999,  3075,  1217,  360,  2313,  714,  2831,  208,  834), (2938,  3101,  390,  1923,  2198,  2778,  1043,  2366,  981,  2270,  2479,  2206,  404,  2375,  687,  25,  3419,  694,  2169,  2105,  2922,  1403,  2340,  435,  1070,  53,  1914,  552,  2989,  2937), (922, 1520, 13), (287, 321, 1707, 165, 2383), (3432, 3021, 3545, 1981, 2849, 2249, 2899), (1857,), (1052,  2880,  3317,  1247,  1104,  2028,  1690,  1536,  1924,  10,  1219,  321,  1873,  182), (2503, 1088), (1067,), (876, 835, 1164, 3293, 1028, 799, 287, 360, 1707, 620, 2081), (3158, 2881, 1552, 2585, 1071, 108, 1371, 1910, 1276, 569, 2831, 3190, 1750), (1965,  2940,  2849,  2541,  347,  1658,  16,  1377,  1974,  353,  2270,  1672,  805,  3344,  1784,  2211,  3236,  2498,  1515,  317,  1523,  2236,  1301,  2346,  843,  2937,  3502), (2070, 1889, 2668, 3580, 554, 2248, 1310, 1794, 2937), (3196,), (930, 1147, 842, 3238), (2268, 2783, 49, 1997, 2049, 3017), (84, 3200, 2376, 1610), (2413,), (2020, 3326, 544, 2920), (1451, 2618, 2982, 1800), (2085, 158, 2629, 458, 842, 2345, 1261, 1190, 2766, 2899, 2010), (1856, 2891), (2366, 3432, 981, 997, 2849, 2220, 3471, 646, 1402), (3237, 2203, 48, 930, 2849, 2293, 1472), (1435, 2604, 946, 3378, 219, 394, 232), (115,  2014,  3268,  617,  1207,  620,  2425,  2024,  2153,  404,  1615,  2375,  1219,  688,  2093,  243,  1327,  3016,  3294,  487,  317,  2286,  2217,  1844,  99,  2751,  3141,  2922,  2177,  2880,  1243,  161,  1802,  383,  843,  276,  2831,  3443), (3191, 3021, 2351, 1168, 2203, 2304, 2849, 380, 2293, 2545, 1472), (280, 902, 3501, 476, 1265, 2899, 3115), (28, 1260, 1629, 991, 2338), (252,  3355,  1300,  1171,  1977,  2831,  203,  1535,  149,  1472,  243,  1327,  1159,  1848,  2922), (3222, 2268), (1164,  922,  2341,  3293,  287,  640,  1520,  2468,  404,  1254,  3001,  13,  1707,  2951), (1727, 1677, 1961, 2268, 1286, 1647, 2392, 3222, 3083, 1975), (3394,  2068,  3266,  1873,  1265,  3407,  1052,  1833,  2167,  3295,  1684,  2804,  321,  705,  2689,  1196,  2930,  1536,  1421,  3203,  3555), (2012, 1300, 1977, 243, 2922), (1694, 1237, 989), (2254, 2503, 904, 873), (3407, 2920, 2849, 153, 321), (1163, 1049, 2017, 430, 782), (2656, 653, 3475, 519, 3515, 1698, 3123, 1910, 461, 2949), (1401, 997, 2814, 2831, 3322, 1889, 24, 1327), (1790, 2633, 1144, 321, 1292), (922, 2085, 3335, 2430, 345, 1756, 711, 2947, 1864, 13, 2530), (280,  902,  3392,  1363,  1028,  2940,  287,  458,  1921,  1773,  2599,  2771,  1728,  3464,  181,  1730,  2725,  1452,  3012,  3237,  1164,  3477,  317,  1337,  892,  2238,  2344,  3378,  3439,  1707), (2940, 404, 121, 1982, 1539, 873, 40), (2839, 429, 1707, 246, 430, 3403), (2462,  280,  118,  3392,  612,  3317,  613,  2061,  2355,  615,  2196,  3160,  1555,  2363,  1776,  2899,  1728,  1100,  191,  300,  934,  1106,  1504,  1982,  2272,  2670,  2432,  362,  809,  1895,  3131,  3237,  1164,  1165,  1679,  145,  592,  2920,  882,  539,  1005,  1707,  889,  2806,  1401,  1341,  1470,  892,  953,  2112,  3191,  435,  2812,  1301,  3439,  3610,  3199,  3548,  445,  3550,  3153,  2403,  843,  2250,  1215,  2937,  2125), (486, 3023, 2845, 1214, 2581, 2682, 2744, 2961, 2602, 1400, 900, 140), (451, 1694, 876, 1982, 2335, 2831, 2315, 1237, 1330), (2922, 1028, 1300, 1982, 3044, 1974), (484, 1057, 710, 1520, 3520, 13, 1175, 891), (2931, 2756, 1784), (1695, 1678, 144, 925, 1363, 1028, 3591, 47, 2512, 876, 3292, 2047, 962), (430, 1892, 2017, 782), (835, 1794), (902, 22, 2670, 1794, 892), (1761, 2318, 1100, 1014, 3252, 3200, 807), (1028,  907,  3265,  2940,  607,  1557,  3331,  2658,  1982,  3126,  3524,  1742,  2799,  1575,  317,  2803,  541,  3378,  2762,  384,  714,  2459,  3501,  2636), (243, 1043, 2922, 1284), (1043, 3268, 1284, 243, 2922), (923, 713), (1910, 2346, 774, 1290, 1469, 556, 2384, 2290, 2492, 27), (1214, 930, 2170, 1472, 164, 125, 3286, 1400, 2545, 140), (2038, 2810, 1300, 54, 869, 1292, 2094), (1124, 3240, 3227, 131, 88), (2270, 1889, 2651), (835, 713), (1043, 2317, 1045, 2804, 3593, 3150, 2975, 152, 2989, 1356, 2899, 3115, 3330), (1393, 1200, 3467, 2352, 2640, 3180, 2883, 714, 244, 2406, 690), (2831, 404, 2442, 3416, 3462, 1847, 1279), (835, 2511, 1679, 2391, 1519), (3589, 1889, 3365, 3510, 2275, 1454, 1817, 27), (1043,  45,  2203,  3319,  3377,  521,  2818,  546,  3378,  2311,  3149,  2849,  1155,  2545), (280,  902,  3021,  1679,  1168,  2291,  2304,  3362,  1472,  1620,  34,  220,  1136,  868,  3161,  2545,  1726,  78,  2062), (2495, 1829, 1275, 3200, 619, 2734), (2147, 1836, 981, 2700, 1379, 425, 2849, 2749, 2545), (509,  3317,  1966,  2302,  3209,  1493,  1921,  3566,  3330,  1879,  1668,  930,  3286,  3177,  3019,  142,  2738,  1573,  2800,  3358,  260,  321,  2234,  375,  2814,  3151,  1074,  2186), (2849, 1043, 2545), (1400, 2871, 321), (2940,  458,  404,  1982,  627,  2071,  742,  1399,  973,  2899,  2517,  714,  715,  1417,  3483,  2263,  2937,  1974), (280, 678, 2595), (1043, 1362, 2566, 2849, 2545, 1635, 2856, 2451), (2265, 235, 1790, 2942, 1755, 791, 664, 1658, 703, 1419, 528), (980,), (2527,), (1161, 981, 1943, 668, 2246, 1910, 863, 3500, 72, 2471, 1523, 648, 606, 2290), (313, 2503, 2197, 1866, 3156), (2948,  1727,  2146,  3227,  2783,  803,  2154,  303,  3415,  247,  813,  145,  1288,  1523,  1473,  1184,  1069,  2581,  334,  775,  1916,  1711), (280, 1404, 902, 1040, 1472, 181), (1214, 3407, 3603, 1428, 2568, 744, 2849, 1617, 321, 495), (3121, 1012, 422, 2633, 360, 1144, 1292, 2450), (728, 3378, 2504, 128, 3501, 1229), (1665, 2413, 1360), (2054, 1029, 1245, 3196, 2503, 2220, 2666), (1164, 3293, 2081, 565, 2154, 1337, 350, 3273, 769), (1982, 1974), (2883, 1292, 735), (1400, 661, 2025, 321), (609, 1028, 2512, 404, 714), (1404, 2150, 1043, 2566, 814, 2849, 2545, 2521, 2561, 56, 2507, 2451), (1162, 2640, 3319, 297, 2243, 910, 2400, 1144, 2699, 3472), (285, 321), (1530, 2779, 1069, 2783, 2581, 3380, 2849, 1647, 793, 247, 557), (280,  509,  1400,  1839,  1977,  2040,  3181,  3196,  425,  134,  2744,  1771,  3365,  1927,  1994,  278,  100,  980), (1906, 758, 438, 2204, 512, 1033, 2154, 1371, 1910, 1706, 3190, 1750, 3261), (835,), (835,), (1799, 1790, 21, 1982, 3378, 714, 261, 3501, 2913), (2820, 2268), (3222, 2268), (1028,  786,  2940,  2467,  393,  1974,  1042,  2722,  3404,  2785,  404,  1735,  872,  694,  2502,  320,  3367,  104,  3247,  2179,  1587,  659,  3378,  2883,  3037,  3039,  714,  446,  384,  1356,  3501,  112), (2651, 3378), (2148, 835), (922, 3488, 3424, 2320, 1520, 1049, 13), (2549, 1043, 2201, 3047, 2284, 317, 2355, 3579, 843, 364, 250), (679, 1945, 2849, 536, 390, 1815, 3330), (842, 1144), (3389, 2923, 2881, 1294, 1283, 1952, 1910, 1750, 556, 1596, 3165), (3070, 2478, 1882, 3318, 2783, 641, 961, 1921, 1702, 2865, 2672), (2064, 1909, 389, 1065, 249), (1550, 2220), (3069, 1449), (835, 922, 876, 1520, 360, 13, 172, 2081), (1630, 446, 3378), (79, 3405, 3485, 2313, 360, 1292), (3504, 1164, 591, 1982, 3271, 1337, 321, 714), (980,), (2268, 271, 2783, 1513, 1647, 12, 2672), (2413,), (2325,), (1654,  2646,  465,  623,  1503,  1781,  2701,  1449,  2870,  1169,  1059,  1001,  154,  3596,  321,  2227,  1409,  2453,  1479,  2828,  165,  168,  279), (1977, 3186, 3222, 1910), (293, 635, 2800, 1644, 2710, 321), (293,  2268,  2880,  3497,  1954,  3361,  526,  2482,  2158,  897,  3597,  3137,  908,  494,  3222,  1676), (2718, 1685, 2168, 3252), (1162, 835, 2086, 439, 3221, 1831, 3463, 2407, 1423, 2011), (3539, 2118, 2849, 2413, 2545, 1875)]

The original items where strings, but I decided to change them to integers in order to optimize the python handling. Anyway, I had to kill the test after half an hour. I haven't test it much further than that but I wanted to ask if this is expected with your implementation.

My computer is an Intel® Xeon(R) CPU E5-2620 v4 @ 2.10GHz × 16 plus 32Gb RAM, and I did the test using Jupyter Notebook.

Thanks in advanced.

Could Polars increase memory usage and speed?

Currently the algorithm requires converting pandas dataframes to lists of tuples for the algorithm the work, which aren't memory optimized compared to numpy arrays. The problem I've found when working with GBs of data is that it will quickly run out of memory on my local machine if I don't tune min_confidence and min_support to the right values my machine can handle. Could Polars potentially improve the speed and efficiency of this package?

From benchmarks Polars has shown to be extremely fast, even when processing 1,000,000,000+ rows on a local machine with just 8GBs of ram, while Pandas runs immediately out of memory if the data size exceeds the machines memory. https://h2oai.github.io/db-benchmark/

H_1 is not reduced, unnecessary rule candidate generation/checking

Ok, let's do this the proper way. My PR #44 was not working because I prematurely tried to fix something that I did not fully understand.

Description

When generating rule candidates with 1-item consequents, no pruning is applied. This leads to unnecessary confidence computations for candidates that are below the confidence threshold.

Minimum Working Example

Going from the docstring for generate_rules_apriori, the following example will generate unnecessary candidates

transactions = [
    ('a', 'b', 'c', 'd'),
    ('a', 'b', 'c'),
]
n = len(transactions)
min_sup = 0.5
min_conf = 1.0

itemsets, _ = itemsets_from_transactions(transactions, min_sup, max_length=4, verbosity=1)
rules = list(generate_rules_apriori(itemsets, min_conf, n, verbosity=1))

When deriving rules of size 4, all of these candidates are being checked:

1) 	{b, c, d} -> {a} (conf: 1.000, supp: 0.500, lift: 1.000, conv: 0.000)
2) 	{a, c, d} -> {b} (conf: 1.000, supp: 0.500, lift: 1.000, conv: 0.000)
3) 	{a, b, d} -> {c} (conf: 1.000, supp: 0.500, lift: 1.000, conv: 0.000)
4) 	{a, b, c} -> {d} (conf: 0.500, supp: 0.500, lift: 1.000, conv: 1.000)
5) 	{c, d} -> {a, b} (conf: 1.000, supp: 0.500, lift: 1.000, conv: 0.000)
6) 	{b, d} -> {a, c} (conf: 1.000, supp: 0.500, lift: 1.000, conv: 0.000)
7) 	{b, c} -> {a, d} (conf: 0.500, supp: 0.500, lift: 1.000, conv: 1.000)
8) 	{a, d} -> {b, c} (conf: 1.000, supp: 0.500, lift: 1.000, conv: 0.000)
9) 	{a, c} -> {b, d} (conf: 0.500, supp: 0.500, lift: 1.000, conv: 1.000)
10)	{a, b} -> {c, d} (conf: 0.500, supp: 0.500, lift: 1.000, conv: 1.000)
11)	{d} -> {a, b, c} (conf: 1.000, supp: 0.500, lift: 1.000, conv: 0.000)

In 10) we check {a, b} -> {c, d} although 4) {a, b, c} -> {d} (conf: 0.500) is already below the confidence threshold of 1.0.
Even the docstring says that it is not necessary to check 10) due to confidence-based pruning.

(In my fork, I added a few print statements to easily track what's being done for this very example in h_1_mwe.py)

Tasks

• confirm that this behavior is not intended
• find a way to prune H_1 properly
• test whether it brings any speed improvement

ModuleNotFoundError: No module named 'dataclasses'

environment：anaconda 3-5.2.0
I just ran the sample code and it reported an error.

`ModuleNotFoundError Traceback (most recent call last)
in
----> 1 from efficient_apriori import apriori
2 transactions = [('eggs', 'bacon', 'soup'),
3 ('eggs', 'bacon', 'apple'),
4 ('soup', 'bacon', 'banana')]
5 itemsets, rules = apriori(transactions, min_support=0.5, min_confidence=1)

E:\anaconda\lib\site-packages\efficient_apriori_init_.py in
10
11 import sys
---> 12 from efficient_apriori.apriori import apriori
13 from efficient_apriori.itemsets import itemsets_from_transactions
14 from efficient_apriori.rules import Rule, generate_rules_apriori

E:\anaconda\lib\site-packages\efficient_apriori\apriori.py in
6
7 import typing
----> 8 from efficient_apriori.itemsets import itemsets_from_transactions, ItemsetCount
9 from efficient_apriori.rules import generate_rules_apriori
10

E:\anaconda\lib\site-packages\efficient_apriori\itemsets.py in
13
14 from collections import defaultdict
---> 15 from dataclasses import field, dataclass
16
17

ModuleNotFoundError: No module named 'dataclasses'`

KeyError while generating rules

The apriori algorithm throws a KeyError when generating rules from itemsets.

Generating itemsets.
 Counting itemsets of length 1.
  Found 457 candidate itemsets of length 1.
  Found 190 large itemsets of length 1.
 Counting itemsets of length 2.
  Found 17955 candidate itemsets of length 2.
  Found 16611 large itemsets of length 2.
 Counting itemsets of length 3.
  Found 67 candidate itemsets of length 3.
  Found 63 large itemsets of length 3.
 Counting itemsets of length 4.
  Found 0 candidate itemsets of length 4.
Itemset generation terminated.

Generating rules from itemsets.
 Generating rules of size 2.
 Generating rules of size 3.
Traceback (most recent call last):
  File "basket.py", line 26, in <module>
    itemsets, rules = apriori(transactions, min_support=.6,  min_confidence=.5, verbosity=1)
  File "/home/.../lib/python3.5/site-packages/efficient_apriori/apriori.py", line 56, in apriori
    return itemsets, list(rules)
  File "/home/.../lib/python3.5/site-packages/efficient_apriori/rules.py", line 329, in generate_rules_apriori
    conf = count(itemset) / count(lhs)
  File "/home/.../lib/python3.5/site-packages/efficient_apriori/rules.py", line 303, in count
    return itemsets[len(itemset)][itemset]
KeyError: ('Item 3', 'Item 5')

Is this a Python version issue?

Misprint in instructional comment

Hi! You have misprint in rules.py line 54.
Now: >>> r.support # Probability of ('a', 'c', 'c') in the data
Should be: >>> r.support # Probability of ('a', 'b, 'c') in the data

It is a good package, I just want to be helpful)

lhs and rhs mixed up in the comments?

Hey

I was going through the code to understand the apriori algorithm, in particular, the rule generation in rules.py
In the _ap_genrules function, there are some comments and I was wondering whether the lhs and rhs got mixed up in the descriptions.
It says from Line 422:

    # Generate **left**-hand itemsets of length k + 1 if H is of length k
    H_m = list(apriori_gen(H_m))
    H_m_copy = H_m.copy()

    # For every possible **right** hand side
    for h_m in H_m:
        # Compute the **right** hand side of the rule
        lhs = tuple(sorted(set(itemset).difference(set(h_m))))

I have highlighted with ** the part of the comments that I believe might have gotten mixed up somehow.
Of course, the code works like a charm but I was wondering whether I had a misunderstanding of how it works.

Reducing H_1 update broken

Hello again,
thank you to @hprshayan for addressing #45 in #53.
However, the following example fails for me although all tests succeed:

from efficient_apriori.apriori import apriori
transactions = [(1, 2, 3), (1, 2, 3), (1, 2, 3), (1, 2), (2, 3)]
apriori(transactions, 0.4, 0.8)

This is due to H_1 being empty at the time of entering _ap_genrules. Thus, the check if len(itemset) <= (len(H_m[0]) + 1) will give an IndexError.

If you could confirm that the example also fails for you, I might get around to creating a PR.

Is there any way to export the rules with data to Excel?

I can't figure out how to write the results of the rules to a list or dataset. I'm only able to write the rules to lists without the calculations like lift, conv etc..
How can I capture the results in a list or dataframe so I'm able to export this to Excel/CSV?

Using the following code, I put the rules in a list without results.
association_results = filter(lambda rule: len(rule.lhs) == 2 and len(rule.rhs) == 1, rules) rulelist = [] for rule in sorted(association_results, key=lambda rule: rule.lift): rulelist.append(rule)

syntax error

  File "efficient_apriori/apriori.py", line 12
    def apriori(transactions: typing.List[tuple], min_support: float=0.5,
                            ^
SyntaxError: invalid syntax

regards,
shibamouli

A doubt

How can i get intersection of 2 rules..for example rules[0] and rule[1] i.e the number of transactions that satisfies rules[0] and rules[1]

Clarifications on rules direction meaning

Hi, again. As I have already mentioned this is a very good quality package, and I have question concerning logic behind the algorithm. Maybe you could help on clarification of the following question.

For example I have the next rules produced by the Apriori algorithm :

[{eggs} -> {bacon}, {bacon} -> {eggs}]

Both with different confidence and support values. If I understand correctly the first rule means that people who first let the system know that they will buy eggs will mostly buy bacon as well with the corresponding probability. And the second one means that people who first let the system know that they will buy bacon will also buy eggs with the corresponding probability.

So if I am not interested in the order people add items to their purchase how shall I interpret this result. Can I just sum the corresponding confidence and support and get rid of the directional arrow or it is forbidden?

Thanks in advance!

the min_support value

Hi，when I set the min_support less than 0.3, there is a error: '<' not supported between instances of 'numpy.ndarray' and 'str'. Howere, it works well when greater than 0.3.

interpret the output

Is there a way to visualize the output (i.e., itemsets and rules)? For example, the mlxtend Apriori can generate and return statistics such as lift, which allows one to visualize the strength of the association. Can we do something similar to the heatmap presented in the article below (the last set of figure): https://medium.com/analytics-vidhya/market-basket-analysis-association-rule-mining-with-visualizations-cda24d537019

Code for count_all

Can u pls explain the code of count_all?

Replace setup.py with pyproject.toml

Anyone wanna grab this task? Let me know!

sort step not needed after combinations for join_step

In join_step, itemsets is already, or rather should be sorted. Therefore tail_items remains sorted as it's being built up in the inner for-loop.

Now, when using itertools.combinations to get a and b, there's no need to use sorted since from the Python 3 docs:

The combination tuples are emitted in lexicographic ordering according to the order of the input iterable. So, if the input iterable is sorted, the output tuples will be produced in sorted order.

My suggestion is to remove the sorted call since it's unnecessary. I've run the tests without it and they all pass. I could make a PR but first wanted to create an issue to see if I missed something.

run time

en python 3.7 with a file of rows 939 and 50 characterstics ,
the algorithm takes more than 2 hours, and I have seen this algorithm run much faster with more data, you know what the problem is.

this are the librarys i have install :

filters

Thank you for this useful tool.
Can i specify the consequent of rules?
For example can i say i just want rules that their right hand is butter or cheese?

Input dataset format

Hi there - love your work on this package! I have a question regarding input datasets, in your example this is a list of tuples, but is it possible to work with dataframes too? What are the restrictions around input data?

Many thanks,
Ben