Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SOMAS07 - Somas proibidas

Nicolau e Carlos são irmãos gêmeos. Eles gostam muito de Matemática e, para desafiarem um ao outro, inventam vários jogos matemáticos.

Carlos inventou um jogo no qual ele dá vários cartões numerados com inteiros positivos distintos a Nicolau. Nicolau tem que dividir esses cartões em dois grupos de forma que a soma de qualquer par de cartões em um mesmo grupo nunca esteja em uma lista de somas proibidas, escolhida por Carlos. Se Nicolau conseguir fazer a divisão, ele ganha; caso contrário, seu irmão ganha.

Nicolau quer uma estratégia vencedora para este jogo, mas isso é muito difícil quando há muitos cartões e, por isso, ele pediu a sua ajuda.

Tarefa

Escreva um programa que, dados os números escritos nos cartões e as somas proibidas por Carlos, determine se é possível fazer a divisão em dois grupos, e, em caso afirmativo, exiba uma possível divisão.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha contém dois inteiros N e M (1 ≤ N ≤ 100.000, 1 ≤ M ≤ 100), que são o número de cartões que Nicolau tem que dividir, e quantas somas foram proibidas por Carlos. A segunda linha contém N inteiros distintos I (1 ≤ I ≤ 1.000.000.000), que são os números escritos nos cartões de Nicolau. A terceira linha contém M inteiros J (3 ≤ J ≤ 1.999.999.999), que são as somas que Carlos proibiu.

Saída

Seu programa deve imprimir, na saída padrão, duas linhas, representando uma possível divisão dos cartões. Cada linha deve conter um conjunto de inteiros representando um grupo: um inteiro, indicando quantos cartões estão naquele grupo, seguido dos números escritos nos cartões daquele grupo; todos os inteiros de uma mesma linha devem ser separados por espaços em branco.

Caso existam várias divisões possíveis, você pode imprimir qualquer uma delas. Se não for possível realizar a divisão, você deve imprimir -1 nas duas linhas.

Exemplo

Entrada:
14 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 4 9 16 25

Saída:
7 2 13 11 4 9 1 6
7 10 12 5 3 14 8 7

Entrada:
4 5
1 2 3 4
3 4 5 6 7

Saída:
-1
-1

Entrada:
5 1
1 2 3 4 5
10

Saída:
5 1 2 3 4 5
0


Adicionado por:Wanderley Guimarăes
Data:2012-07-21
Tempo limite:0.434s-0.868s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Seletiva IOI 2007

hide comments
2012-09-22 21:16:04 Gabriel Luís Mello Dalalio [ITA]
O juiz especial vai ser feito ainda, foi mal galera! Por enquanto siga o conselho do Fonseca
2012-09-09 03:01:49 Fernando Fonseca [ITA]
Imprima sempre a divisăo que contém o primeiro cartăo na linha de cima, e ordene ambos os conjuntos. Aparentemente, esse problema năo tem corretor especial como deveria...
2012-08-29 22:33:59 Ricardo Oliveira [UFPR]
Fato. Tive de ordenar ambos os conjuntos para conseguir AC.
2012-08-06 21:57:09 Alexandre [UFG]
"Caso existam várias divisőes possíveis, vocę pode imprimir qualquer uma delas."
Năo Acredite nisso!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.