別解を簡単に書きます。この問題は Generalized Suffix Tree (参考:Wikipedia) をオイラーツアーすれば解くことができます。これは LCP 配列を segtree に載せて segtree 上の二分探索を利用すれば \(\mathrm{O}(N \log N)\) 程度で簡潔に実装できます。(あるいは Cartesian Tree を利用すれば \(\mathrm{O}(N)\) で計算できます。)

• 実装例 (\(\mathrm{O}(N \log N)\))

#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
#include "atcoder/segtree.hpp"
#include "atcoder/string.hpp"

using ll = long long;
constexpr int inf = 1001001001;
int f(int a, int b) { return min(a, b); }
int ti() { return inf; }

int main() {
  ll N, Q;
  cin >> N;
  vector<string> S(N);
  for (auto& s : S) cin >> s;
  cin >> Q;
  vector<ll> qs(Q);
  for (auto& q : qs) cin >> q;

  string T;
  vector<pair<int, int>> derived;
  for (int i = 0; i < N; i++) {
    T += S[i];
    for (int j = 0; j < (int)S[i].size(); j++) derived.emplace_back(i, j);
    T.push_back('$');
    derived.emplace_back(i, -1);
  }
  auto sa = atcoder::suffix_array(T);
  auto lcp = atcoder::lcp_array(T, sa);
  lcp.push_back(0);
  atcoder::segtree<int, f, ti> seg(lcp);

  ll qid = 0, sid = 0, pos = 0, sum = 0;
  while (T[sa[sid]] == '$') sid++;
  while (sid != (int)T.size()) {
    int r = seg.max_right(sid, [&](int x) { return x > pos; });
    int val = seg.prod(sid, r);
    auto [m, mpos] = derived[sa[sid]];
    val = min<int>(val, S[m].size() - mpos);
    if (pos == val) {
      pos = min<int>(pos, lcp[sid]), sid++;
      continue;
    }
    ll nxtsum = sum + (r - sid + 1) * (val - pos);
    while (qid != Q and qs[qid] <= nxtsum) {
      ll diff = qs[qid] - 1 - sum;
      ll i = diff / (r - sid + 1);
      cout << m + 1 << " " << mpos + 1 << " " << mpos + 1 + pos + i << "\n";
      qid++;
    }
    sum = nxtsum, pos = val;
  }
}