#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
    void add(X &x, const Y &y) {
        x = (x + y);
        if(x >= MOD) x -= MOD;
    }

template<class X, class Y>
    void sub(X &x, const Y &y) {
        x = (x - y);
        if(x < 0) x += MOD;
    }

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e9;
const int N = 1e5 + 10;
const int LOG = 16;

struct SegmentTree {
    int n;
    struct NODE {
        int val = 0;
    };

    vector<NODE> Node;

    SegmentTree(int _n = 0) {
        n = _n;
        Node.resize(4 * n + 7);
    }

private:
    NODE merge(const NODE &a, const NODE &b) {
        NODE ans;
        ans.val = max(a.val, b.val);
        return ans;
    }

    void Build(int L, int R, int id, ll v[]) {
        if(L == R) {
            Node[id].val = v[L];
            return;
        }

        int mid = (L + R) >> 1;
        Build(L, mid, id << 1, v);
        Build(mid + 1, R, id << 1 | 1, v);
        Node[id] = merge(Node[id << 1], Node[id << 1 | 1]);
    }

    void Update(int L, int R, int pos, ll val, int id) {
        if(L == R) {
            Node[id].val = val;
            return;
        }

        int mid = (L + R) >> 1;
        if(pos <= mid) Update(L, mid, pos, val, id << 1);
        else Update(mid + 1, R, pos, val, id << 1 | 1);
        Node[id] = merge(Node[id << 1], Node[id << 1 | 1]);
    }

    NODE Get(int L, int R, int lo, int hi, int id) {
        if(L > hi || R < lo) return NODE();
        if(lo <= L && R <= hi) return Node[id];
        int mid = (L + R) >> 1;
        NODE l = Get(L, mid, lo, hi, id << 1);
        NODE r = Get(mid + 1, R, lo, hi, id << 1 | 1);
        return merge(l, r);
    }

public:
    void build(ll v[]) {
        Build(1, n, 1, v);
    }

    void update(int pos, ll val) {
        Update(1, n, pos, val, 1);
    }

    ll get(int L, int R) {
        NODE ans = Get(1, n, L, R, 1);
        return ans.val;
    }
};

struct Node {
    Node* child[2];
    int pos;

    Node() {
        child[0] = child[1] = nullptr;
        pos = 0;
    }
};

auto addTrie(Node *node, string &s, int id) {
    int n = s.size();
    for(int i = 0; i < n; i++) {
        int p = (s[i] - '0');
        if(node->child[p] == nullptr) node->child[p] = new Node();
        node = node->child[p];
        node->pos = id;
    }
}

int getTrie(Node *node, string &s, int pos, int lim) {
    while(pos < s.size()) {
        int p = s[pos] - '0';
        p ^= 1;

        int index = (node->child[p] != nullptr ? node->child[p]->pos : INF);

        if(index <= lim) {
            node = node->child[p];
        } else {
            node = node->child[p ^ 1];
        }
        pos++;
    }

    return node->pos;
}

struct Queries {
    int r;
    string s;
    int id;
};
vector<Queries> larquery[N], squery[N];
struct LQuery {
    int l, r;
    string s;
    int id;
};
vector<LQuery> lquery;
Node* root[N];
Node* croot[N], *stNode[N];

string x[N];
int f[N][LOG + 2], res[N], Index[N];
vector<int> B[N * 10];
vector<int> pos[N];

void BaoJiaoPisu() {
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> x[i];
        int len = x[i].size();
        f[i][0] = len;
        pos[len].pb(i);
        if(root[len] == nullptr) root[len] = new Node();
    }

    for(int j = 1; j <= LOG; j++) {
        for(int i = 1; i <= n - (1 << j) + 1; i++) {
            int u = i + (1 << (j - 1));
            f[i][j] = max(f[i][j - 1], f[u][j - 1]);
        }
    }

    auto query = [&](int l, int r) -> int {
        int x = 31 - btclz(r - l + 1);
        return max(f[l][x], f[r - (1 << x) + 1][x]);
    };

    for(int i = 1; i <= q; i++) {
        int l, r; string s;
        cin >> l >> r >> s;
        int len = s.size();
        int max_len = query(l, r);
        if(max_len > len) {
            lquery.pb({l, r, s, i});
            larquery[l].pb({r, s, i});
        } else {
            squery[l].pb({r, s, i});
        }
    }

    auto found = [&](int l, int r, int len) -> bool {
        int Index = lower_bound(all(pos[len]), l) - pos[len].begin();
        return (Index < pos[len].size() && pos[len][Index] <= r);
    };

    for(int i = n; i >= 1; i--) {
        addTrie(root[x[i].size()], x[i], i);
        for(auto &query : squery[i]) {
            int l = i;
            int r = query.r;
            int id = query.id;
            string &s = query.s;
            int len = s.size();

            int request = 0;
            for(int i = 0; i < len; i++) {
                if(s[i] == '0') {
                    if(found(l, r, len - i)) {
                        request = len - i;
                        break;
                    }
                }
            }

            if(!request) {
                for(int i = 1; i <= len; i++) {
                    request = i;
                    break;
                }
            }

            res[id] = getTrie(root[request], query.s, len - request, r);
        }
    }

    //difficult case : when ai.size() > x.size();

    SegmentTree IT = SegmentTree(n);
    sort(all(lquery), [&](LQuery &_a, LQuery &_b) {
        return _a.s.size() > _b.s.size();
    });

    for(int i = 1; i <= n; i++) {
        B[x[i].size() + 1].pb(i);
        Index[i] = 1;
        croot[i] = root[x[i].size()];
        addTrie(root[x[i].size()], x[i], INF);
    }

    int iter = 1e6;
    for(int i = 0; i < lquery.size(); i++) {
        int l = lquery[i].l, r = lquery[i].r, id = lquery[i].id;
        string &s = lquery[i].s;
        int len = s.size();

        while(iter - 1 > len) {
            vector<int> one, zero;
            for(auto id : B[iter]) {
                int p = (x[id][x[id].size() - iter + 1] - '0');
                if(p) one.pb(id);
                else zero.pb(id);
            }

            //merge-sort
            int i = 0, j = 0, curr = (B[iter - 1].size() > 0);
            if(B[iter - 1].size() > 0) {
                croot[1] = root[iter - 2];
            }
            pii last = mp(-1, -1);
            while(i < one.size() && j < zero.size()) {
                int x = one[i];
                int y = zero[j];

                if(Index[x] >= Index[y]) {
                    B[iter - 1].pb(y);
                    if(last != mp(Index[y], 0)) {
                        ++curr;
                        croot[curr] = croot[Index[y]]->child[0];
                    }
                    last = mp(Index[y], 0);
                    ++j;
                    Index[y] = curr;
                } else {
                    B[iter - 1].pb(x);
                    if(last != mp(Index[x], 1)) {
                        ++curr;
                        croot[curr] = croot[Index[x]]->child[1];
                    }
                    last = mp(Index[x], 1);
                    ++i;
                    Index[x] = curr;
                }
            }

            while(i < one.size()) {
                int x = one[i];
                B[iter - 1].pb(x);
                if(last != mp(Index[x], 1)) {
                    ++curr;
                    croot[curr] = croot[Index[x]]->child[1];
                }
                last = mp(Index[x], 1);
                ++i;
                Index[x] = curr;
            }

            while(j < zero.size()) {
                int y = zero[j];
                B[iter - 1].pb(y);
                if(last != mp(Index[y], 0)) {
                    ++curr;
                    croot[curr] = croot[Index[y]]->child[0];
                }
                last = mp(Index[y], 0);
                ++j;
                Index[y] = curr;
            }

            iter--;
            if(iter == 3) {
                for(auto x : B[iter]) cout << x << " " << Index[x] << endl;
                cout << endl;
            }
            for(auto id : B[iter]) {
                IT.update(id, Index[id]);
            }
        }

        stNode[id] = croot[IT.get(l, r)];
    }

    for(int i = n; i >= 1; i--) {
        addTrie(root[x[i].size()], x[i], i);
        for(auto query : larquery[i]) {
            int r = query.r, id = query.id;
            string &s = query.s;
            int len = s.size();

            res[id] = getTrie(stNode[id], s, 0, r);
        }
    }

    for(int i = 1; i <= q; i++) {
        cout << res[i] << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #else
    //online
    #endif

    int tc = 1, ddd = 0;
    // cin >> tc;
    while(tc--) {
        //ddd++;
        //cout << "Case #" << ddd << ": ";
        BaoJiaoPisu();
    }
}