Problem Description

You are given sequences $ S_{0} $ and $ T $ of length $ N $. Here, $ N $ is guaranteed to be expressible as $ 2^{r} $ for some natural number $ r $.

You can perform operations between $ 0 $ and $ 500 $ times. Your goal is to make $ S_{k} $ match $ T $ with the number of operations being $ k $.

The $ i $-th operation is performed as follows:

• Specify integers $ x, y $ satisfying $0 \leq x < i, 0 \leq y < i$, and an integer $ f $ satisfying $-(N-1) \leq f \leq N-1$.
• Then, specify a string $ s $ of length $ N $ consisting only of x and y.
• Using $ x, y, f, s $, create a sequence $ S_{i} $ of length $ N $.
• $ S_{i,j} $ is $ S_{x,j} $ if $ s_{j} $ is x.
• $ S_{i,j} $ is $ S_{y,j-f} $ if $ s_{j} $ is y, provided that $1 \leq j-f \leq N$.

Determine if the goal is achievable and, if possible, output an example of the operations. If not possible, output -1 instead.

Refer to Sample $ 1 $ for an explanation of the operations.

Input Format

Input is given from standard input in the following format:

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

Output Format

If the goal is not achievable, output $ -1 $.

If the goal is achievable, output the operations in the following format. The operations will be considered correct if they satisfy the constraints in the problem statement and $ S_{K} $ matches $ T $.

$ K $ $ x_1 $ $ y_1 $ $ f_1 $ $ s_1 $ $ : $ $ x_K $ $ y_K $ $ f_K $ $ s_K $

Sample Input and Output

Sample Input #1

4
1 2 3 4
2 4 3 4

Sample Output #1

2
0 0 1 xxyx
0 1 -2 yyxx

Sample Input #2

4
3 1 2 3
1 2 3 4

Sample Output #2

-1

Notes/Hints

Constraints

• $2 \leq N \leq 8192$
• $1 \leq S_{0,j}, T_{j} \leq N$
• $ N $ is expressible as $ 2^{r} $ for some natural number $ r $.
• All given inputs are integers.

Sample Explanation 1

• In the first operation, specify $ x=0, y=0, f=1, s=$xxyx.
• $ S_{1,1}, S_{1,2}, S_{1,4} $ become $ S_{0,1}, S_{0,2}, S_{0,4} $ respectively, and $ S_{1,3} $ becomes $ S_{0,2} $. Thus, $ S_{1} = (1, 2, 2, 4) $.
• In the second operation, specify $ x=0, y=1, f=-2, s=$yyxx.
• $ S_{2,3}, S_{2,4} $ become $ S_{0,3}, S_{0,4} $ respectively, and $ S_{2,1}, S_{2,2} $ become $ S_{1,3}, S_{1,4} $ respectively. Thus, $ S_{2} = (2, 4, 3, 4) $.
• Since $ S_{2} $ matches $ T $, the output is correct.

Sample Explanation 2

• Output -1 if the goal is not achievable.

见题面 Input 部分

见题面 Output 部分