\(N^2\) 個の順列を先頭の要素で分類すると，\(0,1,\cdots,N-1\) が \(N\) 個ずつになっています． よって，\(K\) の値から答えの順列の先頭の値がわかります． この値を \(v\) とおきます．

先頭の値が \(v\) になる順列をソートできればよいです． そのためには，\(i,j\) (\(0 \leq i,j \leq N-1\)) が与えられたときに，次の比較関数が高速に計算できればよいです． なお，以下の解説では数列の要素は全て \(\bmod N\) で計算しているものとします．

• \(a=v-P_i\) として，\(x=(P_i+a,P_{i+1}+a,\cdots,P_{i-1} + a)\) とおく．
• \(b=v-P_j\) として，\(y=(P_j+b,P_{j+1}+b,\cdots,P_{j-1} + b)\) とおく．
• \(x,y\) を辞書順比較した結果を返す．

この計算のためには，\(x,y\) のLCP（最長共通接頭辞）の長さがわかればよいです． \(x,y\) の先頭の要素は同じなので，\(x,y\) の要素の階差を取って，このLCPの長さを求めてもよいです．

つまり，\(x'=(P_{i+1} - P_i,P_{i+2}-P_{i+1},\cdots,P_{i-1}-P_{i-2})\), \(y'=(P_{j+1} - P_j,P_{j+2}-P_{j+1},\cdots,P_{j-1}-P_{j-2})\) とおいて，\(x',y'\) のLCPの長さがわかればよいです．

\(S=(P_1-P_0,P_2-P_1,\cdots,P_0-P_{N-1},P_1-P_0,\dots,P_{N-1}-P_{N-2})\) という数列 \(S\) を考えると，\(x',y'\) は \(S\) の連続部分列になります． よって，\(x',y'\) のLCPの長さは，\(S\) の suffix array があれば高速に求められることになります．

suffix array の構築は \(O(N)\) で行えます． LCP を取得するためのデータ構造として Sparse Table を用いれば，初期化 \(O(N\log N)\) クエリ \(O(1)\) で LCP が計算できます． ソートで \(O(N \log N)\) クエリ使うことを考えると，計算量は全体で \(O(N \log N)\) になります．

なお，頑張れば全体 \(O(N)\) にもなりますが，ここまでの高速化は必要ありません．

解答例(C++)