Balancing Sequences
题目描述
穿越到幻想乡后,小青鱼得到了两个序列 a1 和 a2。每个序列包含 n 个取值为 1 到 2n 的整数,两个序列中的这 2n 个整数两两不同。
他想把 a1,a2 变成 b1,b2。不幸的是,这些序列有一个自平衡系统,因此他唯一能做的操作是:选取四个整数 (x1,x2,y1,y2),交换 ax1,x2 与 ay1,y2。为了保护自平衡系统,所选整数必须满足:
- x1,y1∈[1,2],x2,y2∈[1,n];
- x2=y2;
- ax1,x2>a3−x1,x2;
- ay1,y2>a3−y1,y2。
这些不等式使用执行本次操作时的数组值。也就是说,每次只能交换两个不同列中各自较大的那个数;两者可以位于相同或不同的行。
小青鱼想知道能否把 a1,a2 变成 b1,b2,因此向你求助。如果可以,还需要给出一份操作方案指导他。
输入格式
输入包含多组测试数据。第一行包含一个整数 T(1≤T≤105),表示测试数据组数。
对于每组测试数据:
第一行包含一个整数 n(2≤n≤2×103),表示 a1,a2,b1,b2 的长度。
接下来一行包含 n 个整数,描述 a1(1≤a1,i≤2n)。
接下来一行包含 n 个整数,描述 a2(1≤a2,i≤2n)。保证 a1,a2 中的这 2n 个整数两两不同。
接下来一行包含 n 个整数,描述 b1(1≤b1,i≤2n)。
接下来一行包含 n 个整数,描述 b2(1≤b2,i≤2n)。保证 b1,b2 中的这 2n 个整数两两不同。
保证所有测试数据的 n2 之和不超过 4×106。
输出格式
对于每组测试数据:
如果无法把初始数组 a1,a2 变成目标 b1,b2,输出一行一个整数 −1。
否则,先输出一个整数 s(0≤s≤5n),表示操作次数。
随后输出 s 行,每行四个整数 x1,x2,y1,y2(1≤x1,y1≤2,1≤x2,y2≤n),表示这一步交换 ax1,x2 与 ay1,y2。每次交换必须满足题目给定的全部限制。
可以证明,只要转换可行,就一定能在不超过 5n 次操作内完成。你可以输出任意合法方案。
样例输入
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