program megasena;

{ ============================================================ }
{ IMPLEMENTACAO DO TAD CONJUNTO                                 }
{ Vetor ordenado em ordem crescente; posicoes 0 e MAX+1        }
{ reservadas para sentinelas                                    }
{ ============================================================ }

const
    MAX = 200;

type
    conjunto = record
        tam:     longint;               { quantidade de elementos }
        proximo: longint;               { cursor para incrementar_proximo }
        v:       array [0..MAX + 1] of longint;
    end;

var
    sorteio, aposta, intersec: conjunto;
    N, M, i, num_acertos: longint;

{ ============================================================ }

procedure inicializar_conjunto(var c: conjunto);
{ Cria um conjunto vazio. Deve ser chamado antes de qualquer operacao. }
{ Custo: constante. }
begin
    c.tam := 0;
end;

{ ------------------------------------------------------------ }

function conjunto_vazio(c: conjunto): boolean;
{ Retorna true se o conjunto c eh vazio e false caso contrario. }
{ Custo: constante. }
begin
    conjunto_vazio := c.tam = 0;
end;

{ ------------------------------------------------------------ }

function cardinalidade(c: conjunto): longint;
{ Retorna a cardinalidade do conjunto c. }
{ Custo: constante. }
begin
    cardinalidade := c.tam;
end;

{ ------------------------------------------------------------ }

function pertence(x: longint; c: conjunto): boolean;
{ Busca binaria - possivel pois o vetor esta ordenado. }
{ Retorna true se x pertence ao conjunto c. }
{ Custo: log(n). }
var
    ini, fim, meio: longint;
    achou:          boolean;
begin
    ini   := 1;
    fim   := c.tam;
    achou := false;
    while (ini <= fim) and not achou do
    begin
        meio := (ini + fim) div 2;
        if c.v[meio] = x then
            achou := true
        else if c.v[meio] < x then
            ini := meio + 1
        else
            fim := meio - 1;
    end;
    pertence := achou;
end;

{ ------------------------------------------------------------ }

procedure inserir_conjunto(x: longint; var c: conjunto);
{ Insere x no conjunto c mantendo o vetor ordenado. }
{ Nao insere se x ja pertence ao conjunto. }
{ Custo: linear (desloca elementos para abrir espaco). }
var
    i: longint;
begin
    if not pertence(x, c) then
    begin
        i := c.tam;
        { desloca elementos maiores que x uma posicao para a direita }
        while (i >= 1) and (c.v[i] > x) do
        begin
            c.v[i + 1] := c.v[i];
            i := i - 1;
        end;
        c.v[i + 1] := x;
        c.tam := c.tam + 1;
    end;
end;

{ ------------------------------------------------------------ }

function interseccao(c1, c2: conjunto): conjunto;
{ Obtem a interseccao dos conjuntos c1 e c2. }
{ Usa dois apontadores - eficiente pois os vetores estao ordenados. }
{ Custo: linear. }
var
    i, j, k: longint;
    intersec: conjunto;
begin
    inicializar_conjunto(intersec);
    i := 1;
    j := 1;
    k := 0;
    while (i <= c1.tam) and (j <= c2.tam) do
        if c1.v[i] < c2.v[j] then
            i := i + 1
        else if c1.v[i] > c2.v[j] then
            j := j + 1
        else
        begin
            { elemento esta nos dois conjuntos: pertence a interseccao }
            k := k + 1;
            intersec.v[k] := c1.v[i];
            i := i + 1;
            j := j + 1;
        end;
    intersec.tam := k;
    interseccao := intersec;
end;

{ ------------------------------------------------------------ }

procedure iniciar_proximo(var c: conjunto);
{ Inicializa o cursor para percorrer o conjunto sem remover elementos. }
{ Custo: constante. }
begin
    c.proximo := 1;
end;

{ ------------------------------------------------------------ }

function incrementar_proximo(var c: conjunto; var x: longint): boolean;
{ Avanca o cursor e devolve o proximo elemento em x. }
{ Retorna false quando o conjunto foi percorrido por completo. }
{ Custo: constante. }
begin
    if c.proximo <= c.tam then
    begin
        x         := c.v[c.proximo];
        c.proximo := c.proximo + 1;
        incrementar_proximo := true;
    end
    else
        incrementar_proximo := false;
end;

{ ============================================================ }
{ PROCEDIMENTOS AUXILIARES DO PROGRAMA DA MEGA SENA            }
{ ============================================================ }

procedure ler_conjunto(var c: conjunto; tam_aposta: longint);
{ Le tam_aposta numeros da entrada e os insere no conjunto c. }
{ inicializar_conjunto deve ser chamado antes desta procedure. }
var
    i, num: longint;
begin
    inicializar_conjunto(c);
    for i := 1 to tam_aposta do
    begin
        read(num);
        inserir_conjunto(num, c);
    end;
end;

procedure imprimir_conjunto(c: conjunto);
{ Imprime todos os elementos do conjunto sem remove-los. }
var
    x: longint;
begin
    iniciar_proximo(c);
    while incrementar_proximo(c, x) do
        write(x, ' ');
    writeln();
end;

{ ============================================================ }
{ PROGRAMA PRINCIPAL                                           }
{ ============================================================ }

begin
    { Formato da entrada:
        linha 1  : 6 dezenas sorteadas
        linha 2  : N (numero de apostadores)
        linhas seguintes: para cada apostador, M seguido de M dezenas }

    writeln('Quais foram as 6 dezenas sorteadas? ');
    ler_conjunto(sorteio, 6);

    writeln('Qual o número de apostadores? ');
    read(N);

    { processa cada aposta }
    for i := 1 to N do
    begin
        writeln('Qual a quantidade de dezenas da aposta ', i, '?');
        read(M);
        writeln('Lendo dezenas... ');
        ler_conjunto(aposta, M);

        { calcula a interseccao entre a aposta e o sorteio }
        intersec    := interseccao(sorteio, aposta);
        num_acertos := cardinalidade(intersec);

        { classifica o resultado }
        if num_acertos = 6 then
        begin
            write('Aposta ', i, ' ganhou a MEGA-SENA! Dezenas: ');
            imprimir_conjunto(intersec);
        end
        else if num_acertos = 5 then
        begin
            write('Aposta ', i, ' ganhou a QUINA! Dezenas: ');
            imprimir_conjunto(intersec);
        end
        else if num_acertos = 4 then
        begin
            write('Aposta ', i, ' ganhou a QUADRA! Dezenas: ');
            imprimir_conjunto(intersec);
        end;
        { apostas com 3 ou menos acertos nao recebem premio: nao imprimimos nada }
    end;
end.