Anna e Bruno são arqueólogos. Eles estão investigando ruínas no Irã.

Suas tarefas são as seguintes: Anna visita as ruínas e descobre artefatos, enquanto Bruno analisa os resultados no acampamento-base.

A investigação está programada para $Q\,(=1\,000)$ dias. Todos os dias, Anna envia os resultados para Bruno usando um dispositivo de comunicação. Os resultados de cada dia são representados por um inteiro $X$.

Anna só pode usar o dispositivo de comunicação uma vez por dia. Ele pode enviar uma sequência de comprimento $N\,(=150)$ formada por 0 e 1.

No entanto, o dispositivo está avariado. Há várias posições avariadas na sequência de comprimento $N$. Em uma posição avariada, ele sempre envia o valor 0, independentemente do valor definido. Quando Anna envia uma sequência, ela pode ver as posições avariadas, mas Bruno não as conhece. As posições e a quantidade de posições avariadas podem mudar todos os dias.

Existe o risco de que a investigação sofra atrasos. Como você é candidato a participante de uma competição internacional de programação no Irã, Anna e Bruno pedem que você escreva um programa que transmita os resultados da investigação.

Tarefa

Escreva dois programas que realizem a comunicação entre Anna e Bruno.

• Dados o comprimento da sequência $N$, o inteiro a transmitir $X$, a quantidade de posições avariadas $K$ e suas posições $P$, o primeiro programa define a sequência $S$ enviada por Anna.
• Dada a sequência $A$ recebida por Bruno, o segundo programa recupera o inteiro $X$.

Em uma posição em que o dispositivo funciona, as sequências $S$ e $A$ têm o mesmo valor. Em uma posição avariada, a sequência $A$ sempre tem o valor 0, independentemente do valor da sequência $S$.

Detalhes de implementação

Você deve enviar dois arquivos escritos na mesma linguagem de programação.

O primeiro arquivo é Anna.c ou Anna.cpp. Esse arquivo define a sequência enviada por Anna e implementa a função a seguir. O programa deve incluir Annalib.h.

• void Anna( int N, long long X, int K, int P[] )

Para cada caso de teste, essa função é chamada $Q=1\,000$ vezes.

• O parâmetro N é o comprimento da sequência a transmitir.
• O parâmetro X é o inteiro a transmitir.
• O parâmetro K é a quantidade de posições avariadas.
• O parâmetro P[] é uma sequência de comprimento $K$ que descreve as posições avariadas.

Na função Anna, a função a seguir deve ser chamada.

• void Set( int pos, int bit )

Essa função define um bit da sequência $S$ que será enviada pelo dispositivo de comunicação.

• O parâmetro pos é a posição a definir. pos deve ser um inteiro entre $0$ e $N-1$, inclusive. Observe que as posições são contadas a partir de $0$. Se a função for chamada com um parâmetro fora desse intervalo, seu programa será considerado Wrong Answer[1]. Não é permitido chamar essa função mais de uma vez com o mesmo parâmetro pos. Se isso ocorrer, seu programa será considerado Wrong Answer[2].
• O parâmetro bit é o valor definido na posição pos da sequência. O valor de bit deve ser 0 ou 1. Se a função for chamada com outros valores, seu programa será considerado Wrong Answer[3].

A função Set deve ser chamada exatamente $N$ vezes dentro da função Anna. Quando Anna terminar, se o número de chamadas a Set for diferente de $N$, seu programa será considerado Wrong Answer[4].

Seu programa será encerrado se a chamada de função feita por Anna for considerada inválida.

O segundo arquivo é Bruno.c ou Bruno.cpp. Esse arquivo recupera o inteiro que representa os resultados da investigação e implementa a função a seguir. O programa deve incluir Brunolib.h.

• long long Bruno( int N, int A[] )

Para cada caso de teste, essa função é chamada $Q=1\,000$ vezes.

• O parâmetro N é o comprimento da sequência recebida por Bruno.
• O parâmetro A é uma sequência de inteiros de comprimento $N$. Ela é a sequência recebida por Bruno.
• A função Bruno deve recuperar o valor de $X$ e retorná-lo.

Procedimento de avaliação

A avaliação é feita da seguinte maneira. Se seu programa for considerado Wrong Answer, ele será encerrado imediatamente.

1. Defina $\mathrm{cnt}=0$.
2. Chame a função Anna uma vez.
3. Seja $S$ a sequência definida pela função Anna. Na sequência $S$, atribua o valor 0 às posições de $P$, obtendo a sequência $A$. Chame a função Bruno uma vez com o parâmetro $A$.
4. Defina $\mathrm{cnt}=\mathrm{cnt}+1$. Se $\mathrm{cnt}<Q$, volte ao passo (2). Se $\mathrm{cnt}=Q$, vá ao passo (5).
5. Seu programa receberá uma pontuação.

Avisos importantes

• O tempo de execução e o uso de memória são calculados para os passos (1), (2), (3) e (4) do Procedimento de avaliação.
• Seu programa não deve ser considerado Wrong Answer na chamada de Anna em (2) ou de Bruno em (3). Seu programa deve executar sem erros de execução.
• Seu programa pode implementar outras funções para uso interno ou usar variáveis globais. Os programas enviados serão compilados com o avaliador e formarão um único arquivo executável. Todas as variáveis globais e funções internas devem ser declaradas como static para evitar conflitos com outros arquivos. Como os programas de Anna e Bruno serão executados como dois processos distintos durante a avaliação, eles não podem compartilhar variáveis globais.
• Em cada processo, cada uma das funções Anna e Bruno é chamada $Q=1\,000$ vezes. As variáveis utilizadas pelos seus programas devem ser inicializadas adequadamente.
• Seu programa não deve usar a entrada padrão nem a saída padrão. Seu programa não deve se comunicar com outros arquivos por nenhum método.

Compilação e execução de testes

Você pode baixar, na página da competição, um arquivo compactado que contém um avaliador de exemplo para testar seu programa. O arquivo também contém um arquivo de código-fonte de exemplo do seu programa.

Um avaliador de exemplo consiste em um arquivo de código-fonte, grader.c ou grader.cpp. Por exemplo, se seus programas forem Anna.c e Bruno.c, ou Anna.cpp e Bruno.cpp, execute os comandos a seguir para compilá-los.

• C

gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm

• C++

g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Quando a compilação for concluída com sucesso, será gerado o arquivo executável grader.

Observe que o avaliador real é diferente do avaliador de exemplo. O avaliador de exemplo será executado como um único processo, que lerá os dados da entrada padrão e escreverá os resultados na saída padrão.

Entrada do avaliador de exemplo

O avaliador de exemplo lê os seguintes dados da entrada padrão.

• A primeira linha contém um inteiro $Q$.
• Em seguida, são dadas as informações de $Q$ consultas.
• As informações de cada consulta consistem em duas linhas, como segue.
  • A primeira linha contém três inteiros $N,X,K$, separados por espaços. Isso significa que o comprimento da sequência a transmitir é $N$, o inteiro a transmitir por Anna é $X$ e há $K$ posições avariadas.
  • A segunda linha contém $K$ inteiros $P_0,P_1,\ldots,P_{K-1}$, separados por espaços. Isso significa que, para cada $i$ ($0\le i\le K-1$), a posição $P_i$ da sequência está avariada.

Saída do avaliador de exemplo

Quando o programa termina com sucesso, o avaliador de exemplo escreve as informações a seguir na saída padrão. (As aspas não são escritas de fato.)

• Se seu programa for considerado Wrong Answer, o avaliador de exemplo escreve seu tipo no formato «Wrong Answer [1]» e seu programa é encerrado.
• Se nenhuma chamada à função Anna for considerada Wrong Answer, o avaliador de exemplo escreve «Accepted» e o valor de $L^*$. Para o valor de $L^*$, consulte a seção Pontuação.

Se seu programa for considerado como vários tipos de Wrong Answer, o avaliador de exemplo informa apenas um deles.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

• $Q=1000$.
• $N=150$.
• $0\le X\le 1\,000\,000\,000\,000\,000\,000$.
• $1\le K\le 40$.
• $0\le P_i\le N-1$ ($0\le i\le K-1$).
• $P_i<P_{i+1}$ ($0\le i\le K-2$).

Pontuação

• Seja $L^*$ o mínimo do valor a seguir entre todos os casos de teste desta tarefa.
  • O maior inteiro $L\le40$ tal que, para toda consulta com $K\le L$, Bruno responde o valor correto de $X$.
• A pontuação desta tarefa é calculada da seguinte maneira:
  • Se $L^*=0$, a pontuação é 0 ponto.
  • Se $1\le L^*\le14$, a pontuação é 8 pontos.
  • Se $15\le L^*\le37$, a pontuação é $(L^*-15)\times2+41$ pontos.
  • Se $38\le L^*\le40$, a pontuação é $(L^*-38)\times5+90$ pontos.

Exemplo de comunicação

Aqui está uma entrada de exemplo para o avaliador e as chamadas de função correspondentes. Observe que o exemplo a seguir não satisfaz as restrições desta tarefa, pois $Q=2$, $N=3$.

Entrada 1

2
3 14 1
2
3 9 2
0 1

Chamadas de exemplo

Aqui, os parâmetros de Anna(...), Bruno(...), Anna(...) e Bruno(...) são os seguintes.