lN3quW - Online C++0x Compiler & Debugging Tool

/*
* @Author: hungeazy
* @Date:   2025-11-11 14:07:38
* @Last Modified by:   hungeazy
* @Last Modified time: 2025-11-11 14:32:09
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
using namespace __gnu_pbds;
bool M1;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define ll long long
#define ull unsigned long long
#define sz(x) x.size()
#define sqr(x) (1LL * (x) * (x))
#define all(x) x.begin(), x.end()
#define fill(f,x) memset(f,x,sizeof(f))
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define debug(x) cout << #x << " = " << x << '\n'
#define ii pair<int,int>
#define iii pair<int,ii>
#define di pair<ii,ii>
#define vi vector<int>
#define vii vector<ii>
#define mii map<int,int>
#define fi first
#define se second
#define pb push_back
#define MOD 1000000007
#define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define MASK(i) (1LL << (i))
#define c_bit(i) __builtin_popcountll(i)
#define BIT(x,i) ((x) & MASK(i))
#define SET_ON(x,i) ((x) | MASK(i))
#define SET_OFF(x,i) ((x) & ~MASK(i))
#define oo 1e18
#define name "ANCTEXT"
#define endl '\n'
#define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
#define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
const int N = (int)5e5+10;
string s;
int n,q;
pair<int,string> mem[N];
// VO20 - Bài 3
namespace hungeazy {

	const int base = 256;
	int pw[N],hashA[N],sorted[N],cnt=0;

	int hashing(int hashVal, char h) {
		return (hashVal*base%MOD+h)%MOD;
	}

	int getHash(int l, int r) {
		return (hashA[r]-hashA[l-1]*pw[r-l+1]%MOD+sqr(MOD))%MOD;
	}

	struct Node {
		int h,endIdx,hashVal;
		Node *child[26], *par[20];
		char cur;
		Node() {
			h = hashVal = 0;
			endIdx = -1;
			FOR(i,0,19) par[i] = NULL;
			FOR(i,0,25) child[i] = NULL;
			cur = '?';
		}
	} *endNode[N];

	struct Trie {
		Node *root;

		Trie() {
			root = new Node();
			FOR(i,0,19) root->par[i] = root;
			endNode[0] = root;
		}

		void insert(Node *p, int idx, string &s)
		{
			for (char c : s)
			{
				int pos = c-'a';
				if (p->child[pos] == NULL)
				{
					p->child[pos] = new Node();
					p->child[pos]->hashVal = (p->hashVal*base%MOD+c)%MOD;
					p->child[pos]->h = p->h+1;
					p->child[pos]->cur = c;
					p->child[pos]->par[0] = p;
					FOR(i,1,19)
						p->child[pos]->par[i] = (p->child[pos]->par[i-1])->par[i-1];
				}
				p = p->child[pos];
			}
			if (p->endIdx == -1) p->endIdx = idx;
			endNode[idx] = p;
		}

		void DFS(Node *u)
		{
			if (u->endIdx != -1) sorted[++cnt] = u->endIdx;
			FOR(pos,0,25)
				if (u->child[pos] != NULL)
					DFS(u->child[pos]);
		}
	} trie;

	bool check(int pos, int L, int R)
	{
		Node *p = endNode[pos];
		int lenS = R-L+1;
		if (p->h <= lenS and p->hashVal == getHash(L,L+p->h-1)) return true;
		FOD(i,19,0)
		{
			int lenT = p->par[i]->h;
			if (lenT > lenS or p->par[i]->hashVal != getHash(L,L+lenT-1))
				p = p->par[i];
		}
		return (p->h <= lenS and p->cur < s[L+p->h-1]);
	}

	void solve(void)
	{
		int len = sz(s);
		s = "#"+s;
		pw[0] = 1;
		FOR(i,1,len)
		{
			pw[i] = pw[i-1]*base%MOD;
			hashA[i] = hashing(hashA[i-1],s[i]);
		}
		FOR(i,1,n)
		{
			auto [par,st] = mem[i];
			trie.insert(endNode[par],i,st);
		}
		trie.DFS(trie.root);
		while (q--)
		{
			int l,r;
			cin >> l >> r;
			int L = 1, R = cnt, ans = -1;
			while (L <= R)
			{
				int mid = (L+R)>>1;
				if (check(sorted[mid],l,r)) ans = sorted[mid], L = mid+1;
				else R = mid-1;
			}
			cout << ans << endl;
		}
	}

}

bool M2;
signed main()
{
    fast;
    if (fopen(name".inp","r"))
    {
    	freopen(name".inp","r",stdin);
    	freopen(name".out","w",stdout);
    }
    int subtask;
    cin >> subtask >> s >> n;
    FOR(i,1,n)
    {
    	int par; string st;
    	cin >> par >> st;
    	mem[i] = {par,st};
    }
    cin >> q;
    hungeazy::solve();
    time();
    memory();
    return 0;
}
// ██░ ██  █    ██  ███▄    █   ▄████
//▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
//▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
//░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
//░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
// ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
// ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
// ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
// ░  ░  ░   ░              ░       ░