#P17964. Cyclic Shift II
Cyclic Shift II
Cyclic Shift II
给定两个由非零整数组成的序列 和 。
对于每个 ,序列 中绝对值为 的元素恰好出现两次,且没有其他绝对值。同理, 中每个 的绝对值恰好出现两次。两次出现的符号可以相同,也可以不同。
可以对当前序列 按任意顺序执行以下操作任意多次。下面用 表示允许为空的子序列,用括号内逗号表示拼接。
- 循环移位。 若当前长度为 ,选择 ,将序列变为
- 删除开头的一对相反数。 若 且 ,可以将其变为 。
- 在开头插入一对新的相反数。 若 (允许为空),选择一个非零整数 ,且 与 均未出现在 中,将其变为 。
- 反转并取反。 定义$$\operatorname{nRev}(A)=(-a_{2k},-a_{2k-1},\ldots,-a_1),$$可以将 替换为 。
- 跨切口重排。 选择一个切口,将序列分为前缀和后缀。若
其中 ,,且切口位于 与 之间,则可以进行相应变换:
- 若 ,替换为$$(S_1,\operatorname{nRev}(S_3),x,\operatorname{nRev}(S_4),S_2,y).$$
- 若 ,替换为
判断能否通过有限次操作,将 变为与 等价的序列。
对于两个长度相同的序列 和 ,若存在映射 ,满足:
- 对所有整数 ,;
- 当 时, 与 同号;
- 对所有 ,有 ;
则称 等价。未出现在序列中的整数所对应的映射值可以任意选择。
输入格式
第一行一个整数 ()。
每个测试用例包含四行:
- 第一行一个整数 ()。
- 第二行 个整数,表示 。
- 第三行一个整数 ()。
- 第四行 个整数,表示 。
两个序列均满足题面给出的绝对值出现次数限制。一个输入文件中 。
输出格式
每个测试用例输出一行。若可以使 与 等价,输出 YES,否则输出 NO。
样例 1
输入
4
1
1 -1
2
-1 -2 2 1
1
1 1
1
-1 1
4
1 2 -1 3 -4 2 3 -4
4
1 2 -1 -2 4 3 4 3
4
4 3 -1 -2 -3 2 1 -4
3
-1 1 3 -3 2 2
输出
YES
NO
YES
NO
样例 2
输入
5
4
1 2 -3 -2 4 -1 3 -4
6
-3 5 2 3 -2 -5 1 -6 -4 -1 4 6
5
-2 4 -4 3 2 -1 -5 1 -3 5
5
3 -4 1 -5 4 -1 2 -2 -3 5
4
-2 1 4 2 -4 3 -1 -3
5
-1 -5 -2 2 1 -4 -3 3 4 5
3
2 -1 -1 -3 -2 3
4
-4 -2 -1 4 1 -2 3 -3
5
3 5 -5 -2 2 -1 -3 -4 1 4
5
3 5 -2 -5 -1 2 -4 1 4 -3
输出
YES
YES
NO
YES
NO