Lâmpadas

Você está de volta em seu hotel na Tailândia depois de um dia de mergulhos. O seu quarto tem duas lâmpadas. Vamos chamá-las de $A$ e $B$. No hotel há dois interruptores, que chamaremos de $I_1$ e $I_2$. Ao apertar $I_1$, a lâmpada $A$ troca de estado, ou seja, acende se estiver apagada e apaga se estiver acesa. Se apertar $I_2$, ambas as lâmpadas $A$ e $B$ trocam de estado.

As lâmpadas inicialmente estão ambas apagadas. Seu amigo resolveu bolar um desafio para você. Ele irá apertar os interruptores em uma certa sequência, e gostaria que você respondesse o estado final das lâmpadas $A$ e $B$.

Entrada

A primeira linha contém um número $N$ que representa quantas vezes seu amigo irá apertar algum interruptor. Na linha seguinte seguirão $N$ números, que pode ser $1$, se o interruptor $I_1$ foi apertado, ou $2$, se o interruptor $I_2$ foi apertado.

Saída

Seu programa deve imprimir dois valores, em linhas separadas. Na primeira linha, imprima $1$ se a lâmpada $A$ estiver acesa no final das operações e $0$ caso contrário. Na segunda linha, imprima $1$ se a lâmpada $B$ estiver acesa no final das operações e $0$ caso contrário.

Restrições

• $1 \leq N \leq 10^5$

Informações sobre a pontuação

• Em um conjunto de casos de teste equivalente a $20$ pontos, $N = 3$.

Exemplos

Exemplo de entrada 1

3
1 2 2

Exemplo de saída 1

1
0

Exemplo de entrada 2

4
2 1 2 2

Exemplo de saída 2

0
1