← 返回题目列表

AtCoder · code_festival_2018_final_j

J. 操作复杂

中文机器翻译题面 查看原题

配点 : 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_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 请输出