O Samuel acabou de ler um artigo sobre a sequência de Thue-Morse, e ficou fascinado com a sua beleza. É uma sequência binária inifinita com propriedades tão interessantes como nunca apresentar três blocos (subsequências contíguas de bits) consecutivos iguais entre si. Os primeiros bits da sequência de Thue-Morse são 01101001100101101001011001101001...
Para obter esta sequência faz-se o seguinte:
O Samuel resolveu começar a contar os bits ligados (marcados a 1) para conhecer melhor a sequência, mas rapidamente ficou cansado e resolveu pedir a tua ajuda. O que ele quer mesmo saber é quantos 1's existem num dado intervalo de posições [a,b] (o primeiro elemento da sequência está na posição 1). Por exemplo, se o intervalo em que ele está interessado for [1,10] (indicado a vermelho), existem 5 bits ligados (indicados a negrito):
01101001100101101001011001101001...
Se o intervalo fosse [5,8], existiam apenas dois bits ligados:
01101001100101101001011001101001...
O Samuel ficou empolgado e achou que podia até generalizar a sequência, modificando os bits iniciais que dão início ao processo de geração. Por exemplo, se os bits iniciais forem 1101, a sequência fica:
Claro que o Samuel quer também poder contar os bits ligados para uma sequência geral como esta. Será que podes ajudá-lo?
Dada um conjunto de N bits iniciais, e P perguntas, cada uma indicando um intervalo [ai, bi], a tua tarefa é, para cada pergunta, indicar quantos bits estão ligados no intervalo correspondente, supondo que a sequência foi gerada como atrás descrito (ir sucessivamente concatenando o complemento da sequência actual).
Na primeira linha vem um número inteiro N indicando o número de bits iniciais.
Na segunda linha vêm os N bits (0's ou 1's) da sequência.
Na terceira linha vem um único inteiro P indicando o número de perguntas. Seguem-se P linhas, cada uma com dois inteiros ai e bi indicando o intervalo a considerar para essa pergunta.
O output deve conter P linhas, uma para cada pergunta, indicando o número de ligados entre as posições ai e bi (inclusive) na sequência criada como atrás descrito e que começa com os bits iniciais indicados
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ N ≤ 10 | Número de bits iniciais | |
| 1 ≤ P ≤ 1 000 | Número de perguntas | |
| 1 ≤ ai ≤ bi ≤ 1015 | Posições dos intervalos a considerar |
Nota que para ler um número da ordem de 1015 são necessários 64 bits, ou seja, deves usar o long long de C/C++ ou o long de Java.
Os casos de teste deste problema estão organizados em 5 grupos com restrições adicionais diferentes:
| Grupo | Nº de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 10 | ai ≤ bi ≤ 100 |
| 2 | 20 | ai ≤ bi ≤ 107, bi - ai ≤ 100 |
| 3 | 20 | ai ≤ bi ≤ 107 |
| 4 | 25 | bi - ai ≤ 100 |
| 5 | 25 | (nenhuma restrição adicional) |
1 0 5 1 10 5 8 6 7 2 2 3 20
5 2 0 1 9
Os intervalos correspondentes a cada uma das 5 perguntas são:
3 110 4 2 11 4 8 12 14 1 20
5 1 0 11
Os intervalos correspondentes a cada uma das 4 perguntas são: