#include <bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
il int pc(int x){
    int s=0;
    while(x) ++s,x-=(x&-x);
    return s;
}
const int N=1e5+5,M=3e6+5,K=5e5+5;
int n,m,k,pos[N],cnt,t[K][2];pii a[N];char s[K];
il void add(int id){
    int len=strlen(s+1),x=0,c;
    for(int i=1;i<=len;++i){
        c=s[i]-'0';if(!t[x][c]) t[x][c]=++cnt;
        x=t[x][c];
    }pos[id]=x;
}
vector<int> e[K];
int q[K],hh,tt,nxt[K],to[K][30][2];ll sum[N],g[K][30][2];
il void build(){
    int x,y,z,u,v,w;hh=1,tt=0;
    for(int i=0;i<2;++i) if(t[0][i]) q[++tt]=t[0][i];
    while(hh<=tt){
        x=q[hh++],e[nxt[x]].push_back(x);//printf("%d\n",x);
        for(int i=0;i<2;++i){
            if(t[x][i]) nxt[t[x][i]]=t[nxt[x]][i],q[++tt]=t[x][i];
            else t[x][i]=t[nxt[x]][i];
        }
    }
    for(int i=0;i<=cnt;++i) for(int c=0;c<2;++c) to[i][0][c]=t[i][c];
    for(int j=1;j<30;++j)
        for(int i=0;i<=cnt;++i)
            for(int c=0;c<2;++c)
                to[i][j][c]=to[to[i][j-1][c]][j-1][!c];
}
void dfs(int x){
    //printf("*** %d\n",x);
    for(int y:e[x]) dfs(y),sum[x]+=sum[y];
}
il void query(){
    int x=0,c,y,z,u,v,w,l,r;
    for(int i=1;i<=n;++i){
        l=a[i].fi,r=a[i].se;
        y=l;
        //printf("%d %d : ",l,r);
        while(y<=r){
            z=(1<<(int(log2(r-y+1)))),z=min(z,(y&-y)),w=log2(z),c=(pc(y)&1);
            ++g[x][w][c],x=to[x][w][c],y+=z;
            //printf("%d %d\n",x,w); 
        }//puts("");
    }
    for(int j=29;j;--j)
        for(int i=0;i<=cnt;++i)
            for(int c=0;c<2;++c){
                g[i][j-1][c]+=g[i][j][c];
                g[to[i][j-1][c]][j-1][!c]+=g[i][j][c];
            }
    for(int i=0;i<=cnt;++i) sum[t[i][0]]+=g[i][0][0],sum[t[i][1]]+=g[i][0][1];
}
int l,r,x,y,z,u,v,w;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d%d",&a[i].fi,&a[i].se);
    for(int i=1;i<=m;++i){
        scanf("%s",s+1);
        add(i);
    }
    build();query();
    dfs(0);
    for(int i=1;i<=m;++i) printf("%lld\n",sum[pos[i]]);
    return 0;
}
/*
4 1
40 1
5 0
3 0
4 1
7 2
8 0
*/