問題文

長さ N の数列 S_{0} と T が与えられます。 ここで、N はある自然数 r に対して 2^{r} と表せることが保証されます。

あなたは 0 回以上 500 回以内、操作を行うことができます。あなたの目的は操作回数を k として S_{k} と T を一致させることです。

i 回目の操作は以下のようにして行われます。

• 0 \leq x < i, 0\leq y < i を満たす整数 x,y、-(N-1) \leq f \leq N-1 を満たす整数 f を指定する
• その後、x,y のみからなる長さ N の文字列 s を指定する
• x,y,f,s を用いて長さ N の数列 S_{i} を作る
  • S_{i,j} は s_{j} が x ならば、S_{x,j} となる
  • S_{i,j} は s_j が y ならば、S_{y,j-f} となる。ただし、1 \leq j-f \leq N を満たさなくてはならない

目的が達成可能かどうか判定し、可能ならば、操作の一例を出力してください。不可能ならば代わりに -1 を出力してください。

操作についてはサンプル 1 も参照してください。

制約

• 2 \leq N \leq 8192
• 1 \leq S_{0,j},T_{j} \leq N
• N はある自然数 r に対して 2^{r} と表せる
• 与えられる入力は全て整数

入力例 1

4
1 2 3 4
2 4 3 4

出力例 1

2
0 0 1 xxyx
0 1 -2 yyxx

• 1 回目の操作では x=0,y=0,f=1,s=xxyx を指定して操作を行います
• S_{1,1},S_{1,2},S_{1,4} はそれぞれ S_{0,1},S_{0,2},S_{0,4} に、S_{1,3} は S_{0,2} となります。よって S_{1}=(1,2,2,4) となります
• 2 回目の操作では x=0,y=1,f=-2,s=yyxx を指定して操作を行います
• S_{2,3},S_{2,4} はそれぞれ S_{0,3},S_{0,4} となり、S_{2,1},S_{2,2} はそれぞれ S_{1,3},S_{1,4} となります。よって S_{2}=(2,4,3,4) となります
• S_{2} と T が一致したため正解です

入力例 2

4
3 1 2 3
1 2 3 4

出力例 2

-1

• 目的が達成不可能な場合は -1 を出力してください