XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: calculo.x, onde x deve ser c, cpp, java, js ou py

Cálculo

Os computadores armazenam todas as informações usando representações binárias, ou seja, representações que utilizam apenas zeros ('0') e uns ('1'). Há vários padrões para a representação de informação na forma binária, como por exemplo "complemento-de-dois" (usado para números inteiros), "ascii" (usado para caracteres e letras sem acentos), ou "ieee-754" (usado para números reais).

Neste problema vamos usar a representação "obi-2015" para certos valores positivos e menores do que 1. Na "obi-2015", o número é representado por uma sequência de 0"s e 1"s de comprimento arbitrário. Lendo a representação da esquerda para a direita, o primeiro dígito binário representa o valor 2-1, o segundo representa 2-2, o terceiro 2-3, e assim por diante. A representação utiliza sempre o menor número de dígitos possível (ou seja, desta forma o dígito mais à direita é sempre 1).

Por exemplo, a sequência de dígitos binários 0 1 representa o seguinte valor:

0*2-1 + 1*2-2 = 0.25

Já a sequência de dígitos binários 1 0 1 0 1 1 representa o seguinte valor:

1*2-1 + 0*2-2 + 1*2-3 + 0*2-4 + 1*2-5 + 1*2-6 = 0.671875

Sua tarefa é, dados dois números X e Y, representados no padrão obi-2015, determinar a representação da soma X+Y, também no padrão obi-2015.

Entrada

A primeira linha contém os inteiros M e N, representando respectivamente o número de dígitos binários de X e de Y. A segunda linha contém M números X_i, representando X no padrão obi-2015. A terceira linha contém N números Y_j, representando Y no padrão obi-2015.

Saída

Seu programa deve produzir uma única linha, contendo a representação do valor X + Y no padrão obi-2015.

Restrições

  • 1 ≤ M, N ≤ 103
  • 0 < X , Y < 1
  • X_i ∈ {0, 1}, para 0 ≤ i ≤ M
  • Y_j ∈ {0, 1}, para 0 ≤ j ≤ N
  • X+Y < 1

Informações sobre a pontuação

  • Em um conjunto de casos de teste somando 20 pontos, N ≤ 5 e M ≤ 5.

Exemplos

Entrada
2 3
0 1
0 0 1
Saída
0 1 1
	
Entrada
5 4
1 0 1 1 1
0 0 0 1
Saída
1 1 0 0 1
	
Entrada
4 5
0 1 1 1
0 0 1 1 1
Saída
1 0 1 0 1
	
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação