#P18679. Balancing Sequences

    ID: 18015 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-矩阵构造不变量分析奇偶性分析一维前缀和排序贪心逆向还原操作

Balancing Sequences

Balancing Sequences

题目描述

穿越到幻想乡后,小青鱼得到了两个序列 a1a_1 和 a2a_2。每个序列包含 nn 个取值为 11 到 2n2n 的整数,两个序列中的这 2n2n 个整数两两不同。

他想把 a1,a2a_1,a_2 变成 b1,b2b_1,b_2。不幸的是,这些序列有一个自平衡系统,因此他唯一能做的操作是:选取四个整数 (x1,x2,y1,y2)(x_1,x_2,y_1,y_2),交换 ax1,x2a_{x_1,x_2} 与 ay1,y2a_{y_1,y_2}。为了保护自平衡系统,所选整数必须满足:

  • x1,y1∈[1,2]x_1,y_1\in[1,2],x2,y2∈[1,n]x_2,y_2\in[1,n];
  • x2≠y2x_2\ne y_2;
  • ax1,x2>a3−x1,x2a_{x_1,x_2}>a_{3-x_1,x_2};
  • ay1,y2>a3−y1,y2a_{y_1,y_2}>a_{3-y_1,y_2}。

这些不等式使用执行本次操作时的数组值。也就是说,每次只能交换两个不同列中各自较大的那个数;两者可以位于相同或不同的行。

小青鱼想知道能否把 a1,a2a_1,a_2 变成 b1,b2b_1,b_2,因此向你求助。如果可以,还需要给出一份操作方案指导他。

输入格式

输入包含多组测试数据。第一行包含一个整数 TT(1≤T≤1051\le T\le10^5),表示测试数据组数。

对于每组测试数据:

第一行包含一个整数 nn(2≤n≤2×1032\le n\le2\times10^3),表示 a1,a2,b1,b2a_1,a_2,b_1,b_2 的长度。

接下来一行包含 nn 个整数,描述 a1a_1(1≤a1,i≤2n1\le a_{1,i}\le2n)。

接下来一行包含 nn 个整数,描述 a2a_2(1≤a2,i≤2n1\le a_{2,i}\le2n)。保证 a1,a2a_1,a_2 中的这 2n2n 个整数两两不同。

接下来一行包含 nn 个整数,描述 b1b_1(1≤b1,i≤2n1\le b_{1,i}\le2n)。

接下来一行包含 nn 个整数,描述 b2b_2(1≤b2,i≤2n1\le b_{2,i}\le2n)。保证 b1,b2b_1,b_2 中的这 2n2n 个整数两两不同。

保证所有测试数据的 n2n^2 之和不超过 4×1064\times10^6。

输出格式

对于每组测试数据:

如果无法把初始数组 a1,a2a_1,a_2 变成目标 b1,b2b_1,b_2,输出一行一个整数 −1-1。

否则,先输出一个整数 ss(0≤s≤5n0\le s\le5n),表示操作次数。

随后输出 ss 行,每行四个整数 x1,x2,y1,y2x_1,x_2,y_1,y_2(1≤x1,y1≤21\le x_1,y_1\le2,1≤x2,y2≤n1\le x_2,y_2\le n),表示这一步交换 ax1,x2a_{x_1,x_2} 与 ay1,y2a_{y_1,y_2}。每次交换必须满足题目给定的全部限制。

可以证明,只要转换可行,就一定能在不超过 5n5n 次操作内完成。你可以输出任意合法方案。

样例输入

2
2
1 2
3 4
4 3
2 1
3
1 2 4
3 5 6
1 2 4
5 3 6

样例输出

-1
1
2 2 2 1