#include <bits/stdc++.h>
using namespace std;

static constexpr int Maxn = 1e5 + 5, Maxm = 5e5 + 5, MaxC = 2, Maxq = 1e5 + 5;
static constexpr int LOG = 30;

int n, q;
int L[Maxn], R[Maxn];
int endpos[Maxq];
int64_t S[Maxm];

int m, N[LOG * 2], I[LOG * 2];
void get_build(int ql, int qr, int l, int r)
{
    if (l >= qr || ql >= r)
        return;
    if (ql <= l && r <= qr)
    {
        int k = 31 - __builtin_clz(r - l);
        int q = l >> k;
        N[m] = k, I[m] = __builtin_parity(q);
        ++m;
        return;
    }
    int mid = (l + r) >> 1;
    get_build(ql, qr, l, mid);
    get_build(ql, qr, mid, r);
} // get_build

int ch[Maxm][MaxC], fail[Maxm];
int root, tot;
static int que[Maxm];
int insert(int len, const char *s)
{
    int u = root;
    for (int i = 0; i < len; ++i)
    {
        int c = s[i] - '0';
        if (!ch[u][c])
            ch[u][c] = ++tot;
        u = ch[u][c];
    }
    return u;
} // insert
void build(void)
{
    int qh = 0, qe = 0;
    fail[root] = root;
    for (int j = 0; j < 2; ++j)
    {
        if (ch[root][j])
        {
            fail[ch[root][j]] = root;
            que[qe++] = ch[root][j];
        }
        else
        {
            ch[root][j] = root;
        }
    }
    while (qh < qe)
    {
        int u = que[qh++];
        for (int j = 0; j < 2; ++j)
        {
            if (ch[u][j])
            {
                fail[ch[u][j]] = ch[fail[u]][j];
                que[qe++] = ch[u][j];
            }
            else
            {
                ch[u][j] = ch[fail[u]][j];
            }
        }
    }
} // build

int f[2][LOG][Maxm], c[2][LOG][Maxm];
int64_t g[2][LOG + 1][Maxm];

int main(void)
{
    std::freopen(".in", "r", stdin);
    std::freopen(".ans", "w", stdout);
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &L[i], &R[i]);
    root = 0;
    tot = 0;
    for (int i = 1; i <= q; ++i)
    {
        static char str[Maxm];
        scanf("%s", str);
        endpos[i] = insert(strlen(str), str);
    }
    build();
    for (int i = 0; i <= tot; ++i)
        f[0][0][i] = ch[i][0], f[1][0][i] = ch[i][1];
    for (int j = 1; j < LOG; ++j)
        for (int i = 0; i <= tot; ++i)
        {
            f[0][j][i] = f[1][j - 1][f[0][j - 1][i]];
            f[1][j][i] = f[0][j - 1][f[1][j - 1][i]];
        }
    int cur = 0;
    for (int i = 1; i <= n; ++i)
    {
        m = 0, get_build(L[i], R[i] + 1, 0, 1 << 30);
        for (int j = 0; j < m; ++j)
        {
            printf("# %d %d\n", N[j], I[j]);
            c[I[j]][N[j]][cur]++;
            cur = f[I[j]][N[j]][cur];
        }
    }
    for (int j = LOG - 1; j >= 0; --j)
        for (int i = 0; i <= tot; ++i)
        {
            g[0][j][i] += c[0][j][i] + g[0][j + 1][i];
            g[1][j][i] += c[1][j][i] + g[1][j + 1][i];
            g[1][j][f[0][j][i]] += g[0][j + 1][i];
            g[0][j][f[1][j][i]] += g[1][j + 1][i];
        }
    memset(S, 0, sizeof(S));
    for (int i = 0; i <= tot; ++i)
    {
        S[ch[i][0]] += g[0][0][i];
        S[ch[i][1]] += g[1][0][i];
        printf("%d %d\n", g[0][0][i], g[1][0][i]);
    }
    for (int i = tot; i >= 0; --i)
        S[fail[que[i]]] += S[que[i]];
    exit(EXIT_SUCCESS);
} // main