#P17964. Cyclic Shift II

Cyclic Shift II

Cyclic Shift II

给定两个由非零整数组成的序列 A=(a1,…,a2n)A=(a_1,\ldots,a_{2n}) 和 B=(b1,…,b2m)B=(b_1,\ldots,b_{2m})。

对于每个 1≤i≤n1\le i\le n,序列 AA 中绝对值为 ii 的元素恰好出现两次,且没有其他绝对值。同理,BB 中每个 1≤i≤m1\le i\le m 的绝对值恰好出现两次。两次出现的符号可以相同,也可以不同。

可以对当前序列 AA 按任意顺序执行以下操作任意多次。下面用 S1,S2,S3,S4S_1,S_2,S_3,S_4 表示允许为空的子序列,用括号内逗号表示拼接。

  1. 循环移位。 若当前长度为 2k2k,选择 0≤r<2k0\le r<2k,将序列变为(ar+1,…,a2k,a1,…,ar).(a_{r+1},\ldots,a_{2k},a_1,\ldots,a_r).
  2. 删除开头的一对相反数。 若 A=(x,−x,S1)A=(x,-x,S_1) 且 x≠0x\ne0,可以将其变为 S1S_1。
  3. 在开头插入一对新的相反数。 若 A=S1A=S_1(允许为空),选择一个非零整数 xx,且 xx 与 −x-x 均未出现在 S1S_1 中,将其变为 (x,−x,S1)(x,-x,S_1)。
  4. 反转并取反。 定义$$\operatorname{nRev}(A)=(-a_{2k},-a_{2k-1},\ldots,-a_1),$$可以将 AA 替换为 nRev⁡(A)\operatorname{nRev}(A)。
  5. 跨切口重排。 选择一个切口,将序列分为前缀和后缀。若A=(S1,x,S2,S3,y,S4),A=(S_1,x,S_2,S_3,y,S_4), 其中 x>0x>0,y∈{x,−x}y\in\{x,-x\},且切口位于 S2S_2 与 S3S_3 之间,则可以进行相应变换:
    • 若 y=xy=x,替换为$$(S_1,\operatorname{nRev}(S_3),x,\operatorname{nRev}(S_4),S_2,y).$$
    • 若 y=−xy=-x,替换为(S1,S4,x,S3,S2,y).(S_1,S_4,x,S_3,S_2,y).

判断能否通过有限次操作,将 AA 变为与 BB 等价的序列。

对于两个长度相同的序列 C=(c1,…,c2k)C=(c_1,\ldots,c_{2k}) 和 D=(d1,…,d2k)D=(d_1,\ldots,d_{2k}),若存在映射 f:Z→Zf:\mathbb Z\to\mathbb Z,满足:

  • 对所有整数 xx,f(−x)=−f(x)f(-x)=-f(x);
  • 当 f(x)≠0f(x)\ne0 时,xx 与 f(x)f(x) 同号;
  • 对所有 1≤i≤2k1\le i\le2k,有 di=f(ci)d_i=f(c_i);

则称 C,DC,D 等价。未出现在序列中的整数所对应的映射值可以任意选择。

输入格式

第一行一个整数 tt(1≤t≤1051\le t\le10^5)。

每个测试用例包含四行:

  • 第一行一个整数 nn(1≤n≤5⋅1051\le n\le5\cdot10^5)。
  • 第二行 2n2n 个整数,表示 AA。
  • 第三行一个整数 mm(1≤m≤5⋅1051\le m\le5\cdot10^5)。
  • 第四行 2m2m 个整数,表示 BB。

两个序列均满足题面给出的绝对值出现次数限制。一个输入文件中 ∑n+∑m≤106\sum n+\sum m\le10^6。

输出格式

每个测试用例输出一行。若可以使 AA 与 BB 等价,输出 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