Arquivo espelhado

Uma sequência binária enorme é definida a partir de caracteres $c_0,c_1,\ldots,c_h$. Defina $S_0=c_0$ e, para $i\ge1$, $S_i=S_{i-1}\,c_i\,\operatorname{rev}(S_{i-1})$, onde $\operatorname{rev}$ inverte a ordem dos caracteres e a justaposição significa concatenação.

Você também recebe um padrão binário não vazio $P$. Para cada consulta $l,r$, conte as ocorrências de $P$ inteiramente contidas no trecho de posições $l$ até $r$ de $S_h$, com posições a partir de 1. Ocorrências sobrepostas são contadas. Não construa nem imprima .

2 3
010
010
1 7
2 6
3 5

2
0
0