/* 

  Frequence Itemset Mining in Picat.

  This is inspired from the Essence' code shown
  in Tias Guns' video talk (from 2009)
  "Constraint Programming for Itemset Mining"
  http://videolectures.net/aop09_guns_cpfim/
  
  (Essence' code at about 19:50)

  (This is a port of my MiniZinc model itemset_mining.mzn.)

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.

main => go.

/*
  Optimal solution (max coverage) on the Borgelt instance:

  obj = max_coverage
  items = [b,c]
  trans = [2,7,9]
  trans = [[2,3,4],[2,3],[2,3,5]]
  coverage = 3
  support = 30
  support = 0.3
  itemset_size = 2

*/
go =>
  nolog,
  data(borgelt,NrI,NrT,Freq,ItemStr,S),
  % data(tias1,NrI,NrT,Freq,ItemStr,S),
  % data(tias2,NrI,NrT,Freq,ItemStr,S),
  % data(tias3,NrI,NrT,Freq,ItemStr,S),
  % data(4,NrI,NrT,Freq,ItemStr,S),
  % data(5,NrI,NrT,Freq,ItemStr,S),
  % data(6,NrI,NrT,Freq,ItemStr,S),
  % data(7,NrI,NrT,Freq,ItemStr,S),
  % data(8,NrI,NrT,Freq,ItemStr,S),
  % data(9,NrI,NrT,Freq,ItemStr,S),
  % data(10,NrI,NrT,Freq,ItemStr,S),

  Obj = max_coverage,
  itemset_mining(NrI,NrT,Freq,S,Obj,  Items,Trans,Coverage,Freq,ItemsetSize,Support),
  
  print_solution(NrI,NrT,Items,ItemStr,S,Obj, Trans,Coverage,ItemsetSize,Support),

  nl.


% max coverage for all instance
go2 =>
  nolog,
  member(Instance, [borgelt,tias1,tias2,tias3,4,5,6,7,8,9,10]),
  println(instance=Instance),
  data(Instance,NrI,NrT,Freq,ItemStr,S),
  Obj = max_coverage,
  itemset_mining(NrI,NrT,Freq,S,Obj,  Items,Trans,Coverage,Freq,ItemsetSize,Support),  
  print_solution(NrI,NrT,Items,ItemStr,S,Obj, Trans,Coverage,ItemsetSize,Support),
  nl,
  fail,

  nl.

% max support for all instances
go3 =>
  nolog,
  member(Instance, [borgelt,tias1,tias2,tias3,4,5,6,7,8,9,10]),
  println(instance=Instance),
  data(Instance,NrI,NrT,Freq,ItemStr,S),
  Obj = max_support,
  itemset_mining(NrI,NrT,Freq,S,Obj,  Items,Trans,Coverage,Freq,ItemsetSize,Support),  
  print_solution(NrI,NrT,Items,ItemStr,S,Obj, Trans,Coverage,ItemsetSize,Support),
  nl,
  fail,
  nl.

% All optimal solutions
go4 => 
  % data(borgelt,NrI,NrT,Freq,ItemStr,S),
  % data(tias1,NrI,NrT,Freq,ItemStr,S),
  % data(tias2,NrI,NrT,Freq,ItemStr,S),
  data(tias3,NrI,NrT,Freq,ItemStr,S),
  % data(4,NrI,NrT,Freq,ItemStr,S),
  % data(5,NrI,NrT,Freq,ItemStr,S),
  % data(6,NrI,NrT,Freq,ItemStr,S),
  % data(7,NrI,NrT,Freq,ItemStr,S),
  % data(8,NrI,NrT,Freq,ItemStr,S),
  % data(9,NrI,NrT,Freq,ItemStr,S),
  % data(10,NrI,NrT,Freq,ItemStr,S),

  member(Obj,[max_coverage,max_support]),
  println(obj=Obj),
  if Obj == max_coverage then
     itemset_mining(NrI,NrT,Freq,S,Obj,  _Items,_Trans,Coverage,Freq,_ItemsetSize,_Support),
     printf("Optimal coverage: %d.\n\nAll optimal solutions:\n", Coverage)
  else
     itemset_mining(NrI,NrT,Freq,S,Obj,  _Items,_Trans,_Coverage,Freq,_ItemsetSize,Support),
     printf("Optimal support: %d.\n\nAll optimal solutions:\n", Support)
  end,
  
  itemset_mining(NrI,NrT,Freq,S,all,  Items,Trans,Coverage,Freq,ItemsetSize,Support),
  print_solution(NrI,NrT,Items,ItemStr,S,Obj, Trans,Coverage,ItemsetSize,Support),
  fail,
  nl.

print_solution(NrI,NrT,Items,ItemStr,S,Obj, Trans,Coverage,ItemsetSize,Support) =>
  println(obj=Obj),
  SelectedItems = [I : I in 1..NrI, Items[I] == 1],
  SelectedTrans = [I : I in 1..NrT, Trans[I] == 1],
  println(items=[ItemStr[I] : I in SelectedItems]),  
  println(trans=SelectedTrans),
  println(trans=[S[T] : T in SelectedTrans]),
  println(coverage=Coverage),
  println(support=Support),
  println(support=(Support/100)),
  println(itemset_size=ItemsetSize),
  nl.

itemset_mining(NrI,NrT,Freq,S,Obj,  Items,Trans,Coverage,Freq,ItemsetSize,Support) => 

  Items = new_list(NrI),
  Items::0..1,
  Trans = new_list(NrT),
  Trans :: 0..1,

  % Coverate: Number of including transactions
  Coverage :: 0..NrT,

  % Frequence: number of transactions that contains the itemset
  % (Often fixed by the problem instance.)
  Freq :: 0..NrT, 

  % Size of the itemset
  ItemsetSize :: 0..NrI,

  % Support: percentage of transactions which contains the itemset
  % (stated as 0..100 since most CP solvers don't handle var floats).
  % Perhaps to be maximized.
  Support #= (100*Coverage) // (NrT),

  % encode TDB
  foreach(T in 1..NrT)
    Trans[T] #= 1 #<=> sum([Items[I] * (1-sum([ST #= I : ST in S[T]]) #> 0)    : I in 1..NrI]) #= 0
  end,


  % Frequency Base model (Frequent Itemset Mining)
  % foreach(I in 1..NrI) 
  %   Items[I] #= 1 #=> (sum([Trans[T]*(sum([ST #= I : ST in S[T]]) #> 0): T in 1..NrT]) #>= Freq)
  % end,

  % For closed Itemset Mining
  % Note: Should be used with Frequency Base model.
  % foreach(I in 1..NrI) 
  %   Items[I] #= 1 #<=> sum([Trans[T]*(1-(sum([ST #= I : ST in S[T]]) #> 0)) : T in 1..NrT]) #= 0
  % end,

  % Frequency: Maximal Frequent Itemset Mining
  % same as Base model, except for the equivalence (<->)
  foreach(I in 1..NrI)
    Items[I] #= 1 #<=> sum([Trans[T]*  (sum([ST #= I : ST in S[T]]) #> 0) : T in 1..NrT]) #>= Freq    
  end,
  
  Coverage #= sum(Trans),
  ItemsetSize #= sum(Items),

  Coverage    #> 0,
  ItemsetSize #> 0,
  Freq        #> 0,

  Vars = Items ++ Trans ++ [Coverage,ItemsetSize,Freq,Support],
  if Obj == max_coverage then
     solve($[min,split,max(Coverage)], Vars)
  elseif Obj == max_support then
     solve($[min,split,max(Support)], Vars)
  else
    solve($[min,split], Vars)
  end.


% From 
% Christian Borgelt presentation
% Frequent Pattern Mining
% http://www.borgelt.net/slides/fpm4.pdf
% page 3.
data(borgelt,NrI,NrT,Freq,ItemStr,S) =>
  NrI = 5,
  NrT = 10,
  Freq = 2,
  ItemStr = ["a","b","c","d","e"],
  [A,B,C,D,E] = [I : I in 1..NrI],
  S = [[A,D,E],
       [B,C,D],
       [A,C,E],
       [A,C,D,E],
       [A,E],
       [A,C,D],
       [B,C],
       [A,C,D,E],
       [B,C,E],
       [A,D,E]].



% First example (about 16:40) where Tias explained the principle
% of variables, domains, and constraints.
data(tias1,NrI,NrT,Freq,ItemStr,S) =>
  NrT = 12,
  NrI = 8,
  Freq = 4,
  ItemStr = [I.to_string : I in 1..NrI],
  S = [[2,3,4],
       [7,8],
       [1,5,6],
       [1,2,3],
       [1,4,6,8],
       [2,5,7,8],
       [1,4,7,8],
       [1,2,3,6,8],
       [1,2,6,7],
       [1,2,3,4,6,7,8],
       [1,6,7,8],
       [1,2,3,5,6]  
  ].

% Second example (where Tias explained the propagations about 19:50)
data(tias2,NrI,NrT,Freq,ItemStr,S) =>
  NrT = 3,
  NrI = 4,
  Freq = 2,
  ItemStr = ["Data Mining1", "Data Mining2", "CP1", "CP2"],
  S = [[1,3,4],
       [1,2,4],
       [3,4]].

% Example from Tias Guns' Thesis 
% "Declarative Pattern Mining using CP", page 12
data(tias3,NrI,NrT,Freq,ItemStr,S) =>
  NrT = 10,
  NrI = 5,
  Freq = 2,
  ItemStr = ["j" ++ I.to_string : I in 1..NrI],
  S = [
   [2],
   [5],
   [1,3],
   [1,5],
   [2,3],
   [4,5],
   [3,4,5],
   [1,2,3],
   [1,2,5],
   [1,2,3,5]].


%
% Another example:
%
% S Itemset
% 1 {apple, durian}
% 2 {bread, cheese}
% 3 {bread, egg}
% 4 {cheese, egg}
% 5 {apple, bread, cheese}
% 6 {apple, bread, cheese, durian}
% 7 {bread, cheese, durian, egg}
% 8 {apple, bread, cheese, egg}
data(4,NrI,NrT,Freq,ItemStr,S) =>
  NrI = 5,
  NrT = 8,
  Freq = 2,
  ItemStr = ["apple","bread","cheese","durian","egg"],
  Apple = 1,
  Bread = 2,
  Cheese = 3,
  Durian = 4,
  Egg = 5,
  S = [[Apple, Durian],                % t1
       [Bread, Cheese],                % t2
       [Bread, Egg],                   % t3
       [Cheese, Egg],                  % t4
       [Apple, Bread, Cheese],         % t5
       [Apple, Bread, Cheese, Durian], % t6
       [Bread, Cheese, Durian, Egg],   % t7
       [Apple, Bread, Cheese, Egg]     % t8
       ].


% From the presentation
% "Association Rules"
% http://www.cse.ohio-state.edu/~srini/674/assoc1.ppt
% slide 4
data(5,NrI,NrT,Freq,ItemStr,S) =>
  NrT = 5,
  NrI = 5,
  Freq = 2,
  ItemStr = ["Beer","Bread","Jelly","PeanutButter","Milk"],
  Beer = 1,
  Bread = 2,
  Jelly = 3,
  PeanutButter = 4,
  Milk = 5,
  S = [[Bread,Jelly,PeanutButter],
       [Bread,PeanutButter],
       [Bread,Milk,PeanutButter],
       [Beer,Bread],
       [Beer,Milk]
  ].


% From the presentation
% "Association Rules"
% http://www.cse.ohio-state.edu/~srini/674/assoc1.ppt
% slide 15
% Note: Slide 16 states {Jeans,Shoes,Shorts,TShirt}
%       as the Largest Itemsets (of #4).
%       Which is the same solution as this model finds with Freq = 2
%       (and it is the unique solution).
% 
% Note2: When Freq is free then {Jeans, Shorts} 
%        has better support (0.25), and Freq is 5.
%
data(6,NrI,NrT,Freq,ItemStr,S) =>
  NrT = 20,
  NrI = 6,
  Freq = 2,
  % Coverage = 3,
  % ItemsetSize = 3,
  Blouse = 1,
  Jeans = 2,
  Shoes = 3,
  Shorts = 4,
  Skirt = 5,
  TShirt = 6,
  ItemStr = ["Blouse","Jeans","Shoes","Shorts","Skirt","TShirt"],
  S = [
       {Blouse},                          % 1
       {Shoes,Skirt,TShirt},              % 2
       {Jeans,TShirt},                    % 3
       {Jeans,Shoes,TShirt},              % 4
       {Jeans,Shorts},                    % 5
       {Shoes,TShirt},                    % 6
       {Jeans,Skirt},                     % 7
       {Jeans,Shoes,Shorts,TShirt},       % 8
       {Jeans},                           % 9
       {Jeans,Shoes,TShirt},              % 10
       {TShirt},                          % 11
       {Blouse,Jeans,Shoes,Skirt,TShirt}, % 12
       {Jeans,Shoes,Shorts,TShirt},       % 13
       {Shoes,Skirt,TShirt},              % 14
       {Jeans,TShirt},                    % 15
       {Skirt,TShirt},                    % 16
       {Blouse,Jeans,Skirt},              % 17
       {Jeans,Shoes,Shorts,TShirt},       % 18
       {Jeans},                           % 19
       {Jeans,Shoes,Shorts,TShirt}        % 20
   ].



% From 
% Frequence Item Mining
% http://www.cs.kent.edu/~jin/DM08/FIM.pdf
% page 4
data(7,NrI,NrT,Freq,ItemStr,S) =>
  NrT = 10,
  NrI = 5,
  Freq = 2,
  ItemStr = ["a","b","c","d","e"],
  A = 1,
  B = 2,
  C = 3,
  D = 4,
  E = 5,
  S = [{A,B,E},
       {B,D},
       {A,B,E},
       {A,C},
       {B,C},
       {A,C},
       {A,C},
       {A,B},
       {A,B,C,E},
       {A,C,E}
     ].

% Frequence Item Mining
% http://www.cs.kent.edu/~jin/DM08/FIM.pdf
% page 15f
data(8,NrI,NrT,Freq,ItemStr,S) =>
  NrT = 5,
  NrI = 6,
  Freq = 2,
  ItemStr = ["Beer","Bread","Coke","Diaper","Eggs","Milk"],
  Beer = 1,
  Bread = 2,
  Coke = 3,
  Diaper = 4,
  Eggs = 5,
  Milk = 6,
  S = [{Bread, Milk},
       {Bread,Diaper,Beer,Eggs},
       {Milk,Diaper,Beer,Coke},
       {Bread,Milk,Diaper,Beer},
       {Bread,Milk,Diaper,Coke}
  ].

% 
% From
% Tan, Steinbach, Kumar: "Introduction to datamining"
%
data(9,NrI,NrT,Freq,ItemStr,S) =>
  NrT = 10,
  NrI = 5,
  Freq = 2,
  A = 1,
  B = 2,
  C = 3,
  D = 4,
  E = 5,
  ItemStr = ["a","b","c","d","e"],
  S = [
  {A,B},      % 1
  {B,C,D},    % 2
  {A,C,D,E},  % 3
  {A,D,E},    % 4
  {A,B,C},    % 5
  {A,B,C,D},  % 6
  {A},        % 7
  {A,B,C},    % 8
  {A,B,D},    % 9
  {B,C,E}     % 10
  ].


%
% Simulation of 10 items 1000 transactions.
%
% perl -e 'my $T = 1000, my $n = 10, print "NrT = $T,\nNrI = $n,\nS = [\n",  for(1..$T) { my @t =(), for(1..$n) { push @t, $_ if rand(1) >= 0.5}, print "{" . join(",",@t) . "},\n",}, print "],\n"'
%
data(10,NrI,NrT,Freq,ItemStr,S) =>
  Freq = 10,
  NrT = 1000,
  NrI = 10,
  ItemStr = ["i" ++ I.to_string : I in 1..NrI],  
  S = [
  {2,4,5,7,10},
  {2,3,4,6,7,10},
  {2,8,9},
  {2,5,6,8,9},
  {1,2,3,8,9},
  {2,4,6,8,9,10},
  {1,3,5,7},
  {4,5,6,7,9,10},
  {3,5,10},
  {1,3,4,5,10},
  {1,2,3,8,9},
  {1,3},
  {1,2,6,8,10},
  {2,3,5,7,9},
  {4,10},
  {1,2,3,4,8,10},
  {1,3,5,6,7},
  {3,7,10},
  {1,2,3,5,8,9},
  {3,5,7,8},
  {1,9},
  {2,4,5,6,7,9,10},
  {2,4,5,6,7,9,10},
  {1,3,4,6,9},
  {1,5,6,7,8,9},
  {1,2,3,5,7,10},
  {1,2,3,4,5,6,8},
  {1,2,4,5,6,8,10},
  {1,3,6,10},
  {2,3,4,5,8,9,10},
  {1,2,4,6,10},
  {4,5,6,8,9},
  {2,3,4,5,6,7,8},
  {4,9,10},
  {1,2,3,4,6,7,8},
  {4,9},
  {1,2,3,4,8,9},
  {5,10},
  {3,10},
  {2,3,5,9,10},
  {1,3,5,6,7},
  {3,5},
  {2,3,4,5,6,7,10},
  {1,3,4,6,8},
  {1,2,9},
  {2,4,6,8,9},
  {1,3,5,6,7,9,10},
  {1,4,6,8},
  {2,3,4,5,6,10},
  {1,2,4,5,6,7,10},
  {2,6,7,10},
  {1,2,4,9},
  {3,4,6,9},
  {1,3,4,6,7,10},
  {1,2,3,7,9},
  {2,3,5,6,8,9},
  {1,8},
  {2,5,6,7,8},
  {1,7,8,10},
  {1,2,4,5,6,8,9},
  {1,5,7},
  {2,3,4,8,9},
  {6,7,9},
  {1,2,3,4,5,9,10},
  {2,3,5,6},
  {1,2,4,6,7,8,9,10},
  {2,3,7,10},
  {1,3,4,10},
  {2,3,5,8},
  {4,5,6,8,9,10},
  {4,5,6,7,8,9,10},
  {1,2,4,5,7,9,10},
  {1,6,7,8,9,10},
  {2,3,6,7,8,9,10},
  {3,4,6,8,10},
  {3,4,5,10},
  {1,2,6,9,10},
  {1,2,3,4,5,8,9},
  {2},
  {2,4,5,6,10},
  {1,3,5,6,8,10},
  {7,8,9,10},
  {3,5,9,10},
  {1,2,5,6,7,8,10},
  {1,2,3,6,7,8,9,10},
  {2,3,4,9},
  {5,6,7,8,9,10},
  {1,2,3,4,5,6,9},
  {6,8,10},
  {1,2,3,6,7,8,9,10},
  {1,3,6,7,9},
  {5,6,8,9,10},
  {1,2,4,6,8},
  {2,3,4,7,10},
  {1,2,3,6,7,9},
  {1,2,3,6,7,9,10},
  {5,7,8,10},
  {1,2,3,4,8},
  {1,2,6,10},
  {4,7,8},
  {1,2,6,10},
  {1,3,6},
  {5,9,10},
  {2,3,8,10},
  {1,2,6,7,10},
  {1,5,6,8,10},
  {1,4,5,6,7,9,10},
  {1,9,10},
  {2,3,6,7,9,10},
  {1,3,5,6},
  {6,7,8},
  {2,3,4,6,7,8},
  {1,3,5,8,9,10},
  {1,2,4,5,7},
  {1,2,3,4,5},
  {1,2,4,9},
  {3,7,8},
  {4,5,7,8,9},
  {1,5,9},
  {1,2,4,5,6,10},
  {1,2,6,8,9,10},
  {1,2,4,6,7,8,9,10},
  {1,6,9},
  {1,3,8,9,10},
  {1,2,3,4,6,9,10},
  {1,3,4,5,10},
  {3,7,8,9},
  {3,4,6,7,9},
  {3,5,6,7,8,9},
  {2,5,6,10},
  {3,4,6},
  {3,5,9,10},
  {3,4,5,8,10},
  {1,3,4,7,8},
  {3,4,5,6,7,10},
  {1,3,4,5,9},
  {2,6,8,9},
  {2,3,4,5,6,9,10},
  {2,3,5,8,9,10},
  {2,4,6,7},
  {9},
  {3,4,6,8,9},
  {2,3,5,7,8,9,10},
  {1,3,5,6,7,8,10},
  {1,3,4,6,7,8},
  {1,3,5,6,9},
  {1,4,8,10},
  {2,3,4,6,7,10},
  {4,6,7,8,9,10},
  {1,7,8},
  {2,5,6,7,10},
  {1,2,5,6,7,8,10},
  {2,3,4,6,7,9,10},
  {1,3,4,6,8,9},
  {3,4},
  {1,2,3,4,5,7,9,10},
  {1,2,3,4,5,6,8,9,10},
  {3,4,5,6,9,10},
  {2,4,5,7,8,9},
  {1,2,3,4,6,8,9},
  {1,4,6,7,9},
  {1,2,10},
  {2,3,4,5,6,7,9,10},
  {1,5,7,8},
  {1,4,5,6,7,8,9,10},
  {1,4,6,8,9},
  {3,8},
  {1,2,3,4,5,8,10},
  {2,3,5,10},
  {1,2,3,4,5,6},
  {1,2,3,4,5,6,7,10},
  {2,4,6,7,8,9,10},
  {1,2,4,10},
  {2,6,7,9,10},
  {1,2,3,8},
  {1,2,3,4,6,7,8,9,10},
  {2,4,5,7,8},
  {2,5,6},
  {1,4},
  {6,9,10},
  {3,4,5,8,9},
  {3,8,10},
  {2,5,8,9},
  {2,4,6,7},
  {1,2,3,5,8,9,10},
  {1,2,3,4,5,6,8},
  {2,3,4,5,6,9,10},
  {2,5,6,9},
  {1,2,3,6,7},
  {1,2,3,6,8,9,10},
  {1,2,7,9},
  {1,2,4,5,8,10},
  {1,2,6,7,8,9},
  {2,3,4,5},
  {1,2,4,8,9},
  {1,2,3,4,5,6},
  {1,5,6,10},
  {1,5,7,10},
  {2,4,5,7,8},
  {1,2,10},
  {1,5,6,7,10},
  {1,3,8,9,10},
  {1,2,4,5,6,7,8},
  {1,3,4,5,7,8,9},
  {1,2,3,8},
  {3,4,5,7,8},
  {2,5,6,10},
  {1,2,3,5,6,7,8,10},
  {5,7,8,9,10},
  {5,7,8},
  {1,2,3,5,7,9},
  {2,3,5,7,8},
  {1,4,6,10},
  {2,3,5,7,8,9},
  {4,8,9,10},
  {1,2,3,4,6,8},
  {1,5,7,9,10},
  {1,5,6,7,9,10},
  {1,2,4,5,7},
  {2,3,5,7,8,9,10},
  {1,2,5,7},
  {1,2,3,4,5,6,8},
  {2,3,6,9,10},
  {1,3,4,6,7,9},
  {1,4,5,6,7,9},
  {2,4,5,6,7,10},
  {2,3,4,7,8,9,10},
  {3,4,5,6,7,8,9},
  {5,8,9},
  {2,5,8,9},
  {2,3,7},
  {2,4,5,7,9,10},
  {3,4,5,9,10},
  {2,4,5,7,10},
  {3,5,6,9},
  {1,5,6,7,8,9},
  {2,4,5,6,7,10},
  {2,3,4,6,7,9,10},
  {2,3,4,6,7},
  {1,6,8,9},
  {1,2,5,6,7,8,9},
  {2,3,5,6,7,8,9},
  {2,4,7,8,9},
  {8,10},
  {2,5,6,8,10},
  {1,2,3,4,8,9,10},
  {1,2,3,4,9,10},
  {2,3,4,6,9,10},
  {1,2,3,4,8,9},
  {2,3,6,8,9,10},
  {1,4,5,6,7,8,9,10},
  {1,3,4,5,6,7},
  {1,3,5,8,9,10},
  {3,4,6,7,8,9,10},
  {1,5,7,10},
  {1,5,7},
  {2,9,10},
  {1,6,7},
  {2,4,5,6,10},
  {1,2,4,5,7,8,9},
  {1,8,9,10},
  {3,6},
  {1,3,4,7,9},
  {1,2,3,4,7},
  {2,3,4,5,6,10},
  {3,4,6,7,9},
  {1,5,8,9},
  {2,3,5,7,8},
  {1,5,10},
  {1,2,3,5,7,10},
  {1,2,3,8},
  {1,4,5,6,7,8,9},
  {2,3,4,6,7,10},
  {4,6,9,10},
  {1,4,10},
  {1,3,9,10},
  {1,2,3,4,5,6,8,9,10},
  {1,2,3,4,6,7},
  {1,3,4,6,7,8,10},
  {1,2,3,6,8,9},
  {1,5,8,10},
  {1,2,4,8,10},
  {1,7,8,9},
  {1,2,3,4,6,7},
  {2,4,7,8,9,10},
  {2,3,6,7,8,9},
  {7,8,9,10},
  {1,3,8,9,10},
  {4,6,7},
  {2,3,5,6,8,9},
  {2,5,10},
  {1,2,5,6,7,9,10},
  {2,3,9,10},
  {1,2,4,5,7,8},
  {3,4,6,7,8,9,10},
  {1,2,6,8,10},
  {1,3,5,6,7,8},
  {1,3,4,5,6,7,9,10},
  {1,7,8,9,10},
  {3,6},
  {2,4,5,6,7,9},
  {2,3,4,6,8,9,10},
  {2,4,7,8,10},
  {3,4,5,6,7,9,10},
  {1,2,3,4,6,7,8},
  {2,4,5,6,10},
  {2,3,5,6,8,9},
  {2,3,4,5,6},
  {3,8,10},
  {1,6,8,9,10},
  {2,3,5,7,8,10},
  {2,3,4,5},
  {2,3,4,8,9},
  {3,4,5,7,8,9,10},
  {1,4,7,9,10},
  {5,7,8,9},
  {1,2,3,6,7,8,10},
  {1,10},
  {1,2,3,5,8,9,10},
  {3},
  {2,3,4,5,6,8},
  {1,4,5,9},
  {1,3,7,8},
  {1,2,4,5,6,7,8,10},
  {1,3,5,9},
  {1,4,6,7,8,9,10},
  {5,7,8,9,10},
  {7,8},
  {2,5,6,7,8,9,10},
  {2,5},
  {2,4,7,9},
  {3,4,5,7,8,9,10},
  {2,4,5,9,10},
  {1,4,5,7,9,10},
  {1,2,5,7,8,10},
  {1,3,6,8,9,10},
  {1,3,4,6,8},
  {6,7,8},
  {4,6,8,10},
  {1,2,3,5,6,7,8,9},
  {2,4,6,9,10},
  {4,5,6,9},
  {6,7,9,10},
  {1,3,10},
  {4,5,8,9,10},
  {2,4,6,8,9,10},
  {7},
  {2,3,4,5,6,7,10},
  {1,2,3,4,6,8,9},
  {1,3,7},
  {3,5,6,7,8},
  {2,4,5},
  {1,2,3,6,8,9,10},
  {2,4,5,6,8},
  {1,2,3,4,5},
  {1,2,3,7,8,9},
  {1,5,7,10},
  {3,5,6,7},
  {1,3,5,6,8,9},
  {2,5,6,7,9,10},
  {1,4,7,8,10},
  {4,5,8,10},
  {1,2,3,4,5,8,10},
  {1,8,9,10},
  {1,6,7},
  {1,2,4,6,7},
  {1,2,5,6,7,8},
  {7,8,9,10},
  {1,3,4,5,7,10},
  {1,2,3,4,5,6,7},
  {1,2,3,4,5,9},
  {1,2,3,5,8},
  {7,8},
  {1,2,3,4,9,10},
  {1,4,6,7,9,10},
  {1,4,6,8},
  {1,2,3,4,6,8},
  {1,2,3,5,7,8,10},
  {1,3,4,6,7,9,10},
  {2,4,6,8,9,10},
  {2,3,5,8,10},
  {1,3,4,5,6},
  {1,2,3,5,6},
  {2,3,4,5,6,7,9},
  {2,3,4,5,8,9,10},
  {1,5,6,7,9},
  {1,8,9,10},
  {1,2,4,5,6,8,9},
  {5,8,10},
  {1,2,3,5,6,10},
  {2,3,5,6,8,9,10},
  {5,6,7,9,10},
  {2,3,4,6},
  {3,9},
  {3,4,5,7},
  {1,5,6,7,8,9},
  {3,4,10},
  {4,7,8,10},
  {1,2,4,5,6,8,9,10},
  {3,5,7,8},
  {3,5,7,9,10},
  {1,5,9,10},
  {4,7,9},
  {2,5,7,8},
  {6,7,9},
  {3,4},
  {3,10},
  {1,2,3,5,8,9},
  {2,4,6,7,8,9},
  {4,6,7},
  {2,4,6,7,10},
  {1,3,4,5,6},
  {1,3,4,5,7},
  {2,3,5,6,8,9,10},
  {3,5,10},
  {2,3,6,8,9,10},
  {4,5,8,9,10},
  {5,6,7,9},
  {5,10},
  {2,6,9,10},
  {1,8,9,10},
  {1,6,8,10},
  {4,5,10},
  {1,2,5,6,8},
  {1,2,3,7,8,10},
  {2,4,5,6,7},
  {1,2,3,5,7,9,10},
  {1,3,4,6,7,8,10},
  {1,2,5,7,8,10},
  {1,4,7,9},
  {1,2,10},
  {1,9},
  {5,6,7,10},
  {1,5,7,8,10},
  {2,3,7,8,10},
  {1,7,8},
  {2,5,8,9},
  {2,3,5,6,9},
  {1,2,3,4,6,10},
  {3,4,5,6,7,8},
  {1,3,4,5},
  {1,2,3,5,7,8,10},
  {1,5,6,7,10},
  {1,3,5},
  {4,8},
  {1,2,3,4,5},
  {4,6,7,10},
  {1,2,5,6,7,8,9,10},
  {5,6,7,10},
  {3,4,8},
  {1,2,4,5,7,9},
  {2,4,7,9,10},
  {1},
  {1,5,6,9},
  {3,7,8,9},
  {1,2,3,4,5,6,8},
  {1,3,6,9,10},
  {2,3,4,6,9,10},
  {3,4,5,6,7,8},
  {1,3,6,8,9},
  {2,3,4,5,6,7,8,9,10},
  {1,2,5,6,7,8,9,10},
  {3,4,7},
  {1,3,10},
  {1,2,3,4,7},
  {4,6,8},
  {1,2,6,7,10},
  {1,2,9,10},
  {6,8,9,10},
  {1,2,4,5,10},
  {3,6,7,9},
  {1,5,6,7,8,9},
  {1,2,3,8,9,10},
  {1,2,3,7,8},
  {3,7,8},
  {2,4,5,6},
  {1,2,4,5,6,8,10},
  {1,3,7,9,10},
  {1,2,3,5,6,8,9,10},
  {1,4,10},
  {5},
  {3,4,8,9,10},
  {4,5,6,10},
  {5,7,8,9,10},
  {1,2,3,5,7,10},
  {3,7,8},
  {2,4,5},
  {1,2,3,4,6,7,8},
  {4,7,9,10},
  {3,5,6,9},
  {1,2,3,7,8,9,10},
  {2,4,5,6,7,8,9},
  {2,3,4,5,6,7},
  {2,3,5,6,8,9},
  {2,4,6,7,8,9,10},
  {1,2,5,6,7,9,10},
  {3,7,8,9,10},
  {2,3,4,7,9,10},
  {3,4,5,6,7,8},
  {1,2,5,6,8,9},
  {1,3,5,8},
  {1,3,4,5,7,8,9},
  {1,2,5,6,8,10},
  {2,3,6,10},
  {3,4,7,8,9,10},
  {1,2,6,7,8,9},
  {1,2,4,7},
  {3,5,6,8,9},
  {1,3,4,5,7,8,9},
  {2,3,7,8,9},
  {4,5,6,7,9,10},
  {2,3,7,8,9,10},
  {1,2,9,10},
  {1,3,5,9},
  {1,2,6,10},
  {1,2,3,5,6,8,9},
  {1,2,8,9},
  {1,2,3,4,5,7,9},
  {3,4,5,10},
  {1,5,6,7,10},
  {2,4,8,9},
  {2,3,4,6,9,10},
  {1,3,6,9,10},
  {1,8,9},
  {2,3,4,6,7,8,10},
  {3,5,6,7,9,10},
  {1,3,6,7,8},
  {1,3,4,5,6,7,8,9},
  {2,6,8},
  {4,5,6,8,10},
  {3,4,6,7,8,9,10},
  {4,5,10},
  {2,4,5,6,7},
  {1,3,4,5,6,7,8,10},
  {1,2,5,8,9,10},
  {2,4,5,8,9},
  {3,8,10},
  {4,7,8,10},
  {2,3,8,9,10},
  {4,6,7,10},
  {7,9},
  {1,3,8,9,10},
  {1,2,4,5,7},
  {1,2,4,8,9,10},
  {1,2,3,5,10},
  {1,2,4,5,7,9,10},
  {2,4,5,6,9,10},
  {5,8},
  {2,3,5,7,10},
  {4,5,6,7,8,9,10},
  {2,3,6,7,9},
  {1,2,5,7,10},
  {2,3,4,5,6,7,8,9},
  {4,7,8,10},
  {1,3,4},
  {4,6},
  {4},
  {1,3,4,5,6,7,9},
  {1,2,4,5,8,9,10},
  {2,3,4,7,8},
  {2,3,5,6,7,10},
  {1,2,4,5,6,8,9,10},
  {1,2,3,4,6},
  {1,3,5,7,9},
  {1,2,3,7,9},
  {1,2,3,4,7,8,9,10},
  {1,3,4,5,6,8,9,10},
  {2,7,8,9},
  {2,3,4,6,8},
  {1,3,6,7,8,9,10},
  {4,5,6,7,9},
  {1,2,4,7,8,9,10},
  {1,2,3,4,5,7,8,10},
  {1,3,4,6,7,8},
  {3,7,8,9},
  {1,2,3,5,6,7,8,9},
  {2,3,4,6,9},
  {2,5,7},
  {1,2,4,6,7,9,10},
  {1,3,6,8,10},
  {1,7,8},
  {4,6},
  {2,3,4,6,7,8,10},
  {1,4,6},
  {1,2,3,5,7,8,9,10},
  {2,4,5,9},
  {2,4,6,7,9},
  {4,6,7,9,10},
  {1,4,10},
  {3,4,5,6,8,10},
  {1,4,5,6,8,9},
  {2,3,6,7},
  {2,5,7,8,9,10},
  {5,7,8},
  {2,5,7,9},
  {9},
  {3,4,7,10},
  {2,3,4,5,7,8,10},
  {1,2,6,7,9,10},
  {4,5,7,8,10},
  {2,6,7,9,10},
  {1,7,10},
  {4,5,6,8,9,10},
  {1,4,5,8,10},
  {3,4,5,6,7,8},
  {6,7,8},
  {2,5,10},
  {1,3,6,8,9,10},
  {2,3,6,7,9,10},
  {1,3,5,6,7,9},
  {1,5,10},
  {3,4,6,10},
  {1,2,3,5,6,7,8,9,10},
  {2,3,7,9,10},
  {2,3,4,5,6,8},
  {4,5,6,7,8,10},
  {1,2,7,8,9,10},
  {1,6,10},
  {1,5,6,7,10},
  {2,4,5,6},
  {5,6,7,10},
  {3,4,5,8,10},
  {2,10},
  {1,4,7,8,9,10},
  {1,2,4,5,6,8,10},
  {1,3,5,6,7,9},
  {3,4,6,8,10},
  {1,4,6,8,9,10},
  {1,3,6,7,9,10},
  {1,2,5,6,8,9},
  {1,3,5},
  {2,3,8,9,10},
  {2,3,5,8},
  {1,4,5,6,10},
  {5,7,10},
  {3,6,7,8,10},
  {2,3,6,7,8,10},
  {3,5,6,7,9},
  {1,2,3,4,6,9},
  {2,3,5,6},
  {2,5,6,7,8},
  {2,5,6,7},
  {3,4,5,10},
  {2,3,4,6,7,8,9},
  {2,5,6,7,9,10},
  {1,2,3,7},
  {2,3,5,6},
  {1,4,6,7,9},
  {3,5,6,7,8},
  {1,2,4,5,7,9,10},
  {1,3,4,5,6,7,10},
  {1,2,7,8,10},
  {1,3,4,8},
  {4,6,8,10},
  {4,10},
  {1,3,4,9},
  {4,5,7,8,9,10},
  {1,10},
  {2,4},
  {1,2,3,4,6,7,10},
  {3,4,6,8,9,10},
  {2,3,4,6},
  {1,2,3,9},
  {2,4,5,6,8,9},
  {1,2,3,4,5,7,9,10},
  {1,2,6,8,10},
  {1,2,3,6,8,9},
  {1,3,4,5,6,9},
  {1,4,8,9},
  {7},
  {1,2,3,4,5,8,10},
  {2,3,4,7},
  {1,4,6,7,8,9},
  {1,2,4,7,10},
  {2,4,6,7,8,10},
  {1,3,5,6,7,10},
  {2,4,5,8,9},
  {1,2,4,7,8},
  {2,5,6,8,9},
  {1,5,10},
  {1,3,7},
  {1,2,7,8},
  {1,6,7},
  {1,2,3,5,6,8,9,10},
  {1,3,4,6,8,10},
  {2,3,10},
  {1,2,3,4,5,6,10},
  {3,5,10},
  {1,2,4,6,7,8,9},
  {1,2,3},
  {1,6,9,10},
  {6,7,8,9},
  {2,7,9},
  {1,4,5,7,8,9,10},
  {1,6},
  {1,4,5,8,9,10},
  {1,2,6,9},
  {1,4,5,8,9,10},
  {3,8},
  {1,2,3,4,5,7,10},
  {1,2,3,4,5,7,8,9},
  {4,6,8,9,10},
  {1,2,3,7,9,10},
  {1,3,5,6,8,10},
  {1,2,10},
  {1,2,3,6,7,9,10},
  {1,2,4,5,9,10},
  {1,3,5,7,10},
  {1,3,4,5,6,9},
  {2,4,7,8,9},
  {4,6,7},
  {5,10},
  {1,2,5,6,7,8,9,10},
  {1,4,5,6,8},
  {3,5,6,8},
  {2,3,8,9,10},
  {1,3,6,7},
  {4,5,6,8,9,10},
  {1,2,3,6,7,8},
  {1,2,3,4,8},
  {1,2,4,6,7,9,10},
  {2,4,5,8,9},
  {3,5,7,8},
  {1,4,6,7,9},
  {1,4,5,7,9,10},
  {5,6,7,8,10},
  {1,2,6,8,9,10},
  {1,2,4,6,7,8,9},
  {2,4,8,10},
  {3,4,5,6,7,9,10},
  {2,5,6},
  {1,4,6,8,9,10},
  {2,4,5},
  {1,3,6,7},
  {2,4,5,7,8,9},
  {2},
  {2,3,5,6,7},
  {1,3,4,6,8},
  {7,10},
  {1,3,7,8,9},
  {2,9},
  {3,5,7,9,10},
  {1,2,3,4,5,6,8,10},
  {5,6},
  {5,8},
  {1,5,8,10},
  {2,5,6,7,8,9,10},
  {1,3,5,8,9,10},
  {2,3,5,6,8},
  {1,3,4,5,6,7,8},
  {2,3,9,10},
  {1,2,7,8,9,10},
  {1,2,3,5,6},
  {1,3,6,8,9,10},
  {6,7,8,9},
  {1,4,5,6,7,9,10},
  {1,3,6},
  {3,4,5,10},
  {1,3,5,7,8,9},
  {2,3,4,8,10},
  {1,2,5,6,7,8,9},
  {2,4,5,7,8},
  {1,2,3,4,5,6,8,9,10},
  {1,3,5,6,7},
  {2,5,6,8,9},
  {1,2,6,7,8,10},
  {1,2,6,8},
  {1,2,4,6,9},
  {1,2,8,10},
  {1,2,3,5,7,8,9,10},
  {1,2,4,6,8,9,10},
  {3,4,10},
  {1,2,3,8,9,10},
  {4,7,10},
  {1,5,6,8,9},
  {1,3,5,6,8,9},
  {1,2,7},
  {1,4,5,7,9},
  {1,3,5,7,8},
  {2,3,4,5,6,8,10},
  {2,4,8,9,10},
  {2,3,4,6,9},
  {1,2,3,6,8,9},
  {1,3,4,7,9,10},
  {2,7,8,9,10},
  {1,2,3,7,9,10},
  {1,3,4,5,6,8},
  {1,2,5,6,9},
  {2,3,4,7,9},
  {1,2,3,4},
  {2,3,4,5,7,8,9,10},
  {1,2,3,4,7},
  {2,4,9},
  {3,6,7,9,10},
  {3,4,5,8,10},
  {4,5,6,7,8,10},
  {4,6,7},
  {1,2,4,5,8,9},
  {9},
  {2,5,8,9},
  {4,5,6,7,10},
  {2,3,5,7,8,9},
  {1,2,4,6,10},
  {1,3,5,8,9,10},
  {3,8},
  {1,2,3,4,6,9,10},
  {1,4,8,9,10},
  {1,2,4,5,7},
  {1,3,4,6,7,10},
  {1,3,8},
  {1,2,3,7,9,10},
  {2,4,5,6},
  {8,9,10},
  {1,2,4,8,10},
  {1,2,4,5,8,9,10},
  {2,3,5,8},
  {1,2,3,8,9,10},
  {3,5,7},
  {4,5,6,7,8,10},
  {4,7,10},
  {2,3,4,5,6,7,8,9,10},
  {3,6,10},
  {1,3,4,6,7,8,9,10},
  {1,3,4,5,7,9,10},
  {1,3,4,5,6,7,10},
  {5,6,7,9,10},
  {4,6,8,9},
  {1,5,8,9},
  {1,3,4,6,7,8,9,10},
  {3,7,8,9,10},
  {2,6,7,9,10},
  {3,4,7,9,10},
  {2,4,8,10},
  {1,4,5,7,8,9,10},
  {1,3,4,6,7,9,10},
  {2,5,7,9},
  {1,4,6,8,9,10},
  {2,3,4,8},
  {3,5,7,8,10},
  {1,2,4,5,7,10},
  {1,2,3,5,7,8,10},
  {1,2,4,5,8,9},
  {1,2,4,5,6,9},
  {2,8,9},
  {4,6,7,10},
  {3,4,6,8,9,10},
  {2,3,6,7,9},
  {2,3,5,7,8},
  {1,3,4,5,10},
  {1,2,3,4,5,6,10},
  {1,2,4,5,6,9,10},
  {1,3,5,6,9},
  {2,4,5,7,8,10},
  {2,5,6,7,8,9},
  {3,4,5,10},
  {2,3,5,7,8,9},
  {1,5,6,7,8},
  {1,4,8,9},
  {1,2,6,7,8,9},
  {3,7,9,10},
  {1,2,3,7},
  {3,4,5,8,9},
  {2,4,7,10},
  {2,8,9,10},
  {4,6,7,8},
  {2,3,7,8,9},
  {1,5,6,8,9,10},
  {1,3,4,6,8,9,10},
  {3,6,10},
  {1,3,5,7,9,10},
  {2,4,5,8,10},
  {1,2,5,7,9,10},
  {1,5,7,9,10},
  {1,2,7,8,10},
  {2,3,4,5,10},
  {2,5,7,8},
  {1,5,6,7},
  {4,5,6,7,10},
  {1,2,3,4,5,6,7,8},
  {2,4,5,7,8,9,10},
  {1,2,3,4,5,9},
  {2,5,6,9},
  {3,8,9},
  {1,2,4,5,7},
  {1,8},
  {3,4,6,7,8,10},
  {1,3},
  {5,6,7,8},
  {1,4,5,7,8,10},
  {2,9},
  {2,3,7,9},
  {2,3,4,7,8},
  {3,4,5,6,7},
  {1,4,10},
  {1,2,7},
  {2,5,6,7},
  {4,8,9,10},
  {2,3,4,5,6,8,10},
  {1,2,6,7,8,9,10},
  {4,8,9,10},
  {2,5},
  {2,4,7,10},
  {1,2,4,7,8},
  {2,5,6,7,8,9,10},
  {1,3,4,9},
  {1,5,6,7,9,10},
  {1,2,3,4,6,9,10},
  {2,5,7,9},
  {1,2,7,8,9,10},
  {3,4,5,6,9},
  {1,2,4,5,6,8,9,10},
  {1,2,7,8,10},
  {1,3,4,5,6,8,9},
  {1,2,3,5,6,9,10},
  {5,6,7,10},
  {3,4,7,8,9,10},
  {3,6,7,9,10},
  {2,3,4,7,8,9},
  {3,5,6,7,9},
  {2,5,9,10},
  {1,4,6,7,9},
  {1,2,3,5,6,8,9},
  {2,4,5,6,7},
  {1,3,5,7,8,9,10},
  {7},
  {6,7,8,9,10},
  {2,4,5,8,9},
  {2,3,6,9},
  {1,2,4,5,9,10},
  {1,2,3,4,5,8,9,10},
  {2,5,7,8,9,10},
  {2,4,7,9,10},
  {2,3,6,7,8,9},
  {1,3,4,5,7,8,9,10},
  {4,5,10},
  {1,3,5,6,7,8,10},
  {2,3,5,7,8,9},
  {3,5,8,10},
  {1,2,3,4,5,6,8},
  {2,3,4,5,6,7,8,9,10},
  {4,5,9},
  {1,2,4,5,6},
  {1,4,7,9,10},
  {6,8,9,10},
  {1,3,6,7},
  {1,4},
  {1,5,8,10},
  {8},
  {3,4,6,8,9,10},
  {1,2,3,5,6,7},
  {3,5,6,8},
  {1,2,3,4},
  {1,2,5,6,7,8,10},
  {1,2,6,8,9},
  {1,4,5,7,8,9},
  {2,3,5,8,10},
  {1,2,5,7,9},
  {3,4,6,8},
  {2,3,4,6,9,10},
  {1,4,5,10},
  {2,4,6,9,10},
  {1,3,4,5,7,8,9},
  {2,3,6,8,9},
  {5,6,7},
  {2,4,5,7,8},
  {2,3,4,5,7,9,10},
  {3,5,7,9,10},
  {1,2,4,10},
  {1,5,10},
  {1,2,4,7,8,10},
  {2,4,5,7,10},
  {1,3,4,7,9},
  {1,3,4,8,9},
  {1,3,4,5,6,7,9},
  {2,4,7,10},
  {1,3,4,6,10},
  {1,2,3,6,7},
  {1,5,6,7},
  {3,4,5,6,7,9,10},
  {7,8},
  {1,8,9,10},
  {1,4,6,7,8,9},
  {4,5,6,7,8,10},
  {2,4,5,7,10},
  {3,4,7,8,9,10},
  {1,3,4},
  {1,5,6,7,8,9,10},
  {1,3,4,5,6,10},
  {1,3,4,5,8},
  {1,3,6,7},
  {3,4,5},
  {2,3,4,5,6,8,9,10},
  {2,3,4,5,6,10},
  {1,2,4,6,9},
  {3,4,5,6,8,9},
  {1,5,8,10},
  {2,4,5,6,8,9},
  {3,5,9},
  {2,4,5,6,8,10},
  {1,2,4,5,7,8}
  ].