teamA(marikoShinoda).
teamK(tomomiItano).

akb(X) :- teamA(X).
akb(X) :- teamK(X).
akb(X) :- teamB(X).


parent(ieyasu,hidetada).
parent(hidetada,iemitsu).
parent(iemitsu,ietsuna).
parent(iemitsu,tsunayoshi).
parent(iemitsu,tsunashige).
parent(tsunashige,ienobu).
parent(ienobu,ietsugu).

grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).


merge([], X, X).
merge(X, [], X).
merge([X|L1],[Y|L2],[X|L3]) :- X =< Y, merge(L1,[Y|L2],L3).
merge([X|L1],[Y|L2],[Y|L3]) :- X > Y, merge([X|L1],L2,L3).

partition([], [], []).
partition([X], [X], []).
partition([X, Y | Rest], [X | L1], [Y | L2]) :- partition(Rest, L1, L2).

msort([], []).
msort([X], [X]).
msort([X, Y | L1], L2) :-
  partition([X, Y | L1], L3, L4),
  msort(L3, L5),
  msort(L4, L6),
  merge(L5, L6, L2).