#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using ull=unsigned long long;
const llt N=500100;
llt n,q,L[N],R[N],Q[N],us=1,ans[N];char s[N];
struct TRIE 
{
    llt son[N][2],fail[N],siz=1,nxt[2][N][33],tag[2][N][33],in[N],v[N];
    llt insert(char* S,llt Len)
    {
        llt now=1;
        for(int i=1;i<=Len;i++)
        {
            if(!son[now][S[i]-'0'])  son[now][S[i]-'0']=++siz;
            now=son[now][S[i]-'0'];
        }
        return now;
    }
    void build()
    {
        queue<llt> qu;
        for(int i=0;i<=1;i++)   if(son[1][i]) fail[son[1][i]]=1,in[1]++,qu.push(son[1][i]);else son[1][i]=1;
        while(!qu.empty())
        {
            llt now=qu.front();qu.pop();
            for(int i=0;i<=1;i++)   
                if(son[now][i]) fail[son[now][i]]=son[fail[now]][i],qu.push(son[now][i]),in[son[fail[now]][i]]++;
                else son[now][i]=son[fail[now]][i];
        }
        for(int i=1;i<=siz;i++) nxt[0][i][0]=son[i][0],nxt[1][i][0]=son[i][1];
        for(int j=1;(1<<j)<=1e9;j++)
            for(int i=1;i<=siz;i++)
                nxt[0][i][j]=nxt[1][nxt[0][i][j-1]][j-1],
                nxt[1][i][j]=nxt[0][nxt[1][i][j-1]][j-1];
    }
    #define C(o) (__builtin_popcount(o)&1)
    void Run(llt &now,llt l,llt r)
    {
        for(int i=0;(1<<i)<=(r-l+1);i++)
            if(l&(1<<i))    tag[C(l)][now][i]++,now=nxt[C(l)][now][i],l+=(1<<i);
        for(int i=30;i>=0;i--)
            if((1<<i)&(r-l+1))
                tag[C(l)][now][i]++,now=nxt[C(l)][now][i],l+=(1<<i);
    }
    void solve()
    {
        for(int j=30;j>=1;j--)
            for(int i=1;i<=siz;i++)
                tag[0][i][j-1]+=tag[0][i][j],tag[1][nxt[0][i][j-1]][j-1]+=tag[0][i][j],
                tag[1][i][j-1]+=tag[1][i][j],tag[0][nxt[1][i][j-1]][j-1]+=tag[1][i][j];
        for(int i=1;i<=siz;i++) v[son[i][0]]+=tag[0][i][0],v[son[i][1]]+=tag[1][i][0];
    }
    void topu()
    {
        queue<llt> qu;
        for(int i=1;i<=siz;i++) if(!in[i])  qu.push(i);
        while(!qu.empty())  
        {
            llt tmp=qu.front();qu.pop();
            v[fail[tmp]]+=v[tmp];in[fail[tmp]]--;
            if(!in[fail[tmp]])    qu.push(fail[tmp]);
        }
    }
}trie;
int main()
{
    #ifdef LOCAL
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)   scanf("%lld%lld",&L[i],&R[i]);
    for(int i=1;i<=q;i++)   scanf("%s",s+1),Q[i]=trie.insert(s,strlen(s+1));
    trie.build();for(int i=1;i<=n;i++)   trie.Run(us,L[i],R[i]);
    trie.solve();trie.topu();
    for(int i=1;i<=q;i++)   printf("%lld\n",trie.v[Q[i]]);
    return 0;
}