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:
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 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 |