#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1e9+9,base=1145141;
int n,m,len,p[1000005],ans,val[500001];
char s[1000005];
inline void init()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
}
inline void read()
{
    s[0]='~';
    s[len=1]='|';
    char c;
    cin>>c;
    while(c<'a'||c>'z')
        cin>>c;
    while(c>='a'&&c<='z')
    {
        s[++len]=c;
        s[++len]='|';
        cin>>c;
    }
}
inline int Mod(int x)
{
    return x>=mod? x-mod:x;
}
int main()
{
    init();
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        read();
        for(int j=1;j<=len;++j)
            p[j]=0;
        for(int j=1,mid=0,r=0;j<=len;++j)
        {
            if(j<=r)
                p[j]=min(p[(mid<<1)-j],r-j+1);
            while(s[i-p[j]]==s[i+p[j]])
                ++p[j];
            if(j+p[j]-1>r)
            {
                r=j+p[j]-1;
                mid=j;
            }
            val[i]=Mod(1ll*base*val[i]%mod+p[j]);
        }
    }
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        cout<<(val[x]==val[y])<<'\n';
    }
    cout.flush();
    return 0;
}