問題文

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

入力

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

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