tommyod / efficient-apriori Goto Github PK
View Code? Open in Web Editor NEWAn efficient Python implementation of the Apriori algorithm.
License: MIT License
An efficient Python implementation of the Apriori algorithm.
License: MIT License
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?
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:
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. 👍
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]
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/
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.
File "efficient_apriori/apriori.py", line 12
def apriori(transactions: typing.List[tuple], min_support: float=0.5,
^
SyntaxError: invalid syntax
regards,
shibamouli
Can u pls explain the code of count_all?
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)
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.
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 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?
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
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.
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.
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.
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
)
Anyone wanna grab this task? Let me know!
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
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.
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
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)
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
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.
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.
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'`
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.