J - Complicated Operations

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1200

問題文

長さ 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_jy ならば、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} と表せる
  • 与えられる入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
S_{0,1} S_{0,2} ... S_{0,N}
T_{1} T_{2} ... T_{N}

出力

目的が達成不可能な場合は -1 を出力せよ。

目的が達成可能な場合は以下の形式で操作を出力せよ。操作が問題文中の制約を満たし、S_{K}T と一致したならば正解となる。

K
x_1 y_1 f_1 s_1
:
x_K y_K f_K s_K

入力例 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 を出力してください