Disjoint Sparse Table の区間分割 Bash(Beta)編（paizaランク S 相当）

はじめに

この章では Disjoint Sparse Table というデータ構造を学習します。
Disjoint Sparse Table は、Sparse Table を冪等性を満たさない演算にも対応させたものです。

説明

冪等性を満たさない演算を扱うために、任意の区間 [l,r) の答えをあらかじめ前計算した 重複しない 2 つの区間 の答えから高速に求めたいです。
つまり、区間 [l,r) の答えを l < m < r を満たす区間 [l,m), [m,r) から求めたいです。
ただし、前計算する区間が多くなると計算時間・メモリ使用量の両方が大きくなってしまうので、前計算する区間の数がある程度少なくなるようにいくつか m の値を決めたいです。
また、どんな区間 [l,r) に対しても区間 [l,m), [m,r) に分割できなければなりません。

長さ N の数列が与えられ、任意の区間に対して（結合則を満たす）何らかの演算結果を求めるクエリが与えられるとします。
簡単のため、以下では N が 2 べきであるときを考えます。
N/2 を境界として数列を左右半分に分割することにします。
さらに、分割した左半分と右半分の区間に対しても同様に左右半分に分割します。
これを区間の長さが 1 になるまで再帰的に繰り返します。
ここで、再帰的な分割の深さを「レベル」と呼ぶこととします（最も深い層をレベル 0 とします）。
以下の画像は N = 8 の場合の例です。


この区間の分割を用いて、任意の区間の演算結果を重複しない 2 つの区間の演算結果から求める方法を考えます。
まず、レベル 2 の区間では、すべての l,r に対して区間 [l,N/2)、[N/2,r) の演算結果が求められているとします。
このとき、l ≦ N/2 < r を満たすすべての区間 [l,r) の演算結果は、区間 [l,N/2)、[N/2,r) の演算結果から求めることができます。
しかし、l < r < N/2 または N/2 < l < r を満たす区間は、区間を分割することができず演算結果を求められません。
そこで、すべてのレベルのすべての分割境界 m に対して、すべての l,r に対して区間 [l,m)、[m,r) の演算結果を求めておきます。
以下の画像の直線は、演算結果を求めておく区間を表しています。


このように分割された区間に対して演算結果を求めておくと、任意の区間 [l,r) に対して、あるレベルにおいて l < m < r を満たす m が存在するため、区間 [l,m)、[m,r) の演算結果から区間 [l,r) の演算結果を求めることができます（m は各レベルの分割境界のいずれかとします）。
区間 [l,r) を分割するレベルや分割境界 m を求める方法は本問題の課題とし、本問題の解説で説明します。
また、区間の長さが 1 のときは l < m < r を満たす m が存在しないため区間を分割できず、特別な処理が必要となります（これについては後の問題で補足します）。

N が 2 べきでないときは、N' = (N 以上の最小の 2 べき) を考え同様に分割を行えばよいです。
以下の画像は N = 6 の場合の例です。

問題

数列の長さ N が与えられます。
Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・l r：上の説明にしたがったとき、区間 [l,r) を分割する 2 つの区間 [l,m), [m,r) の l,m,r を空白区切りで出力する。ただし、区間の長さが 2 以上 (r - l ≧ 2) であることが保証されます。