便宜上、数列 \(A\) の要素を \(A = (A_0, A_1, \ldots, A_{N-1})\) と \(0\) -indexed にします。

タイプ \(1\) のクエリについては、初めに変数 \(X = 0\) を準備しておき、 \(A\) を実際に \(x\) 回だけ巡回シフトする代わりに、\(X\) に \(x\) を加算します。 そして、タイプ \(2, 3\) のクエリで与えられる \(l, r\) をそれぞれ \(L \coloneqq (l+X) \bmod N, R \coloneqq(r+X) \bmod N\) に置き換える（ \(L > R\) のときはさらに区間 \([0, R]\) と区間 \([L, N-1]\) の \(2\) つの区間に対するクエリに置き換える）ことで、タイプ \(1\) のクエリの処理を \(O(1)\) 時間で仮想的に処理できます。

タイプ \(2, 3\) のクエリは遅延伝搬セグメント木を用いて、各クエリ \(O(D\log N)\) 時間で実現できます。 具体的には、数列 \(A\) の区間 \([p, q]\) に対応するノードには 「 \(A\) の区間 \([p, q]\) の要素それぞれを \(i\) 桁シフトしたものの排他的論理和 \(v_i\) 」のすべての \(i = 0, 1, \ldots, D-1\) にわたる組 \((v_0, v_1, \ldots, v_{D-1})\) を持たせます。 区間 \([p, q]\) に対する \(y\) 桁のシフトは、\((v_0, v_1, \ldots, v_{D-1})\) を \((v_y, v_{y+1}, \ldots, v_{D-1}, v_0, \ldots, v_{y-1})\) に置き換えることで実現できます。 また、\(2\) つのノードの情報 \((v_0, v_1, \ldots, v_{D-1})\) と \((v'_0, v'_1, \ldots, v'_{D-1})\) は \((v_0 \oplus v'_0, v_1 \oplus v'_1, \ldots, v_{D-1} \oplus v'_{D-1})\) とマージされます。