#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 42, logn = 20, sigma = 26;
string s[maxn];
struct suffix_automaton
{
vector<int> len, link, fpos, lpos, left, right, ans, max, cnt, st;
vector<vector<int>> to;
vector<vector<int>> up;
string s;
int sz, last;
void clear()
{
up.clear();
to.clear();
len.clear();
link.clear();
fpos.clear();
lpos.clear();
cnt.clear();
st.clear();
s.clear();
}
void reserve(int n)
{
up.reserve(n);
to.reserve(n);
len.reserve(n);
link.reserve(n);
fpos.reserve(n);
lpos.reserve(n);
cnt.reserve(n);
st.reserve(n);
s.reserve(n);
left.reserve(n);
right.reserve(n);
ans.reserve(n);
max.reserve(n);
}
int make_state(vector<int> new_to = vector<int>(sigma + 1), int new_link = 0, int new_fpos = 0, int new_len = 0)
{
to.push_back(new_to);
link.push_back(new_link);
fpos.push_back(new_fpos);
len.push_back(new_len);
lpos.push_back(new_fpos);
left.push_back(0);
right.push_back(0);
ans.push_back(0);
max.push_back(0);
cnt.push_back(0);
up.push_back(vector<int>(logn));
return sz++;
}
void add_letter(char c)
{
s += c;
int p = last;
last = make_state(vector<int>(sigma + 1), 0, len[p] + 1, len[p] + 1);
st.push_back(last);
cnt[last] = 1;
for(; to[p][c] == 0; p = link[p])
to[p][c] = last;
if(to[p][c] == last)
return;
int q = to[p][c];
if(len[q] == len[p] + 1)
{
link[last] = q;
return;
}
int cl = make_state(to[q], link[q], fpos[q], len[p] + 1);
link[last] = link[q] = cl;
for(; to[p][c] == q; p = link[p])
to[p][c] = cl;
}
void build(string s)
{
make_state();
int n = s.size();
reserve(4 * n);
for(auto c: s)
add_letter(c);
int mx_len[n]; // kill states like "X#Y"
memset(mx_len, 0, sizeof(mx_len));
int count = 0;
for(int i = 0; i < n; i++)
{
mx_len[i] = count++;
if(s[i] == sigma)
count = 1;
}
for(int state = 1; state < sz; state++)
{
if(len[link[state]] < mx_len[fpos[state] - 1] && len[state] > mx_len[fpos[state] - 1])
{
int cl = make_state(to[state], link[state], fpos[state], mx_len[fpos[state] - 1]);
link[state] = cl;
}
}
for(int state = 1; state < sz; state++) // sparse table, like in LCA
up[state][0] = link[state];
for(int lvl = 1; lvl < logn; lvl++)
for(int state = 1; state < sz; state++)
up[state][lvl] = up[up[state][lvl - 1]][lvl - 1];
vector<int> g[n + 1]; // this actually gives us reversed topsort
for(int state = 1; state < sz; state++)
g[len[state]].push_back(state);
for(int ln = n; ln > 0; ln--)
for(auto state: g[ln])
{
if(link[state])
cnt[link[state]] += cnt[state];
lpos[link[state]] = std::max(lpos[link[state]], lpos[state]);
}
}
int get(int pos, int ln) // kind of binary search on path to the root
{ // pos 1-based
int state = st[pos - 1];
for(int i = logn - 1; i >= 0; i--)
if(len[up[state][i]] >= ln)
state = up[state][i];
return state;
}
} me[4 * maxn];
void build(int v = 1, int l = 1, int r = maxn)
{
if(r - l == 1)
{
s[l] = char(sigma) + s[l];
me[v].build(s[l]);
for(int state = 0; state < me[v].sz; state++)
{
me[v].ans[state] = l;
me[v].max[state] = me[v].cnt[state];
}
return;
}
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m, r);
me[v].build(me[2 * v].s + me[2 * v + 1].s);
for(int state = 1; state < me[v].sz; state++)
{
if(me[v].fpos[state] <= (int) me[2 * v].s.size()) // we want to know states corresponding to strings from this state in children
me[v].left[state] = me[2 * v].get(me[v].fpos[state], me[v].len[state]);
if(me[v].lpos[state] > (int) me[2 * v].s.size())
me[v].right[state] = me[2 * v + 1].get(me[v].lpos[state] - me[2 * v].s.size(), me[v].len[state]);
me[v].max[state] = max(me[2 * v].max[me[v].left[state]], me[2 * v + 1].max[me[v].right[state]]);
if(me[v].max[state] == me[2 * v].max[me[v].left[state]])
me[v].ans[state] = me[2 * v].ans[me[v].left[state]];
else
me[v].ans[state] = me[2 * v + 1].ans[me[v].right[state]];
}
me[2 * v].clear(); // we don't need O(n log^2 n) memory
me[2 * v + 1].clear();
}
pair<int, int> get(int a, int b, int state, int v = 1, int l = 1, int r = maxn)
{
if(a <= l && r <= b)
return {me[v].max[state], me[v].ans[state]};
if(r <= a || b <= l)
return {0, 0};
int m = (l + r) / 2;
auto A = get(a, b, me[v].left[state], 2 * v, l, m);
auto B = get(a, b, me[v].right[state], 2 * v + 1, m, r);
if(A.first >= B.first)
return A;
else
return B;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string Q;
cin >> Q;
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> s[i + 1];
for(auto &it: s[i + 1])
it -= 'a';
}
build(); // yeah, this thing builds!
int state = 0, ln = 0;
vector<int> states, lens;
for(auto c: Q)
{
c -= 'a';
while(state && !me[1].to[state][c])
{
state = me[1].link[state];
ln = me[1].len[state];
}
if(me[1].to[state][c])
{
state = me[1].to[state][c];
ln++;
}
lens.push_back(ln);
states.push_back(state);
}
int m;
cin >> m;
while(m--)
{
int l, r, pl, pr;
cin >> l >> r >> pl >> pr;
if(pr - pl + 1 > lens[pr - 1])
{
cout << l << ' ' << 0 << "\n";
continue;
}
int state = me[1].get(me[1].fpos[states[pr - 1]], pr - pl + 1);
auto ans = get(l, r + 1, state);
cout << max(l, ans.second) << ' ' << ans.first << "\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IG1heG4gPSA1ZTQgKyA0MiwgbG9nbiA9IDIwLCBzaWdtYSA9IDI2OwoKc3RyaW5nIHNbbWF4bl07CgpzdHJ1Y3Qgc3VmZml4X2F1dG9tYXRvbgp7Cgl2ZWN0b3I8aW50PiBsZW4sIGxpbmssIGZwb3MsIGxwb3MsIGxlZnQsIHJpZ2h0LCBhbnMsIG1heCwgY250LCBzdDsKCXZlY3Rvcjx2ZWN0b3I8aW50Pj4gdG87Cgl2ZWN0b3I8dmVjdG9yPGludD4+IHVwOwoJc3RyaW5nIHM7CglpbnQgc3osIGxhc3Q7CgkKCXZvaWQgY2xlYXIoKQoJewoJCXVwLmNsZWFyKCk7CgkJdG8uY2xlYXIoKTsKCQlsZW4uY2xlYXIoKTsKCQlsaW5rLmNsZWFyKCk7CgkJZnBvcy5jbGVhcigpOwoJCWxwb3MuY2xlYXIoKTsKCQljbnQuY2xlYXIoKTsKCQlzdC5jbGVhcigpOwoJCXMuY2xlYXIoKTsKCX0KCQoJdm9pZCByZXNlcnZlKGludCBuKQoJewoJCXVwLnJlc2VydmUobik7CgkJdG8ucmVzZXJ2ZShuKTsKCQlsZW4ucmVzZXJ2ZShuKTsKCQlsaW5rLnJlc2VydmUobik7CgkJZnBvcy5yZXNlcnZlKG4pOwoJCWxwb3MucmVzZXJ2ZShuKTsKCQljbnQucmVzZXJ2ZShuKTsKCQlzdC5yZXNlcnZlKG4pOwoJCXMucmVzZXJ2ZShuKTsKCQlsZWZ0LnJlc2VydmUobik7CgkJcmlnaHQucmVzZXJ2ZShuKTsKCQlhbnMucmVzZXJ2ZShuKTsKCQltYXgucmVzZXJ2ZShuKTsKCX0KCQoJaW50IG1ha2Vfc3RhdGUodmVjdG9yPGludD4gbmV3X3RvID0gdmVjdG9yPGludD4oc2lnbWEgKyAxKSwgaW50IG5ld19saW5rID0gMCwgaW50IG5ld19mcG9zID0gMCwgaW50IG5ld19sZW4gPSAwKQoJewoJCXRvLnB1c2hfYmFjayhuZXdfdG8pOwoJCWxpbmsucHVzaF9iYWNrKG5ld19saW5rKTsKCQlmcG9zLnB1c2hfYmFjayhuZXdfZnBvcyk7CgkJbGVuLnB1c2hfYmFjayhuZXdfbGVuKTsKCQlscG9zLnB1c2hfYmFjayhuZXdfZnBvcyk7CgkJbGVmdC5wdXNoX2JhY2soMCk7CgkJcmlnaHQucHVzaF9iYWNrKDApOwoJCWFucy5wdXNoX2JhY2soMCk7CgkJbWF4LnB1c2hfYmFjaygwKTsKCQljbnQucHVzaF9iYWNrKDApOwoJCXVwLnB1c2hfYmFjayh2ZWN0b3I8aW50Pihsb2duKSk7CgkJcmV0dXJuIHN6Kys7Cgl9CgkKCXZvaWQgYWRkX2xldHRlcihjaGFyIGMpCgl7CgkJcyArPSBjOwoJCWludCBwID0gbGFzdDsKCQlsYXN0ID0gbWFrZV9zdGF0ZSh2ZWN0b3I8aW50PihzaWdtYSArIDEpLCAwLCBsZW5bcF0gKyAxLCBsZW5bcF0gKyAxKTsKCQlzdC5wdXNoX2JhY2sobGFzdCk7CgkJY250W2xhc3RdID0gMTsKCQlmb3IoOyB0b1twXVtjXSA9PSAwOyBwID0gbGlua1twXSkKCQkJdG9bcF1bY10gPSBsYXN0OwoJCWlmKHRvW3BdW2NdID09IGxhc3QpCgkJCXJldHVybjsKCQlpbnQgcSA9IHRvW3BdW2NdOwoJCWlmKGxlbltxXSA9PSBsZW5bcF0gKyAxKQoJCXsKCQkJbGlua1tsYXN0XSA9IHE7CgkJCXJldHVybjsKCQl9CgkJaW50IGNsID0gbWFrZV9zdGF0ZSh0b1txXSwgbGlua1txXSwgZnBvc1txXSwgbGVuW3BdICsgMSk7CgkJbGlua1tsYXN0XSA9IGxpbmtbcV0gPSBjbDsKCQlmb3IoOyB0b1twXVtjXSA9PSBxOyBwID0gbGlua1twXSkKCQkJdG9bcF1bY10gPSBjbDsKCX0KCQoJdm9pZCBidWlsZChzdHJpbmcgcykKCXsKCQltYWtlX3N0YXRlKCk7CgkJaW50IG4gPSBzLnNpemUoKTsKCQlyZXNlcnZlKDQgKiBuKTsKCQkKCQlmb3IoYXV0byBjOiBzKQoJCQlhZGRfbGV0dGVyKGMpOwoJCQoJCWludCBteF9sZW5bbl07IC8vIGtpbGwgc3RhdGVzIGxpa2UgIlgjWSIKCQltZW1zZXQobXhfbGVuLCAwLCBzaXplb2YobXhfbGVuKSk7CgkJaW50IGNvdW50ID0gMDsKCQlmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQoJCXsKCQkJbXhfbGVuW2ldID0gY291bnQrKzsKCQkJaWYoc1tpXSA9PSBzaWdtYSkKCQkJCWNvdW50ID0gMTsKCQl9CgkJZm9yKGludCBzdGF0ZSA9IDE7IHN0YXRlIDwgc3o7IHN0YXRlKyspIAoJCXsKCQkJaWYobGVuW2xpbmtbc3RhdGVdXSA8IG14X2xlbltmcG9zW3N0YXRlXSAtIDFdICYmIGxlbltzdGF0ZV0gPiBteF9sZW5bZnBvc1tzdGF0ZV0gLSAxXSkKCQkJewoJCQkJaW50IGNsID0gbWFrZV9zdGF0ZSh0b1tzdGF0ZV0sIGxpbmtbc3RhdGVdLCBmcG9zW3N0YXRlXSwgbXhfbGVuW2Zwb3Nbc3RhdGVdIC0gMV0pOwoJCQkJbGlua1tzdGF0ZV0gPSBjbDsKCQkJfQoJCX0KCQkJCgkJZm9yKGludCBzdGF0ZSA9IDE7IHN0YXRlIDwgc3o7IHN0YXRlKyspIC8vIHNwYXJzZSB0YWJsZSwgbGlrZSBpbiBMQ0EKCQkJdXBbc3RhdGVdWzBdID0gbGlua1tzdGF0ZV07CgkJZm9yKGludCBsdmwgPSAxOyBsdmwgPCBsb2duOyBsdmwrKykKCQkJZm9yKGludCBzdGF0ZSA9IDE7IHN0YXRlIDwgc3o7IHN0YXRlKyspCgkJCQl1cFtzdGF0ZV1bbHZsXSA9IHVwW3VwW3N0YXRlXVtsdmwgLSAxXV1bbHZsIC0gMV07CgkJCgkJdmVjdG9yPGludD4gZ1tuICsgMV07IC8vIHRoaXMgYWN0dWFsbHkgZ2l2ZXMgdXMgcmV2ZXJzZWQgdG9wc29ydAoJCWZvcihpbnQgc3RhdGUgPSAxOyBzdGF0ZSA8IHN6OyBzdGF0ZSsrKQoJCQlnW2xlbltzdGF0ZV1dLnB1c2hfYmFjayhzdGF0ZSk7CgkJZm9yKGludCBsbiA9IG47IGxuID4gMDsgbG4tLSkgCgkJCWZvcihhdXRvIHN0YXRlOiBnW2xuXSkKCQkJewoJCQkJaWYobGlua1tzdGF0ZV0pCgkJCQkJY250W2xpbmtbc3RhdGVdXSArPSBjbnRbc3RhdGVdOwoJCQkJbHBvc1tsaW5rW3N0YXRlXV0gPSBzdGQ6Om1heChscG9zW2xpbmtbc3RhdGVdXSwgbHBvc1tzdGF0ZV0pOwoJCQl9Cgl9CgkKCWludCBnZXQoaW50IHBvcywgaW50IGxuKSAvLyBraW5kIG9mIGJpbmFyeSBzZWFyY2ggb24gcGF0aCB0byB0aGUgcm9vdAoJeyAvLyBwb3MgMS1iYXNlZAoJCWludCBzdGF0ZSA9IHN0W3BvcyAtIDFdOwoJCWZvcihpbnQgaSA9IGxvZ24gLSAxOyBpID49IDA7IGktLSkKCQkJaWYobGVuW3VwW3N0YXRlXVtpXV0gPj0gbG4pCgkJCQlzdGF0ZSA9IHVwW3N0YXRlXVtpXTsKCQlyZXR1cm4gc3RhdGU7Cgl9Cn0gbWVbNCAqIG1heG5dOwoKdm9pZCBidWlsZChpbnQgdiA9IDEsIGludCBsID0gMSwgaW50IHIgPSBtYXhuKQp7CglpZihyIC0gbCA9PSAxKQoJewoJCXNbbF0gPSBjaGFyKHNpZ21hKSArIHNbbF07CgkJbWVbdl0uYnVpbGQoc1tsXSk7CgkJZm9yKGludCBzdGF0ZSA9IDA7IHN0YXRlIDwgbWVbdl0uc3o7IHN0YXRlKyspCgkJewoJCQltZVt2XS5hbnNbc3RhdGVdID0gbDsKCQkJbWVbdl0ubWF4W3N0YXRlXSA9IG1lW3ZdLmNudFtzdGF0ZV07CgkJfQoJCXJldHVybjsKCX0KCWludCBtID0gKGwgKyByKSAvIDI7CglidWlsZCgyICogdiwgbCwgbSk7CglidWlsZCgyICogdiArIDEsIG0sIHIpOwoJbWVbdl0uYnVpbGQobWVbMiAqIHZdLnMgKyBtZVsyICogdiArIDFdLnMpOwoJZm9yKGludCBzdGF0ZSA9IDE7IHN0YXRlIDwgbWVbdl0uc3o7IHN0YXRlKyspCgl7CgkJaWYobWVbdl0uZnBvc1tzdGF0ZV0gPD0gKGludCkgbWVbMiAqIHZdLnMuc2l6ZSgpKSAvLyB3ZSB3YW50IHRvIGtub3cgc3RhdGVzIGNvcnJlc3BvbmRpbmcgdG8gc3RyaW5ncyBmcm9tIHRoaXMgc3RhdGUgaW4gY2hpbGRyZW4KCQkJbWVbdl0ubGVmdFtzdGF0ZV0gPSBtZVsyICogdl0uZ2V0KG1lW3ZdLmZwb3Nbc3RhdGVdLCBtZVt2XS5sZW5bc3RhdGVdKTsKCQlpZihtZVt2XS5scG9zW3N0YXRlXSA+IChpbnQpIG1lWzIgKiB2XS5zLnNpemUoKSkKCQkJbWVbdl0ucmlnaHRbc3RhdGVdID0gbWVbMiAqIHYgKyAxXS5nZXQobWVbdl0ubHBvc1tzdGF0ZV0gLSBtZVsyICogdl0ucy5zaXplKCksIG1lW3ZdLmxlbltzdGF0ZV0pOwoJCW1lW3ZdLm1heFtzdGF0ZV0gPSBtYXgobWVbMiAqIHZdLm1heFttZVt2XS5sZWZ0W3N0YXRlXV0sIG1lWzIgKiB2ICsgMV0ubWF4W21lW3ZdLnJpZ2h0W3N0YXRlXV0pOwoJCWlmKG1lW3ZdLm1heFtzdGF0ZV0gPT0gbWVbMiAqIHZdLm1heFttZVt2XS5sZWZ0W3N0YXRlXV0pCgkJCW1lW3ZdLmFuc1tzdGF0ZV0gPSBtZVsyICogdl0uYW5zW21lW3ZdLmxlZnRbc3RhdGVdXTsKCQllbHNlCgkJCW1lW3ZdLmFuc1tzdGF0ZV0gPSBtZVsyICogdiArIDFdLmFuc1ttZVt2XS5yaWdodFtzdGF0ZV1dOwoJfQoJbWVbMiAqIHZdLmNsZWFyKCk7IC8vIHdlIGRvbid0IG5lZWQgTyhuIGxvZ14yIG4pIG1lbW9yeQoJbWVbMiAqIHYgKyAxXS5jbGVhcigpOwp9CgpwYWlyPGludCwgaW50PiBnZXQoaW50IGEsIGludCBiLCBpbnQgc3RhdGUsIGludCB2ID0gMSwgaW50IGwgPSAxLCBpbnQgciA9IG1heG4pCnsKCWlmKGEgPD0gbCAmJiByIDw9IGIpCgkJcmV0dXJuIHttZVt2XS5tYXhbc3RhdGVdLCBtZVt2XS5hbnNbc3RhdGVdfTsKCWlmKHIgPD0gYSB8fCBiIDw9IGwpCgkJcmV0dXJuIHswLCAwfTsKCWludCBtID0gKGwgKyByKSAvIDI7CglhdXRvIEEgPSBnZXQoYSwgYiwgbWVbdl0ubGVmdFtzdGF0ZV0sIDIgKiB2LCBsLCBtKTsKCWF1dG8gQiA9IGdldChhLCBiLCBtZVt2XS5yaWdodFtzdGF0ZV0sIDIgKiB2ICsgMSwgbSwgcik7CglpZihBLmZpcnN0ID49IEIuZmlyc3QpCgkJcmV0dXJuIEE7CgllbHNlCgkJcmV0dXJuIEI7Cn0KCmludCBtYWluKCkKewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwogICAgc3RyaW5nIFE7CiAgICBjaW4gPj4gUTsKICAgIAogICAgaW50IG47CiAgICBjaW4gPj4gbjsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICB7CgkJY2luID4+IHNbaSArIDFdOwoJCWZvcihhdXRvICZpdDogc1tpICsgMV0pCgkJCWl0IC09ICdhJzsKCX0KCWJ1aWxkKCk7IC8vIHllYWgsIHRoaXMgdGhpbmcgYnVpbGRzIQoJaW50IHN0YXRlID0gMCwgbG4gPSAwOwoJdmVjdG9yPGludD4gc3RhdGVzLCBsZW5zOwoJZm9yKGF1dG8gYzogUSkKCXsKCQljIC09ICdhJzsKCQl3aGlsZShzdGF0ZSAmJiAhbWVbMV0udG9bc3RhdGVdW2NdKQoJCXsKCQkJc3RhdGUgPSBtZVsxXS5saW5rW3N0YXRlXTsKCQkJbG4gPSBtZVsxXS5sZW5bc3RhdGVdOwoJCX0KCQlpZihtZVsxXS50b1tzdGF0ZV1bY10pCgkJewoJCQlzdGF0ZSA9IG1lWzFdLnRvW3N0YXRlXVtjXTsKCQkJbG4rKzsKCQl9CgkJbGVucy5wdXNoX2JhY2sobG4pOwoJCXN0YXRlcy5wdXNoX2JhY2soc3RhdGUpOwoJfQoJCglpbnQgbTsKCWNpbiA+PiBtOwoJd2hpbGUobS0tKQoJewoJCWludCBsLCByLCBwbCwgcHI7CgkJY2luID4+IGwgPj4gciA+PiBwbCA+PiBwcjsKCQlpZihwciAtIHBsICsgMSA+IGxlbnNbcHIgLSAxXSkKCQl7CgkJCWNvdXQgPDwgbCA8PCAnICcgPDwgMCA8PCAiXG4iOwoJCQljb250aW51ZTsKCQl9CgkJaW50IHN0YXRlID0gbWVbMV0uZ2V0KG1lWzFdLmZwb3Nbc3RhdGVzW3ByIC0gMV1dLCBwciAtIHBsICsgMSk7CgkJYXV0byBhbnMgPSBnZXQobCwgciArIDEsIHN0YXRlKTsKCQljb3V0IDw8IG1heChsLCBhbnMuc2Vjb25kKSA8PCAnICcgPDwgYW5zLmZpcnN0IDw8ICJcbiI7Cgl9CiAgICByZXR1cm4gMDsKfQo=