まず、問題文における、「\(S_{L_i}\) と \(S_{R_i}\) をこの順に連結した文字列を \(S_{i+1}\) とする。」という操作を「\(S_{L_i}\) と \(S_{R_i}\) をこの順に連結した文字列の、\(1\) 文字目から \(\min(\lvert S_{L_i}\rvert+\lvert S_{R_i}\rvert,10^{18})\) 文字目までを抜き出した部分文字列を \(S_{i+1}\) とする。」と変更しても答えは変わりません。 なぜなら、\(X_i\leq 10^{18}\) のため各文字列の \(10^{18}+1\) 文字目以降は参照されることはなく、新しく連結によって作られる文字列の \(10^{18}\) 文字目以前の部分においても、連結前の文字列の\(10^{18}+1\) 以降の文字が関与することはないためです。
以下では、この設定の問題を解くことを考えます。

まず、\(O(Q^2)\) でこの問題を解く方法を考えます。各文字列 \(S_i\) \((2\leq i\leq Q+1)\) について、文字列自身を保存する代わりに、文字列の長さ \(\lvert S_i\rvert\) および連結の元となった文字列の添字 \(c_{i,\mathrm{left}}=L_{i-1}\), \(c_{i,\mathrm{right}}=R_{i-1}\) および その文字列の\(S_i\) における開始位置\(x_{i,\mathrm{left}}=0\), \(x_{i,\mathrm{right}}=\lvert S_{L_{i-1}} \rvert\) を記録しておきます。 \(S_i\) の \(X_{i-1}\) 文字目が何かについては、その文字が、連結前のどちらの文字列に属するか、その何文字目であったかを\(S_0\) または\(S_1\) に行き着くまで辿ることによって求めることができます。
具体的には \((A,B)=(i,X_{i-1})\) から始めて、次の操作を繰り返します。

• \(A=0\) ならば \(0\) を出力し、操作を終了する。
• \(A=1\) ならば \(1\) を出力し、操作を終了する。
• \(x_{A,\mathrm{left}}+1\leq B\leq x_{A,\mathrm{left}}+\lvert S_{c_{A,\mathrm{left}}}\rvert\) ならば、 \((A,B)\leftarrow(c_{A,\mathrm{left}},B-x_{A,\mathrm{left}})\)
• そうでないならば、\((A,B)\leftarrow(c_{A,\mathrm{right}},B-x_{A,\mathrm{right}})\)

ここで、\((A,B)\leftarrow(C,D)\) は \((A,B)\) に \((C,D)\) を代入する、すなわち \((C,D)\) を新たな \((A,B)\) とすることを意味します。

この繰り返しによって、 \(A\) は狭義単調減少するため、操作は高々 \(i\) 回しか行われず、\(O(Q^2)\) でこの問題を解くことができます。

次に \(O(Q\log Q\log \max (X_i))\) 解法を示します。
方針としては 根付き木に対する Heavy Light Decomposition と類似した考え方を用います。

\(S_{c_{i,\mathrm{left}}}\), \(S_{c_{i,\mathrm{right}}}\) のうち \(S_i\) に含まれる長さが多い方の添字を \(c_{i,\mathrm{heavy}}\) 、少ない方の添字を \(c_{i,\mathrm{light}}\) として定義します。 長さが等しい場合は、どちらを \(c_{i,\mathrm{heavy}}\) として選んでも良いです。\(x_{i,\mathrm{heavy}}\), \(x_{i,\mathrm{light}}\) についても同様に割り当てます。 具体的には、例えば以下のように定義できます。

• \(x_{i,\mathrm{right}}>\lvert S_i\rvert-x_{i,\mathrm{right}}\) ならば、\(c_{i,\mathrm{heavy}}=c_{i,\mathrm{left}}\), \(c_{i,\mathrm{light}}=c_{i,\mathrm{right}}\).
• そうでないならば、\(c_{i,\mathrm{heavy}}=c_{i,\mathrm{right}}\), \(c_{i,\mathrm{light}}=c_{i,\mathrm{left}}\).

以下、上記の \(O(Q^2)\) 解法における連結前のどちらの文字列に属するか、その何文字目であったかを辿る操作を同様にして行う場合、 \(A\) に \(c_{A,\mathrm{heavy}}\) を代入する操作を heavy edge を辿る、 \(A\) に \(c_{A,\mathrm{light}}\) を代入する操作を light edge を辿る、とよぶことにします。

このとき、以下が成り立ちます。

\((A,B)\) から \(A\leq 1\) となるまで繰り返し操作を行う時、 light edge を辿る操作は高々 \(\lfloor \log_2 10^{18}\rfloor +1=60\) 回しか行われない。

これは、任意のheavy edgeまたは light edgeを辿る操作において、\(A, B\) は広義単調減少であること、および light edge を辿って \((A,B)\leftarrow (A',B')\)となったとき、以下が成り立つことから従います。

• \(\lvert S_A\rvert=10^{18}\) かつ \(\lvert S_{A'}\rvert=10^{18}\) となったとき、\(B'\leq 5\times 10^{17}\).
• \(\lvert S_A\rvert=10^{18}\) かつ \(B\leq 5\times 10^{17}\) のとき、\(\lvert S_{A'}\rvert \leq 5\times 10^{17}\).
• \(\lvert S_A\rvert<10^{18}\) のとき、\(\lvert S_{A'}\rvert\leq \frac{1}{2}\lvert S_A\rvert\).

なお、上記の \(10^{18}\) は最初の問題設定の変更における上限値に由来していますが、これはさらに \(X_i\) の最大値に由来していたことに注意してください。

一方で、heavy edgeは最大 \(i\) 回 辿る可能性があります。そこで、 \(S_i\) から \(2^k\) 回 \((0\leq k\leq \lfloor \log_2 Q\rfloor)\) だけ heavy edgeを辿った後の文字列の添字と、その文字列の \(S_i\) における開始位置を \(c'_{i,\mathrm{heavy},k}\), \(x'_{i,\mathrm{heavy},k}\) として定義します。特に、 \(c'_{i,\mathrm{heavy},0}=c_{i,\mathrm{heavy}}\), \(x'_{i,\mathrm{heavy},0}=x_{i,\mathrm{heavy}}\) であり、さらに、

• \(c'_{i,\mathrm{heavy},k}=c'_{c'_{i,\mathrm{heavy},k-1},\mathrm{heavy},k-1}\),
• \(x'_{i,\mathrm{heavy},k}=x'_{i,\mathrm{heavy},k-1}+x'_{c'_{i,\mathrm{heavy},k-1},\mathrm{heavy},k-1}\)

が成り立ちます。これらの関係性を用いて各クエリにおいて \(O(\log Q)\) でこれらの値を求めることができます。最後に、\(S_0\) または\(S_1\) に行き着くまで辿る際には、\(k=\lfloor \log_2 Q\rfloor, \lfloor \log_2 Q\rfloor-1,\ldots,0 \) の順に、\(2^k\) 回まとめて heavy edgeを辿ることができるかを試します。
具体的には \((A,B)=(i,X_{i-1})\) から始めて、次の操作を繰り返します。

• \(A=0\) ならば \(0\) を出力し、\(A=1\) ならば \(1\) を出力し、操作を終了する。また、以下の操作の最中においても \(A=0\) または \(1\) となったならば直ちに同様の手順を行う。
• \(k=\lfloor \log_2 Q\rfloor, \lfloor \log_2 Q\rfloor-1,\ldots,0 \) の順に以下の操作を行う。
  • \(x'_{A,\mathrm{heavy},k}+1\leq B\leq x'_{A,\mathrm{heavy},k}+\lvert S_{c'_{A,\mathrm{heavy},k}}\rvert\) ならば、 \((A,B)\leftarrow(c'_{A,\mathrm{heavy},k},B-x'_{A,\mathrm{heavy},k})\)
  • そうでないならば、何もしない。
• \((A,B)\leftarrow(c_{A,\mathrm{light}},B-x_{A,\mathrm{light}})\)

この操作自体は高々 \(60(=\log \max(X_i))\) 回しか行われず、操作は \(O(\log Q)\) で行うことができるため、各クエリについて値の格納に \(O(\log Q)\), 答えを求めるのに \(O(\log \max(X_i)\log Q)\) であるため、問題全体で \(O(Q\log Q\log \max(X_i))\) で答えを求めることができ、問題の制約下で十分高速です。

c++ による実装例:

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

#define rep(i, n) for(long long i = 0; i < n; ++i)
#define ll long long
#define Q 500010
#define K 20
#define LMAX (ll)1e+18

struct seg{
	long long idx;
	long long ofs;
};

ll len[Q];
seg lgt[Q];
seg hev[Q][K];

void init(void){
	rep(i,Q){
		len[i]=-1;
		lgt[i]={-1,-1};
		rep(j,K)hev[i][j]={-1,-1};
	}
	len[0]=1,len[1]=1;
	return;
}

void concat_seg(long long nidx, long long le,long long ri){
	ll nlen=len[le]+len[ri];
	if(nlen>LMAX)nlen=LMAX;
	len[nidx]=nlen;
	ll llen=len[le];
	ll rlen=nlen-llen;
	if(llen<rlen){
		lgt[nidx]={le,0};
		hev[nidx][0]={ri,llen};
		long long cur=ri;
		ll curofs=llen;
		for(long long i=1;i<K;i++){
			curofs+=hev[cur][i-1].ofs;
			cur=hev[cur][i-1].idx;
			if(cur==-1)break;
			if(curofs>LMAX)break;
			hev[nidx][i]={cur,curofs};
		}
	}
	else{
		lgt[nidx]={ri,llen};
		hev[nidx][0]={le,0};
		long long cur=le;
		ll curofs=0;
		for(long long i=1;i<K;i++){
			curofs+=hev[cur][i-1].ofs;
			cur=hev[cur][i-1].idx;
			if(cur==-1)break;
			if(curofs>LMAX)break;
			hev[nidx][i]={cur,curofs};
		}
	}
	return;
}

long long search(long long k,long long x){
	if(k<=1)return k;
	long long curk=k, curx=x;
	for(long long i=19;i>=0;i--){
		if(hev[curk][i].idx==-1)continue;
		if((hev[curk][i].ofs<=curx)&&(curx<(hev[curk][i].ofs+len[hev[curk][i].idx]))){
			curx-=hev[curk][i].ofs;
			curk=hev[curk][i].idx;
		}
	}
	while(lgt[curk].idx!=-1){
		if((lgt[curk].ofs<=curx)&&(curx<(lgt[curk].ofs+len[lgt[curk].idx]))){
			curx-=lgt[curk].ofs;
			curk=lgt[curk].idx;
		}
		else break;
	}
	return search(curk,curx);
}



int main() {
	long long q,le,ri,x;
	init();
	cin>>q;
	rep(qq,q){
		cin>>le>>ri>>x;
		concat_seg(qq+2,le,ri);
		cout<<search(qq+2,x-1)<<endl;
	}

	return 0;
}