First, we modify the problem statement as follows: instead of letting “\(S_{i+1}\) be the concatenation of \(S_{L_i}\) and \(S_{R_i}\),” let \(S_{i+1}\) be the first \(\min(\lvert S_{L_i}\rvert+\lvert S_{R_i}\rvert,10^{18})\) characters of the concatenation of \(S_{L_i}\) and \(S_{R_i}\). This modification does not change the answer, because the \((10^{18}+1)\)-th and further characters are never referred to, since \(X_i\leq 10^{18}\), and the first \(10^{18}\) characters of a string obtained by a concatenation performed later are not affected by the \((10^{18}+1)\)-th and further characters before the concatenation.
From now on, we consider this modified problem.

First, we describe an \(O(Q^2)\) solution. For each string \(S_i\) \((2\leq i\leq Q+1)\), instead of maintaining the string itself, let us record the length \(\lvert S_i\rvert\) of the string, the indices \(c_{i,\mathrm{left}}=L_{i-1}\) and \(c_{i,\mathrm{right}}=R_{i-1}\) of the strings being concatenated, and their respective positions \(x_{i,\mathrm{left}}=0\) and \(x_{i,\mathrm{right}}=\lvert S_{L_{i-1}} \rvert\) in \(S_i\). The \(X_{i-1}\)-th character of \(S_i\) can be found by traversing the strings being concatenated, while maintaining the relative position within them, until reaching \(S_0\) or \(S_1\).
Specifically, starting from \((A,B)=(i,X_{i-1})\), repeat the following step.

• If \(A=0\), print \(0\) and terminate the procedure.
• If \(A=1\), print \(1\) and terminate the procedure.
• If \(x_{A,\mathrm{left}}+1\leq B\leq x_{A,\mathrm{left}}+\lvert S_{c_{A,\mathrm{left}}}\rvert\), let \((A,B)\leftarrow(c_{A,\mathrm{left}},B-x_{A,\mathrm{left}})\).
• Otherwise, let \((A,B)\leftarrow(c_{A,\mathrm{right}},B-x_{A,\mathrm{right}})\).

Here, \((A,B)\leftarrow(C,D)\) means assigning \((C,D)\) to \((A,B)\), or letting \((C,D)\) be new \((A,B)\).

Through the repetition, \(A\) decreases strictly monotonically, so the operation is repeated at most \(i\) times, and the problem can be solved in \(O(Q^2)\) time.

Next, we describe an \(O(Q\log Q\log \max (X_i))\).
Roughly speaking, we adopt the same idea as Heavy-Light Decomposition of a rooted tree.

Compare the lengths of \(S_{c_{i,\mathrm{left}}}\) and \(S_{c_{i,\mathrm{right}}}\). Let \(c_{i,\mathrm{heavy}}\) be the index of the longer, and \(c_{i,\mathrm{light}}\) be of the shorter. If they have the same length, choose any one and let it be \(c_{i,\mathrm{heavy}}\). Define \(x_{i,\mathrm{heavy}}\) and \(x_{i,\mathrm{light}}\) in the same way. Specifically, we have:

• \(c_{i,\mathrm{heavy}}=c_{i,\mathrm{left}}\) and \(c_{i,\mathrm{light}}=c_{i,\mathrm{right}}\) if \(x_{i,\mathrm{right}}>\lvert S_i\rvert-x_{i,\mathrm{right}}\).
• \(c_{i,\mathrm{heavy}}=c_{i,\mathrm{right}}\) and \(c_{i,\mathrm{light}}=c_{i,\mathrm{left}}\) otherwise.

Recall the \(O(Q^2)\) solution above. When traversing the original string and position before the concatenation, we either assign \(c_{A,\mathrm{heavy}}\) or \(c_{A,\mathrm{light}}\) to \(A\). If we assign the former, let us call it “traversing a heavy edge,” and for the latter, “traversing a light edge.”

Then, the following holds:

If we repeatedly perform the operation from \((A,B)\) until \(A\leq 1\), we traver light edges at most \(\lfloor \log_2 10^{18}\rfloor +1=60\) times.

This is because, whenever we traverse a heavy or light edge, \(A\) and \(B\) weakly monotonically decreases, and whenever we traverse a light edge to set \((A,B)\leftarrow (A',B')\), the following holds:

• If \(\lvert S_A\rvert=10^{18}\) and \(\lvert S_{A'}\rvert=10^{18}\), then \(B'\leq 5\times 10^{17}\).
• If \(\lvert S_A\rvert=10^{18}\) and \(B\leq 5\times 10^{17}\), then \(\lvert S_{A'}\rvert \leq 5\times 10^{17}\).
• If \(\lvert S_A\rvert<10^{18}\), then \(\lvert S_{A'}\rvert\leq \frac{1}{2}\lvert S_A\rvert\).

Here, note that \(10^{18}\) originates from the modification we initially applied, which in turn originates from the maximum possible \(X_i\).

On the other hand, a heavy edge may be traversed at most \(i\) times. To handle this, define \(c'_{i,\mathrm{heavy},k}\) as the index of the string you arrive after traversing a heavy edge \(2^k\) times \((0\leq k\leq \lfloor \log_2 Q\rfloor)\) from \(S_i\), and \(x'_{i,\mathrm{heavy},k}\) as the position of the string in \(S_i\). In particular,\(c'_{i,\mathrm{heavy},0}=c_{i,\mathrm{heavy}}\) and \(x'_{i,\mathrm{heavy},0}=x_{i,\mathrm{heavy}}\); furthermore,

• \(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}\).

With these relations, these values can be found in \(O(\log Q)\) time for each query. Finally, when we traverse until reaching \(S_0\) or \(S_1\), we check if we can traverse a heavy edge \(2^k\) times at once, for each \(k=\lfloor \log_2 Q\rfloor, \lfloor \log_2 Q\rfloor-1,\ldots,0 \) in order.
Specifically, starting form \((A,B)=(i,X_{i-1})\), we repeat the following.

• If \(A=0\), print \(B\) and terminate the procedure; if \(A=1\), print \(1\) and stop. In the course of the following procedure also, once you reach \(A=0\) or \(1\), perform the same termination.
• For \(k=\lfloor \log_2 Q\rfloor, \lfloor \log_2 Q\rfloor-1,\ldots,0 \) in order, do the following.
  • If \(x'_{A,\mathrm{heavy},k}+1\leq B\leq x'_{A,\mathrm{heavy},k}+\lvert S_{c'_{A,\mathrm{heavy},k}}\rvert\), let \((A,B)\leftarrow(c'_{A,\mathrm{heavy},k},B-x'_{A,\mathrm{heavy},k})\).
  • Otherwise, do nothing.
• \((A,B)\leftarrow(c_{A,\mathrm{light}},B-x_{A,\mathrm{light}})\)

This procedure itself has at most \(60(=\log \max(X_i))\) steps, and the operation can be performed in \(O(\log Q)\) time, so for each query, storing values costs \(O(\log Q)\) and finding the answer costs \(O(\log \max(X_i)\log Q)\) time. In total, the problem can be solved in \(O(Q\log Q\log \max(X_i))\) time, which is fast enough under the constraints of the problem.

Sample code in 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;
}