Cálculo

1112
Tempo Limite: 10 | Nível: 4

Descrição

Os computadores armazenam todas as informações usando representações binárias, ou seja, representações que utilizam apenas 0’s e 1’s. 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:

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

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 Xi , representando X no padrão obi-2015. A terceira linha contém N números Yj , 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 ≤ 10^3
• 0 < X, Y < 1
• Xi ∈ {0, 1}, para 0 ≤ i ≤ M
• Yj ∈ {0, 1}, para 0 ≤ j ≤ N
• X +Y < 1


Exemplos de Entrada Exemplos de Saída

4 5
0 1 1 1
0 0 1 1 1

1 0 1 0 1

5 4
1 0 1 1 1
0 0 0 1

1 1 0 0 1

2 3
0 1
0 0 1

0 1 1

Efetue Login ou Cadastre-se para submeter uma solução.



Adaptado por Erich Rodrigues | Competição: OBI 2015, Nível 2, Fase 2