팝카운트 단어

구간 $[l,r]$의 팝카운트 단어는 다음과 같이 정의한다. $w(l,r)=s_ls_{l+1}\dots s_{r-1}s_{r}$ 여기서 $s_i=\text{popcount}(i)\bmod 2$이다. $\text{popcount}(i)$는 정수 $i$를 이진수로 표현했을 때 나타나는 1의 개수다.

$n$개의 구간 $[l_1,r_1],[l_2,r_2],\dots,[l_n,r_n]$이 주어진다. 문자열 $S=w(l_1,r_1)+w(l_2,r_2)+\dots+w(l_n,r_n)$을 만든다. 여기서 $+$는 이어 붙이기를 뜻한다.

$q$개의 질의가 주어진다. $i$번째 질의에서는 비트 패턴 $p_i$가 주어진다. $p_i$가 $S$의 부분 문자열로 몇 번 나타나는지 구한다. 출현이 서로 겹쳐도 각각 센다.

첫 줄에 정수 $n$과 $q$($1 \leq n,q \leq 100\,000$)가 주어진다. 다음 $n$개 줄에는 $i$번째 구간을 나타내는 정수 $l_i$와 $r_i$($1\leq l_i\leq r_i\leq 10^9$)가 한 줄에 하나씩 주어진다. 다음 $q$개 줄에는 비어 있지 않은 문자열 $p_i$가 주어지며, '0'과 '1'로만 이루어진다. 모든 패턴 길이의 합은 최대 $500\,000$이다.

입력에는 테스트 케이스가 하나만 주어진다.

각 질의마다 패턴이 $S$에 나타나는 횟수를 한 줄에 하나씩 출력한다.

$w(l_1,r_1)=w(2,6)=$ 10100, $w(l_2,r_2)=w(1,3)=$ 110, $w(l_3,r_3)=w(4,8)=$ 10011.

$S=w(l_1,r_1)+w(l_2,r_2)+w(l_3,r_3)=$ 1010011010011