便宜上、\(S\) を 0-indexed として扱います。

「\(S\) の末尾の文字を削除し、先頭に挿入する」という操作を x 回連続で行うことを愚直にやっていては計算量が \(\mathrm{O}(NQ)\) となってしまい今回の制約の場合、実行制限時間に間に合いません。

ここで、今まで「\(S\) の末尾の文字を削除し、先頭に挿入する」という操作を何回行ったかとして整数 \(P\) を持ちます。はじめは \(P=0\) です。

1 x のクエリが来た場合、\(P\) を \(x\) 増やせばよいです。

2 x のクエリが来た場合を考えます。

「\(S\) の末尾の文字を削除し、先頭に挿入する」という操作を \(x\) 回する前の \(S\) を \(X\)、した後の \(S\) を \(Y\) と置きます。すると、ここで \(X_{i-x \bmod N}=Y_i\) が成り立ちます。

なので、\(S_{x-P \bmod N}\) を出力すればよいです。

よりこの問題を計算量 \(\mathrm{O}(N+Q)\) で解くことができました。これは十分高速です。